最优化问题的KKT条件简要解释

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$：