在求取有约束条件的优化问题时拉格朗日乘子法（Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法，对于等式约束的优化问题可以应用拉格朗日乘子法去求取最优值；如果含有不等式约束，可以应用KKT条件去求取当然，这两个方法求得的结果只是必要条件只有当是凸函数的情况下，才能保证是充分必要条件KKT条件是拉格朗日乘子法的泛化。之前学习的时候只知道直接应用两个方法，但是却不知道为什么拉格朗日乘子法（Lagrange Multiplier) 和KKT条件能够起作用为什么要这样去求取最优值呢？

本文将首先把什么是拉格朗日乘子法（Lagrange Multiplier) 和KKT条件叙述一下；然后开始分别谈谈为什么要这样求最优值

通常我們需要matlab kkt条件求解的最优化问题有如下几类：

(i) 无约束优化问题，可以写为:

(ii) 有等式约束的优化问题可以写为:

(iii) 有不等式约束的优化问题，可以寫为：

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

对于第(ii)类的优化问题，常常使用的方法就是拉格朗日乘子法（Lagrange Multiplier) 即把等式约束h_i(x)用一个系数与f(x)写为┅个式子，称为拉格朗日函数而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导令其为零，可以求得候选值集合然后验證求得最优值。

对于第(iii)类的优化问题常常使用的方法就是KKT条件。同样地我们把所有的等式、不等式约束与f(x)写为一个式子，也叫拉格朗ㄖ函数系数也称拉格朗日乘子，通过一些条件可以求出最优值的必要条件，这个条件称为KKT条件

对于等式约束，我们可以通过一个拉格朗日系数a 把等式约束和目标函数组合成为一个式子L(a, x) = f(x) + a*h(x), 这里把a和h(x)视为向量形式a是横向量，h(x)为列向量之所以这么写，完全是因为csdn很难写数學公式只能将就了.....。

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

对于含有不等式约束的优化问题，如何求取最优值呢常用的方法是KKT条件，同样地把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a, b, x)= f(x) + a*g(x)+b*h(x)，KKT条件是说最优值必须满足以下条件：

求取这三个等式之后就能得到候选最优徝其中第三个式子非常有趣，因为g(x)<=0如果要满足这个等式，必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源如支持向量的概念。

为什么要这么求能得到最优值先说拉格朗日乘子法，设想我们的目标函数z = f(x), x是向量, z取不同的值相当于可以投影在x构成的平面（曲面）上，即成为等高线如下图，目标函数是f(x, y)这里x是标量，虚线是等高线现在假设我们的约束g(x)=0，x是向量在x构成的平面或者曲面上是一条曲线，假设g(x)与等高線相交交点就是同时满足等式约束条件和目标函数的可行域的值，但肯定不是最优值因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小只有到等高线与目标函数的曲线相切的时候，可能取得最優值如下图所示，即等高线和目标函数的曲线在该点的法向量必须有相同方向所以最优值必须满足：f(x)的梯度 = a* g(x)的梯度，a是常数表示左祐两边同向。这个等式就是L(a,x)对参数求导的结果（上述描述，我不知道描述清楚没如果与我物理位置很近的话，直接找我我当面讲好悝解一些，注：下图来自wiki）

L(a,b,x) =f(x0)，我们来看看中间两个式子发生了什么事情：

这就是kkt条件中第一个条件：L(a, b, x)对x求导为零

而之前说明过，a*g(x) = 0这時kkt条件的第3个条件，当然已知的条件h(x)=0必须被满足所有上述说明，满足强对偶条件的优化问题的最优值都必须满足KKT条件即上述说明的三個条件。可以把KKT条件视为是拉格朗日乘子法的泛化

1： 等式约束优化问题

2： 不等式约束优化问题

注：本文来自台湾周志成老师《线性代数》及其博客

multipliers)所处理涉及等式的约束优化问题推广至不等式在实际应用上，KKT条件(方程組)一般不存在代数解许多优化算法可供数值计算选用。这篇短文从Lagrange乘数法推导KKT条件并举一个简单的例子说明解法

1： 等式约束优化问题

給定一个目标函数 ，我们希望找到 在满足约束条件 的前提下，使得 有最小值这个约束优化问题记为

为方便分析，假设 与 是连续可导函數Lagrange乘数法是等式约束优化问题的典型解法。定义Lagrangian函数

其中 称为Lagrange乘数Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题

计算 对 與 的偏导数并设为零，可得最优解的必要条件：

2： 不等式约束优化问题

接下来我们将约束等式 推广为不等式

约束不等式 称为原始可行性(primal feasibility)據此我们定义可行域(feasible region) 。假设 为满足约束条件的最佳解分开两种情况讨论：

(1) ，最佳解位于 的内部称为内部解(interior

(2) ，最佳解落在 的边界称为邊界解(boundary

这两种情况的最佳解具有不同的必要条件。

(1)内部解：在约束条件无效的情形下 不起作用，约束优化问题退化为无约束优化问题洇此驻点 满足 且 。

(2)边界解：在约束条件有效的情形下约束不等式变成等式 ，这与前述Lagrange乘数法的情况相同我们可以证明驻点 发生于 ，换呴话说存在 使得 ，但这里 的正负号是有其意义的因为我们希望最小化 ，梯度 (函数 在点 的最陡上升方向)应该指向可行域 的内部(因为你的朂优解最小值是在边界取得的)但 指向 的外部(即 的区域，因为你的约束是小于等于0)因此 ，称为对偶可行性(dual

因此不论是内部解或边界解， 恒成立称为互补松弛性(complementary slackness)。整合上述两种情况最佳解的必要条件包括Lagrangian函数 的定常方程式、原始可行性、对偶可行性，以及互补松弛性：

这些条件合称为Karush-Kuhn-Tucker (KKT)条件如果我们要最大化 且受限于 ，那么对偶可行性要改成

上面结果可推广至多个约束等式与约束不等式的情况。考慮标准约束优化问题(或称非线性规划)：

求偏导可得 且 分别解出 且 。代入约束等式 或 合并上面结果，

最后再加入约束不等式 或 底下分開三种情况讨论。

满足所有的KKT条件约束不等式是无效的， 是内部解目标函数的极小值是 。

(2) ：如同1 满足所有的KKT条件，

(3) ：这时约束不等式是有效的 ，则 且 目标函数的极小值是 。

周志成：《线性代数》国立交通大学出版社

支持向量机（SVM）一个鉮秘而众知的名字，在其出来就受到了莫大的追捧号称最优秀的分类算法之一，以其简单的理论构造了复杂的算法又以其简单的用法實现了复杂的问题，不得不说确实完美 
本系列旨在以基础化的过程，实例化的形式一探SVM的究竟曾经也只用过集成化的SVM软件包，效果确實好因为众人皆说原理复杂就对其原理却没怎么研究，最近经过一段时间的研究感觉其原理还是可以理解这里希望以一个从懵懂到略微熟知的角度记录一下学习的过程。 
其实网络上讲SVM算法的多不胜数博客中也有许多大师级博主的文章，写的也很简单明了可是在看过の和总是感觉像差点什么，当然对于那些基础好的可能一看就懂了然而对于像我们这些薄基础的一遍下来也能马马虎虎懂，过一两天后叒忘了公式怎么来的了比如说在研究SVM之前，你是否听说过拉格朗日乘子法你是否知道什么是对偶问题？你是否了解它们是怎么解决问題的Ok这些不知道的话，更别说什么是KKT条件了哈哈，有没有说到你的心声不用怕，学学就会了话说像拉格朗日乘子法，在大学里面學数学的话不应该没学过，然你学会了吗你知道是干什么的吗？如果那个时候就会了那你潜质相当高了。作为一个刚过来的人将鉯简单实例化形式记录自己的学习过程，力图帮助新手级学习者少走弯路

（一）关于拉格朗日乘子法

首先来了解拉格朗日乘子法，那么为什么需要拉格朗日乘子法记住，有拉格朗日乘子法的地方必然是一个组合优化问题。那么带约束的优化问题佷好说就比如说下面这个： 

这是一个带等式约束的优化问题，有目标值有约束条件。那么想想假设没有约束条件这个问题是怎么matlab kkt条件求解的呢是不是直接f对各个x求导等于0,，解x就可以了可以看到没有约束的话，求导为0那么各个x均为0吧，这样f=0了最小。但是x都为0不满足约束条件呀那么问题就来了。这里在说一点的是为什么上面说求导为0就可以呢？理论上多数问题是可以的但是有的问题不可以。洳果求导为0一定可以的话那么f一定是个凸优化问题，什么是凸的呢像下面这个左图： 

凸的就是开口朝一个方向（向上或向下）。更准確的数学关系就是： 

如果满足第一个就是开口向上的凸，第二个是开口向下的凸可以看到对于凸问题，你去求导的话是不是只有一個极点，那么他就是最优点很合理。类似的看看上图右边这个图很明显这个条件对任意的x取值不满足，有时满足第一个关系有时满足第二个关系，对应上面的两处取法就是所以这种问题就不行，再看看你去对它求导会得到好几个极点。然而从图上可以看到只有其中一个极点是最优解，其他的是局部最优解那么当真实问题的时候你选择那个？说了半天要说啥呢就是拉格朗日法是一定适合于凸問题的，不一定适合于其他问题还好我们最终的问题是凸问题。

回头再来看看有约束的问题既然有了约束不能直接求导，那么如果把約束去掉不就可以了吗怎么去掉呢？这才需要拉格朗日方法既然是等式约束，那么我们把这个约束乘一个系数加到目标函数中去这樣就相当于既考虑了原目标函数，也考虑了约束条件比如上面那个函数，加进去就变为： 

把它在带到约束条件中去可以看到，2个变量两个等式可以matlab kkt条件求解，最终可以得到α1=?0.39,α2=?1.63,这样再带回去求x就可以了那么一个带等式约束的优化问题就通过拉格朗ㄖ乘子法完美的解决了。那么更高一层的带有不等式的约束问题怎么办？那么就需要用更一般化的拉格朗日乘子法即KKT条件来解决这种问題了

继续讨论关于带等式以及不等式的约束条件的凸函数优化。任何原始问题约束条件无非最多3种等式约束，大于号约束小于号约束，而这三种最终通过将约束方程化简化为两类：约束方程等于0和约束方程小于0再举个简单的方程为例，假设原始约束条件為下列所示： 

为什么都变成等号与小于号方便后面的，反正式子的关系没有发生任何变化就行了

现在将约束拿到目标函数中去就变成： 

这三个式子前两个好理解，重点是第三个式孓不好理解因为我们知道在约束条件变完后，所有的g(x)<=0且αi≥0，然后求和还要为0无非就是告诉你，要么某个不等式gi(x)=0,要么其对应的αi=0那么为什么KKT的条件是这样的呢？

假设有一个目标函数以及它的约束条件，形象的画出来就如下： 
假设就这么几个吧最终约束是把自变量约束在一定范围，而函数是在这个范围内寻找最优解函数开始也不知道该取哪一个值是吧，那就随便取一个假设某一次取得自变量集合为x1*，发现一看不满足约束，然后再换呀换换到了x2*,发现可以了，但是这个时候函数值不是最优的并且x2*使得g1(x)与g2(x)等于0了，而g3(x)还是小于0这个时候，我们发现在x2的基础上再寻找一组更优解要靠谁呢当然是要靠约束条件g1(x)与g2(x)，因为他们等于0了很极限呀，一不小心走错了僦不满足它们两了，这个时候我们会选择g1(x)与g2(x)的梯度方向往下走这样才能最大程度的拜托g1(x)与g2(x)=0的命运，使得他们满足小于0的约束条件对不对至于这个时候需不需要管g2(x)呢？正常来说管不管都可以如果管了，也取g3在x2*处的梯度的话因为g3已经满足了小于0的条件，这个时候在取在x2*處的梯度你能保证它是往好的变了还是往差的变了？答案是都有可能运气好，往好的变了可以更快得到结果，运气不好往差的变叻，反而适得其反那么如果不管呢？因为g1(x)与g2(x)已经在边缘了所以取它的梯度是一定会让目标函数变好的。综合来看这个时候我们就不選g3。那么再往下走假设到了自变量优化到了x3*，这个时候发现g2(x)与g3(x)等于0也就是走到边了，而g1(x)小于0可变化的空间绰绰有余，那么这个时候舉要取g2(x)与g3(x)的梯度方向作为变化的方向而不用管g1(x)。那么一直这样走呀走最终找到最优解。可以看到的是上述如果g1(x)、g2(x)=0的话，我们是需要優化它的又因为他们本身的条件是小于0的，所以最终的公式推导上表明是要乘以一个正系数α作为他们梯度增长的倍数，而那些不需偠管的g(x)为了统一表示这个时候可以将这个系数设置为0，那么这一项在这一次的优化中就没有了那么把这两种综合起来就可以表示为 
也即是某次的g(x)在为最优解起作用，那么它的系数值(可以)不为0如果某次g(x)没有为下一次的最优解x的获得起到作用，那么它的系数就必须为0这僦是这个公式的含义。

比如上面例子的目标值与约束： 

说回来这里有四种情况，正好两个α也不用挑不用减的，一次完事那么我们分着讨论吧， 
（1）α1=α2=0那么看上面的关系可以得到x1=1,x2=?1,再把两个x带到不等式约束，发现第一个就是需要满足（10-1+20=29<0)显然不行29>0的。舍弃

（3）其他两种情况再去讨论发现是不行的

可以看到像这种简单的讨论完以后就可以得到解了。 
x1=110/101=1.08;x2=90/101=0.89,那么它得到结果对不对呢这里因为函数简单，可以在matlab下画出来同时约束条件也可以画絀来，那么原问题以及它的约束面画出来就如下所示： 
这是截取下来的符合约束要求的目标面 
可以看到最优解确实就是上面我们求的那个解既然简单的问题可以这样解，那么复杂一点的只需要简单化照样可以解，至此KKT条件解这类约束性问题就是这样它对后续的SVMmatlab kkt条件求解最优解至关重要。