优化问题的拉格朗日Lagrange对偶法原理

这篇具有很好参考价值的文章主要介绍了优化问题的拉格朗日Lagrange对偶法原理。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

首先我们定义一般形式的求解x的优化问题:

  • 表示优化的目标函数,上述为最小优化,实际上最大优化可以改写为的形式
  • 表示第i个不等式约束
  • 表示等式约束

1. Lagrange对偶问题

上述优化问题的拉格朗日Lagrange对偶法求解,是将上述带约束的目标优化问题改写为如下无约束的Lagrange函数式子。

优化问题的拉格朗日Lagrange对偶法原理

上述Lagrange函数式子存在如下对偶函数,其是Lagrange函数关于取最小值,即:

优化问题的拉格朗日Lagrange对偶法原理

对偶函数是关于的函数,很显然其是原来Lagrange函数式子的下界,假设优化问题存在最优解,当时,此时存在最优目标大于对偶函数。

优化问题的拉格朗日Lagrange对偶法原理

Lagrange对偶法即是通过最大化原问题Lagrange对偶函数,从而逼近原问题的下界来求解原问题最优解,因为的参数远小于原问题的求解参数,因此转换为对偶问题后,求解更为简单。

2. 强弱对偶性

接下来的问题是通过对偶函数得到下界同原问题的最优解之间的差距是多少?当对偶函数得到下界同原问题的最优解相等时,称之为强对偶性,反之称为弱对偶性。而这个差值称之为最优对偶间距

Slater约束准则给出为强对偶性成立的条件:

  • 原问题是凸问题
  • 存在内点使得所有的不等式约束严格成立即,如果是仿射不等式时取等于也是可行的。

3. 如何转换为对偶函数

因为对偶函数是Lagrange函数关于取最小值,假设是关于x的凸函数,且存在关于x的最小值,此时存在使得关于x的偏导数为0,则存在对偶函数为。

假设为对偶函数为也是关于可导,此时最优值存在

此外最优值要使对偶函数存在最大值,由于,因此:

上述五个条件构成了在Slater约束准则下求解优化问题最优解存在的KKT条件:

例子1:线性规划问题

首先我们定义一个一般性的线性规划问题,其中x是表示求解向量,该问题可解是指存在唯一解。

Lagrange函数式子表示为:

优化问题的拉格朗日Lagrange对偶法原理

Lagrange函数仅当优化问题的拉格朗日Lagrange对偶法原理时,才是有界的,此时对偶函数为,否则为负无穷,因此原问题可以转换为求解对偶问题的最大值,此时Slater约束准则,对偶问题的解也是原问题的最优解。

优化问题的拉格朗日Lagrange对偶法原理

例子2:最小二乘法

考虑以下问题:

Lagrange函数式子表示为:

优化问题的拉格朗日Lagrange对偶法原理

Lagrange函数关于x是二阶可导的凸函数,存在最小值的解:

优化问题的拉格朗日Lagrange对偶法原理

此时对偶函数为下式,此时原问题被转换为一个无约束的对偶问题的求解。

优化问题的拉格朗日Lagrange对偶法原理

4. 最优问题的转换

接下来我们考虑更为通用的优化问题形式,之前讨论了不等式约束中的大于和小于可以通过变换符号进行调整,实际上我们可以通过新增求解变量将不等式约束转换为等式约束:

优化问题的拉格朗日Lagrange对偶法原理

结合上述对偶问题的转换,我们可以将通用的优化问题形式转换为等式约束问题,甚至无约束的问题,下一篇我们将介绍等式约束优化问题和无约束优化问题的通用求解方法。文章来源地址https://www.toymoban.com/news/detail-432901.html

到了这里,关于优化问题的拉格朗日Lagrange对偶法原理的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机器人中的数值优化(十四)——罚函数法(Penalty Method)、障碍函数法(Barrier Method)、拉格朗日松弛法(Lagrangian Relaxation)

       本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考,主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等,本系列文章篇数较多,不定期更新,上半部分介绍无约束优化,下半部分介绍带约束的优化,中间会

    2024年02月04日
    浏览(38)
  • 计算机图形学中的曲线问题——拉格朗日插值曲线绘制实践

    限于篇幅,我们将在这篇文章中介绍拉格朗日插值曲线绘制实践,主文章链接: GGN_2015 计算机图形学中的曲线问题 在主文章中我们已经介绍了拉格朗日插值函数的绘制方法。给定一个函数必须通过的点的集合,保证任意两点 x x x 指不同,我们就能构造出一条拉格朗日插值函

    2024年02月14日
    浏览(43)
  • 单摆的动力学建模以及matlab仿真(牛顿法和拉格朗日方程法)

    有空再写 首先我们先确定广义坐标,并同时计算出来摆杆的转动惯量 接着列拉格朗日方程 计算动能(转动动能)  计算势能(取铰链处为零势能高度):  计算L 计算拉格朗日方程中的中间量   将上述的中间量带入拉格朗日方程,得到动力学模型: 变换一下形式:  当角

    2023年04月08日
    浏览(44)
  • 牛顿插值法、拉格朗日插值法、三次插值、牛顿插值多项式、拉格朗日插值多项式

    两点式线性插值 调用Matlab库函数 拉格朗日二次插值: 牛顿二次插值 结果分析:通过对比不同插值方法,可以看到在一定范围内(高次会出现龙格现象),插值次数越高,截断误差越小(插值结果越接近于真实函数值);同时,对于相同次数的插值,由于不同的插值方法它们

    2024年02月11日
    浏览(43)
  • 拉格朗日乘数法

    拉格朗日函数用于约束优化问题。约束优化问题简而言之就是在有一堆约束 Σ i = 1 g i ( x ) Sigma_{i=1} g_i(x) Σ i = 1 ​ g i ​ ( x ) 的情况下求目标函数 f ( x ) f(x) f ( x ) 的问题,说起来很抽象,直接来点例子看比较直观。 例1. 求 f ( x , y , z ) = x y z f(x,y,z)=xyz f ( x , y , z ) = x yz 在条件

    2024年02月09日
    浏览(39)
  • 【高等数学】拉格朗日乘数法

    #16 拉格朗日乘数法 所谓拉格朗日乘数法,是一种求 条件极值 的办法。所谓条件极值,就是在给定的约束条件下,求目标函数的极值。 符号解释:目标函数 u = f ( x , y ) u = f(x,y) u = f ( x , y ) , 约束条件 φ ( x , y ) = 0 varphi(x,y) = 0 φ ( x , y ) = 0 应用条件: f ( x , y ) f(x,y) f ( x , y

    2024年02月16日
    浏览(41)
  • MATLAB-拉格朗日插值运算

    在结点上给出结点基函数,接着做该基函数的线性组合,组合的系数为结点的函数值,这种插值多项式称为拉格朗日插值公式。通俗地说,就是通过平面上的两个点确定一条直线。该插值方法是一种较为基础的方法,同时该方法也较容易理解与实现。 拉格朗日插值多项式的表

    2024年02月06日
    浏览(40)
  • 浅谈拉格朗日插值法

    好像FFT要用到,所以就学习一手 版题 其意义在于: 理解一下: 就是把一个足球踢出去,假设球始终在一个平面上飞行,它的轨迹就可以抽象为 (f(x)) (假设这个函数至于时间有关) 现在你有一些照片,所以你可以得到某几个时间点球的位置,想要还原出这个函数 (f(x)) 的

    2023年04月25日
    浏览(36)
  • 解读 拉格朗日插值法python,保你学明白

    什么是插值法 插值法是一种数学方法,用于在已知数据点(离散数据)之间插入数据,以生成连续的函数曲线。 插值法可以用于确定一个未知数据点的值,并简化复杂的数学计算过程。 插值法的应用广泛,如统计学、工程学、科学研究等领域。 拉格朗日插值法的原理 格朗

    2024年02月08日
    浏览(43)
  • 22matlab数据分析 拉格朗日插值(matlab程序)

    1. 简述        第一部分:问题分析 (1)实验题目:拉格朗日插值算法 具体实验要求:要求学生运用拉格朗日插值算法通过给定的平面上的n个数据点,计算拉格朗日多项式Pn(x)的值,并将其作为实际函数f(x)的估计值。用matlab编写拉格朗日插值算法的代码,要求代码实现用户

    2024年02月15日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包