学习笔记|线性规划的标准化提到了用拉格朗日乘子法求解标准形式的线性规划，实际上拉格朗日乘子法更适用于求解非线性优化问题，而对于线性规划的求解，更加适合用单纯形法求解，不再继续展开。本篇主要讨论传说中的KKT条件与拉格朗日乘子法。

KKT条件是Karush[1939]，以及Kuhn和Tucker[1951]先后独立发表出來的，是确定某点为极值点的必要条件。在引入KKT条件前，让我们先回到拉格朗日乘子法。

1. 拉格朗日乘子法的图形解析

为了便于图形展示，我们以二维优化问题为例。

假设优化目标为

约束条件为

在xy直角坐标系中画出f(x,y)的等高线（如下图所示，来源于参考文献1），并且假设；图中的封闭曲线为g(x,y)=0。

从图上可以看到，优化问题的解是点。

在原优化问题中引入拉格朗日乘子λ，构造拉格朗日函数

通过偏导数法列出求解条件如下

即

结合图形和上述条件可以看到，拉格朗日乘子法实际上是找出f(x,y)与g(x,y)相切且满足g(x,y)=0的点。它的解是三个点。事实上，上面的方程组也可以看成等式约束下最优化问题的KKT条件。

2. KKT条件

假设最优化问题如下：

则KKT条件如下：

其中，i=1,2,...,m为拉格朗日乘子，，j=1,2,...,l为KKT乘子（也有文献将其称为松弛变量，不过容易跟优化问题标准化的松弛变量相混淆）。

可以看到，在单一等式约束下KKT条件与上一节的方程组是一致的。

3. KKT条件推导

3.1. 原可行性与拉格朗日平稳性的推导

首先引入松弛变量（引入方法可参见学习笔记|线性规划的标准化），将原优化问题转化为

这里假设。

令，则优化问题进一步转化为

引入拉格朗日乘子可构建拉格朗日函数

偏导数法可得取到极值的必要条件为

即

因为，所以。原可行性与拉格朗日平稳性推导完毕。

3.2. 互补松弛条件的推导

因为当且仅当时，。因此，等价于。

因此，上面的方程组可以进一步改写成：

即互补松弛条件成立。

3.3. 对偶可行性的推导

对偶可行性，即，必有。

3.3.1. 单一不等式约束下对偶可行性的推导

单一不等式约束优化可表述为：

（图片来源于参考文献6）

则拉格朗日平稳性为

即

如果μ<0，由于不等式约束的可行域为，所以g(x)的梯度指向可行域外，f(x)的梯度同样指向可行域外，当x向可行域内移动时，f(x)的值减小，说明当前的(x,f(x))不是极小值点，与优化目标矛盾，所以μ≥0。

3.3.2. 对偶可行性的推导

先看两个不等式约束优化问题，它可表述如下：

拉格朗日平稳性为

我们先来推导。

当时，有效不等式约束只有一个，与f(x)取极小值矛盾。

当时，假设，且下图是极小值点，f(x)的梯度下降方向如图中标有的红色箭头所示，平面k是与f(x)梯度垂直的平面，则，有，与是极小值点矛盾。

当时，以类似的图形解析同样可以证伪，此处不再展开。

完整优化问题下，拉格朗日平稳性为

由于向量乘以常数仍为向量、向量的和仍为向量，可以将其转化为两约束来考虑，同样不再赘述。

需要指出的是此处对，j=1,2,...,l的证明并不非常严谨。我们也可以引入广义拉格朗日函数，从另一个视角来看待KKT条件中的对偶可行性条件。

参考文献

1.https://baike.baidu.com/item/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0%E6%B3%95/8550443?fromtitle=%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E5%AD%90%E6%B3%95&fromid=1946079&fr=aladdin
2.https://baijiahao.baidu.com/s?id=1618344063706450694&wfr=spider&for=pc
3.https://blog.csdn.net/qq_36607894/article/details/89917997
4.https://zhuanlan.zhihu.com/p/26514613
5.https://blog.csdn.net/qq_36607894/article/details/89917997
6.https://blog.csdn.net/qq_36607894/article/details/89922839
7.https://www.cnblogs.com/xinchen1111/p/8804858.html

相关链接：

1. 学习笔记|线性规划的标准化
2. 学习笔记|对偶理论入门
3. 学习笔记|拉格朗日乘子法
4. 学习笔记|最大熵模型的理解
5. 学习笔记|最大熵模型