第 9 周作业：KKT 与二阶条件

#作业

本周源文件是我的手写作业，题号为 2、4、5、8、9。我根据扫描中的题面与作答过程还原，并用参考解核对候选点、乘子和二阶型。统一把不等式写成 gi(x)≥0g_i(x)\ge0，并取

L(x,w,v)=f(x)−∑iwigi(x)−∑jvjhj(x),wi≥0.L(x,w,v)=f(x)-\sum_iw_ig_i(x)-\sum_jv_jh_j(x), \qquad w_i\ge0.

等式乘子的正负只取决于 Lagrange 函数的记号约定，不影响最优性结论。

题目（根据扫描还原）

完成第 2、4、5、8、9 题：对给定约束优化问题检查候选点，求 KKT 乘子，并在临界锥上用 Lagrange 函数的 Hessian 判断二阶必要或充分条件。扫描可辨认的完整模型随解答一起保留。

查看还原题面与解答

第 2 题：圆盘与直线交集上的投影

min⁡(x1−3)2+(x2−2)2s.t.−x12−x22+5≥0,x1+2x2−4=0,x1,x2≥0.\begin{aligned} \min\quad &(x_1-3)^2+(x_2-2)^2\\ \text{s.t.}\quad &-x_1^2-x_2^2+5\ge0,\\ &x_1+2x_2-4=0,\\ &x_1,x_2\ge0. \end{aligned}

第一条是圆盘约束，不是线性约束。由等式消去 x1=4−2x2x_1=4-2x_2，圆盘与非负约束给 1≤x2≤21\le x_2\le2，目标变成

ϕ(x2)=5x22−8x2+5.\phi(x_2)=5x_2^2-8x_2+5.

无约束极小点 x2=4/5x_2=4/5 不在区间内，因此

x∗=(2,1)T.\boxed{x^*=(2,1)^T}.

在该点，圆盘约束和等式都活动。梯度为

∇f=(−2,−2)T,∇g=(−4,−2)T,∇h=(1,2)T.\nabla f=(-2,-2)^T,\quad \nabla g=(-4,-2)^T,\quad \nabla h=(1,2)^T.

驻点方程

∇f−w∇g−v∇h=0\nabla f-w\nabla g-v\nabla h=0

给出

w=13,v=−23.\boxed{w=\frac13,\qquad v=-\frac23}.

w≥0w\ge0，KKT 成立。目标严格凸，可行域是圆盘、仿射直线与非负正交象限的凸交集，所以该点还是唯一全局最优解。

第 4 题：逐个检查候选点

根据作答过程还原问题：

min⁡(x1−94)2+(x2−2)2s.t.−x12+x2≥0,−x1−x2+6≥0,x1,x2≥0.\begin{aligned} \min\quad &\left(x_1-\frac94\right)^2+(x_2-2)^2\\ \text{s.t.}\quad &-x_1^2+x_2\ge0,\\ &-x_1-x_2+6\ge0,\\ &x_1,x_2\ge0. \end{aligned}

题目给出三个候选点。

候选点 x(1)=(3/2,9/4)Tx^{(1)}=(3/2,9/4)^T

它满足全部约束，且只有 g1=−x12+x2g_1=-x_1^2+x_2 活动。此时

∇f=(−32,12)T,∇g1=(−3,1)T.\nabla f=\left(-\frac32,\frac12\right)^T, \qquad \nabla g_1=(-3,1)^T.

由 ∇f−w1∇g1=0\nabla f-w_1\nabla g_1=0 得

w1=12>0.\boxed{w_1=\frac12}>0.

KKT 成立，目标值为

f(x(1))=(−34)2+(14)2=58.f(x^{(1)})= \left(-\frac34\right)^2+\left(\frac14\right)^2 =\frac58.

目标严格凸，而可行域是凸函数 x12x_1^2 的上图集与半空间的交，因此

x∗=(32,94)T,f∗=58\boxed{x^*=\left(\frac32,\frac94\right)^T,\qquad f^*=\frac58}

是唯一全局最优解。

候选点 x(2)=(9/4,2)Tx^{(2)}=(9/4,2)^T

代入第一条约束：

−(94)2+2=−4916<0,-\left(\frac94\right)^2+2=-\frac{49}{16}<0,

所以它不可行，直接排除。

候选点 x(3)=(0,−2)Tx^{(3)}=(0,-2)^T

扫描和参考解都印出了这个候选点，但它与题面中的 x2≥0x_2\ge0 直接矛盾，也不满足 −x12+x2≥0-x_1^2+x_2\ge0。因此这里存在源材料笔误，不能把它当作可行 KKT 点；手写过程中得到负乘子，也会独立排除它。

第 5 题：等式与不等式混合

根据作答过程还原问题：

min⁡x12−x2−3x3s.t.g(x)=−x1−x2−x3≥0,h(x)=x12+2x2−x3=0.\begin{aligned} \min\quad &x_1^2-x_2-3x_3\\ \text{s.t.}\quad &g(x)=-x_1-x_2-x_3\ge0,\\ &h(x)=x_1^2+2x_2-x_3=0. \end{aligned}

解 KKT 方程得到

x∗=(−72,−3512,7712)T,w∗=73,v∗=23.\boxed{ x^*=\left(-\frac72,-\frac{35}{12},\frac{77}{12}\right)^T, \quad w^*=\frac73,\quad v^*=\frac23 }.

两个约束在 x∗x^* 处都活动。按本页的记号

L=f−wg−vh,L=f-wg-vh,

其 Hessian 为

∇xx2L=[2/300000000].\nabla_{xx}^2L = \begin{bmatrix} 2/3&0&0\\ 0&0&0\\ 0&0&0 \end{bmatrix}.

正乘子活动约束与等式约束给临界方向条件

−d1−d2−d3=0,−7d1+2d2−d3=0.-d_1-d_2-d_3=0, \qquad -7d_1+2d_2-d_3=0.

解得

d=(d1,2d1,−3d1)T.d=(d_1,2d_1,-3d_1)^T.

因此对任意非零临界方向，

dT∇xx2L d=23d12>0.d^T\nabla_{xx}^2L\,d =\frac23d_1^2>0.

故 x∗x^* 是严格局部极小点，目标值为

f(x∗)=−4912.\boxed{f(x^*)=-\frac{49}{12}}.

第 8 题：两圆约束的三个候选点

根据作答过程还原问题：

min⁡x2s.t.g(x)=−x12−(x2−4)2+16≥0,h(x)=(x1−2)2+(x2−3)2−13=0.\begin{aligned} \min\quad &x_2\\ \text{s.t.}\quad &g(x)=-x_1^2-(x_2-4)^2+16\ge0,\\ &h(x)=(x_1-2)^2+(x_2-3)^2-13=0. \end{aligned}

题目给出

x(1)=(0,0)T,x(2)=(165,325)T,x(3)=(2,3+13)T.x^{(1)}=(0,0)^T,\qquad x^{(2)}=\left(\frac{16}{5},\frac{32}{5}\right)^T,\qquad x^{(3)}=(2,3+\sqrt{13})^T.

在 x(1)=(0,0)Tx^{(1)}=(0,0)^T

两条约束都活动，KKT 乘子为

w=18,v=0.\boxed{w=\frac18,\qquad v=0}.

临界方向需满足

(0,8)d=0,(−4,−6)d=0,(0,8)d=0,\qquad (-4,-6)d=0,

只能得到 d=0d=0。两个活动边界在该点横截，局部没有非零临界方向，因此二阶充分条件成立，x(1)x^{(1)} 是局部极小点。

在 x(2)=(16/5,32/5)Tx^{(2)}=(16/5,32/5)^T

两条约束也都活动。解驻点方程得到

w=340,v=15.\boxed{w=\frac{3}{40},\qquad v=\frac15}.

两条活动约束梯度线性无关，临界方向仍只有 d=0d=0，所以 x(2)x^{(2)} 也是局部极小点。

在 x(3)=(2,3+13)Tx^{(3)}=(2,3+\sqrt{13})^T

圆盘约束不活动，故 w=0w=0；等式约束给

v=1326.\boxed{v=\frac{\sqrt{13}}{26}}.

等式切方向满足 d2=0d_2=0。此时

∇xx2L=−113I,\nabla_{xx}^2L =-\frac{1}{\sqrt{13}}I,

所以对 d=(d1,0)T≠0d=(d_1,0)^T\ne0，

dT∇xx2L d=−d1213<0.d^T\nabla_{xx}^2L\,d =-\frac{d_1^2}{\sqrt{13}}<0.

它不是局部极小点。

第 9 题：参数 β\beta 改变二阶性质

min⁡12[(x1−1)2+x22]s.t.−x1+βx22=0.\begin{aligned} \min\quad &\frac12\left[(x_1-1)^2+x_2^2\right]\\ \text{s.t.}\quad &-x_1+\beta x_2^2=0. \end{aligned}

考察 (0,0)T(0,0)^T。驻点方程给等式乘子 v=1v=1，切方向由

−d1=0-d_1=0

得到 d=(0,d2)Td=(0,d_2)^T。Lagrange Hessian 在切方向上的二阶型是

dT∇xx2L d=(1−2β)d22.d^T\nabla_{xx}^2L\,d=(1-2\beta)d_2^2.

因此 β<1/2\beta<1/2 时二阶充分条件直接给严格局部极小；β>1/2\beta>1/2 时存在二阶下降方向，不是局部极小。边界 β=1/2\beta=1/2 时二阶型为零，还不能停在必要条件上。

用约束精确消元 x1=βt2, x2=tx_1=\beta t^2,\ x_2=t：

f(t)=12[(βt2−1)2+t2]=12+(12−β)t2+β22t4.\begin{aligned} f(t) &=\frac12\left[(\beta t^2-1)^2+t^2\right]\\ &=\frac12+\left(\frac12-\beta\right)t^2 +\frac{\beta^2}{2}t^4. \end{aligned}

当 β=1/2\beta=1/2 时，非零小 tt 仍使四次项严格增加。因此完整结论是

β≤12 时 (0,0) 是严格局部极小点；β>12 时不是局部极小点。\boxed{ \beta\le\frac12\text{ 时 }(0,0)\text{ 是严格局部极小点；} \quad \beta>\frac12\text{ 时不是局部极小点。} }

作业自检

  • 先验可行性，再列活动约束；不可行候选点无需解 KKT。
  • 二阶条件检查 dT∇xx2L dd^T\nabla_{xx}^2L\,d，不是只看 ∇2f\nabla^2f。
  • 二阶型等于零时必要条件没有给答案，要像参数题一样回到原函数或更高阶项。

评论