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的点
参考:李航,统计学习方法