王树尧老师运筹学课程笔记 03 KKT定理

第3讲 KKT定理

KKT定理求解过程

1. 化为标准型，得到新的约束条件
   1. 把强约束条件（等号）化为弱约束条件$g=0\iff g\le 0且g\ge 0$
   2. 把$\ge$两边同乘$-1$，换成$\le$（也可以都换成$\ge$，但为了和Lag乘数法统一，推荐换成$\le$）
2. 有几个约束条件就引入几个广义Lag乘子${\lambda }_i^{\ast }$，并且要求${\lambda }_i^{\ast }\ge 0$，即所有乘子都非负
3. 构造一个Lag函数$F=f+{\sum }_i{\lambda }_i^{\ast }{g}_i$，其中$f$是目标函数，$g_i$是约束条件。
4. 对目标函数的自变量求偏导数，都令其等于0，并令广义Lag乘子$\ast$约束条件=0，即${\lambda }_i^{\ast }\ast g_i=0$。（Lag乘数法中是直接令约束条件=0）。
5. 然后解方程组（注意需要仔细讨论解的情况），得到若干组解。比较这些解的函数值，其对应的函数值中最大的就是最大值，最小的就是最小值。

（注意比较Lag乘数法和KKT定理求解过程的不同之处。）

注：KKT定理需要要求函数有连续的一阶偏导，但这个前提条件不需要刻意关心，一般都是可以满足的。

KKT定理的思考

当使用KKT定理求出一个解时，如果其对应的某个${\lambda }_i^{\ast }>0$，则由${\lambda }_i^{\ast }\ast g_i=0$可得$g_i=0$，即$g_i$退化为了强约束条件，说明该解对应的点恰好落在曲线$g_i=0$上。

Lag乘数法和KKT定理的局限性

Lag乘数法和KKT定理虽然是可以解决非线性规划问题的通用方法，但是其难点在于求解方程组中对解的讨论，解方程本身十分困难，对于有限的解讨论方程组的解可能十分繁琐，甚至可能会解出来无限多个解。

因此针对线性规划问题我们可以用一些更为特殊、更有针对性的方法进行求解。

总结

KKT定理是Lag乘数法的一种推广，其求解过程在形式上与Lag乘数法是非常相似的。需要特别注意的是KKT定理中的广义Lag乘子必须要$\ge 0$。