Chapter 5. Duality Notes

[摘要作者对Convex Optimization是入门级的level. 写这个notes主要是为了理清楚Duality的基础概念以及对以前一些知识盲点的澄清.]

1. 优化问题的标准形式:

minimize f0(x)subject tofi(x)≤0,i=1,...,mhi(x)=0,i=1,...,p

其中自变量x∈Rn，问题的定义域为D=⋂mi=0domfi⋂pi=1hi是非空集合. 目标问题的最优解为p∗. 这里没有不需要目标问题是凸优化问题.

2. Lagrange函数以及Lagrange对偶函数

Lagrange对偶的基本思想是在目标问题上添加约束条件的加权和，得到增广的目标函数,得到Lagrange函数,即:

L(x,λ,ν)=f0(x)+∑mi=1λifi(x)+∑pi=1νihi(x)

其定义域为domL=L×Rm×Rp，向量λ和ν称为对偶变量或者Lagrange乘子向量.

Lagrange对偶函数定义为g:Rm×Rp→R为Lagrange函数关于x取得的最小值:即

g(λ,ν)=infx∈DL(x,λ,ν)=infx∈D(f0(x)+∑mi=1λifi(x)+∑pi=1hi(x))

由上式可以看出对偶函数是一族关于(λ,ν)的仿射函数的逐点下确界，所以即使原始问题不是凸的，对偶函数总是凹函数.

3. 最优值的下界

对偶函数是原问题的最优值的下界,即对任意λ⪰0和ν下式总是成立:

g(λ,ν)≤p∗

见下图的直观理解:

Alt text

4. Lagrange对偶函数与共轭函数的关系

关于函数f:Rn→R的共轭函数f∗定义是:

f∗(y)=supx∈domf(yTx−f(x))

该函数是关于y的逐点上确界,而Lagrange对偶函数是关于(λ,ν)的逐点下确界，因此两者之间可以通过这个性质进行转换.

5. Lagrange对偶问题

对于任何一组(λ,ν)，Lagrange对偶函数给出了标准优化问题的最优解p∗的一个下界. 自然更关心的问题是，从Lagrange对偶函数，能够得到的最好下界是什么？将上述问题表达为优化问题:

maximize g(λ,ν)subject toλ⪰0

该问题最大化Lagrange对偶函数，称之为Lagrange对偶问题.
设该问题的最优解为d∗，可以得到d∗≤p∗，并且，即使标准优化问题不是凸优化问题，这里的不等式仍然成立!这个性质称为弱对偶性.
差值p∗−d∗称为原问题的最优对偶间隙.

将原标准优化问题转化成Lagrange对偶问题形式的重要意义在于，Larange对偶函数总是凸问题(极大化的目标函数是凹函数，且约束集合是凸集),相比原问题更容易求解得到d∗，而弱对偶不等式又给出了原问题最优值的下界. 实际上，因为Larange对偶问题的目标函数是凸问题，因此通常有d∗=p∗.

d∗=p∗，称为强对偶性. 当问题是凸问题并且满足下述Slater准则时，强对偶性成立.
Slater条件为:存在一个点x∈relintD,使得

fi(x)<0,i=1,...,m,Ax=b.

容易知道，满足上述条件的点x使得d∗=p∗.
当不等式约束函数fi有一些是仿射函数时，Slater条件可以适当放宽，对这些仿射函数不要求严格小于0，这是因为最优化问题取得最优解时，仿射函数总要求取值为0，否则p∗→≁.
一些结论:

线性规划问题，只要原问题可行，强对偶性总是成立.
QCQR问题: 具有二次目标函数和一个二次不等式约束的优化问题，强对偶性总是成立.

6.强弱对偶性的几何解释

见图:
Alt text

阴影部分为优化问题的定义域，直线为不等式(λ,ν,1)T(u,v,t)≥(λ,ν)定义的关于优化问题的支撑超平面. 注意到不等式法向量的最优一个分量不为0，因此这个超平面有时称为非竖直支撑超平面.
图中描述的优化问题不是凸优化问题，至少定义域不是凸集，因此最优对偶间隙大约0.

6.互补松弛性与KKT最优性条件

当强对偶性成立容易得到，

∑mi=1λi∗fi(x∗)=0

上式的每一行均大于0，因此有

λ∗ifi(x∗)=0,i,...m.

上式称为互补松弛性,对上式分解，容易得到

fi(x∗)<0⇒λ∗i=0λ∗i>0⇒fi(x∗)=0

上式意味着在最优解处，出了第i个约束起作用的情况，最优Lagrange乘子的第i项都为0.

令x∗和(λ∗,ν∗)分别是原问题和对偶问题的最优解，对偶间隙为0，因此:

▽f0(x∗)+∑mi=1λ∗i▽fi(x∗)+∑pi=1ν∗▽hi(x∗)=0

因此有Karush-Kuhn-Tucker(KKT)条件:

fi(x∗)≤0hi(x∗)=0λ∗i≥0λ∗ifi(x∗)=0▽f0(x∗)+∑mi=1λ∗i▽fi(x∗)+∑pi=1ν∗▽hi(x∗)=0

对于目标函数和约束函数可微的任何优化问题，如果强对偶性成立，那么原问题最优解和对偶问题最优解必须满足KKT条件.
对于目标函数和约束函数可微的凸优化问题，任意满足KKT条件的点分别是原、对偶问题的最优解，对偶间隙为0.

很多求解凸优化问题的方法可以认为或者理解为求解KKT条件的方法.
例如，SVM极优美的性质与KKT条件十分相关. 后续有空余时间再写一篇notes...

7. 扰动与灵敏度分析

当强对偶性成立时，对原问题的约束进行扰动，对偶问题最优变量为原问题最优值的灵敏度分析提供了很多有用的信息.
对原问题进行扰动之后的问题为，

minimize f0(x)subject tofi(x)≤ui,i=1,...,mhi(x)=vi,i=1,...,p

定义p∗(u,v)是扰动问题的最优解：

p∗(u,v)=inf{f0(x)|∋x∈D,fi(x)≤ui,i=1,...,m,hi(x)=vi,i=1,...,p}

当强对偶性成立时，总有

p∗(u,v)≥p∗(0,0)−λ∗Tu−v∗Tν.

其中，(λ∗,ν∗)是未扰动问题的对偶问题的最优解.

图例:
Alt text

假设p∗(u,v)在u=0和v=0处可微，强对偶性成立时，最优对偶变量λ∗,ν∗可以和p∗在u=0，v=0处的梯度联系起来:

λ∗i=φp∗(0,0)φuiν∗i=φp∗(0,0)φvi

因此，p∗(u,v)在u=0和v=0处可微且强对偶性成立，那么最优Lagrange乘子就是最优值关于约束扰动的局部灵敏度.

参考文献

Convex Optimization by Stephen Boyd and Lieven Vandenberghe
Convex Optimization Edx
Geometric View of Weak Duality
Essentials of Convex Optimization