1. 问题背景
优化理论中常见的问题是：
$$ \min_x f_0(x) $$
但变量 $x$ 往往需要满足一些约束，例如等式约束和不等式约束：
$$ f_i(x) \le 0,\quad i=1,\dots,m $$
$$ h_j(x)=0,\quad j=1,\dots,p $$
于是标准约束优化问题可以写成：
$$ \begin{aligned} \min_x\quad & f_0(x) \ \text{s.t.}\quad & f_i(x) \le 0,\quad i=1,\dots,m, \ & h_j(x)=0,\quad j=1,\dots,p. \end{aligned} $$
其中：
- $f_0(x)$ 是目标函数。
- $f_i(x)\le 0$ 是不等式约束。
- $h_j(x)=0$ 是等式约束。
- 满足所有约束的 $x$ 称为可行点。
- 所有可行点构成可行域。
拉格朗日乘子法、对偶函数和 KKT 条件都是研究这类约束优化问题的核心工具。
2. 等式约束下的拉格朗日乘子法
先考虑最简单的等式约束问题：
$$ \begin{aligned} \min_x\quad & f(x) \ \text{s.t.}\quad & h(x)=0. \end{aligned} $$
直观上，如果最优点 $x^\star$ 位于约束曲面 $h(x)=0$ 上，那么在 $x^\star$ 处，目标函数沿着约束曲面的切向方向不能继续下降。
这等价于说：
$$ \nabla f(x^\star) $$
必须与约束曲面的法向方向平行。而约束曲面 $h(x)=0$ 的法向量是：
$$ \nabla h(x^\star). $$
因此存在一个标量 $\lambda^\star$，使得：
$$ \nabla f(x^\star)+\lambda^\star \nabla h(x^\star)=0. $$
这就是拉格朗日乘子法的基本思想。
定义拉格朗日函数：
$$ L(x,\lambda)=f(x)+\lambda h(x). $$
必要条件为：
$$ \nabla_x L(x^\star,\lambda^\star)=0, $$
$$ h(x^\star)=0. $$
也就是：
$$ \begin{cases} \nabla f(x^\star)+\lambda^\star \nabla h(x^\star)=0,\ h(x^\star)=0. \end{cases} $$
其中 $\lambda$ 称为拉格朗日乘子。
3. 多个等式约束的情况
如果有多个等式约束：
$$ h_j(x)=0,\quad j=1,\dots,p, $$
则拉格朗日函数为：
$$ L(x,\nu)=f_0(x)+\sum_{j=1}^p \nu_j h_j(x). $$
其中 $\nu_j$ 是等式约束对应的拉格朗日乘子。
一阶必要条件为：
$$ \nabla f_0(x^\star)+\sum_{j=1}^p \nu_j^\star \nabla h_j(x^\star)=0, $$
$$ h_j(x^\star)=0,\quad j=1,\dots,p. $$
向量形式为：
$$ \nabla_x L(x^\star,\nu^\star)=0, $$
$$ h(x^\star)=0. $$
4. 不等式约束与拉格朗日函数
考虑包含不等式约束的优化问题：
$$ \begin{aligned} \min_x\quad & f_0(x) \ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1,\dots,m. \end{aligned} $$
对于不等式约束，引入非负乘子：
$$ \lambda_i \ge 0. $$
拉格朗日函数定义为：
$$ L(x,\lambda)=f_0(x)+\sum_{i=1}^m \lambda_i f_i(x). $$
为什么要求 $\lambda_i\ge 0$？
如果 $x$ 是可行点，则：
$$ f_i(x)\le 0. $$
当 $\lambda_i\ge 0$ 时：
$$ \lambda_i f_i(x)\le 0. $$
因此：
$$ L(x,\lambda) =f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) \le f_0(x). $$
也就是说，对任何可行点 $x$ 和任何 $\lambda\ge 0$，拉格朗日函数都给出了目标函数的一个下界结构。
如果同时有不等式和等式约束，则标准拉格朗日函数为：
$$ L(x,\lambda,\nu) =f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) +\sum_{j=1}^p \nu_j h_j(x), $$
其中：
$$ \lambda_i\ge 0, $$
而 $\nu_j$ 没有符号限制。
5. 对偶函数
5.1 定义
对偶函数定义为拉格朗日函数对原变量 $x$ 的下确界：
$$ g(\lambda,\nu) =\inf_x L(x,\lambda,\nu). $$
也就是：
$$ g(\lambda,\nu) =\inf_x \left[ f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) +\sum_{j=1}^p \nu_j h_j(x) \right]. $$
注意这里的 $\inf_x$ 是在所有 $x$ 上取下确界，而不是只在可行域上取下确界。
5.2 对偶函数给出原问题最优值的下界
设原问题最优值为 $p^\star$。
对任何可行点 $x$，有：
$$ f_i(x)\le 0,\quad h_j(x)=0. $$
若 $\lambda_i\ge 0$，则：
$$ \sum_{i=1}^m \lambda_i f_i(x)\le 0, $$
而：
$$ \sum_{j=1}^p \nu_j h_j(x)=0. $$
因此：
$$ L(x,\lambda,\nu)\le f_0(x). $$
又因为：
$$ g(\lambda,\nu)=\inf_z L(z,\lambda,\nu)\le L(x,\lambda,\nu), $$
所以：
$$ g(\lambda,\nu)\le f_0(x). $$
对所有可行点取最小，得到：
$$ g(\lambda,\nu)\le p^\star. $$
这说明：只要 $\lambda\ge 0$，对偶函数 $g(\lambda,\nu)$ 一定是原问题最优值 $p^\star$ 的下界。
这个性质称为弱对偶性。
6. 拉格朗日对偶问题
既然 $g(\lambda,\nu)$ 是原问题最优值的下界，那么自然希望找到最好的下界，即让 $g(\lambda,\nu)$ 尽可能大。
于是得到拉格朗日对偶问题：
$$ \begin{aligned} \max_{\lambda,\nu}\quad & g(\lambda,\nu) \ \text{s.t.}\quad & \lambda_i\ge 0,\quad i=1,\dots,m. \end{aligned} $$
通常记对偶问题的最优值为：
$$ d^\star. $$
由弱对偶性：
$$ d^\star \le p^\star. $$
差值：
$$ p^\star-d^\star $$
称为对偶间隙。
如果：
$$ p^\star=d^\star, $$
则称强对偶成立。
7. 弱对偶与强对偶
7.1 弱对偶性
弱对偶性总是成立，不要求原问题是凸问题。
只要拉格朗日函数按标准方式构造，并且不等式乘子满足：
$$ \lambda\ge 0, $$
就有：
$$ d^\star\le p^\star. $$
弱对偶性的意义是：
- 对偶问题可以给出原问题最优值的下界。
- 如果找到一个可行点 $x$ 和一个对偶可行点 $(\lambda,\nu)$，并且二者目标值相同，那么它们都是最优解。
7.2 强对偶性
强对偶性不总是成立。
对凸优化问题，如果满足一定的约束资格条件，通常可以保证强对偶成立。最常用的是 Slater 条件。
考虑凸优化问题：
$$ \begin{aligned} \min_x\quad & f_0(x) \ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1,\dots,m,\ & Ax=b. \end{aligned} $$
其中 $f_0,f_1,\dots,f_m$ 都是凸函数，等式约束是仿射的。
Slater 条件要求存在一个点 $\tilde{x}$，使得：
$$ f_i(\tilde{x})<0,\quad i=1,\dots,m, $$
$$ A\tilde{x}=b. $$
也就是说，存在一个严格满足所有不等式约束并满足等式约束的点。
若 Slater 条件成立，则通常有：
$$ p^\star=d^\star. $$
8. KKT 条件
KKT 条件是 Karush-Kuhn-Tucker 条件的简称，是约束优化问题的一阶最优性条件。
考虑标准问题：
$$ \begin{aligned} \min_x\quad & f_0(x) \ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1,\dots,m,\ & h_j(x)=0,\quad j=1,\dots,p. \end{aligned} $$
拉格朗日函数为：
$$ L(x,\lambda,\nu) =f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) +\sum_{j=1}^p \nu_j h_j(x). $$
KKT 条件包括四组条件。
8.1 原始可行性
最优解必须满足原问题约束：
$$ f_i(x^\star)\le 0,\quad i=1,\dots,m, $$
$$ h_j(x^\star)=0,\quad j=1,\dots,p. $$
这称为 primal feasibility。
8.2 对偶可行性
不等式约束对应的拉格朗日乘子必须非负：
$$ \lambda_i^\star\ge 0,\quad i=1,\dots,m. $$
这称为 dual feasibility。
等式约束对应的乘子 $\nu_j^\star$ 没有符号限制。
8.3 互补松弛条件
对每个不等式约束：
$$ \lambda_i^\star f_i(x^\star)=0,\quad i=1,\dots,m. $$
这称为 complementary slackness。
它的含义是：
- 如果约束不紧，即 $f_i(x^\star)<0$，则必须有 $\lambda_i^\star=0$。
- 如果 $\lambda_i^\star>0$，则必须有 $f_i(x^\star)=0$。
换句话说，只有在最优点处被“顶住”的约束，才可能有非零乘子。
这类约束称为活跃约束或有效约束。
8.4 驻点条件
拉格朗日函数对原变量 $x$ 的梯度必须为零：
$$ \nabla_x L(x^\star,\lambda^\star,\nu^\star)=0. $$
展开为：
$$ \nabla f_0(x^\star) +\sum_{i=1}^m \lambda_i^\star \nabla f_i(x^\star) +\sum_{j=1}^p \nu_j^\star \nabla h_j(x^\star) =0. $$
这称为 stationarity。
9. KKT 条件的必要性与充分性
9.1 一般非凸问题
对于一般非凸问题，KKT 条件通常只是局部最优解的一阶必要条件。
也就是说：
如果 $x^\star$ 是局部最优解，并且满足适当的约束资格条件，那么存在乘子 $(\lambda^\star,\nu^\star)$，使得 KKT 条件成立。
但是反过来不一定成立：
满足 KKT 条件的点不一定是全局最优点，甚至可能只是鞍点或局部极值点。
9.2 凸优化问题
对于凸优化问题：
$$ \begin{aligned} \min_x\quad & f_0(x) \ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1,\dots,m,\ & Ax=b, \end{aligned} $$
其中 $f_0,\dots,f_m$ 是凸函数，等式约束是仿射的。
如果强对偶成立，则 KKT 条件是最优性的充分必要条件。
也就是说，若存在 $x^\star,\lambda^\star,\nu^\star$ 满足 KKT 条件，则 $x^\star$ 是原问题最优解，$(\lambda^\star,\nu^\star)$ 是对偶问题最优解。
10. 利用对偶函数求解问题的一般步骤
给定原问题：
$$ \begin{aligned} \min_x\quad & f_0(x) \ \text{s.t.}\quad & f_i(x)\le 0,\quad i=1,\dots,m,\ & h_j(x)=0,\quad j=1,\dots,p. \end{aligned} $$
通常可以按以下步骤求解。
第一步：构造拉格朗日函数
$$ L(x,\lambda,\nu) =f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) +\sum_{j=1}^p \nu_j h_j(x). $$
注意：
- 不等式约束必须统一成 $f_i(x)\le 0$ 的形式。
- 对应乘子 $\lambda_i\ge 0$。
- 等式约束对应乘子 $\nu_j$ 无符号限制。
第二步：计算对偶函数
对 $x$ 求下确界：
$$ g(\lambda,\nu)=\inf_x L(x,\lambda,\nu). $$
通常需要解：
$$ \nabla_x L(x,\lambda,\nu)=0. $$
如果 $L$ 关于 $x$ 是凸二次函数，经常可以直接求出最小点。
如果某些 $\lambda,\nu$ 使得 $L$ 关于 $x$ 无下界，则：
$$ g(\lambda,\nu)=-\infty. $$
第三步：写出对偶问题
$$ \begin{aligned} \max_{\lambda,\nu}\quad & g(\lambda,\nu) \ \text{s.t.}\quad & \lambda\ge 0. \end{aligned} $$
第四步：求解对偶问题
求出最优乘子：
$$ \lambda^\star,\nu^\star. $$
第五步：恢复原变量
利用驻点条件：
$$ \nabla_x L(x^\star,\lambda^\star,\nu^\star)=0 $$
恢复 $x^\star$。
第六步：验证 KKT 条件
检查：
$$ f_i(x^\star)\le 0, $$
$$ h_j(x^\star)=0, $$
$$ \lambda_i^\star\ge 0, $$
$$ \lambda_i^\star f_i(x^\star)=0, $$
$$ \nabla_x L(x^\star,\lambda^\star,\nu^\star)=0. $$
如果是凸问题且强对偶成立，则这些条件足以证明最优性。
11. 例 1：等式约束的拉格朗日乘子法
求解：
$$ \begin{aligned} \min_{x,y}\quad & x^2+y^2 \ \text{s.t.}\quad & x+y=1. \end{aligned} $$
构造拉格朗日函数：
$$ L(x,y,\nu)=x^2+y^2+\nu(x+y-1). $$
驻点条件：
$$ \frac{\partial L}{\partial x}=2x+\nu=0, $$
$$ \frac{\partial L}{\partial y}=2y+\nu=0, $$
$$ \frac{\partial L}{\partial \nu}=x+y-1=0. $$
由前两个式子：
$$ x=y. $$
再由约束：
$$ x+y=1, $$
得到：
$$ x^\star=y^\star=\frac12. $$
最优值为：
$$ p^\star=\left(\frac12\right)^2+\left(\frac12\right)^2=\frac12. $$
12. 例 2：不等式约束与 KKT 条件
求解：
$$ \begin{aligned} \min_x\quad & x^2 \ \text{s.t.}\quad & x\ge 1. \end{aligned} $$
先把约束写成标准形式：
$$ 1-x\le 0. $$
拉格朗日函数为：
$$ L(x,\lambda)=x^2+\lambda(1-x), $$
其中：
$$ \lambda\ge 0. $$
KKT 条件为：
原始可行性：
$$ 1-x^\star\le 0. $$
对偶可行性：
$$ \lambda^\star\ge 0. $$
互补松弛：
$$ \lambda^\star(1-x^\star)=0. $$
驻点条件：
$$ \frac{dL}{dx}=2x^\star-\lambda^\star=0. $$
由驻点条件：
$$ \lambda^\star=2x^\star. $$
由于约束 $x^\star\ge 1$，所以 $x^\star>0$，因此：
$$ \lambda^\star>0. $$
根据互补松弛条件，若 $\lambda^\star>0$，则：
$$ 1-x^\star=0. $$
所以：
$$ x^\star=1. $$
于是：
$$ \lambda^\star=2. $$
最优值为：
$$ p^\star=1. $$
13. 例 3：通过对偶函数求解
考虑问题：
$$ \begin{aligned} \min_x\quad & x^2 \ \text{s.t.}\quad & x\ge 1. \end{aligned} $$
仍将约束写成：
$$ 1-x\le 0. $$
拉格朗日函数为：
$$ L(x,\lambda)=x^2+\lambda(1-x), $$
其中 $\lambda\ge 0$。
对偶函数为：
$$ g(\lambda)=\inf_x \left[x^2+\lambda(1-x)\right]. $$
展开：
$$ L(x,\lambda)=x^2-\lambda x+\lambda. $$
对 $x$ 求最小：
$$ \frac{dL}{dx}=2x-\lambda=0. $$
所以：
$$ x=\frac{\lambda}{2}. $$
代回拉格朗日函数：
$$ g(\lambda) =\left(\frac{\lambda}{2}\right)^2 -\lambda\left(\frac{\lambda}{2}\right) +\lambda. $$
即：
$$ g(\lambda)=\lambda-\frac{\lambda^2}{4}. $$
对偶问题为：
$$ \begin{aligned} \max_\lambda\quad & \lambda-\frac{\lambda^2}{4}\ \text{s.t.}\quad & \lambda\ge 0. \end{aligned} $$
求导：
$$ \frac{d}{d\lambda} \left( \lambda-\frac{\lambda^2}{4} \right) =1-\frac{\lambda}{2}. $$
令其为零：
$$ 1-\frac{\lambda}{2}=0. $$
得到：
$$ \lambda^\star=2. $$
对偶最优值：
$$ d^\star =g(2) =2-\frac{4}{4} =1. $$
原问题最优值也是：
$$ p^\star=1. $$
所以：
$$ p^\star=d^\star. $$
强对偶成立。
再由：
$$ x^\star=\frac{\lambda^\star}{2} $$
得到：
$$ x^\star=1. $$
14. 例 4：带等式约束的对偶函数
考虑二次优化问题：
$$ \begin{aligned} \min_x\quad & \frac12 x^TQx+c^Tx \ \text{s.t.}\quad & Ax=b, \end{aligned} $$
其中 $Q$ 是正定矩阵。
拉格朗日函数为：
$$ L(x,\nu) =\frac12 x^TQx+c^Tx+\nu^T(Ax-b). $$
整理：
$$ L(x,\nu) =\frac12 x^TQx+(c+A^T\nu)^Tx-\nu^Tb. $$
对 $x$ 求下确界。由于 $Q\succ 0$，该函数关于 $x$ 是严格凸的，最小点满足：
$$ \nabla_x L(x,\nu)=Qx+c+A^T\nu=0. $$
因此：
$$ x(\nu)=-Q^{-1}(c+A^T\nu). $$
代回拉格朗日函数，得到对偶函数：
$$ g(\nu) =-\frac12(c+A^T\nu)^TQ^{-1}(c+A^T\nu)-\nu^Tb. $$
对偶问题为：
$$ \max_\nu \left[ -\frac12(c+A^T\nu)^TQ^{-1}(c+A^T\nu)-\nu^Tb \right]. $$
如果原问题可行且满足适当条件，则可通过求解对偶问题得到 $\nu^\star$，再由：
$$ x^\star=-Q^{-1}(c+A^T\nu^\star) $$
恢复原变量。
15. 活跃约束的理解
对于不等式约束：
$$ f_i(x)\le 0, $$
在最优点 $x^\star$ 处：
- 如果 $f_i(x^\star)=0$，称该约束是活跃的。
- 如果 $f_i(x^\star)<0$，称该约束是非活跃的。
KKT 条件中的互补松弛：
$$ \lambda_i^\star f_i(x^\star)=0 $$
说明：
- 非活跃约束不会影响最优点的一阶平衡，因此其乘子为 $0$。
- 活跃约束可能影响最优点，因此其乘子可以大于 $0$。
几何上可以理解为：
在最优点，目标函数的下降方向被某些约束边界阻挡。只有真正阻挡目标函数继续下降的约束，才会出现在梯度平衡方程中。
16. KKT 条件的几何解释
驻点条件：
$$ \nabla f_0(x^\star) +\sum_{i=1}^m \lambda_i^\star \nabla f_i(x^\star) +\sum_{j=1}^p \nu_j^\star \nabla h_j(x^\star) =0 $$
可以改写为：
$$ \nabla f_0(x^\star)
-\sum_{i=1}^m \lambda_i^\star \nabla f_i(x^\star) -\sum_{j=1}^p \nu_j^\star \nabla h_j(x^\star). $$
这表示目标函数梯度可以由约束函数梯度线性表示。
直观解释是：
在最优点处，目标函数想要下降的方向已经被约束的法向方向抵消，因此不存在可行的局部下降方向。
对于不等式约束，只有活跃约束可能进入这个平衡关系，因为非活跃约束的乘子为 $0$。
17. 常见错误
17.1 不等式方向写错
KKT 和对偶构造通常要求不等式写成：
$$ f_i(x)\le 0. $$
如果原问题是：
$$ x\ge 1, $$
应改写为：
$$ 1-x\le 0. $$
不能直接写成 $x-1\ge 0$ 后仍然使用 $\lambda\ge 0$ 的标准形式。
17.2 忘记乘子符号限制
不等式约束乘子：
$$ \lambda_i\ge 0. $$
等式约束乘子：
$$ \nu_j\in \mathbb{R}. $$
17.3 把对偶函数的下确界限制在可行域上
对偶函数是：
$$ g(\lambda,\nu)=\inf_x L(x,\lambda,\nu). $$
这里的 $x$ 通常在原变量的整个定义域上取值，而不是只在原问题可行域上取值。
17.4 以为 KKT 条件总是充分条件
KKT 条件对一般非凸问题通常只是必要条件。
只有在凸优化并且强对偶成立等适当条件下，KKT 条件才是充分必要条件。
17.5 忽略无下界的情况
计算对偶函数时，有时对某些乘子，拉格朗日函数关于 $x$ 无下界。
这时：
$$ g(\lambda,\nu)=-\infty. $$
不能强行用驻点条件求出不存在的最小值。
18. 总结
拉格朗日乘子法的核心是把约束优化问题转化为拉格朗日函数的驻点问题。
对偶函数通过：
$$ g(\lambda,\nu)=\inf_x L(x,\lambda,\nu) $$
为原问题最优值提供下界。
对偶问题通过最大化这个下界：
$$ \max_{\lambda\ge 0,\nu} g(\lambda,\nu) $$
寻找最紧的下界。
KKT 条件由四部分组成：
$$ \begin{cases} f_i(x^\star)\le 0,\ h_j(x^\star)=0, & \text{原始可行性},\ \lambda_i^\star\ge 0, & \text{对偶可行性},\ \lambda_i^\star f_i(x^\star)=0, & \text{互补松弛},\ \nabla_x L(x^\star,\lambda^\star,\nu^\star)=0, & \text{驻点条件}. \end{cases} $$
对于凸优化问题，在强对偶成立时，KKT 条件是判断最优解的最重要工具。