广州电子商城网站,网站建设需要学什么,建设局主要负责什么,网页设计网站官网from:https://blog.csdn.net/xianlingmao/article/details/7919597
在求取有约束条件的优化问题时#xff0c;拉格朗日乘子法#xff08;Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法#xff0c;对于等式约束的优化问题#xff0c;可以应用拉格朗日乘子法去求…from:https://blog.csdn.net/xianlingmao/article/details/7919597
在求取有约束条件的优化问题时拉格朗日乘子法Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法对于等式约束的优化问题可以应用拉格朗日乘子法去求取最优值如果含有不等式约束可以应用KKT条件去求取。当然这两个方法求得的结果只是必要条件只有当是凸函数的情况下才能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化。之前学习的时候只知道直接应用两个方法但是却不知道为什么拉格朗日乘子法Lagrange Multiplier) 和KKT条件能够起作用为什么要这样去求取最优值呢
本文将首先把什么是拉格朗日乘子法Lagrange Multiplier) 和KKT条件叙述一下然后开始分别谈谈为什么要这样求最优值。
一. 拉格朗日乘子法Lagrange Multiplier) 和KKT条件
通常我们需要求解的最优化问题有如下几类
(i) 无约束优化问题可以写为: min f(x);
(ii) 有等式约束的优化问题可以写为: min f(x), s.t. h_i(x) 0; i 1, ..., n
(iii) 有不等式约束的优化问题可以写为 min f(x), s.t. g_i(x) 0; i 1, ..., n h_j(x) 0; j 1, ..., m
对于第(i)类的优化问题常常使用的方法就是Fermat定理即使用求取f(x)的导数然后令其为零可以求得候选最优值再在这些候选值中验证如果是凸函数可以保证是最优解。
对于第(ii)类的优化问题常常使用的方法就是拉格朗日乘子法Lagrange Multiplier) 即把等式约束h_i(x)用一个系数与f(x)写为一个式子称为拉格朗日函数而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导令其为零可以求得候选值集合然后验证求得最优值。
对于第(iii)类的优化问题常常使用的方法就是KKT条件。同样地我们把所有的等式、不等式约束与f(x)写为一个式子也叫拉格朗日函数系数也称拉格朗日乘子通过一些条件可以求出最优值的必要条件这个条件称为KKT条件。
(a) 拉格朗日乘子法Lagrange Multiplier)
对于等式约束我们可以通过一个拉格朗日系数a 把等式约束和目标函数组合成为一个式子L(a, x) f(x) a*h(x), 这里把a和h(x)视为向量形式a是横向量h(x)为列向量之所以这么写完全是因为csdn很难写数学公式只能将就了.....。
然后求取最优值可以通过对L(a,x)对各个参数求导取零联立等式进行求取这个在高等数学里面有讲但是没有讲为什么这么做就可以在后面将简要介绍其思想。
(b) KKT条件
对于含有不等式约束的优化问题如何求取最优值呢常用的方法是KKT条件同样地把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a, b, x) f(x) a*g(x)b*h(x)KKT条件是说最优值必须满足以下条件
1. L(a, b, x)对x求导为零
2. h(x) 0;
3. a*g(x) 0;
求取这三个等式之后就能得到候选最优值。其中第三个式子非常有趣因为g(x)0如果要满足这个等式必须a0或者g(x)0. 这是SVM的很多重要性质的来源如支持向量的概念。
二. 为什么拉格朗日乘子法Lagrange Multiplier) 和KKT条件能够得到最优值
为什么要这么求能得到最优值先说拉格朗日乘子法设想我们的目标函数z f(x), x是向量, z取不同的值相当于可以投影在x构成的平面曲面上即成为等高线如下图目标函数是f(x, y)这里x是标量虚线是等高线现在假设我们的约束g(x)0x是向量在x构成的平面或者曲面上是一条曲线假设g(x)与等高线相交交点就是同时满足等式约束条件和目标函数的可行域的值但肯定不是最优值因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部使得新的等高线与目标函数的交点的值更大或者更小只有到等高线与目标函数的曲线相切的时候可能取得最优值如下图所示即等高线和目标函数的曲线在该点的法向量必须有相同方向所以最优值必须满足f(x)的梯度 a* g(x)的梯度a是常数表示左右两边同向。这个等式就是L(a,x)对参数求导的结果。上述描述我不知道描述清楚没如果与我物理位置很近的话直接找我我当面讲好理解一些注下图来自wiki。
而KKT条件是满足强对偶条件的优化问题的必要条件可以这样理解我们要求min f(x), L(a, b, x) f(x) a*g(x) b*h(x)a0我们可以把f(x)写为max_{a,b} L(a,b,x)为什么呢因为h(x)0, g(x)0现在是取L(a,b,x)的最大值a*g(x)是0所以L(a,b,x)只有在a*g(x) 0的情况下才能取得最大值否则就不满足约束条件因此max_{a,b} L(a,b,x)在满足约束条件的情况下就是f(x)因此我们的目标函数可以写为 min_x max_{a,b} L(a,b,x)。如果用对偶表达式 max_{a,b} min_x L(a,b,x)由于我们的优化是满足强对偶的强对偶就是说对偶式子的最优值是等于原问题的最优值的所以在取得最优值x0的条件下它满足 f(x0) max_{a,b} min_x L(a,b,x) min_x max_{a,b} L(a,b,x) f(x0)我们来看看中间两个式子发生了什么事情 f(x0) max_{a,b} min_x L(a,b,x) max_{a,b} min_x f(x) a*g(x) b*h(x) max_{a,b} f(x0)a*g(x0)b*h(x0) f(x0)
可以看到上述加黑的地方本质上是说 min_x f(x) a*g(x) b*h(x) 在x0取得了最小值用fermat定理即是说对于函数 f(x) a*g(x) b*h(x)求取导数要等于零即
f(x)的梯度a*g(x)的梯度 b*h(x)的梯度 0
这就是kkt条件中第一个条件L(a, b, x)对x求导为零。
而之前说明过a*g(x) 0这时kkt条件的第3个条件当然已知的条件h(x)0必须被满足所有上述说明满足强对偶条件的优化问题的最优值都必须满足KKT条件即上述说明的三个条件。可以把KKT条件视为是拉格朗日乘子法的泛化。 --------------------- 作者xianlingmao 来源CSDN 原文https://blog.csdn.net/xianlingmao/article/details/7919597?utm_sourcecopy 版权声明本文为博主原创文章转载请附上博文链接
