约束最优性条件：可行方向、Fritz John 与 KKT

Views: --

有约束时，梯度不必为零：目标还想下降，但可行域边界挡住了它。最优性条件就是把“所有下降方向都被活动约束挡住”写成代数关系。

活动约束与可行方向

考虑

min⁡f(x),gi(x)≥0,hj(x)=0.\min f(x),\qquad g_i(x)\ge0,\qquad h_j(x)=0.

在可行点 xx，满足 gi(x)=0g_i(x)=0 的不等式叫活动约束，记集合 I(x)I(x)。先区分两个看起来相似、实际不完全相同的对象。

真实的射线可行方向集合是

FS(x)={d:∃δ>0,  x+td∈S, ∀t∈(0,δ)}.F_S(x)=\{d:\exists\delta>0,\; x+td\in S,\ \forall t\in(0,\delta)\}.

也就是说，真的沿直线走一小段仍留在可行域。只对活动约束做一阶展开，则得到线性化锥

LS(x)={d:∇gi(x)Td≥0,i∈I(x),∇hj(x)Td=0,∀j}.L_S(x)=\left\{d: \begin{aligned} \nabla g_i(x)^Td&\ge0,\quad i\in I(x),\\ \nabla h_j(x)^Td&=0,\quad \forall j \end{aligned} \right\}.

任何真实射线可行方向都满足线性化条件，所以 FS(x)⊆LS(x)F_S(x)\subseteq L_S(x)；有曲率时反向包含未必成立。例如

S={(x1,x2):x2−x12≥0}S=\{(x_1,x_2):x_2-x_1^2\ge0\}

在原点的线性化条件只有 d2≥0d_2\ge0，故 d=(1,0)d=(1,0) 属于 LS(0)L_S(0)；但直线点 (t,0)(t,0) 对任意 t>0t>0 都不满足 0−t2≥00-t^2\ge0，所以它不是射线可行方向。若课程之外还见到用收敛序列定义的切锥，要注意那是对曲线趋近方向的闭包概念，不能与这里的直线可行方向混写。

因此，若存在真正可行的 dd 同时满足 ∇f(x)Td<0\nabla f(x)^Td<0，就能直接否定局部最优；在线性化锥中找方向则需要约束资格保证一阶近似足够可靠。

Lagrange 乘子

取

L=f−∑iμigi+∑jλjhj,μi≥0.L=f-\sum_i\mu_i g_i+\sum_j\lambda_jh_j,\qquad\mu_i\ge0.

KKT 条件为

∇f−∑iμi∇gi+∑jλj∇hj=0,\nabla f-\sum_i\mu_i\nabla g_i+\sum_j\lambda_j\nabla h_j=0, gi≥0,hj=0,μi≥0,μigi=0.g_i\ge0,\quad h_j=0,\quad \mu_i\ge0,\quad \mu_i g_i=0.

驻点式说明目标负梯度落在活动约束法向量生成的法锥中。

约束资格为什么必要

最优点不一定自动存在 KKT 乘子。若活动约束梯度退化，目标梯度可能无法由它们表示。Fritz John 条件总允许目标前多一个乘子：

μ0∇f−∑iμi∇gi+∑jλj∇hj=0,\mu_0\nabla f-\sum_i\mu_i\nabla g_i+\sum_j\lambda_j\nabla h_j=0,

其中 μ0,μi≥0\mu_0,\mu_i\ge0 且所有乘子不全为零。约束资格的作用是排除 μ0=0\mu_0=0 的异常情形，进而归一化为 μ0=1\mu_0=1。

常见资格包括：

  • LICQ：活动不等式和等式的梯度线性无关；
  • MFCQ：等式梯度线性无关，并存在一个方向严格进入所有活动不等式内部；
  • 凸问题中的 Slater：存在严格满足全部凸不等式的点。

一个圆约束例子

min⁡x1x2,x12+x22=1.\min x_1x_2,\qquad x_1^2+x_2^2=1.

Lagrange 函数

L=x1x2+λ(x12+x22−1).L=x_1x_2+\lambda(x_1^2+x_2^2-1).

驻点方程给 x2+2λx1=0x_2+2\lambda x_1=0、x1+2λx2=0x_1+2\lambda x_2=0，结合约束得到四个候选点。再比较目标或检查约束切空间上的二阶型，才能区分极大与极小。

二阶条件

设 x∗x^* 满足 KKT，对应不等式乘子为 μ∗\mu^*。二阶条件检查的不是“把所有活动不等式都强行当等式”的切空间，而是临界锥

C(x∗,μ∗)={d:  ∇hj(x∗)Td=0,∇gi(x∗)Td=0,i∈I(x∗), μi∗>0,∇gi(x∗)Td≥0,i∈I(x∗), μi∗=0}.\begin{aligned} C(x^*,\mu^*)=\{d:\;&\nabla h_j(x^*)^Td=0,\\ &\nabla g_i(x^*)^Td=0, &&i\in I(x^*),\ \mu_i^*>0,\\ &\nabla g_i(x^*)^Td\ge0, &&i\in I(x^*),\ \mu_i^*=0\}. \end{aligned}

正乘子的活动约束在临界方向上必须保持等式；零乘子的活动约束仍保留朝可行侧的不等式，不能漏掉。标准正则条件下，局部极小的二阶必要条件为

dT∇xx2L(x∗,μ∗,λ∗)d≥0,∀d∈C(x∗,μ∗).\boxed{ d^T\nabla_{xx}^2L(x^*,\mu^*,\lambda^*)d\ge0, \quad \forall d\in C(x^*,\mu^*). }

严格大于零配合正则性可给严格局部极小。注意检查的是 Lagrange 函数 Hessian 在可行切方向上的限制，不是只看 ∇2f\nabla^2f。

考试要点

  • 先统一不等号方向，乘子符号才不会错。
  • 非活动约束由互补松弛立即给乘子零。
  • KKT 点只是候选；非凸问题还需二阶条件或直接比较。
  • 问“为什么 KKT 必要”时，必须说出约束资格。

评论