对应 note 4_optcon.pdf。本章是整门课最关键、最高频被考的一章之一。它把"什么是最优解"用方程组刻画出来。

0. 一句话理解这一章

最优解 = 满足"梯度组合为 0 + 互补松弛 + 原始/对偶可行"的点。在凸问题 + Slater 条件下，KKT 既是必要也是充分条件。

1. 知识地图

            无约束情形（先把"必要 / 充分"分清楚）
            ─────────────────────────────────────
            一阶必要：∇f(x*) = 0
            二阶必要：∇²f(x*) ⪰ 0
            二阶充分：∇f(x*) = 0 且 ∇²f(x*) ≻ 0
            凸的特例：∇f(x*) = 0  ⇔  全局最优

            约束情形（核心是处理"约束的方向"）
            ─────────────────────────────────────
                            FJ 条件 (最弱)
                                ↓ 加正则性
                            KKT 条件 (Theorem 3.2)
                            ↑   ↑   ↑
                       三种情况下的"必要性"：
                       (1) 线性无关 (LICQ)
                       (2) Slater (凸不等式 + 仿射等式)
                       (3) 凹不等式 + 仿射等式

            凸 + KKT  ⇒  全局最优 (Theorem 3.7, 充分性)

2. 无约束的最优性条件

考虑 $f:{\mathbb{R}}^n\to \mathbb{R}$ 二次连续可微。

命题	内容	备注
一阶必要 (Cor 2.2)	$\overline{x}$ 局部最小 ⇒ $\mathrm{\nabla }f(\overline{x})=0$	反证：若梯度 $\ne 0$，沿 $-\mathrm{\nabla }f$ 走能下降
二阶必要 (Prop 2.5)	$\overline{x}$ 局部最小 ⇒ ${\mathrm{\nabla }}^{2}f(\overline{x})⪰0$	反证：若有负特征值，沿对应特征向量下降
二阶充分 (Prop 2.4)	$\mathrm{\nabla }f(\overline{x})=0$ + ${\mathrm{\nabla }}^{2}f(\overline{x})\succ 0$ ⇒ $\overline{x}$ 局部最小	这里是 $\succ$ 严格
凸特例 (Prop 2.3)	凸 + $\mathrm{\nabla }f(\overline{x})=0$ ⇒ 全局最小	由 Ch2 一阶条件

必要 vs 充分的区别：必要是"如果是最优 → 这个条件成立"；充分是"如果这个条件成立 → 它一定是最优"。考试经常考它们对凸/非凸函数的差别。

反例

• $f(x)=-x^2$：$\mathrm{\nabla }f(0)=0$ 但是局部最大——所以一阶必要不充分。
• $f(x,y)=x^2-y^2$：在 $(0,0)$ 处梯度 0、Hessian 不是半正定（saddle point）。

3. FJ 条件（Fritz John）

针对一般约束问题 (5)：

$$minf(x)\text{s.t.}{g}_i(x)\le 0,h_j(x)=0,x\in X.$$

FJ 必要条件（Theorem 3.1）：$\overline{x}$ 局部最优 ⇒ 存在 $(u,{\lambda }_1,\dots ,{\lambda }_m,{\nu }_1,\dots ,{\nu }_p)\ne 0$ 使

$$u\mathrm{\nabla }f(\overline{x})+\sum _i{\lambda }_i\mathrm{\nabla }{g}_i(\overline{x})+\sum _j{\nu }_j\mathrm{\nabla }{h}_j(\overline{x})=0,$$$$u,{\lambda }_i\ge 0,{\lambda }_i{g}_i(\overline{x})=0\text{(互补松弛)}.$$

这里的 $u$ 是目标函数前面的"乘子"。FJ 条件最弱，只保证有一组非全零乘子。它的弱点是：可能 $u=0$ ——这种情况叫"退化"，目标函数没有起到任何作用。

FJ → KKT 的过渡：只要能保证 $u>0$，就可以两边除以 $u$，把它"归一化"为 $u=1$，得到 KKT。所以正则性条件的本质就是排除 $u=0$ 的情形。

4. KKT 条件（Karush-Kuhn-Tucker）⭐⭐⭐

KKT 必要条件（Theorem 3.2）：$\overline{x}$ 局部最优 + 正则性条件（线性无关：$\{\mathrm{\nabla }{g}_i(\overline{x}){\}}_{i\in I}\cup \{\mathrm{\nabla }{h}_j(\overline{x})\}$ 线性无关）⇒ 存在 $\lambda ,\nu$ 使

$$\boxed{{\displaystyle \begin{array}{rlrl}& g_i(\overline{x})\le 0,h_j(\overline{x})=0& & \text{(原始可行)}\\ & \mathrm{\nabla }f(\overline{x})+\sum _i{\lambda }_i\mathrm{\nabla }{g}_i(\overline{x})+\sum _j{\nu }_j\mathrm{\nabla }{h}_j(\overline{x})=0& & \text{(梯度方程)}\\ & {\lambda }_i\ge 0& & \text{(对偶可行)}\\ & {\lambda }_i{g}_i(\overline{x})=0& & \text{(互补松弛)}\end{array}}}$$

与 FJ 的区别：$u$ 已经被规范为 1，目标函数有真正的作用。

4.1 三种保证 KKT 必要性的"正则性条件"

名称	适用情形	条件
LICQ（线性无关）	一般非线性	$\{\mathrm{\nabla }{g}_i(\overline{x}){\}}_{i\in I}\cup \{\mathrm{\nabla }{h}_j(\overline{x})\}$ 线性无关（Theorem 3.2）
Slater（最常用）⭐	凸不等式 + 仿射等式	存在 $x^{\prime }\in S$ 使 $g_i(x^{\prime })<0,\mathrm{\forall }i$（严格内点） (Theorem 3.4)
凹 + 仿射	$g_i$ 凹、$h_j$ 仿射	自动满足（Theorem 3.5）

Slater 的特殊放宽：若其中部分 $g_j$ 是仿射的，则这些仿射不等式可以放松为 "$\le$"（不要求严格 "<")。

考试技巧：作业中遇到的凸问题几乎全是 Slater；遇到 LP / 仿射约束的问题，根据 Theorem 3.5 自动满足。

4.2 KKT 不必要的"反例"（Example 3.3）

$min{x}_1$ s.t. $(x_1-1{)}^2+(x_2\mp 1{)}^2\le 1$。可行域只有一个点 $(1,0)$，它必然最优，但是两个约束的梯度在该点共线，不满足 LICQ 也不满足 Slater——KKT 系统无解。

这个例子告诉你：没有正则性时 KKT 可能无解——所以"必要性"是建立在正则性之上的。

4.3 KKT 充分性（Theorem 3.7）⭐

凸优化问题 + KKT 系统有解 $(\overline{x},\overline{\lambda },\overline{\nu })$ ⇒ $\overline{x}$ 是全局最优解。

证明思路（要会）：

1. $L(x,\overline{\lambda },\overline{\nu })=f(x)+\sum {\overline{\lambda }}_i{g}_i+\sum {\overline{\nu }}_j{h}_j$ 是凸函数（凸 + 非负组合 + 仿射）
2. KKT 的梯度方程 ${\mathrm{\nabla }}_{x}L(\overline{x},\overline{\lambda },\overline{\nu })=0$ → $\overline{x}$ 是 $L(\cdot ,\overline{\lambda },\overline{\nu })$ 的全局极小点（凸的一阶充分性，Prop 2.3）。
3. 用互补松弛 ${\overline{\lambda }}_i{g}_i(\overline{x})=0$ 和 $h_j(\overline{x})=0$，得 $L(\overline{x},\overline{\lambda },\overline{\nu })=f(\overline{x})$。
4. 对任意可行 $x$：$f(\overline{x})=L(\overline{x},\overline{\lambda },\overline{\nu })\le L(x,\overline{\lambda },\overline{\nu })\le f(x)$（最后一步用 $g_i\le 0,\overline{\lambda }\ge 0,h_j=0$）。

5. KKT 解析求解的"标准流程"

讲义 Example 3.6 给了 4 个示范，都是先写 KKT、再解 KKT 的标准流程。

Example 3.6.1 LP $min{c}^{T}x$ s.t. $Ax=b,x\ge 0$

写出 KKT：

$$c-A^T\nu =\lambda \ge 0,{\lambda }^{T}x=0,Ax=b,x\ge 0.$$

这里 $\lambda \ge 0$ 是对应 $x\ge 0$ 的乘子；$\nu$ 是对应 $Ax=b$ 的。LP 的 KKT 同时也是它的"对偶可行"条件——这是为什么 LP 强对偶恒成立。

Example 3.6.2 最小特征值

$min{x}^{T}Ax$ s.t. $\parallel x{\parallel }^2=1$。KKT：$2Ax=\nu \cdot 2x$ → $Ax=\nu x$，即 $x$ 是特征向量；目标值 $(x^{\ast }{)}^{T}A{x}^{\ast }=\nu \cdot 1=\nu$，所以 ${\nu }^{\ast }={\lambda }_{min}(A)$。

Example 3.6.3 $min-\log detZ$ s.t. $A\bullet Z\le b$

KKT 解出唯一解 $Z^{\ast }=b{A}^{-1}/n$（用矩阵微积分 $\mathrm{\nabla }(-\log detZ)=-Z^{-1}$ + 约束 + 互补松弛）。

Example 3.6.4 信道分配 / Water-filling ⭐

$min-\sum \log (x_i+{\alpha }_i)$ s.t. $x\ge 0,e^{T}x=1$。KKT 推导出：

$$x_i^{\ast }=max\{0,1/{\nu }^{\ast }-{\alpha }_i\},\text{其中 }{\nu }^{\ast }\text{ 由 }\sum _{i}max\{0,1/{\nu }^{\ast }-{\alpha }_i\}=1\text{ 唯一确定}.$$

直观图像：把每个信道的"地面高度" ${\alpha }_i$ 画出来，"灌水"到水深 $1/{\nu }^{\ast }$，每个信道得到的水量就是 $x_i^{\ast }$。

这种用 KKT 推出"显式解+一个 1 维方程"的题型经常出现。

6. 作业题型对照（A6.1）

作业	题面	考点
A6.1(a)	Kantorovich 的辅助优化问题：$min-\log (a^{T}x)-\log (b^{T}x)$ s.t. $x\ge 0,{\mathbf{1}}^{T}x=1$	1) 验证凸性（每项是 $-\log (\text{正的线性})$）；2) 写 KKT 系统：$-\frac{a}{a^{T}x}-\frac{b}{b^{T}x}-\lambda +\nu \mathbf{1}=0$，$\lambda \ge 0,{\lambda }_i{x}_i=0,x\ge 0,{\mathbf{1}}^{T}x=1$；3) 验证 $x=(1/2,0,\dots ,0,1/2)$ 满足 KKT
A6.1(b)	由 (a) 推 Kantorovich 不等式 $2(u^{T}Au{)}^{1/2}(u^T{A}^{-1}u{)}^{1/2}\le \sqrt{{\lambda }_1/{\lambda }_n}+\sqrt{{\lambda }_n/{\lambda }_1}$	用 $A=\sum {\lambda }_k{v}_k{v}_k^T$ 谱分解；记 $x_k=(v_k^{T}u{)}^2$，则 $\sum x_k=1,x\ge 0$，$u^{T}Au=\sum {\lambda }_k{x}_k=a^{T}x$（$a_k={\lambda }_k$），$u^T{A}^{-1}u=\sum x_k/{\lambda }_k=b^{T}x$；用 (a) 的最优值给出上界

这道题展示了 KKT 的强大用途：先把不等式归约到一个凸优化问题，再用 KKT 求 closed form 最优值，最后反推不等式。

---

7. 解题"招式手册"

招式 1：写 KKT 系统的标准模板

遇到题目要写 KKT，按这个 5 行模板永远不会漏：

$$\{\begin{array}{l}\text{原始可行：}{g}_i(\overline{x})\le 0,h_j(\overline{x})=0\\ \text{对偶可行：}{\lambda }_i\ge 0\\ \text{梯度方程：}\mathrm{\nabla }f(\overline{x})+\sum {\lambda }_i\mathrm{\nabla }{g}_i(\overline{x})+\sum {\nu }_j\mathrm{\nabla }{h}_j(\overline{x})=0\\ \text{互补松弛：}{\lambda }_i{g}_i(\overline{x})=0,\mathrm{\forall }i\\ \text{(若有 PSD 约束 }X⪰0\text{：}\mathrm{\Lambda }⪰0,\mathrm{\Lambda }\bullet X=0\text{)}\end{array}$$

招式 2：互补松弛"二选一"案例分析

互补松弛 ${\lambda }_i{g}_i(\overline{x})=0$ 意味着每个约束要么 ${\lambda }_i=0$ 要么 $g_i(\overline{x})=0$（约束"激活"）。 按"哪些 i 激活、哪些 i 不激活"分情况讨论。例 3.6.4 就是这个套路（$x_i>0\Rightarrow \nu =1/({\alpha }_i+x_i)$ vs. $x_i=0\Rightarrow \nu \ge 1/{\alpha }_i$）。

招式 3：用 KKT 充分性证最优

要证 $\overline{x}$ 是凸问题的最优解，只需写出对应的 $\overline{\lambda },\overline{\nu }$ 让 KKT 成立，然后引用 Theorem 3.7。这是 A6.1(a) 的核心思路。

招式 4：把不等式问题归约到凸优化 + KKT

A6.1(b) 是这种思路的代表：把不等式 $P\le Q$ 写成 $\underset{x}{sup}P(x)\le Q$，再把 $sup$ 转成 $min$（取负号 / 取倒数 / log），用 KKT 求显式解。

招式 5：检查 Slater 永远先做

写 KKT 之前，先看一眼正则性是否满足。凸 + 至少一个严格内点 = Slater 满足。仿射约束直接套 Theorem 3.5。

---

8. 自检清单

• [ ] 无约束一阶 / 二阶必要 / 二阶充分 / 凸特例分别说什么？
• [ ] FJ 条件 vs KKT 条件的差别？什么是"正则性 → $u>0$"？
• [ ] LICQ、Slater、凹+仿射 三种正则性条件分别是什么？
• [ ] KKT 5 个条件能完整默写？
• [ ] KKT 在凸问题下是充分的——证明的核心步骤记得吗？
• [ ] LP / 最小特征值 / Water-filling 的 KKT 推导都能复现？

9. 常见陷阱

1. 必要 ≠ 充分：在凸问题 + 正则性下 KKT 才同时是必要+充分；非凸问题中 KKT 只是必要。
2. LICQ 在凸问题里其实弱于 Slater：如果你在凸问题里只验证了 LICQ 而没用 Slater，也是对的（任何一个正则性都行）。
3. 写 $\mathrm{\nabla }$ 时正负号：约束写成 $g_i\le 0$ 时，乘子 ${\lambda }_i\ge 0$；写成 $g_i\ge 0$ 时乘子改 $\le 0$。书上 Example 3.6.1 里 $-e_i^{T}x\le 0$ 对应乘子 ${\lambda }_i\ge 0$，$\mathrm{\nabla }(-e_i^{T}x)=-e_i$，要小心负号。
4. 互补松弛的"分情况讨论"必须穷尽：每个约束都要选一支（紧或不紧）。
5. 存在性：KKT 给的是"如果最优解存在 → ..."；存在性要用 Weierstrass 或者 coercive 性质（Ch4 §3.2）。
6. $X⪰0$ 约束的乘子是矩阵 $\mathrm{\Lambda }⪰0$，互补松弛是 $\mathrm{\Lambda }\bullet X=0$（即 $\text{tr}(\mathrm{\Lambda }X)=0$）——这一点在 SDP / A6.4 中用到。

---

10. 接下来怎么学

1. 默写 KKT 五行（题目 = 写 KKT 几乎是 100% 起手式）。
2. 把 Example 3.6 四个例子重做一遍。
3. 完成 A6.1，体会"用 KKT 证不等式"的玩法。
4. 进入 5_拉格朗日对偶——KKT 与对偶是同一枚硬币的两面。