最近学习优化理论，正好在机器学习中支持向量机(Support Vector Machine )和最大熵模型(Maximum Entropy Model )使用的KKT条件) ka rushKuhntucker
以前看过一些相关书籍，发现证明KKT条件并不简单，或者“数学”(除数学以外的学生可能不懂) ——不适合非数学学生的入门。 因此，整理教材、做课堂笔记、加入帮助理解的重要注释(我个人认为不“明显”)来写这篇文章，供大家学习和交流！
PS :我知道的排版有点混乱。 官吏们请不要在意：)
目录：什么是0.kkt条件
1 .等式约束优化问题(Lagrange乘数法) ) ) ) ) ) )。
2 .不等式约束的优化问题
3 .总结
什么是0.KKT条件
本文从本科高数(微积分)中条件极值的Lagrange乘数法入手，进一步推导KKT条件。 但是，在说明导出过程之前，我想先给出KKT条件。
具有等式和不等式约束的一般优化问题
kt条件给出了判断
是否为最优解的必要条件，即：
1 .等式约束优化问题(Lagrange乘数法) ) ) ) ) ) )。
关于这一部分的内容，其实本科高数课程已经学过，所以本文直接得出结论，并补充了一些我的理解和总结，它有助于理解不等式约束中的一些内容。 具体推导过程已在同济7版的高数下卷(P.116-118 )中详细描述。
什么是等式约束优化问题
我们应该
、函数
称为Lagrange函数，参数
叫做Lagrange算子。
联立方程式：
，
得到的解是可能极值点，我们使用了必要条件，所以具体是否是极值点需要根据问题本身的具体情况来验证。 该方程组被称为等式约束的极值必要条件。
上式我们是对的
个
和
个
请各求偏导，回想无约束的优化问题
那么，根据极值的必要条件分别
求出可能的极值点。 因此，可以联想到引入了等式约束下的Lagrange乘数法
我乘坐洛杉矶。 我们应该
优化变量(
称为优化变量) .相当于将优化变量的数量增加到
个，与
和同事一样，都是优化变量，要求对它们进行偏导。
2 .不等式约束的优化问题
以上讨论了等式约束的情况，接下来介绍不等式约束的优化问题。 首先，提出其主要思想。 转换后的思想——将不等式制约条件变为等式制约条件。 具体方法：引入松弛变量。 松弛变量也是优化变量，需要一视同仁地寻求偏导。
具体来说，首先看一元函数的例子：
(注：在优化问题中，必须求出确定的值，所以可以将所有不等式取为等号。 也就是说
的情况)
约束情况
和
分别引入两个松弛变量
和
按一下
和
.注意这里直接加上平方项
在、
而不是
在、
是理由
和
如果不在这两个不等式的左边加上正数，不等式就不能成为等式。 如果只是加上的话
和
将引入新的约束条件
和
这不符合我们的意愿
据此，将不等式制约转换为等式制约，得到Lagrange函数
根据等式约束优化问题(极值必
要条件)对其求解，联立方程(注：这里的
，
先承认，我们待会再解释！(先上车再买票，手动斜眼)实际上对于不等式约束前的乘子，我们要求其大于等于0)
得出方程组后，便开始动手解它. 看到第3行的两式
和
比较简单，我们就从它们入手吧~
对于
，我们有两种情况：
情形1：
此时由于乘子
，因此
与其相乘为零，可以理解为约束
不起作用，且有
.
情形2：
此时
且
，可以理解为约束
起作用，且有
.
合并情形1和情形2得：
，且在约束起作用时
，
；约束不起作用时
，
.
同样地，分析
，可得出约束
起作用和不起作用的情形，并分析得到
.
由此，方程组(极值必要条件)转化为
这是一元一次的情形.类似地，对于多元多次不等式约束问题
我们有
上式便称为不等式约束优化问题的KKT(Karush-Kuhn-Tucker)条件.
称为KKT乘子，且约束起作用时
，
；约束不起作用时
，
.
别急，还木有完，我们还剩最后一个问题没有解决：为什么KKT乘子必须大于等于零——我将用几何性质来解释.
由于
用梯度表示：
，
为起作用约束的集合.
移项：
注意到梯度为向量. 上式表示在约束极小值点
处，函数
的负梯度一定可以表示成：所有起作用约束在该点的梯度(等值线的法向量)的线性组合.(复习课本中梯度的性质：某点梯度的方向就是函数等值线
在这点的法线方向，等值线就是地理的等高线)
为方便作图，假设现在只有两个起作用约束，我们作出图形如下图.注意我们上面推导过，约束起作用时
，所以此时约束在几何上应该是一簇约束平面.我们假设在
取得极小值点，若同时满足
和
，则
一定在这两个平面的交线上，且
，即
、
和
共面.
下图是在点
处沿
面的截面，过点
作目标函数的负梯度
，它垂直于目标函数的等值线
(高数课本：一点的梯度与等值线相互垂直)，且指向目标函数
的最速减小方向.再作约束函数
和
的梯度
和
，它们分别垂直
和
两曲面在
的切平面，并形成一个锥形夹角区域.此时，可能有a、b两种情形：
我们先来看情形b：若3个向量的位置关系如b所示，即
落在
和
所形成的锥角区外的一侧. 此时，作等值面
在点
的切平面(它与
垂直)，我们发现：沿着与负梯度
成锐角的方向移动(如下图红色箭头方向)，只要在红色区域取值，目标函数
总能减小.而红色区域是可行域(
，C取不同的常数能得到不同的等值线，因此能取到红色区域)，因此既可减小目标函数值，又不破坏约束条件. 这说明
仍可沿约束曲面移动而不破坏约束条件，且目标函数值还能够减小.所以
不是稳定的最优点，即不是局部极值点.
反过头来看情形a：
落在
和
形成的锥角内. 此时，同样作
在点
与
垂直的切平面. 当从
出发沿着与负梯度
成锐角的方向移动时，虽然能使目标函数值减小，但此时任何一点都不在可行区域内. 显然，此时
就是局部最优点
，再做任何移动都将破坏约束条件，故它是稳定点.
由于
和
、
在一个平面内，所以前者可看成是后两者的线性组合. 又由上面的几何分析知，
在
和
的夹角之间，所以线性组合的系数为正，有
，且
，
.
这就是
的原因. 类似地，当有多个不等式约束同时起作用时，要求
处于
形成的超角锥(高维图形，我姑且称之为“超”)之内.
3.总结：同时包含等式和不等式约束的一般优化问题
KKT条件(
是最优解的必要条件)为
注意，对于等式约束的Lagrange乘子，并没有非负的要求！以后求其极值点，不必再引入松弛变量，直接使用KKT条件判断！
这样，我们就推导完了KKT条件。各位看官可以自己分别罗列并比较一下：无约束优化、等式约束优化和等式+不等式约束优化条件下某点为局部最优解(极值点)的必要条件。
如果对于Lagrange对偶性感兴趣的同学，可以进一步地研究下去，这样才能较深入地掌握SVM，本人也在学习中，欢迎交流~