admin 管理员组

文章数量: 1087652

拉格朗日函数、对偶上升法、对偶分解法

    • 拉格朗日函数
        • 拉格朗日乘子法
        • KKT条件
    • 对偶上升法
        • 共轭函数
        • 拉格朗日对偶函数
        • 线性约束下拉格朗日函数对偶函数的共轭形式
        • 对偶问题
        • 对偶上升法
    • 对偶分解法

拉格朗日函数

用于解决满足约束条件的最值问题
注意，该方法均只能保证求得的结果是必要条件。只有当原函数是凸函数时，才能保证求得的结果是充要条件

拉格朗日乘子法

适用于具有等式约束的最大值/最小值问题

minf(x)s.t.ormaxf(x)φi(x)=0,i=1,2,…,n}⇒{L(x,λ)=f(x)+∑ni=1λiφi(x)∇L(x,λ)=0(1) (1) min f ( x ) or max f ( x ) s.t. φ i ( x ) = 0 , i = 1 , 2 , … , n } ⇒ { L ( x , λ ) = f ( x ) + ∑ i = 1 n λ i φ i ( x ) ∇ L ( x , λ ) = 0
其中 L(x,λ) L ( x , λ ) 被称为拉格朗日函数，系数 λ λ 被称为拉格朗日乘子或者对偶变量。通过 ∇ ∇ 计算后，可得到候选集，然后从候选集中验算选择满足条件的结果即可。（ ∇ ∇ ：依次对函数所有自变量求偏导）

KKT条件

适用于同时具有等式约束和不等式约束的最小值问题

mins.t.f(x)φi(x)=0,i=1,2,…,nhj(x)≤0,j=1,2,…,m⎫⎭⎬⎪⎪⇒L(x,λ,ι)=f(x)+∑i=1nλiφi(x)+∑j=1mιjhj(x)(2) (2) min f ( x ) s.t. φ i ( x ) = 0 , i = 1 , 2 , … , n h j ( x ) ≤ 0 , j = 1 , 2 , … , m } ⇒ L ( x , λ , ι ) = f ( x ) + ∑ i = 1 n λ i φ i ( x ) + ∑ j = 1 m ι j h j ( x )
上述式子成立的 必要前提是KKT条件：
KKT s.t.L(x,λ,ι)对x求偏导存在λi(x)=0,i=1,2,…,nιjhj(x)=0,ιj≥0,j=1,2,…,m(3) (3) KKT s.t. L ( x , λ , ι ) 对 x 求 偏 导 存 在 λ i ( x ) = 0 , i = 1 , 2 , … , n ι j h j ( x ) = 0 , ι j ≥ 0 , j = 1 , 2 , … , m
其中 λ,ι λ , ι 被称为拉格朗日乘子或者对偶变量

下面直观地说下为什么会有第三个条件要成立
由于 ιj≥0,hj(x)≤0 ι j ≥ 0 , h j ( x ) ≤ 0 ，所以 ιjhj(x)≤0 ι j h j ( x ) ≤ 0 ；又因为 λi(x)=0 λ i ( x ) = 0 ，所以 L(x,λ,ι) L ( x , λ , ι ) 仅有在 ιjhj(x)=0 ι j h j ( x ) = 0 下才能取得最大值，故这是KKT第三个条件必须要成立的原因——即第三个条件满足时，它意味着有 maxL(x,λ,ι)=f(x) max L ( x , λ , ι ) = f ( x ) ，接下来就是求解 minf(x) min f ( x ) ，所以该过程又可记为： minf(x)=minx

本文标签： 拉格朗日函数对偶上升法对偶分解法

版权声明：本文标题：拉格朗日函数、对偶上升法、对偶分解法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700323932a396989.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。