kkt条件例题求解_kkt条件证明

kkt条件例题求解_kkt条件证明继前面讲的拉格朗日乘子法。拉格朗日乘子法主要用于求解等式约束的问题，当约束加上不等式之后，情况变得更加复杂，首先来看一个简单的情况，给定如下不等式约束问题：对应的Lagrangian与图形分别如下所示：上面这段话可能描述的不够清楚。我总结一下。上图左表达的是，当我们要找的局部最优解（或者全局最优解）刚好就在约束条件的可行区域内部（这个时候最优解对应的是g(x)<...

大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说kkt条件例题求解_kkt条件证明,希望能够帮助大家进步!!!

继前面讲的拉格朗日乘子法。拉格朗日乘子法主要用于求解等式约束的问题，当约束加上不等式之后，情况变得更加复杂，首先来看一个简单的情况，给定如下不等式约束问题：

对应的 Lagrangian 与图形分别如下所示：

上面这段话可能描述的不够清楚。我总结一下。上图左表达的是，当我们要找的局部最优解（或者全局最优解）刚好就在约束条件的可行区域内部（这个时候最优解对应的是g(x)

其实就是在这种情况下，我们考虑上图右约束圆圈的边界，而最优点就落在，约束条件的圆心与目标函数的圆心相连直线与边界相交的那个点上。

有一点需要注意的是，在无约束的拉格朗日乘子法中等式约束与目标函数的梯度是平行的，在这里其实也是平行的，但多了一个条件不仅要平行还要相反，故

必须>0，在等式约束中就没有这个限制。

看完这张图你可能会觉得这和我上面讲的不一样，但实际上是一样的。这一段不是在解释为什么

为什么一定要大于0，而是在解释当取到最优解的时候，（用我上面的话来讲就是）最优点就落在，约束条件的圆心与目标函数的圆心相连直线与边界相交的那个点上。它是在解释为什么两者是平行的（线性相关的）。

其实按照我之前的理解来就好了，图中的梯度只画了一个目标函数的，容易搞混了，在红点处其实还有一个反方向的约束条件的梯度。

可见对于不等式约束，只要满足一定的条件，依然可以使用拉格朗日乘子法解决，这里的条件便是 KKT 条件。接下来给出形式化的 KKT 条件 首先给出形式化的不等式约束优化问题：

列出 Lagrangian 得到无约束优化问题：

经过之前的分析（算上拉格朗日乘子法处理等式约束那一篇文章的），便得知加上不等式约束后可行解x（局部最优解或全局最优解，可能有多个，要代原式中判断）需要满足的就是以下的 KKT 条件：

注意这边L只对x求偏导。

满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。KKT 条件看起来很多直线搜索方法,无约束优化方法,约束优化方法，其实很好理解:

(1) ：拉格朗日取得可行解的必要条件；

(2) ：这就是以上分析的一个比较有意思的约束，称作松弛互补条件；

(3)～～(4) ：初始的约束条件；

(5) ：不等式约束的 Lagrange Multiplier 需满足的条件。

一个简单的例子

其实这边有个问题，约束函数一般是取到等号的，不然很有可能就无解了。

还有两个约束就是原本的不等式约束

用这6个等式联立方程组解出x，

就好了。在例子原文中作者啰嗦了一大堆。但实际上就是这个道理。不过对于这种求解方程组的工作，会有一些更高效的方法去做。如SMO算法。以后有时间会再详细讲解的。

SVM 中的支持向量便是来自于此，需要注意的是 KKT 条件与对偶问题也有很大的联系，下一篇文章就是拉格朗日对偶。

从拉格朗日乘子法到KKT条件，讲了这么多，对于拉格朗日乘子

或者

在做什么似乎还没有明了的讲过。

拉格朗日乘子加入到目标函数中，有两个作用：

将约束函数引入到目标函数中，转化为无约束问题，不满足约束条件的解会使得目标函数无穷大，故而无解。引入拉格朗日乘子另一个最大的作用就是将约束条件与目标函数混在一起，使得我们可以同时计算目标函数的梯度与约束条件的梯度，根据相关的性质从而找到我们想找到的局部最优解或者全局最优解。

参考文章：

约束优化方法之拉格朗日乘子法与KKT条件

解密SVM系列（一）：关于拉格朗日乘子法和KKT条件

（编辑：海南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!