拉格朗日乘子法（Lagrange Multiplier) 和KKT条件

参考：
1.深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件
2.简易解说拉格朗日对偶（Lagrange duality）
3.支持向量机（SVM）必备知识(KKT、slater、对偶）

一、应用场景及使用：

拉格朗日乘子法（Lagrange Multiplier) 和KKT条件是求解有约束优化问题非常重要的两个求取方法。对于等式约束的优化问题，可以应用拉格朗日乘子法去求取最优值；如果含有不等式约束，可以应用KKT条件去求取。当然，这两个方法求出的点只满足必要条件（也就是常说的极值点不一定是最值点，但最值点一定是极值点），当目标函数是凸函数时可转化为充分必要条件。（凸函数对应min类优化问题）

通常我们需要求解的最优化问题有如下几类：
（1）无约束优化问题，形如

（2）有等式约束的优化问题，形如

（3）有不等式约束的优化问题，形如

对于第(1)类的优化问题，常常使用的方法就是Fermat定理，即使用求取f(x)的导数，然后令其为零，可以求得候选最优值，再在这些候选值中验证；如果是凸函数，可以保证是最优解。

对于第(2)类问题，利用拉格朗日系数将约束与目标函数按如下形式组合：

然后求取最优值，
L(a,x)对x求导取零，联立hi(x)=0(ai≠0)进行求取，这个在高等数学里面有讲，但是没有讲为什么这么做就可以，在后面，将简要介绍其思想。

对于第(3)类问题，同样将所有条件和目标函数写成一个式子：

利用KKT条件求解最优值，
1.L(a,b,x)对x求导为零
2.hi(x)=0;i=1,…,n,gi(x)≤0;i=1,…,m
3.ai≥0;bi≠0
4.aigi(x)=0(松弛互补)
其中第三个式子是SVM很多重要性质的来源，如支持向量的概念

二、原理解释：

为什么拉格朗日乘子法（Lagrange Multiplier) 和KKT条件能够得到最优值？

先说说拉格朗日乘子法，设我们的目标函数为z=f(x)，x为向量，将z投影到自变量x构成的平面上，即形成等高线。如下图，目标函数是f(x,y)，这里x，y是标量，虚线是等高线，箭头为导数方向，显然范围越小的等高线越接近无约束条件下的最值。现在假设我们的约束g(x)=0，x是向量，在x构成的平面或者曲面上是一条曲线，假设g(x)与等高线相交，交点就是同时满足等式约束条件和目标函数的可行域的值。但肯定不是最优值，因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与约束函数的交点的值更大或者更小，也就是存在两种变化方向的可能性。而只有当等高线与约束条件相切时，可能取值最优值，即此时单向不可更优。如下图所示，等高线与约束函数的曲线在该点的法向量必须有相同方向，所以最优点满足：f(x)的梯度=ai∗gi(x)的梯度;i=1,…,n

而KKT条件是满足强对偶条件的优化问题的必要条件，需要结合拉格朗日对偶（Lagrange duality）进行理解：
1.原问题转化
定义

θP(x)是L(a,b,x)将a,b看作参数并求max所得到的，此时结果只与x有关。
显然（读者可自行证明），

我们再考虑minθP(x)，显然最优解x∗会出现在x满足原始问题约束的可行域之内，即

通过拉格朗日乘子法我们成功的构造了一个与原约束优化问题等价的无约束问题，从而实现闲了约束问题无约束化。

2.对偶问题
现在我们先将x看做参数，定义

考虑极大化，则

3.原始问题与对偶问题的关系
显然两者在形式上是对称的，其次有如下定理：
定理：若原始问题与对偶问题都有最优值，则二者相等。即强对偶性，

证明：对任意的a,b和x，有

即，

由于原始问题与对偶问题都有最优值，所以

即，d∗≤p∗
可见原问题的最优值不小于对偶问题的最优值，但是当我们想要利用对偶问题来求解原始问题时（当然是对偶问题求解比直接求解原始问题简单的情况下），就必须使得两者的最优值相等，于是可以得出下面的推论：

推论：设a,b和x分别是原始问题和对偶问题的可行解，如果d∗=p∗，那么a,b和x分别是原始问题和对偶问题的最优解。

但是到底满足什么样的条件才能使得d∗=p∗呢，这就是下面要阐述的 KKT 条件。

4.KKT条件
强对偶性：存在a∗,b∗,x∗使得d∗=p∗

现在假设强对偶性成立，并且假设x∗是原函数的最优解，a∗,b∗是对偶函数的最优点，那么

因为上式取等号，所以θD(a∗,b∗)在x=x∗取得最小值，即∂L∂x|x=x∗=0
这也是KKT第一个条件，之后为了保证解在可行域内（导数方程已无法包含约束条件），需要满足
1. 约束条件：hi(x)=0;gj(x)≤0
2. 拉格朗日系数约束：ai≥0,bi≠0
3.互补松弛条件：aigi(x)=0
关于第三条互补松弛条件，我们可以回顾一下这样一个式子：

显然∑mi=1aigi(x)在aigi(x)=0时取得最大，因此这也是隐含的d∗=p∗时的条件

最终我们得到了所有的KKT条件，可以看出KKT是一组解成为最优解的必要条件，我们甚至可能通过他它求解最优解。

最后说明一下
slater条件：存在x，使得不等式约束g(x)<=0严格成立。
slater条件性质： slater条件是原问题可以等价于对偶问题的一个充分条件，满足他就说明存在最优解。

*补充知识：

1.凸集和凸函数
凸集：在点集拓扑学与欧几里得空间中，凸集是一个点集，其中每两点之间的直线上的点都落在该点集中。请看下图：

凸函数：一个定义在向量空间的凸子集C(区间)上的实值函数f，如果在其定义域C上的任意两点x，y以及t∈[0,1]有：

则该函数为凸函数！凸函数另一个判别方式是：如果一个凸函数是一个二阶可微函数，则它的二阶导数是非负的。上图：

下面引自*：

注意：*数学界某些机构关于函数凹凸性定义和国外的定义是相反的。Convex Function在某些*的数学书中指凹函数。Concave Function指凸函数。但在*涉及经济学的很多书中，凹凸性的提法和其他国家的提法是一致的，也就是和数学教材是反的。举个例子，同济大学高等数学教材对函数的凹凸性定义与本条目相反，本条目的凹凸性是指其上方图是凹集或凸集，而同济大学高等数学教材则是指其下方图是凹集或凸集，两者定义正好相反。 另外，也有些教材会把凸定义为上凸，凹定义为下凸。碰到的时候应该以教材中的那些定义为准。

在机器学习领域大多数是采用上文中所描述的凸函数和凹函数的定义。

2.凸优化问题
凸优化：凸优化是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问题。其中，目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。而目标函数和不等式约束函数均为凸函数，等式约束函数为仿射函数，并且定义域为凸集的优化问题为约束优化问题。

上面是来自百度百科定义，下面我们对其总结，将其公式化！

凸优化性质：
1、目的是求取目标函数的最小值；
2、目标函数和不等式约束函数都是凸函数，定义域是凸集；
3、若存在等式约束函数，则等式约束函数为仿射函数；
4、对于凸优化问题具有良好的性质，局部最优解便是全局最优解。

一个凸优化问题用公式描述为：

所以其目标函数f(x)以及不等式约束条件g(x)便是凸函数，而等式约束条件h(x)是仿射函数。
大家可能要问：何为仿射函数！！！

仿射函数：即是deg(h(x))=1的函数，常数项为0的仿射函数称为线性函数。

其中符号 deg() 表示多项式h(x)的次数