最优化问题的KKT条件简要解释
14,029 阅读
KKT条件（Karush–Kuhn–Tucker conditions）是求解带不等式约束的最优化问题中非常重要的一个概念和方法。这篇博客将解释相关概念和操作。
一、带等式约束的优化问题
带等式约束的优化问题是指我们有个求最大值或者最小值的目标函数，同时，针对该目标函数我们还有一些约束条件，这些约束条件是等式。该问题的形式化描述如下：
\min f(x_1,\cdots,x_n)
加载中...
加载中...
s.t. \begin{cases}
g_i(x_1,\cdots,x_n) &=0, \space\space i=1,2,\cdots, k \\
x_1,\cdots,x_n &\geq 0
\end{cases}
求解上述问题一般有两种方法，一种是消元法，就是把这些等式联立，然后求解即可。也就是多元一次方程组的求解了。之类不多说了。另一种方法是拉格朗日乘数法，这是高等数学里面提供的一种方法。这是一种寻找多元函数在其变量受到一个或者多个条件的约束的时候，求极值的方法。该方法将一个有$n$个变量和$k$个等式约束条件的最优化问题，转换成一个有$n+k$个变量的方程组求解问题。该方法会引入一组未知数，这些未知数称为拉格朗日乘子（或者算子、乘数等）。对上式进行拉格朗日乘数法转换得到一个新的函数：
\mathcal{L}(x_1,\cdots,x_n,\lambda_1,\cdots,\lambda_k)=f(x_1,\cdots,x_n) - \sum_{i=1}^k\lambda_ig_i(x_1,\cdots,x_n)
这个时候对上述转换后的方程求解其极值点会包含原问题所有的极值点，但是不保证每个极值点都是原问题的极值点。这个理论上有证明这里忽略了。因此，当转换后的公式只包含一个极值点的时候，我们可以对上市求偏导后联立方程，得到的结果就是原来结果的极值点。上式中的未知数包含了所有的$x$和$\lambda$：
\begin{cases}
\frac{\partial \mathcal L}{\partial x_1} = 0 \\
\cdots \\
\frac{\partial \mathcal L}{\partial x_n} = 0 \\ \\
\frac{\partial \mathcal L}{\partial \lambda_1} = 0 \\
\cdots \\
\frac{\partial \mathcal L}{\partial \lambda_k} = 0
\end{cases}
拉格朗日乘数法有很强的几何意义，也可以用来解释为何这样做可以求出最终结果。可参考拉格朗日乘子法如何理解。
与拉格朗日乘法类似，如果最优化问题的约束是不等式，那么我们可以使用KKT条件来求解。KKT条件就是拉格朗日乘数法在带不等式约束优化问题上的推广。
假设我们有如下的最优化问题：
\min f(x_1,\cdots,x_n)
s.t. \begin{cases}
g_i(x_1,\cdots,x_n) &=0, \space\space i=1,2,\cdots, k \\
h_i(x_1,\cdots,x_n) & \leq 0, \space\space i=1,2,\cdots, l \\
x_1,\cdots,x_n &\geq 0
\end{cases}
那么该问题的拉格朗日函数为：
\begin{aligned}
\mathcal{L}(x_1,\cdots,x_n,\lambda_1,\cdots,\lambda_k,\mu_1,\cdots,\mu_l) & = f(x_1,\cdots,x_n) - \sum_{i=1}^k\lambda_ig_i(x_1,\cdots,x_n) - \sum_{i=1}^l\mu_ih_i(x_1,\cdots,x_n)
\end{aligned}
KKT条件是指一组条件，它是一组解成为原问题最优解的必要条件。如果原问题是凸问题，那么这个条件也是充分条件。K.K.T.条件包括平稳条件、互补松弛条件、对偶可行性条件、原问题可行性条件等几类。上述问题的KKT条件如下：
K.K.T. \begin{cases}
\frac{\partial \mathcal L}{\partial x} &= 0,\space\space\space\text{for all i}\space\space\space (\text{Stationarity}) \\
\mu_i \cdot h_i(x) &= 0, \space\space\space\text{for all i}\space\space\space(\text{Complementary Slackness}) \\
\lambda_i,\mu_i &\geq 0,\space\space\space\text{for all i}\space\space\space (\text{Dual Feasibility}) \\
g_i(x) &= 0,\space\space\space\text{for all i}\space\space\space (\text{Primal Feasibility})
\end{cases}
上述KKT条件的必要性和充分性的证明可参考凸优化-KKT条件。