预算约束下的二次模型

等式 $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$，故整条直线上没有全局最小值。单靠驻点方程，不能判断最优点的类型。