KKT条件（Karush-Kuhn-Tucker条件）是约束优化理论中最重要的最优性条件之一。它提供了在约束条件下判断局部最优解的必要条件，是拉格朗日乘数法的推广。本文将从几何直观出发，深入讲解KKT条件的理论基础、几何意义和实际应用。
一、KKT条件的背景
1.1 从拉格朗日乘数法到KKT条件
在无约束优化问题中，我们通过梯度为零来寻找最优解：
\(\nabla f(x^*) = 0\)
对于等式约束问题：
\(\begin{align}
\min \quad & f(x) \\
\text{s.t.} \quad & h_i(x) = 0, \quad i = 1, \ldots, m
\end{align}\)
拉格朗日乘数法告诉我们，在最优解处存在乘子 $\lambda_i$ 使得：
\(\nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla h_i(x^*) = 0\)
KKT条件将这一思想推广到包含不等式约束的一般约束优化问题。
1.2 约束优化问题的标准形式
考虑一般约束优化问题：
\(\begin{align}
\min \quad & f(x) \\
\text{s.t.} \quad & g_i(x) \leq 0, \quad i = 1, \ldots, p \\
& h_j(x) = 0, \quad j = 1, \ldots, q
\end{align}\)
其中：
$f: \mathbb{R}^n \to \mathbb{R}$ 是目标函数
$g_i: \mathbb{R}^n \to \mathbb{R}$ 是不等式约束函数
$h_j: \mathbb{R}^n \to \mathbb{R}$ 是等式约束函数
二、KKT条件的数学表述
2.1 KKT条件的内容
设 \(x^*\) 是约束优化问题的局部最优解，且满足线性无关约束条件（LICQ），则存在拉格朗日乘子 \(\lambda_i^* \geq 0\) 和 \(\nu_j^*\) 使得：
1. 平稳性条件（Stationarity）(驻点条件)：
\(\nabla f(x^*) + \sum_{i=1}^p \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^q \nu_j^* \nabla h_j(x^*) = 0\)
👉 目标函数的梯度，被约束的“拉力”平衡住了。
2. 原始可行性（Primal Feasibility）：
\(g_i(x^*) \leq 0, \quad i = 1, \ldots, p\)
\(h_j(x^*) = 0, \quad j = 1, \ldots, q\)
👉 解必须在可行域内。
3. 对偶可行性（Dual Feasibility）：
\(\lambda_i^* \geq 0, \quad i = 1, \ldots, p\)
👉 不等式约束的“罚力度”不能为负。
4. 互补松弛性（Complementary Slackness）：
\(\lambda_i^* g_i(x^*) = 0, \quad i = 1, \ldots, p\)
👉 如果约束没“卡住”（$g_i(x^)<0$），它的乘子$\lambda$必须=0； 如果约束正好“贴住”（$g_i(x^)=0$），它的乘子$\lambda$可以> 0。
直观理解就是：
👉 最优点的梯度被一部分约束”抵消”，最终解要么在内部（无约束情况），要么在边界（激活约束起作用.
三、KKT条件的几何意义
3.1 几何直观
图1：KKT条件单约束情况
图2：KKT条件多约束情况
KKT条件的几何意义可以通过以下方式理解：
在最优解处，目标函数的梯度可以表示为约束函数梯度的非负线性组合。
具体来说：
对于起作用的不等式约束（激活约束）（\(g_i(x^*) = 0\)），其梯度 \(\nabla g_i(x^*)\) 指向可行域外部
对于不起作用的不等式约束（非激活约束）（\(g_i(x^*) < 0\)），对应的乘子 \(\lambda_i^* = 0\)
对于等式约束（始终是激活的），梯度 \(\nabla h_j(x^*)\) 垂直于约束曲面
3.2 几何解释的数学表述
设 \(\mathcal{A}(x^*) = \{i : g_i(x^*) = 0\}\) 为在 \(x^*\) 处起作用的约束集合，则KKT条件可以写成：
\[\nabla f(x^*) + \sum_{i \in \mathcal{A}(x^*)} \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^q \nu_j^* \nabla h_j(x^*) = 0\]
其中 $\lambda_i^* \geq 0$ 对所有 $i \in \mathcal{A}(x^*)$。
四、约束条件（”正则点”）
4.1 线性无关约束条件（LICQ）
定义：在点 $x^*$ 处，所有起作用约束的梯度线性无关，即：线性无关。
\(\{\nabla g_i(x^*) : i \in \mathcal{A}(x^*)\} \cup \{\nabla h_j(x^*) : j = 1, \ldots, q\}\)
重要性：LICQ是KKT条件成立的必要条件。如果不满足LICQ，KKT条件可能不成立。
4.2 其他约束条件
除了LICQ，还有其他约束条件可以保证KKT条件的成立：
Mangasarian-Fromovitz条件（MFCQ）：比起LICQ稍微弱一些，要求等式约束梯度线性无关，并且在一个方向能“离开”激活约束。
线性独立约束条件（LICQ） ：在点$x*$所有激活的不等式约束的梯度 \(\nabla g_i(x^*)\) 和等式约束的梯度$\nabla h_j(x^*)$必须线性无关。
Slater条件（对于凸优化问题） ：如果问题是凸的，只要存在一个严格可行点（即$g_i(x) < 0 且h_j(x) = 0$）,则满足正则条件。
五、KKT条件的应用实例
例1：简单的二次规划问题
问题：
\(\begin{align}
\min \quad & f(x_1, x_2) = x_1^2 + x_2^2 \\
\text{s.t.} \quad & g_1(x_1, x_2) = x_1 + x_2 - 1 \leq 0 \\
& g_2(x_1, x_2) = -x_1 \leq 0 \\
& g_3(x_1, x_2) = -x_2 \leq 0
\end{align}\)
解：
步骤1：构造拉格朗日函数
\(L(x_1, x_2, \lambda_1, \lambda_2, \lambda_3) = x_1^2 + x_2^2 + \lambda_1(x_1 + x_2 - 1) - \lambda_2 x_1 - \lambda_3 x_2\)
步骤2：写出KKT条件
\(\begin{cases}
\frac{\partial L}{\partial x_1} = 2x_1 + \lambda_1 - \lambda_2 = 0 \\
\frac{\partial L}{\partial x_2} = 2x_2 + \lambda_1 - \lambda_3 = 0 \\
x_1 + x_2 - 1 \leq 0, \quad -x_1 \leq 0, \quad -x_2 \leq 0 \\
\lambda_1 \geq 0, \quad \lambda_2 \geq 0, \quad \lambda_3 \geq 0 \\
\lambda_1(x_1 + x_2 - 1) = 0, \quad \lambda_2 x_1 = 0, \quad \lambda_3 x_2 = 0
\end{cases}\)
步骤3：分析约束的起作用情况
由于目标函数是 $x_1^2 + x_2^2$，最优解应该在可行域内距离原点最近的点。
情况1：如果 $x_1 > 0, x_2 > 0$，则 $\lambda_2 = \lambda_3 = 0$
如果 $x_1 + x_2 < 1$，则 $\lambda_1 = 0$，得到 $x_1 = x_2 = 0$，但这不满足 $x_1 > 0, x_2 > 0$
如果 $x_1 + x_2 = 1$，则 $\lambda_1 > 0$，得到 $x_1 = x_2 = \frac{1}{2}$
情况2：如果 $x_1 = 0, x_2 > 0$，则 $\lambda_2 \geq 0, \lambda_3 = 0$
如果 $x_2 < 1$，则 $\lambda_1 = 0$，得到 $x_2 = 0$，矛盾
如果 $x_2 = 1$，则 $\lambda_1 > 0$，得到 $x_1 = 0, x_2 = 1$
情况3：如果 $x_1 > 0, x_2 = 0$，类似分析得到 $x_1 = 1, x_2 = 0$
情况4：如果 $x_1 = 0, x_2 = 0$，则 $\lambda_2 \geq 0, \lambda_3 \geq 0$
步骤4：比较目标函数值
$f(0, 0) = 0$
$f(\frac{1}{2}, \frac{1}{2}) = \frac{1}{2}$
$f(0, 1) = 1$
$f(1, 0) = 1$
结论：最优解为 $x^* = (0, 0)$，对应的乘子为 $\lambda_1^* = 0, \lambda_2^* = 0, \lambda_3^* = 0$。
例2：带等式约束的问题
问题：
\(\begin{align}
\min \quad & f(x_1, x_2) = x_1^2 + x_2^2 \\
\text{s.t.} \quad & h(x_1, x_2) = x_1 + x_2 - 1 = 0
\end{align}\)
解：
步骤1：构造拉格朗日函数
\(L(x_1, x_2, \nu) = x_1^2 + x_2^2 + \nu(x_1 + x_2 - 1)\)
步骤2：写出KKT条件
\(\begin{cases}
\frac{\partial L}{\partial x_1} = 2x_1 + \nu = 0 \\
\frac{\partial L}{\partial x_2} = 2x_2 + \nu = 0 \\
x_1 + x_2 - 1 = 0
\end{cases}\)
步骤3：求解
从前两个方程得：$x_1 = x_2 = -\frac{\nu}{2}$
代入第三个方程：$-\frac{\nu}{2} - \frac{\nu}{2} = 1$，得 $\nu = -1$
因此：$x_1 = x_2 = \frac{1}{2}$
结论：最优解为 $x^* = (\frac{1}{2}, \frac{1}{2})$，对应的乘子为 $\nu^* = -1$。
例3：复杂的约束优化问题
问题：
\(\begin{align}
\min \quad & f(x_1, x_2) = x_1^2 + 2x_2^2 - 4x_1 - 4x_2 \\
\text{s.t.} \quad & g_1(x_1, x_2) = x_1 + x_2 - 3 \leq 0 \\
& g_2(x_1, x_2) = -x_1 - 2x_2 + 5 \leq 0
\end{align}\)
解：
步骤1：构造拉格朗日函数
\(L(x_1, x_2, \lambda_1, \lambda_2) = x_1^2 + 2x_2^2 - 4x_1 - 4x_2 + \lambda_1(x_1 + x_2 - 3) + \lambda_2(-x_1 - 2x_2 + 5)\)
步骤2：写出KKT条件
\(\begin{cases}
\frac{\partial L}{\partial x_1} = 2x_1 - 4 + \lambda_1 - \lambda_2 = 0 \\
\frac{\partial L}{\partial x_2} = 4x_2 - 4 + \lambda_1 - 2\lambda_2 = 0 \\
x_1 + x_2 - 3 \leq 0, \quad -x_1 - 2x_2 + 5 \leq 0 \\
\lambda_1 \geq 0, \quad \lambda_2 \geq 0 \\
\lambda_1(x_1 + x_2 - 3) = 0, \quad \lambda_2(-x_1 - 2x_2 + 5) = 0
\end{cases}\)
步骤3：分情况讨论
情况1：$\lambda_1 = 0, \lambda_2 = 0$
从KKT条件得：$x_1 = 2, x_2 = 1$
检查约束：$g_1(2,1) = 0 \leq 0$，$g_2(2,1) = 1 > 0$
结论：不满足约束，舍去
情况2：$\lambda_1 = 0, \lambda_2 > 0$
从互补松弛性：$-x_1 - 2x_2 + 5 = 0$，即 $x_1 + 2x_2 = 5$
从KKT条件：$2x_1 - 4 - \lambda_2 = 0$，$4x_2 - 4 - 2\lambda_2 = 0$
解得：$x_1 = \frac{7}{3}, x_2 = \frac{4}{3}, \lambda_2 = \frac{2}{3}$
检查约束：$g_1(\frac{7}{3}, \frac{4}{3}) = \frac{2}{3} > 0$
结论：不满足约束，舍去
情况3：$\lambda_1 > 0, \lambda_2 = 0$
从互补松弛性：$x_1 + x_2 - 3 = 0$，即 $x_1 + x_2 = 3$
从KKT条件：$2x_1 - 4 + \lambda_1 = 0$，$4x_2 - 4 + \lambda_1 = 0$
解得：$x_1 = 2, x_2 = 1, \lambda_1 = 0$
结论：与假设 $\lambda_1 > 0$ 矛盾，舍去
情况4：$\lambda_1 > 0, \lambda_2 > 0$
从互补松弛性：$x_1 + x_2 = 3$ 且 $x_1 + 2x_2 = 5$
解得：$x_1 = 1, x_2 = 2$
从KKT条件：$\lambda_1 = 8, \lambda_2 = 6$
检查约束：$g_1(1,2) = 0 \leq 0$，$g_2(1,2) = 0 \leq 0$
结论：满足所有条件
步骤4：计算目标函数值
\(f(1,2) = 1^2 + 2(2)^2 - 4(1) - 4(2) = 1 + 8 - 4 - 8 = -3\)
结论：最优解为 x^* = (1, 2)，对应的乘子为 λ₁* = 8, λ₂* = 6，最优值为 f* = -3。
六、二阶最优性条件
6.1 二阶必要条件
设 $x^*$ 是约束优化问题的局部最优解，且满足KKT条件，则对于所有满足以下条件的 $d \neq 0$：
\(\nabla g_i(x^*)^T d = 0\) 对所有 \(i \in \mathcal{A}(x^*)\)（起作用的不等式约束）
\(\nabla h_j(x^*)^T d = 0\) 对所有 \(j = 1, \ldots, q\)（等式约束）
有：
\(d^T \nabla^2 L(x^*, \lambda^*, \nu^*) d \geq 0\)
其中 \(\nabla^2 L(x^*, \lambda^*, \nu^*)\) 是拉格朗日函数关于 \(x\) 的Hessian矩阵。
6.2 二阶充分条件
设 $x^*$ 满足KKT条件，且对于所有满足上述条件的 $d \neq 0$，有：
\(d^T \nabla^2 L(x^*, \lambda^*, \nu^*) d > 0\)
则 $x^*$ 是严格局部最优解。
6.3 正则点
定义：设 $x^$ 是约束优化问题的可行点，如果所有起作用约束的梯度线性无关，则称 $x^$ 为正则点。
重要性：正则点是KKT条件成立的重要前提条件。
6.4 二阶条件应用实例
问题：考虑优化问题
\(\begin{align}
\min \quad & f(x_1, x_2) = x_1 \\
\text{s.t.} \quad & g(x_1, x_2) = 3(x_1-3)^2 + x_2 \geq 0 \\
& h(x_1, x_2) = (x_1-3)^2 + x_2^2 - 10 = 0
\end{align}\)
判断点 $x^{(1)} = (2, -3)^T$ 是否为局部最优解。
解：
步骤1：构造拉格朗日函数
\(L(x_1, x_2, \lambda, \mu) = x_1 - \lambda[3(x_1-3)^2 + x_2] - \mu[(x_1-3)^2 + x_2^2 - 10]\)
步骤2：计算梯度
\(\nabla f(x) = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad \nabla g(x) = \begin{pmatrix} 6(x_1-3) \\ 1 \end{pmatrix}, \quad \nabla h(x) = \begin{pmatrix} 2(x_1-3) \\ 2x_2 \end{pmatrix}\)
步骤3：在点 $x^{(1)} = (2, -3)^T$ 处计算梯度
\(\nabla f(2, -3) = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad \nabla g(2, -3) = \begin{pmatrix} -6 \\ 1 \end{pmatrix}, \quad \nabla h(2, -3) = \begin{pmatrix} -2 \\ -6 \end{pmatrix}\)
步骤4：检查KKT条件
\(\nabla f(2, -3) - \lambda \nabla g(2, -3) - \mu \nabla h(2, -3) = \begin{pmatrix} 1 \\ 0 \end{pmatrix} - \lambda \begin{pmatrix} -6 \\ 1 \end{pmatrix} - \mu \begin{pmatrix} -2 \\ -6 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}\)
得到方程组：
\(\begin{cases} 1 + 6\lambda + 2\mu = 0 \\ -\lambda + 6\mu = 0 \end{cases}\)
解得：$\lambda = -\frac{3}{19} < 0$，$\mu = -\frac{1}{38}$
步骤5：判断KKT条件
由于 $\lambda < 0$ 违反了KKT条件中的对偶可行性条件（$\lambda \geq 0$），因此 $x^{(1)} = (2, -3)^T$ 不满足KKT条件。
结论：$x^{(1)} = (2, -3)^T$ 不是局部最优解。
七、KKT条件的特殊情况
7.1 只有不等式约束
当 $q = 0$（无等式约束）时，KKT条件简化为：
\(\begin{cases}
\nabla f(x^*) + \sum_{i=1}^p \lambda_i^* \nabla g_i(x^*) = 0 \\
g_i(x^*) \leq 0, \quad i = 1, \ldots, p \\
\lambda_i^* \geq 0, \quad i = 1, \ldots, p \\
\lambda_i^* g_i(x^*) = 0, \quad i = 1, \ldots, p
\end{cases}\)
7.2 只有等式约束
当 $p = 0$（无不等式约束）时，KKT条件简化为拉格朗日乘数法：
\(\begin{cases}
\nabla f(x^*) + \sum_{j=1}^q \nu_j^* \nabla h_j(x^*) = 0 \\
h_j(x^*) = 0, \quad j = 1, \ldots, q
\end{cases}\)
7.3 凸优化问题
对于凸优化问题，KKT条件不仅是必要条件，也是充分条件。如果目标函数和约束函数都是凸函数，则满足KKT条件的点就是全局最优解。
八、KKT条件的计算步骤
8.1 一般计算流程
构造拉格朗日函数
写出KKT条件
分析约束的起作用情况
求解方程组
验证解的可行性
8.2 注意事项
约束条件：确保LICQ等约束条件得到满足
乘子符号：不等式约束的乘子必须非负
互补松弛性：不起作用的约束对应的乘子为零
唯一性：KKT条件提供的是必要条件，不是充分条件
九、KKT条件的实际应用
9.1 支持向量机
在支持向量机中，KKT条件用于：
确定支持向量
计算最优分离超平面
理解软间隔分类器
相关文章:
《最优化理论基础》
《最优化理论基础例题集》
《惩罚函数法》
《内点法》
Previous
最优化理论——基础_例题集
Next
最优化方法——最速下降法与共轭梯度法