拉格朗日对偶

简介: 拉格朗日对偶

对偶是最优化方法里的一种方法,它将一个最优化问题转换成另外一个问题,二者是等价的。拉格朗日对偶是其中的典型例子。对于如下带等式约束和不等式约束的优化问题:


image.png

与拉格朗日乘数法类似,构造广义拉格朗日函数:


image.png


image.png必须满足 image.png的约束。原问题为:


image.png





即先固定住x,调整拉格朗日乘子变量,让函数L取极大值;然后控制变量x,让目标函数取极小值。原问题与我们要优化的原始问题是等价的。


对偶问题为:

image.png


和原问题相反,这里是先控制变量x,让函数L取极小值;然后控制拉格朗日乘子变量,让函数取极大值。



一般情况下,原问题的最优解大于等于对偶问题的最优解,这称为弱对偶。在某些情况下,原问题的最优解和对偶问题的最优解相等,这称为强对偶。



强对偶成立的一种条件是Slater条件:一个凸优化问题如果存在一个候选x使得所有不等式约束都是严格满足的,即对于所有的i都有gi (x)<0,不等式不取等号,则强对偶成立,原问题与对偶问题等价。注意,Slater条件是强对偶成立的充分条件而非必要条件。



拉格朗日对偶在机器学习中的典型应用是支持向量机。


相关文章
|
机器学习/深度学习 算法
专题六数值微积分与方程求解-2
专题六数值微积分与方程求解
106 0
|
算法 Serverless
专题六数值微积分与方程求解-1
专题六数值微积分与方程求解
121 0
对偶定理的介绍
对偶定理:问题的对偶性与解的对偶性 一、引言 对偶定理是数学中的一个重要概念,它描述了问题的对偶性与解的对偶性之间的关系。通过对偶定理,我们可以将一个问题转化为其对偶问题,并通过解决对偶问题来解决原问题。本文将介绍对偶定理的概念、证明方法以及应用场景。 二、对偶定理的概念 对偶定理是指在某些情况下,一个问题的对偶问题与原问题具有相同的性质和结构。对偶问题是通过对原问题的变量、约束条件或目标函数进行转换而得到的。对偶定理认为,如果原问题的解存在,则对偶问题的解也存在,并且两个问题的解具有一种对应关系。 三、对偶定理的证明方法 对偶定理的证明方法通常是通过构造一个对偶映射来进行推导。具体步骤
283 0
|
数据采集 算法 Python
[模型]拉格朗日插值法
[模型]拉格朗日插值法
1238:一元三次方程求解 2020-12-27
1238:一元三次方程求解 2020-12-27
102 0
最优化理论(二)拉格朗日乘子法
最优化理论(二)拉格朗日乘子法
202 0
|
人工智能 开发者
求解拉格朗日乘子法 | 学习笔记
快速学习求解拉格朗日乘子法
求解拉格朗日乘子法 | 学习笔记