預算約束下的二次模型

等式 $x+y=1$ 描述哪些選擇獲准採用；二次式描述怎樣比較這些選擇。這是最優化問題的兩個不同部分。只有先交代可行集與目標函數，求導所得的方程才有明確意義。

本節研究一個假設的數學模型。$x,y$ 是實數權重，目標是題目指定的二次準則。以下計算不需要替各係數賦予任何經驗性的解釋。

1. 求導前先寫清楚可行集

考慮

$$V(x,y)=4x^2+2xy+9y^2, \qquad x+y=1.$$

若只有等式約束，可行集是整條直線

$$F_{\mathbb R}=\{(x,1-x):x\in\mathbb R\}.$$

例如 $(2,-1)$ 也滿足等式。若不准出現負權重，便須另外假設 $x\ge0$、$y\ge0$。由 $y=1-x$，可行集變成閉線段

$$F_+=\{(x,1-x):0\le x\le1\}.$$

在整條直線上最小與在線段上最小，是兩個不同的結論。等式約束的候選點可能違反額外的不等式約束；必須核查，不能直接假設它可行。

2. 消去一個變量，逐步求出候選點

每個可行點都有唯一的表示 $(x,1-x)$，因此代入這個表示不會遺漏任何可行選擇：

$$\begin{aligned} g(x)=V(x,1-x) &=4x^2+2x(1-x)+9(1-x)^2\\ &=4x^2+2x-2x^2+9-18x+9x^2\\ &=11x^2-16x+9. \end{aligned}$$

此時 $g'(x)=22x-16$，唯一駐點為 $x_*=8/11$，所以 $y_*=1-8/11=3/11$。兩個權重均為正數，總和為一。

導數只找出了一個候選點。下一步要證明它為何是全局最小點，以及為何不存在另一個可行點達到相同的值。

3. 用精確的平方恆等式證明全局最優性

配方得到

$$g(x)=\frac{35}{11}+11\left(x-\frac8{11}\right)^2.$$

平方項的係數 11 為正數，因此對每個實數 $x$ 都有 $g(x)\ge35/11$，而等號恰在 $x=8/11$ 時成立。所以 $(8/11,3/11)$ 是 $F_{\mathbb R}$ 上唯一的全局最小點，最小值為 $35/11$。

由於此點亦屬於 $F_+$，它同時解決了非負權重問題。兩個端點提供一項獨立核查：

$$V(0,1)=9,\qquad V(1,0)=4,$$

兩者都大於 $35/11$。平方恆等式比只檢查端點更強：它已將候選點與整條可行直線上的每一點作比較。

若再限制 $a\le x\le b$，同一恆等式告訴我們，應選取區間 $[a,b]$ 中最接近 $8/11$ 的點，然後令 $y=1-x$。當區間不包含 $8/11$ 時，最小點便移到邊界。這個結論來自平方項，並不需要把邊界點誤當作駐點。

4. 核對乘數法與矩陣表示

採用以下符號慣例：

$$L(x,y,\lambda)=V(x,y)-\lambda(x+y-1).$$

拉格朗日乘數方程為

$$8x+2y=\lambda,\qquad 2x+18y=\lambda,\qquad x+y=1.$$

前兩式相減得到 $6x-16y=0$，所以 $x=(8/3)y$。再由預算等式得到 $(11/3)y=1$，故 $y=3/11$、$x=8/11$，以及 $\lambda=70/11$。這與代入法一致，但兩種方法得出相同候選點，仍不能代替上面的全局比較。

令 $w=(x,y)^T$，則同一目標可寫成

$$V=w^T\Sigma w, \qquad \Sigma=\begin{pmatrix}4&1\\1&9\end{pmatrix}.$$

兩個非對角元素各貢獻一項，合起來是 $xy+yx=2xy$。因 $\Sigma$ 對稱，$\nabla V=2\Sigma w=(8x+2y,2x+18y)^T$，正好解釋乘數方程中的偏導數。若要把這個二次式稱為方差模型，仍須另行給出關於 $\Sigma$ 的概率假設；代數本身並不提供這種解釋。

練習

P08. 在本節模型中加上 $0\le x\le1/2$。求最小化權重與最小值，並解釋為何只有等式約束時的駐點不再可行。

P08a. 展開所示矩陣的 $w^T\Sigma w$。解釋為何把兩個非對角元素都改成 2，便會得到不同的目標函數。

P08b. 改為要求 $3/4\le x\le1$，並保留 $y=1-x$。利用與 $8/11$ 的距離，求最小化權重與目標值。

P08c. 將目標改成 $-V$，但保留整條可行直線 $F_{\mathbb R}$。同一駐點是否使新目標最小？說明該點的性質，並判斷全局最小值是否存在。

完整解答

P08. 因為 $8/11>1/2$，只有等式約束時的候選點被排除。在 $[0,1/2]$ 上最接近 $8/11$ 的點為 $1/2$，故 $(x,y)=(1/2,1/2)$。直接代入得

$$V(1/2,1/2)=\frac44+\frac24+\frac94=\frac{15}{4}.$$

邊界最小點不必滿足 $g'(x)=0$；事實上 $g'(1/2)=-5$。

P08a. 乘開得到 $4x^2+xy+yx+9y^2=4x^2+2xy+9y^2$。若兩個非對角元素均為 2，交叉項便合成 $4xy$，目標函數也隨之改變。

P08b. 由於 $8/11<3/4$，最近的可行點是 $x=3/4$，所以 $y=1/4$，且

$$V(3/4,1/4)=\frac{36+6+9}{16}=\frac{51}{16}.$$

P08c. 沿直線有 $-V=-35/11-11(x-8/11)^2$，所以同一點變成唯一的全局最大點。當 $|x|\to\infty$ 時，目標趨向 $-\infty$，故整條直線上沒有全局最小值。單靠駐點方程，不能判斷最優點的類型。