库恩塔克条件(Kuhn-Tucker conditions)是非线性规划领域里最重要的理论成果之一，是确定某点为极值点的必要条件。如果所讨论的规划是凸规划，那么库恩-塔克条件也是充分条件。本文不对数学公式进行详细推导，而是从直观上对KKT条件进行理解。
一、带有不等式约束的模型
\[ \min f(X) \\
\text { s.t. } \quad g_i(X) \leq 0, \quad i=1, \ldots, m \Rightarrow \mathbf{m} \text { 个不等式约束 } \\
h_j(X)=0, \quad j=1, \ldots, n \Rightarrow \mathbf{n} \text { 个等式约束 }\]
二、库恩塔克条件
KKT条件(Karush–Kuhn–Tucker conditions)是最优化（特别是非线性规划）领域最重要的成果之一，是判断某点是极值点的必要条件。虽然该理论的数学公式看似复杂，但其实它的数学思想极其简单。
对应地，定义的拉格朗日函数为：
\[L\left(X,\left\{\lambda_i\right\},\left\{\mu_j\right\}\right)=f(X)+\sum_{i=1}^m \lambda_i g_i(X)+\sum_{j=1}^n \mu_j h_j(Y)
\]
其中，\({λ_i}\)指的是一系列的λ（有\(m\)个），同理{\(μ_j\)}也是。
该最优化问题的KKT条件为：
\[ \nabla f\left(X^*\right)+\sum_{i=1}^m \lambda_i \nabla g_i\left(X^*\right)+\sum_{j=1}^n \mu_j \nabla h_j(X)=0 \quad (1) \\
\lambda_i g_i\left(X^*\right)=0, \quad i=1, \ldots, m \quad (2)\\
h_j\left(X^*\right)=0,\quad j=1, \ldots, n \quad (3)\\
\lambda_i \geq 0, \quad i=1, \ldots, m \quad (4)\\
g_i\left(X^*\right) \leq 0, \quad i=1, \ldots, m \quad (5)
\]
解题思路与之前叙述类似，就是用几个等式计算最优值，用不等式验证这些值，不满足则排除。即，利用式(1)(2)(3)求最优\(X^*\)和\(λ_i\)，然后通过式(4)和(5)验证这些解是否可行，“可行”指的是这些解是否能让(4)和(5)的不等号成立，不成立则排除。注意，\(μ_j\)是可以取任意值的，不受限制，因为它们是等式约束的乘子，不是不等式约束的乘子。
2.1 仅含有一个不等式约束
| min |
max |
| $min f(X) \quad g(X) \leq 0 $ |
$max f(X) \quad g(X) \geq 0 $ |
\[\begin{aligned}
& \
& \min f(X) \\
& \max f(X) \\
& \text { 仅含有一个 } \\
& \text { s.t. } g(X) \leq 0 \quad \text { 和 } \\
& \text { s.t. } \quad g(X) \geq 6 \\
& -\nabla f\left(X^*\right)=\lambda \nabla g\left(X^*\right) \Rightarrow \nabla f\left(X^*\right)+\lambda \nabla g\left(X^*\right)=0 \\
& \nabla f\left(X^*\right)=\lambda \nabla g\left(X^*\right) \Rightarrow \nabla f\left(X^*\right)-\lambda \nabla g\left(X^*\right)=0 \\
& \nabla f\left(X^*\right)+\lambda \nabla g\left(X^*\right)=0 \text {, 且 } \lambda<0 \\
& -\nabla f\left(X^*\right)=\lambda_1 \nabla g_1\left(X^*\right)+\lambda_2 \nabla g_2\left(X^*\right) \\
& \nabla f\left(X^*\right)+\lambda_1 \nabla g_1\left(X^*\right)+\lambda_2 \nabla g_2\left(X^*\right)=0 \\
&
\end{aligned}
\]
\(\Downarrow\)
\[\nabla f\left(X^*\right)+\lambda_1 \nabla g_1\left(X^*\right)+\lambda_2 \nabla g_2\left(X^*\right)=f^{\prime}
\]
三、实例
考虑非线性规划问题:
\[\begin{aligned}
& \min f\left(x_1, x_2\right)=\left(x_1-1\right)^2+\left(x_2-2\right)^2 \\
& \text { s.t. }\left\{\begin{array}{c}
-x_1+x_2=1 \\
x_1+x_2 \leq 2 \\
x_1, x_2 \geq 0
\end{array}\right.
\end{aligned}
\]
利用Kuhn-Tucker条件求其全局最优解。
解: 构造 Lagrange 函数如下:
\[L(x, \lambda)=\left(x_1-1\right)^2+\left(x_2-2\right)^2+\lambda_1\left(-x_1+x_2-1\right)+\lambda_2\left(x_1+x_2-2\right)
\]
根据 \(K u h n-T u c\) ker 条件, 存在 \(x^*=\left(x_1^*, x_2^*\right)^T\) 和 \(\lambda_1^* \in R, \lambda_2^* \geq 0\), 使得
(1)
\[\begin{aligned}
& -x_1^*+x_2^*=1 \\
& x_1^*+x_2^* \leq 2
\end{aligned}
\]
(2) \(\lambda_2^*\left(x_1^*+x_2^*-2\right)=0\)
(3) \(\begin{aligned} \frac{\partial L}{\partial x_1} & =2\left(x_1^*-1\right)-\lambda_1^*+\lambda_2^*=0 \\ \frac{\partial L}{\partial x_2} & =2\left(x_2^*-2\right)+\lambda_1^*+\lambda_2^*=0\end{aligned}\)
设 \(x_1+x_2=2\), 根据条件 1\()\), 我们可求出 \(x_1^*=\frac{1}{2}, x_2^*=\frac{3}{2}\), 将它们代入 3\()\), 有:
\[\begin{aligned}
& 2\left(\frac{1}{2}-1\right)-\lambda_1^*+\lambda_2^*=0 \\
& 2\left(\frac{3}{2}-2\right)+\lambda_1^*+\lambda_2^*=0
\end{aligned}
\]
由此可得 \(\lambda_1^*=0, \lambda_2^*=1\), 由于点 \(x^*=\left(\frac{1}{2}, \frac{3}{2}\right)\) 满足条件 (1) - (3), 它. 是 Kuhn -Tucker 点. 容易验证, 目标函数 \(f(x)\) 是凸函数, 两个约束函数也都是凸函数 ( 纪 知, 点 \(x^*=\left(\frac{1}{2}, \frac{3}{2}\right)\) 是全局最优解, \(\bar{f}=\frac{1}{2}\) 是全局最小值。
KKT条件是判断某点是极值点的必要条件，不是充分条件。换句话说，最优解一定满足KKT条件，但KKT条件的解不一定是最优解。对于凸规划，KKT条件就是充要条件了，只要满足KKT条件，则一定是极值点，且得到的一定还是全局最优解。
参考文献
- KKT条件，原来如此简单 (上) | 理论部分