文档章节

简易解说拉格朗日对偶(Lagrange duality)

tantexian
 tantexian
发布于 2017/07/07 00:05
字数 1588
阅读 22
收藏 0

请尊重原创知识,本人非常愿意与大家分享 转载请注明出处:http://www.cnblogs.com/90zeng/ 作者:博客园-太白路上的小混混

引言:尝试用最简单易懂的描述解释清楚机器学习中会用到的拉格朗日对偶性知识,非科班出身,如有数学专业博友,望多提意见!

http://www.cnblogs.com/90zeng/p/Lagrange_duality.html

 

1.原始问题

假设是定义在上的连续可微函数(为什么要求连续可微呢,后面再说,这里不用多想),考虑约束最优化问题:

称为约束最优化问题的原始问题。

现在如果不考虑约束条件,原始问题就是:

因为假设其连续可微,利用高中的知识,对求导数,然后令导数为0,就可解出最优解,很easy. 那么,问题来了(呵呵。。。),偏偏有约束条件,好烦啊,要是能想办法把约束条件去掉就好了,bingo! 拉格朗日函数就是干这个的。

 

 

引进广义拉格朗日函数(generalized Lagrange function):

不要怕这个式子,也不要被拉格朗日这个高大上的名字给唬住了,让我们慢慢剖析!这里是拉格朗日乘子(名字高大上,其实就是上面函数中的参数而已),特别要求.

 

 

现在,如果把看作是关于的函数,要求其最大值,即

再次注意是一个关于的函数,经过我们优化(不要管什么方法),就是确定的值使得取得最大值(此过程中把看做常量),确定了的值,就可以得到的最大值,因为已经确定,显然最大值就是只和有关的函数,定义这个函数为:

其中 

 

下面通过是否满足约束条件两方面来分析这个函数:

  • 考虑某个违反了原始的约束,即或者,那么:

  注意中间的最大化式子就是确定的之后的结果,若,则令,如果,很容易取值使得

 

  • 考虑满足原始的约束,则:,注意中间的最大化是确定的过程,就是个常量,常量的最大值显然是本身.

 

通过上面两条分析可以得出:

那么在满足约束条件下:

与原始优化问题等价,所以常用代表原始问题,下标 P 表示原始问题,定义原始问题的最优值:

 

 

原始问题讨论就到这里,做一个总结:通过拉格朗日这位大神的办法重新定义一个无约束问题(大家都喜欢无拘无束),这个无约束问题等价于原来的约束优化问题,从而将约束问题无约束化!

 

2.对偶问题

定义关于的函数:

注意等式右边是关于的函数的最小化,确定以后,最小值就只与有关,所以是一个关于的函数. 

 

考虑极大化,即

  

这就是原始问题的对偶问题,再把原始问题写出来:

形式上可以看出很对称,只不过原始问题是先固定中的,优化出参数,再优化最优,而对偶问题是先固定,优化出最优,然后再确定参数.

定义对偶问题的最优值:

 

3. 原始问题与对偶问题的关系

定理:若原始问题与对偶问题都有最优值,则

证明:对任意的,有

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

也就是说原始问题的最优值不小于对偶问题的最优值,但是我们要通过对偶问题来求解原始问题,就必须使得原始问题的最优值与对偶问题的最优值相等,于是可以得出下面的推论:

推论:设分别是原始问题和对偶问题的可行解,如果,那么分别是原始问题和对偶问题的最优解。

所以,当原始问题和对偶问题的最优值相等:时,可以用求解对偶问题来求解原始问题(当然是对偶问题求解比直接求解原始问题简单的情况下),但是到底满足什么样的条件才能使的呢,这就是下面要阐述的 KKT 条件

 

4. KKT 条件

定理:对于原始问题和对偶问题,假设函数是凸函数,是仿射函数(即由一阶多项式构成的函数,f(x)=Ax + b, A是矩阵,x,b是向量);并且假设不等式约束是严格可行的,即存在,对所有,则存在,使得是原始问题的最优解,是对偶问题的最优解,并且

 

 

定理:对于原始问题和对偶问题,假设函数是凸函数,是仿射函数(即由一阶多项式构成的函数,f(x)=Ax + b, A是矩阵,x,b是向量);并且假设不等式约束是严格可行的,即存在,对所有,则分别是原始问题和对偶问题的最优解的充分必要条件是满足下面的Karush-Kuhn-Tucker(KKT)条件:

关于KKT 条件的理解:前面三个条件是由解析函数的知识,对于各个变量的偏导数为0(这就解释了一开始为什么假设三个函数连续可微,如果不连续可微的话,这里的偏导数存不存在就不能保证),后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束。

特别注意当时,由KKT对偶互补条件可知:,这个知识点会在 SVM 的推导中用到.

 

5. 总结

一句话,某些条件下,把原始的约束问题通过拉格朗日函数转化为无约束问题,如果原始问题求解棘手,在满足KKT的条件下用求解对偶问题来代替求解原始问题,使得问题求解更加容易。

请尊重原创知识,本人非常愿意与大家分享 转载请注明出处:http://www.cnblogs.com/90zeng/ 作者:博客园-太白路上的小混混

© 著作权归作者所有

共有 人打赏支持
tantexian
粉丝 201
博文 503
码字总数 725322
作品 0
成都
架构师
机器学习系列(23)_SVM碎碎念part6:对偶和拉格朗日乘子

原文地址:SVM - Understanding the math - duality-lagrange-multipliers/ by Brandon Amos 感谢参与翻译同学:@Fox && @程超 && @吕征达 时间:2018年1月。 出处:http://blog.csdn.net/ha......

yaoqiang2011
01/16
0
0
一步一步走向锥规划 - QP [续]

Active set strategies Active set的基本思想和Simplex方法(Simplex方法参考 “一步一步走向锥规划 - LP”)的基本思想大体一致,就是要先找到一个可行解 feasible solution, fs, 然后沿着...

史春奇
2017/11/22
0
0
机器学习基础-高质量博客收藏

SVM的理解 拉格朗日对偶 - 博客频道 - CSDN.NET(完美) SVM的三层境界 支持向量机通俗导论(理解SVM的三层境界)(后面有点乱,一般般) 【整理】深入理解拉格朗日乘子法(Lagrange Multip...

陈司空
2017/04/15
0
0
拉格朗日乘子法和KKT条件

转载自:http://www.cnblogs.com/zhangchaoyang/articles/2726873.html#3592012 拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush-Kuhn-Tucker)条件是求解约束优化问题的重要方法,在有等式...

weixin_37589896
2017/11/27
0
0
SVM学习笔记-对偶形式的SVM

SVM学习笔记第二篇 SVM学习笔记-线性支撑向量机 SVM学习笔记-对偶形式的SVM SVM学习笔记-核函数与非线性SVM SVM学习笔记-软间隔SVM 回顾 上一篇笔记讲述了一个模型:线性支撑向量机。其目的是...

robin_Xu_shuai
2017/08/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx的简单使用:负载均衡

nginx:反向代理的服务器;用户发送请求到nginx,nginx把请求发送给真正的服务器,等待服务器处理完数据并返回,再把数据发送给用户。 nginx作为一个反向代理服务器,能缓存我们项目的静态文...

osliang
13分钟前
1
0
网站title标题被改并被百度网址安全中心提醒的解决办法

国庆假日期间我们Sine安全接到众多网站站长求助网站标题被改导致在百度搜索中百度安全中心提醒被拦截,导致网站正常用户无法浏览网站被跳转到一些菠菜du博网站,而且很明显的一个特征就是在百...

网站安全
15分钟前
1
0
JDK版本与major.minor version的对照关系

其实,只需要记住jdk6对于major.minor version 50即可,其他版本自行计算即可。 ---------------------

码代码的小司机
17分钟前
1
0
Gitlab安装

具体步骤如下: sudo yum install -y curl policycoreutils-python openssh-server cronie sudo lokkit -s http -s ssh sudo yum install postfix sudo service postfix start sudo chkconfi......

很好亦平凡ms
25分钟前
1
0
C++基础教程面向对象学习笔记及心得感悟[图]

C++基础教程面向对象学习笔记及心得感悟[图] 使用友元函数重载算术运算符: C ++中一些最常用的运算符是算术运算符 - 即加号运算符(+),减运算符( - ),乘法运算符(*)和除法运算符(/...

原创小博客
26分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部