发文章
发文工具
撰写
网文摘手
文档
视频
思维导图
随笔
相册
原创同步助手
其他工具
图片转文字
文件清理
AI助手
留言交流
对偶是最优化方法里的一种方法,它将一个最优化问题转换成另外一个问题,二者是等价的。拉格朗日对偶是其中的典型例子。对于如下带等式约束和不等式约束的优化问题:
与拉格朗日乘数法类似,构造广义拉格朗日函数:
必须满足 的约束。原问题为:
即先固定住x,调整拉格朗日乘子变量,让函数L取极大值;然后控制变量x,让目标函数取极小值。原问题与我们要优化的原始问题是等价的。
对偶问题为:
和原问题相反,这里是先控制变量x,让函数L取极小值;然后控制拉格朗日乘子变量,让函数取极大值。
一般情况下,原问题的最优解大于等于对偶问题的最优解,这称为弱对偶。在某些情况下,原问题的最优解和对偶问题的最优解相等,这称为强对偶。
强对偶成立的一种条件是Slater条件:一个凸优化问题如果存在一个候选x使得所有不等式约束都是严格满足的,即对于所有的i都有gi (x)<0,不等式不取等号,则强对偶成立,原问题与对偶问题等价。注意,Slater条件是强对偶成立的充分条件而非必要条件。
拉格朗日对偶在机器学习中的典型应用是支持向量机。
来自: SAP虾客 > 《待分类》
0条评论
发表
请遵守用户 评论公约
用一张图理解SVM的脉络
如果原问题和对偶问题都存在最优解,则对偶问题的最优值不大于原问题的最优值,即:在这里我们看到了求解对偶问题的另外一个好处,对偶...
支持向量机入门系列(4)
与原问题(1)相对应,我们把上面的问题(2)称作拉格朗日对偶问题(Lagrange dual problem)。显然,对偶问题的最优值d*就是我们可以获得的p*的最优下界,也就是所有下界中离p*最近的一个,它们的关系...
支持向量机SVM(二)
至于为什么引入拉格朗日算子可以求出极值,原因是f(w)的dw变化方向受其他不等式的约束,dw的变化方向与f(w)的梯度垂直时才能获得极值,...
人工智能的本质是最优化过程
人工智能的本质是最优化过程模型三要素。fi(x)和hj(x)作为约束函数,分不等式约束和等式约束两类,约束函数用来限制可能空间,如果不存...
MOMOAN
一. 拉格朗日乘子法(Lagrange Multiplier) 和KKT条件。二. 为什么拉格朗日乘子法(Lagrange Multiplier) 和KKT条件能够得到最优值?如...
对偶和KKT条件
什么是对偶?这便是为什么要有对偶算法这个算法的一个原因,因为对偶问题都是凸问题(其实是凹问题,凹问题加个负号就是凸问题了),而...
机器学习----最大熵模型 原理详解
拉格朗日对偶性。上面的拉格朗日乘数法理论中,我们最终将问题转化为了求拉格朗日函数的稳定点,但是,有时直接求稳定点是不容易的,因...
简易解说拉格朗日对偶(Lagrange duality)
简易解说拉格朗日对偶(Lagrange duality)也就是说原始问题的最优值不小于对偶问题的最优值,但是我们要通过对偶问题来求解原始问题,...
KKT 条件
KKT 条件。KKT 条件:通常我们要求解的最优化条件有如下三种:有等式约束的优化问题:通常使用拉格朗日乘子法,即把等式约束用拉格朗日乘子和优化问题合并为一个式子,通过对各个变量求导使其为零,求...
微信扫码,在手机上查看选中内容