浅谈最优化问题的KKT条件_ZNDS问答

xscjf2005

最近学习了最优化理论，正好学到了机器学习中支持向量机（Support Vector Machine）和最大熵模型（Maximum Entropy Model）中用到的KKT条件（Karush–Kuhn–Tucker conditions）.
之前看了一些相关书籍，发现KKT条件的证明不是有些简略，就是太偏“数学”（对于非数学专业的学生可能看不懂）——不适合非数学专业的同学入门. 因此我通过总结教材、上课笔记和加入一些帮助理解的重要注记（个人认为不“显然”的内容），写下这篇文章，供大家学习和交流！
PS：资深的排版有些乱，望看官们不要介意：）
目录：

0.什么是KKT条件
1.等式约束优化问题（Lagrange乘数法）
2.不等式约束优化问题
3.总结

0.什么是KKT条件

本文从本科高数（微积分）中的有条件极值的Lagrange乘数法入手，一步步推导到KKT条件. 但在讲述推导过程之前，我想先给出KKT条件：
对于具有等式和不等式约束的一般优化问题

KKT条件给出了判断是否为最优解的必要条件，即：

1. 等式约束优化问题（Lagrange乘数法）

对于这部分内容，其实本科高数课程中已学过，因此本文直接给出结论，并补充一些我的理解与总结，它能帮助理解不等式约束中的一些内容，具体的推导过程在同济7版的高数下册（P.116-118）中已写的较详细。
所谓的等式约束优化问题是指
                                                                                                             $minf(x_{1} ,x_{2} ,...,x_{n} )$
$s.t.h_{k} (x_{1} ,x_{2} ,...,x_{n} )=0$
我们令 $L({\bf{x}},{\bf{\lambda }}) = f({\bf{x}}) + \sum\limits_{k = 1}^l {{\lambda _k}{h_k}({\bf{x}})}$ ，函数 $L(x,y)$ 称为Lagrange函数，参数 $\lambda$ 称为Lagrange乘子.

再联立方程组： $\left\{ \begin{array}{l} \frac{{\partial L}}{{\partial {x_i}}} = 0{\rm{ ( }}i{\rm{ = 1 ,2 ,}} \cdots {\rm{,}}n{\rm{ ) }}\\ \frac{{\partial L}}{{\partial {\lambda _k}}} = 0{\rm{ ( }}k{\rm{ = 1 ,2 ,}} \cdots {\rm{,}}l{\rm{ ) }} \end{array} \right.$ ，

得到的解为可能极值点，由于我们用的是必要条件，具体是否为极值点需根据问题本身的具体情况检验. 这个方程组称为等式约束的极值必要条件.
上式我们对 $n$ 个和个分别求偏导，回想一下在无约束优化问题 $f(x_{1}, x_{2},...,x_{n} )=0$ 中，我们根据极值的必要条件，分别令 $\frac{\partial f}{\partial x_{i} } =0$ ，求出可能的极值点. 因此可以联想到：等式约束下的Lagrange乘数法引入了个Lagrange乘子，或许我们可以把也看作优化变量（就叫做优化变量）. 相当于将优化变量个数增加到 $(n+l)$ 个，与一视同仁，均为优化变量，均对它们求偏导.
2. 不等式约束优化问题

以上我们讨论了等式约束的情形，接下来我们来介绍不等式约束的优化问题.我们先给出其主要思想：转化的思想——将不等式约束条件变成等式约束条件.具体做法：引入松弛变量.松弛变量也是优化变量，也需要一视同仁求偏导.

具体而言，我们先看一台一元函数的例子：
$minf(x)$
$s.t. g_{1}(x) =a-x\leq 0 \\g_{2}(x) =x-b\leq 0$
（注：优化问题中，我们必须求得一台确定的值，因此不妨令所有的不等式均取到等号，即 $\leq$ 的情况.）

对于约束和，我们分别引入两个松弛变量和，得到 $h_{1} (x,a_{1} )=g_{1} +a_{1}^{2} =0$ 和 $h_{2} (x,b_{1} )=g_{2} +b_{1}^{2} =0$ .注意，这里直接加上平方项、而非、，是因为和这两个不等式的左边必须加上一台正数才能使不等式变为等式.若只加上和，又会引入新的约束 $a_{1} \geq 0$ 和 $b_{1} \geq 0$ ，这不符合我们的意愿.

由此我们将不等式约束转化为了等式约束，并得到Lagrange函数
                           $L(x,a_{1} ,b_{1} ,\mu _{1} ,\mu _{2} )=f(x)+\mu _{1}(a-x+a_{1}^{2} )+\mu _{2}(x-b+b_{1}^{2} )$
我们再按照等式约束优化问题（极值必要条件）对其求解，联立方程

（注：这里的 $\mu _{1} \geq 0$ ， $\mu _{2} \geq 0$ 先承认，我们待会再解释！（先上车再买票，手动斜眼）实际上对于不等式约束前的乘子，我们要求其大于等于0）

得出方程组后，便开始动手解它. 看到第3行的两式和比较简单，我们就从它们入手吧~
对于，我们有两种情况：
情形1： $\mu _{1} =0,a_{1} \ne 0$
此时由于乘子 $\mu _{1} =0$ ，因此与其相乘为零，可以理解为约束不起作用，且有 $g_{1}(x) =a-x< 0$ .
情形2： $\mu _{1} \geq 0,a_{1} =0$
此时 $g_{1}(x) =a-x= 0$ 且，可以理解为约束 $g_{1}$ 起作用，且有.
合并情形1和情形2得： $\mu _{1}g_{1}=0$ ，且在约束起作用时，；约束不起作用时 $\mu _{1}=0$ ， $g_{1}(x)<0$ .

同样地，分析 $\mu _{2}b_{1}=0$ ，可得出约束 $g_{2}$ 起作用和不起作用的情形，并分析得到 $\mu _{2}g_{2}=0$ .

由此，方程组（极值必要条件）转化为

$\left\{ \begin{array}{l} \frac{{df}}{{dx}} + {\mu _1}\frac{{d{g_1}}}{{dx}} + {\mu _2}\frac{{d{g_2}}}{{dx}} = 0,\\ {\mu _1}{g_1}\left( x \right) = 0,{\mu _2}{g_2}\left( x \right) = 0,\\ {\mu _1} \ge 0,{\mu _2} \ge 0. \end{array} \right.$
这是一元一次的情形.类似地，对于多元多次不等式约束问题

$\begin{array}{l} \min {\rm{ }}f({\bf{x}})\\ s.t.{\rm{ }}{g_j}({\bf{x}}) \le 0{\rm{ }}(j = 1,2, \cdots ,m) \end{array}$
我们有
$\left\{ \begin{array}{l} \frac{{\partial f\left( {{x^*}} \right)}}{{\partial {x_i}}} + \sum\limits_{j = 1}^m {{\mu _j}\frac{{\partial {g_j}\left( {{x^*}} \right)}}{{\partial {x_i}}}} = 0{\rm{ }}\left( {i = 1,2,...,n} \right),\\ {\mu _j}{g_j}\left( {{x^*}} \right) = 0{\rm{ }}\left( {j = 1,2,...,m} \right),\\ {\mu _j} \ge 0{\rm{ }}\left( {j = 1,2,...,m} \right). \end{array} \right.$
上式便称为不等式约束优化问题的KKT（Karush-Kuhn-Tucker）条件. $\mu _{j}$ 称为KKT乘子，且约束起作用时 $\mu _{j}\geq 0$ ， $g_{j}(x)=0$ ；约束不起作用时 $\mu _{j}= 0$ ， $g_{j}(x)<0$ .

别急，还木有完，我们还剩最后一台问题没有解决：为啥KKT乘子必须大于等于零——我将用几何性质来解释.

由于
$\frac{{\partial f\left( {{x^*}} \right)}}{{\partial {x_i}}} + \sum\limits_{j = 1}^m {{\mu _j}\frac{{\partial {g_j}\left( {{x^*}} \right)}}{{\partial {x_i}}}} = 0{\rm{ }}\left( {i = 1,2,...,n} \right)$
用梯度表示： $\nabla f\left( {{{\bf{x}}^*}} \right) + \sum\limits_{j \in J} {{\mu _j}\nabla {g_j}\left( {{{\bf{x}}^*}} \right)} = 0$ ， $J$ 为起作用约束的集合.
移项： $- \nabla f\left( {{{\bf{x}}^*}} \right) = \sum\limits_{j \in J} {{\mu _j}\nabla {g_j}\left( {{{\bf{x}}^*}} \right)} ,$

注意到梯度为向量. 上式表示在约束极小值点处，函数 $f\left( {{{\bf{x}}^*}} \right)$ 的负梯度一定可以表示成：所有起作用约束在该点的梯度（等值线的法向量）的线性组合.（复习课本中梯度的性质：某点梯度的方向就是函数等值线在这点的法线方向，等值线就是地理的等高线）
为省事作图，假设目前只有两个起作用约束，我们作出图形如下图.注意我们上面推导过，约束起作用时 ${g_j}\left( {\bf{x}} \right) = 0$ ，所以此时约束在几何上应该是一簇约束平面.我们假设在取得极小值点，若同时满足和，则一定在这两个平面的交线上，且 $- \nabla f\left( {{{\bf{x}}^*}} \right) = \sum\limits_{j \in J} {{\mu _j}\nabla {g_j}\left( {{{\bf{x}}^*}} \right)}$ ，即、和共面.

下图是在点处沿 $x_{1}Ox_{2}$ 面的截面，过点作目标函数的负梯度，它垂直于目标函数的等值线（高数课本：一点的梯度与等值线相互垂直），且指向目标函数的最速减小方向.再作约束函数和的梯度和，它们分别垂直和两曲面在的切平面，并形成一台锥形夹角区域.此时，可能有a、b两种情形：

我们先来看情形b：若3个向量的位置关系如b所示，即落在和所形成的锥角区外的一侧. 此时，作等值面在点的切平面（它与垂直），我们发现：沿着与负梯度成锐角的方向移动（如下图红色箭头方向），只要在红色区域取值，目标函数总能减小.而红色区域是可行域（，C取不同的常数能得到不同的等值线，因此能取到红色区域），因此既可减小目标函数值，又不破坏约束条件. 这说明仍可沿约束曲面移动而不破坏约束条件，且目标函数值还能够减小.所以不是稳定的最优点，即不是局部极值点.

反过头来看情形a：落在和形成的锥角内. 此时，同样作在点与垂直的切平面. 当从出发沿着与负梯度成锐角的方向移动时，虽然能使目标函数值减小，但此时任何一点都不在可行区域内. 显然，此时就是局部最优点，再做任何移动都将破坏约束条件，故它是稳定点.
由于和、在一台平面内，所以前者可看成是后两者的线性组合. 又由上面的几何分析知，在和的夹角之间，所以线性组合的系数为正，有

$- \nabla f\left( {{{\bf{x}}^*}} \right){\rm{ = }}{\mu _{\rm{1}}}\nabla {g_{\rm{1}}}\left( {{{\bf{x}}^*}} \right){\rm{ + }}{\mu _{\rm{2}}}\nabla {g_{\rm{2}}}\left( {{{\bf{x}}^*}} \right)$ ，且 $\mu _{1}>0$ ， $\mu _{2}>0$ .
这就是 $\mu _{j}>0$ 的原因. 类似地，当有多个不等式约束同时起作用时，要求处于 $\nabla g_{j}\left( {{{\bf{x}}^*}} \right)$ 形成的超角锥（高维图形，我姑且称之为“超”）之内.
3.总结：同时包含等式和不等式约束的一般优化问题


KKT条件（是最优解的必要条件）为

注意，对于等式约束的Lagrange乘子，并没有非负的要求！以后求其极值点，不必再引入松弛变量，直接使用KKT条件判断！
这样，我们就推导完了KKT条件。各位看官可以自个分别罗列并比较一下：无约束优化、等式约束优化和等式+不等式约束优化条件下某点为局部最优解（极值点）的必要条件。
如果对于Lagrange对偶性感兴趣的同学，可以进一步地研究下去，这样才能较深入地掌握SVM，本人也在学习中，欢迎交流~

mark，有时间翻出我的笔记来对照看看，这种知识点隔一段时间就忘一次2333

推导很精彩，这些分享

谢谢~欢迎交流

写完这个我的印象又深了一些~

谢谢分享上课没咋听懂

为什么你在求解KKT乘子，几何证明时的f函数的负梯度为何超上呢？

上课时，年轻老师经验不足，还是课下看公开课搞懂的。现在看楼主的笔记，是非常好的复习，加深理解。

u1=a1之后的推导不够严谨。u1=0，并不能得到a1!=0，因为a1=0也可以。u1=0只能得到g1<=0，不能得到g1<0.

乘子大于等于0从目标函数就可以看出，不等式约束小于0，目标函数又是最小化，乘子肯定大于等于0。

		自动登录	找回密码
密码			立即注册

浅谈最优化问题的KKT条件

相关问题更多>

最新回答