Lagrange duality拉格朗日对偶性

2023-11-20 16:10

本文主要是介绍Lagrange duality拉格朗日对偶性,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Welcome To My Blog
在约束最优化问题(Constrained Optimization)中,常常利用拉格朗日对偶性(Lagrange duality)将原始问题转换为对偶问题,通过求解对偶问题而得到原始问题的解,该方法可用在最大熵模型(Maximum Entropy)和支持向量机(Support Vector Machine).

约束最优化问题

标准形式:
1.png
f(x),c(x),h(x)是定义在R^n上的连续可微函数,c(x)为不等式约束(inequality constraints),h(x)为等式约束(equality constraints).
几个重要定义:
可行点(feasible point):满足所有约束条件的x
可行域Ω(feasible set):所有可行点组成的集合
2.png
激活集A(x): 可行域中使得不等式约束取等的点以及满足等式约束的那些点
LICQ条件:对于激活集A(x),如果激活集中的点对应的约束的梯度向量线性无关,
3.png
那么称LICQ(linear independence constraint qualification)条件成立
这个条件说明了各个取等的约束都是独立的,不能被消掉,比如说其中两个等式约束为:
2x+3y=10
4x+6y=20
这两个等式实质上是一个等式,对应梯度向量分别为(2,3)^t,(4,6)^t,可能发现这两个向量线性相关

拉格朗日对偶

原始问题

刚才已经讨论过了,下图就被称为约束最优化问题的原始问题
1.png
拉格朗日在哪里?下面引进广义拉格朗日函数(generalized Lagrange function)
4.png
这里,x=(x1,x2,…xn)^t∈R,αi,βj是拉格朗日乘子,αi≥0.考虑x的函数:

5.png
下标P表示原始问题
假设给定某个x.如果x违反原始问题的约束条件,即存在某个i使得ci(w)>0或者存在某个j使得hj(x)≠0,那么有:
6.png
因为若某个i使约束ci(x)>0,则可令αi→+∞,若某个j使约束hj(x)≠0,则可令βj是βj*hj(x)→+∞
相反地,如果x满足等式与不等式约束条件,则有θp(x)=f(x),因此有
7.png
此时考虑极小化问题
8.png
这是与原始问题等价的,即它们有相同的解.
下图称为广义拉格朗日函数的极小极大问题,
9.png
这样一来就把原始问题表示为广义拉格朗日函数的极小极大问题
定义原始问题的最优值p*
10.png
p*称为原始问题的值

对偶问题

定义:
11.png
再考虑极大化θ,如下图
12.png
上面两个式子合起来写就是,下式称为拉格朗日函数的极大极小问题
13.png
可以将拉格朗日函数的极大极小问题表示为约束最优化问题:
14.png
称为原始问题的对偶问题.定义对偶问题的最优值
15.png
称为对偶问题的值

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

定理1:若原始问题和对偶问题都有最优值,则
16.png
证明:容易知道,对任意的α,β,x,有:
17.png

18.png
由于原始问题和对偶问题均有最优值,所以
19.png

16.png

推论1:设x*和α*,β*分别是原始问题和对偶问题的可行解,并且d*=p*,则x*和α*,β*分别是原始问题和对偶问题的最优解.

在某些条件下,原始问题和对偶问题的最优值相等,d*=p*.这时可以用解对偶问题替代解原始问题.
定理2:考虑之前的原始问题和对偶问题,假设函数f(x)和ci(x)是凸函数,hj(x)是仿射函数;并且假设不等式约束ci(x)是严格可行的,即存在x,对所有i有ci(x)<0,则存在x*,α*,β*,使x*是原始问题的解,α*,β*是对偶问题的解,并且p*=d*=L(x*,α*,β*)

定理3 考虑之前的原始问题和对偶问题,假设函数f(x)和ci(x)是凸函数,hj(x)是仿射函数;并且假设不等式约束ci(x)是严格可行的,那么x*,α*,β*分别是原始问题和对偶问题的最优解的充分必要条件是x*,α*,β*满足KKT条件(Karush-Kuhn-Tucker)
KKT条件:
20.png
特别地,
21.png
称为KKT的对偶互补条件.由此条件可知:若αi*>0,则ci(x*)=0.或者说,约束优化问题的解,要么αi*=0,要么x是激活集中的点,也就是满足ci(x*)=0的点
参考:李航,统计学习方法

这篇关于Lagrange duality拉格朗日对偶性的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/395840

相关文章

最优化方法Python计算:二次规划的拉格朗日算法

目标函数为二次式,约束条件为线性式的最优化问题称为二次规划。其一般形式为 { minimize 1 2 x ⊤ H x + c ⊤ x s.t.   A e q x − b e q = o A i q x − b i q ≥ o . \begin{cases} \text{minimize}\quad \frac{1}{2}\boldsymbol{x}^\top\boldsymbol{Hx}+\

先从路径优化开始学习FastPlanner之B样条曲线平滑路径(一):从拉格朗日插值到B样条曲线

参考B站视频学习 注:我会列出学习他人的博客,但我不涉及具体推导,原理讲解,旨在于理解必须概念后写代码出效果。 给若干点如何获得一条平滑的曲线? 两个方法插值、拟合 插值要经过给定点,拟合不用经过。 经典插值方法:拉格朗日插值法和牛顿插值法。 区别: 拉格朗日插值法 优点 简单易懂: 拉格朗日插值法公式简单直观,易于理解和实现。无需求导: 拉格朗日插值法不需要对函数进行求导,只需知

二次规划(Lagrange 方法,起作用集方法)

二次规划是非线性规划中一种特殊情形,它的目标函数是二次实函数,约束是线性的。由于二次规划比较简单,便于求解,且一些非线性规划可以转化为求解一系列二次规划问题,因此二次规划算法较早引起人们的重视,成为求解非线性规划的一个重要通径。二次规划的算法较多,本章介绍其中几个典型的方法,它们是 Lagrange 方法,起作用集方法,Lemke 方法和路径路踪法。 一、Lagrange 方法 考虑二次规划问

SVM(二)从拉格朗日对偶问题到SVM

2.1 拉格朗日对偶(Lagrange duality)      先抛开上面的二次规划问题,先来看看存在等式约束的极值问题求法,比如下面的最优化问题:              目标函数是f(w),下面是等式约束。通常解法是引入拉格朗日算子,这里使用来表示算子,得到拉格朗日公式为              L是等式约束的个数。     然后分别对w和求偏导,使得偏导数等

Python | C# | MATLAB 库卡机器人微分运动学 | 欧拉-拉格朗日动力学 | 混合动力控制

🎯要点 🎯正向运动学几何矩阵,Python虚拟机器人模拟动画二连杆平面机械臂 | 🎯 逆向运动学几何矩阵,Python虚拟机器人模拟动画三连杆平面机械臂 | 🎯微分运动学数学形态,Python模拟近似结果 | 🎯欧拉-拉格朗日动力学数学形态,Python模拟机器人操纵器推导的运动方程有效性 | 🎯运动规划算法,Python虚拟机器人和摄像头模拟离线运动规划算法 | 🎯移动导航卡尔曼

拉格朗日(Lagrange)插值曲线

简介         拉格朗日(Lagrange)插值曲线是最简单的一种插值曲线。假设给定控制点(Xi, Yi)(i = 0,1,…,n),拉格朗日差值方法构造出一个不超过n次的插值多项式Pn(x)。得到的差值公式为: 代码         此段代码用于从一致的一系列控制点生成一系列点构成的插值曲线。 //xmax 为控制点中最大的横坐标//xmin 为控制点中最小的横坐标/

自然数幂和 拉格朗日插值法和第二类斯特林数法

写在这里,目的是在以后需要看的时候不用再去网上抄(划掉) 求 s ( n ) = ∑ i = 1 n i k 求s(n)=\sum_{i=1}^n i^k 求s(n)=i=1∑n​ik 拉格朗日插值法 给定若干个点值,(x0,y0),(x1,y1),(xn,yn),它们的差值多项式 L ( x ) = ∑ i = 0 n y i ∗ ∏ j ≠ i x − x j x i − x j L(

拉格朗日插值法 C语言实现

/*  *作者:KDF5000  *功能:利用拉格朗日插值法求解近似值  *时间:2013.4.15  */   #include <stdio.h>   #include <stdlib.h>   #include <string.h>   //存放插值节点   struct Data{       double x;       double y;       struct Data *

SVM中的拉格朗日乘数法和KKT条件的深入解析

在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去求取。当然,这两个方法求得的结果只是必要条件,只有当是凸函数的情况下,才能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化。之前学习的时候,只知道直接应用两个方法,但是