【约束非线性优化】拉格朗日法与KKT

拉格朗日乘子法（Lagrange Multiplier)是解决有约束条件的优化问题的重要方法

问题

回忆非线性最优化的问题表达形式

无约束优化问题

minf(x)
另一篇文章中给出了几种方法，分别是对一维问题的搜索法、梯度下降法（和变种）、牛顿法（和变种）

等式约束优化问题

minf(x),
s.t. hi(x)=0;i=1,…,n

用拉格朗日乘子法解决（本文内容）

不等式约束优化问题

minf(x),
s.t. gi(x)<=0;i=1,…,n
hi(x)=0;i=1,…,n

常用KKT条件（本文内容）

拉格朗日乘子法

一个看似可行的方案

考察这样的问题：
目标函数f(x)=f(x1,x2,…xm+p)
约束条件:{g1(x)=g1(x1,x2,...xm+p).........gp(x)=gp(x1,x2,...xm+p)

当然要求rank[∂g1∂x1...∂g1∂xm+p...........∂gp∂x1...∂gp∂xm+p]=p

移动变量位置，使得rank[∂g1∂x1...∂g1∂xp...........∂gp∂x1...∂gp∂xp]=p

那么，可以解出{xm+1=ψ1(x1,x2,...xm)...xm+p=ψp(x1,x2,...xm)

带入目标函数，得到
ϕ((x1,…,xm)=f(x1,…,xm,ψ1(x1,x2,…xm),…,ψp(x1,x2,…xm))(1-1)
这就转化为无约束最优化问题。

然而，显示的解出约束变量几乎是不可能的

拉格朗日乘子法的内容

引入辅助函数
F(x,λ)=f(x)+p∑r=1λrgr(x)
其中，x=(x1,…xm+p)

如果a是极值，那么存在λ，使得(a,λ)是F(x,λ)的临界点
也就是说{∂F∂xk=0∂F∂λr=gr=0

拉格朗日乘子法的证明

必要条件

用到(1-1)式
ϕ((x1,…,xm)=f(x1,…,xm,ψ1(x1,x2,…xm),…,ψp(x1,x2,…xm))在a取临界点
gr(x1,…,xm,ψ1(x1,x2,…xm),…,ψp(x1,x2,…xm))=0是恒等式

上式分别取偏导数，分别得到甲式和乙式。乙式与λ线性组合加到甲式上。(略)

得到：
∂f∂xi+p∑r=1λr∂gr∂xi+p∑j=1(∂f∂xm+j+p∑r=1λr∂gr∂xm+j)∂ψj∂xi=0(1-2)

选择λ,可以使得
∂f∂xm+j+p∑r=1λr∂gr∂xm+j=0(1-3)
带回(1-2)，得到：
∂f∂xi+p∑r=1λr∂gr∂xi=0(1-4)

(1-3)与(1-4)就是拉格朗日条件。

充分条件

a+h,a在可行域上M，g(a+h)−g(a)=0二阶展开，带入f(a+h)−f(a)后，可以找到取极值的条件。

Lagrange对偶函数

从上面知道，对于优化问题：
minf(x),
s.t. gi(x)<=0;i=1,…,n
hi(x)=0;i=1,…,n

对应的Lagrange函数是L(x,λ,v)=f(x)+m∑i=1λigi(x)+p∑i=1vihi(x)

那么Lagrange对偶函数是g(λ,v)=infxL(x,λ,v)

Lagrange对偶问题

maxg(λ,v)
s.t.λ≥0

性质1

即使原问题不是凸的，对偶函数也是凹函数

性质2

∀λ≥0,v有g(λ,v)≤p∗
（其中，p∗是原问题的最优值）

进一步说，如果Lagrange 对偶问题的最优解是 d∗，那么有d∗≤p∗
（称为 弱对偶性 ）

性质3

如果d∗=p∗称为 强对偶性

如果强对偶性成立，问题就更容易解决。
如果原问题是凸优化问题，且满足 slater 条件，那么强对偶性成立。

KKT条件

minf(x),
s.t. hj(x)=0;j=1,...,pgi(x)≤0;k=1,...,q

定义拉格朗日函数 L(X,λ,u)=f(X)+p∑j=1λjhj(X)+q∑k=1ukgk(X)

KKT条件
∂L∂X∣X=X∗=0(1)λj≠0,j=1,2,...,p(2)uk≥,0k=1,2,...q(3)ukg(X∗)=0,k=1,2,...q(4)hj(X∗)=0,j=1,2,...,p(5)gk(X∗)≤0k=1,2,...,q(6)

KKT条件的解释
(1)是对拉格朗日函数取极值时候带来的一个必要条件，
(2)是拉格朗日系数约束（同等式情况），
(3)是不等式约束情况，保证L(x,λ,u)<=f(x)
(4)是互补松弛条件，
(5)、(6)是原约束条件。
KKT条件是最优解的必要条件，当原问题是凸问题时，KKT条件也是充分条件

罚函数法

外点法

对于原问题：
minf(x),
s.t. hj(x)=0;j=1,...,pgi(x)≤0;k=1,...,q

转化为 F(x)=f(x)+σP(x)
其中，罚函数P(x)=p∑j=1∣hj(x)∣β+q∑k=1[max(0,−gk(x))]α
其中α,β>0，通常α=β=2

内点法

适用于只有不等式约束的问题
minf(x)
s.t. gi(x)≥0,i=1,2,…,m

定义状态函数G(x,r)=f(x)+rB(x)
其中，x接近D的边界时，B(x)→+∞
通常形式是B(x)=m∑i=11gi(x),B(x)=−m∑i=1loggi(x)
r是一个很小的正数，便可以保证当x接近D边界G(x,r)→+∞，当x在D内G(x,r)≈f(x)

问题转化为求解minG(x,r)

参考资料

施光燕：《最优化方法》，高等教育出版社
龚纯：《Matlab最优化计算》，电子工业出版社
David R. Anderson ：《数据、模型与决策–管理科学篇》，机械工业出版社
https://blog.csdn.net/johnnyconstantine/article/details/46335763
http://www.jianshu.com/p/96db9a1d16e9
http://www.cnblogs.com/zhangchaoyang/articles/2726873.html