优化 III · 对偶与 KKT 条件

约束优化的两大支柱：Lagrange 对偶（把可写成 Lagrangian 的问题映成一个凹的对偶函数，给出下界与边际价值信息）与 KKT 条件（把“导数为零”改写成约束几何中的平衡）。对偶函数总是凹，并不保证对偶问题自动更容易；数分 V 的 Lagrange 乘数法在这里补全不等式约束的另一半，ai 课 02 讲 SVM 对偶推导的每一步也都有出处。

1. 问题形式与 Lagrange 函数

标准形：

Lagrange 函数（给每条约束配一个"价格"）：

关键观察（把内层 \(\max\) 理解为上确界）：\(\sup_{\lambda \geq 0, \nu} L = \begin{cases} f(x) & x \text{ 可行} \\ +\infty & \text{违反某条不等式或等式} \end{cases}\)。因此在扩展实数意义下，原问题的值可写成 \(\inf_x\sup_{\lambda,\nu}L\)；这是把不可行点标成 \(+\infty\) 的值函数恒等式，不等于说外层极小值或内层乘子一定取得（ai 课 02 讲 SVM 推导开头的那句话在此验明）。

2. 对偶问题

对偶函数：\(d(\lambda, \nu) = \inf_x L(x, \lambda, \nu)\)；\(\inf\) 不一定在某个有限 \(x\) 上取得。

性质一（凹性，无条件成立）：\(d\) 是 \((\lambda,\nu)\) 的仿射函数族的逐点下确界 ⇒ 恒为凹函数（优化 I 保凸运算）。所以对偶的“最大化凹函数”可按凸优化的形式处理，但不保证它比原问题更容易，也不保证对偶最优解取得——哪怕原问题极度非凸，弱对偶仍然成立。

性质二（弱对偶，无条件成立）：对任意可行 \(x\) 与 \(\lambda \geq 0\)：

一行证明：\(d(\lambda,\nu) = \inf_z L \leq L(x,\lambda,\nu) = f + \underbrace{\textstyle\sum\lambda_i g_i}_{\leq 0} + \underbrace{\textstyle\sum \nu_j h_j}_{=0} \leq f(x)\)。——对偶给原问题免费下界（分支定界、验证解质量都靠它）。

强对偶 \(d^* = p^*\)（对偶间隙为零）：一般不成立。对 proper、闭凸的目标和不等式函数、仿射等式约束，在原问题可行且最优值有限，并存在位于公共定义域相对内部、满足等式且对所有不等式严格可行的点（Slater 点），则零对偶间隙成立，且对偶最优乘子取得。等式约束不要求“严格”。Slater 是凸问题中的充分约束资格，不是每个强对偶实例的必要条件；若 Slater 失败，不能只凭凸性推出强对偶或对偶最优解存在。线性规划则由 LP 对偶定理给出更专门的结论：在相应问题可行且最优值有限时，原/对偶最优值相等（不必把 LP 生硬套成一般非线性 Slater 论证，详见优化 IV）。

影子价格解读：若把约束参数化为 \(a_i(x)\le b_i\)，并记最优值函数为 \(p^*(b)\)，在强对偶、适当可解性和局部正则性下，任一匹配的最优乘子满足 \(-\lambda^*\in\partial p^*(b)\)；若 \(p^*\) 在该点可微，才可写成 [ \frac{\partial p^}{\partial b_i}=-\lambda_i^. ] 因此放松 \(b_i\) 一单位的局部最优值变化约为 \(-\lambda_i^*\)，符号依赖于你把右端写在不等式哪一侧。若值函数不可微，影子价格可能是一个集合；\(\lambda_i^*=0\) 对非活动约束是必然的，但活动约束也可能因退化而有零乘子，所以不能把零乘子直接等同于“全局不稀缺”。

3. KKT 条件（本页顶点）

定理（凸问题的 KKT 充要性） 设 \(f,g_i\) 可微凸、\(h_j\) 仿射；若原问题可行、最优值有限，并满足 Slater 等适当约束资格，则 \(x^*\) 为全局最优 \(\iff\) 存在 \((\lambda^*,\nu^*)\) 满足四组 KKT 条件。任意满足这四组条件的三元组都是原/对偶最优并给出零对偶间隙；一般凸不可微时，把梯度平稳性改成次梯度包含关系。这里的“存在乘子”是结论的一部分，不能仅由一句“强对偶成立”无条件推出，因为还要排除对偶最优不取得、目标不可微或约束资格失败等情况。

（凸问题 + 适当 CQ 下是充要条件；对非凸问题，若局部极小点满足 LICQ、MFCQ 等约束资格，KKT 通常只是必要条件。没有 CQ 时，局部极小点可能没有 KKT 乘子；即使有，KKT 点也可能是鞍点或非全局最优点。）

逐条读：第 1 条是数分 V Lagrange 乘数法的推广（目标梯度被约束梯度的锥组合抵消）；第 4 条是灵魂——\(g_i<0\) 时必有 \(\lambda_i=0\)，\(\lambda_i>0\) 时必有 \(g_i=0\)，但 \(g_i=0,\lambda_i=0\) 也完全允许。价格机制的读法是局部边际信息，而不是对所有参数扰动都成立的绝对稀缺性判定。

🔗 AI 衔接对账：SVM 的支持向量（ai 课 02 讲）正是互补松弛的产物——按所选标准形记号，严格位于间隔约束外侧的点满足 \(g_i<0\) ⇒ \(\alpha_i=0\)，而 \(\alpha_i>0\) 的点必在间隔边界上；边界点取零乘子也可能是退化情形。岭回归/Lasso 的约束形式 \(\|w\|\le t\) 与惩罚形式 \(f(w)+\lambda\|w\|\) 来自同一个拉格朗日/值函数视角，但并非对任意 \(t,\lambda\) 一一等价；在适当凸性、闭性、可解性和强对偶条件下，才可以讨论某个约束解与某个乘子参数的匹配，且解路径平台会造成多对一或参数区间。

4. 求解套路与例题

KKT 手算流程：按互补松弛对"哪些约束绷紧"分类讨论 → 每种情形解平稳性方程 → 验可行性与 \(\lambda \geq 0\) → 比较候选点。

例 1（完整 KKT 流程） \(\min x_1^2 + x_2^2\) s.t. \(x_1 + x_2 \geq 4\)（即 \(g = 4 - x_1 - x_2 \leq 0\)）。 解：\(L = x_1^2 + x_2^2 + \lambda(4 - x_1 - x_2)\)。平稳性：\(2x_1 = \lambda,\ 2x_2 = \lambda\) ⇒ \(x_1 = x_2\)。情形 A（先试 \(\lambda = 0\)，并不预先断言约束松弛）：\(x = (0,0)\) 违反可行性，弃。情形 B（绷紧 \(x_1 + x_2 = 4\)）：\(x^* = (2,2),\ \lambda^* = 4 \geq 0\) ✓。最优值 8。（几何：原点到直线的投影——最近点问题的 KKT 面目。）

例 2（对偶推导演练） 对例 1 构造对偶：\(d(\lambda) = \inf_x L = -\frac{\lambda^2}{2} + 4\lambda\)（对 \(x\) 配方），\(\sup_{\lambda \geq 0} d\) 得 \(\lambda^* = 4\)，\(d^* = 8 = p^*\)——强对偶亲手验证一次（凸 + Slater 显然）。

例 3（水填充，信息论名例） \(\max \sum_i \ln(x_i + a_i)\) s.t. \(\sum x_i = 1,\ x_i \geq 0\)（功率分配，设有限个信道、每个 \(a_i>0\)）。KKT 给出 \(x_i^* = \max(0,\ \tfrac{1}{\nu} - a_i)\)。推导时最小化 \(-\sum_i\log(x_i+a_i)\)，取 \(L=-\sum_i\log(x_i+a_i)+\nu(\sum_i x_i-1)-\sum_i\lambda_i x_i\)；平稳性为 \(-1/(x_i+a_i)+\nu-\lambda_i=0\)。若 \(x_i>0\) 则 \(\lambda_i=0\)，若 \(x_i=0\) 则 \(\nu\ge1/a_i\)；合并得到上述截断式，再由 \(\sum_i\max(0,w-a_i)=1\) 确定水位 \(w=1/\nu\)。例如 \(a=(0.2,0.6,1.4)\) 时 \(w=0.9\)，分配 \((0.7,0.3,0)\)；第三条信道没有分到功率，正是互补松弛的结果。\(\blacksquare\)

5. 收束：对偶的思维价值

对偶不只是技巧，是一种换视角：原问题问"怎么分配变量"，对偶问题在适当正则性下问"每条约束的局部边际价值是多少"。同一个最优解，两套语言互为镜像（互补松弛是镜面）。这个视角在经济学（影子价格）、组合优化（最大流-最小割）、机器学习（SVM 对偶把数据表示为内积，便于用核替代；RKHS 原始表述也可使用核）反复变现——遇到难优化问题，先写对偶看看是受用终身的动作，但要同时检查可行性、间隙和乘子是否取得。

下一页：约束优化最重要的特例——线性规划：单纯形法、LP 对偶，以及动态规划一瞥。

先修与来源：先补 凸性与一阶条件、多元微分与乘子法，再到 LP/DP。对偶、Slater 与 KKT 的完整条件见 Boyd–Vandenberghe 《Convex Optimization》第 5 章讲义。