KKT 与约束最优性

无约束时，下降方向可以朝任意方向走；有约束时，一部分方向被墙挡住。最优点不必让完整梯度为零，但它不能在任何可行的微小方向上继续下降。KKT 条件把这句话拆成四个可检查的部分。

四个条件

考虑最小化问题

若 $x^*$ 与乘子 $\lambda_i,\nu_j$ 满足：

1. 原可行：$g_i(x^*)\le0,h_j(x^*)=0$；
2. 对偶可行：$\lambda_i\ge0$；
3. stationarity：$\nabla f(x^*)+\sum_i\lambda_i\nabla g_i(x^*)+\sum_j\nu_j\nabla h_j(x^*)=0$；
4. 互补松弛：$\lambda_i g_i(x^*)=0$；

它们合起来就是 KKT。等式乘子不受正负限制，因为等式两侧都能限制移动；不等式乘子必须非负，方向来自“只能从可行侧接近边界”。

active set 说的是哪几面墙在接触

若 $g_i(x^*)=0$，约束 active；若严格小于零，约束 inactive。互补松弛说明 inactive 约束的乘子为零。active 约束才可能在 stationarity 中抵消目标梯度，但“可能”不等于“每个 active 都有正乘子”。退化时 active 集合和正乘子集合不必一一对应。

例题：最简单的边界最优

求 $\min (x-3)^2$ s.t. $x\le1$。写成 $g(x)=x-1\le0$。候选最优点应在边界 $x^*=1$，因为无约束最小点 3 不可行。stationarity 为

所以 $\lambda=4\ge0$；原可行、互补 $4(1-1)=0$ 也成立。这个乘子把“目标还想向右走”和“约束把右侧挡住”平衡起来。

为什么凸问题中的 KKT 足够证明全局最优

假设 $f$ 和每个 $g_i$ 凸，$h_j$ 仿射，且 KKT 成立。对任意可行 $y$，凸性给出

用 stationarity 替换梯度：

凸约束的一阶不等式给 $\nabla g_i(x^*)^T(y-x^*)\le g_i(y)-g_i(x^*)\le -g_i(x^*)$；乘以 $\lambda_i\ge0$ 后，互补松弛使右侧为零。仿射等式项也为零，于是 $f(y)\ge f(x^*)$。因此 $x^*$ 是全局最优。

必要性则需要约束资格，例如 active 约束梯度与等式梯度线性无关；凸问题中常用 Slater 条件：存在一个点严格满足所有不等式、同时满足等式。条件失败时，局部最优仍可能存在，但不一定找得到 KKT 乘子。

练习

1. 对 $\min x^2$ s.t. $x\ge2$，写成 $g(x)=2-x\le0$ 并求 KKT 乘子。

2. 一个约束严格满足 $g_i(x^*)<0$。由互补松弛能推出什么？

3. KKT 满足但问题非凸时，能否直接断言全局最优？