等式預算約束下的正定二次目標

4.4 二次型與全局約束公式

若 $A=QDQ^T$ 且 $z=Q^Tx$，則 $x^TAx=z^TDz=\sum_i\lambda_iz_i^2$。因此，$A$ 正定當且僅當每個特徵值均為正。負特徵值產生負方向，零特徵值產生非零的平坦方向。這一適用於一般階數的判據推廣了第 2 章的二變量行列式檢驗。

例 2：將二次目標對角化。 對於 $\Sigma=\begin{pmatrix}5&2\\2&2\end{pmatrix}$，特徵向量 $(2,1)^T$ 和 $(1,-2)^T$ 的特徵值分別為 6 和 1。各自除以 $\sqrt5$ 得到正交矩陣 $Q$。在其坐標下，

$$w^T\Sigma w=6z_1^2+z_2^2,$$

這證明了正定性，並顯示垂直方向上的曲率不同。

對於對稱正定矩陣 $\Sigma$ 和約束 $\mathbf1^Tw=1$，由乘數方程得到

$$w_* =\frac{\Sigma^{-1}\mathbf1}{\mathbf1^T\Sigma^{-1}\mathbf1},\qquad V_* =\frac1{\mathbf1^T\Sigma^{-1}\mathbf1}.$$

分母為正，因為逆矩陣是正定的。為證明全局最優性，將另一個可行向量寫成 $w_*+h$，其中 $\mathbf1^Th=0$。由於 $\Sigma w_*$ 是 $\mathbf1$ 的倍數，交叉項為零，因此 $V(w_*+h)=V_*+h^T\Sigma h>V_*$，其中 $h\ne0$。若還要求權重非負，仍需另行檢查；只考慮等式約束的公式在其他例子中可能給出負分量。

練習

P06. 驗證例 2 中 $\Sigma$ 的特徵向量和對角化後的二次表達式。

P09. 對 $\Sigma=\operatorname{diag}(2,8)$ 使用等式約束公式，計算使目標值最小的兩個權重及其值。通過代入 $w_2=1-w_1$ 直接驗證。

完整解答

P06. $\Sigma(2,1)^T=(12,6)^T=6(2,1)^T$，且 $\Sigma(1,-2)^T=(1,-2)^T$。歸一化後的向量互相正交，因此 $Q^T\Sigma Q=\operatorname{diag}(6,1)$，二次型變為 $6z_1^2+z_2^2$。

P09. $\Sigma^{-1}\mathbf1=(1/2,1/8)^T$ 的分量之和為 $5/8$，因此權重為 $(4/5,1/5)$，目標值為 $8/5$。直接計算得 $2x^2+8(1-x)^2=10(x-4/5)^2+8/5$，證明同一個唯一全局最小值。