文档章节

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

tantexian
 tantexian
发布于 2017/07/07 00:05
字数 1588
阅读 19
收藏 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
粉丝 198
博文 492
码字总数 721387
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

配置Spring的注解支持

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 配置Spring的注解支持 以上也提到了使用注解来配...

凯哥学堂
29分钟前
0
0
关于Spring Aop存在的一点问题的思考

在本人前面的文章Spring Aop原理之切点表达式解析中讲解了Spring是如何解析切点表达式的,在分析源码的时候,出现了如下将要讲述的问题,我认为是不合理的,后来本人单纯使用aspectj进行试验...

爱宝贝丶
31分钟前
0
0
JavaScript 概述

JavaScript是面向Web的编程语言。绝大多数现代网站都使用了JavaScript,并且所有的现代Web浏览器——基于桌面系统、游戏机、平板电脑和智能手机的浏览器——均包含了JavaScript解释器。这使得...

Mr_ET
今天
0
0
Java Run-Time Data Areas(Java运行时数据区/内存分配)

Java运行时数据区(内存分配) 本文转载官网 更多相关内容可查看官网 中文翻译可参考 2.5. Run-Time Data Areas The Java Virtual Machine defines various run-time data areas that are use...

lichuangnk
今天
0
0
docker learn :services docker-compose.yml

docker-compose.yml定义了服务的运行参数 version: "3" services: web: # replace username/repo:tag with your name and image details image: hub.c.163.com/dog948453219/friendlyhello d......

writeademo
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部