整体理解对偶问题,slater,kkt条件
本文不做严谨的数学推导,只为了帮助小白能对优化问题,对偶问题,拉格朗日,slater,kkt有一个快速的整体把控
0.对偶问题,why?
对于一个优化问题,为什么我们要找它的对偶问题呢?
因为一个优化问题,无论是否为凸,其对偶问题一定为凸优化问题(下面解释)
那么为什么一定要找一个凸优化问题呢?
因为凸优化问题有一些很好的性质,比如
凸优化问题的局部最优解就是全局最优解
凸问题和其对偶问题解相等是kkt的充分必要条件
下面我们来一步步看.
1.给一个标准形式的优化问题
min
f
0
(
x
)
s.t.
f
i
(
x
)
≤
0
,
i
=
1
,
2
,
⋯
,
m
h
i
(
x
)
=
0
,
i
=
1
,
2
,
⋯
,
p
\begin{aligned} &\min f_{0}(x)\\ &\text { s.t. } \quad f_{i}(x) \leq 0, \quad i=1,2, \cdots, m\\ &h_{i}(x)=0, \quad i=1,2, \cdots, p \end{aligned}
minf0(x) s.t. fi(x)≤0,i=1,2,⋯,mhi(x)=0,i=1,2,⋯,p
定义域为
D
=
⋂
i
=
0
m
d
o
m
f
i
(
x
)
⋂
i
=
1
p
d
o
m
h
i
(
x
)
D=\bigcap ^{m}_{i=0}domf_{i}( x) \bigcap ^{p}_{i=1}domh_{i}( x)
D=i=0⋂mdomfi(x)i=1⋂pdomhi(x)
我们定义上面这个优化问题的拉格朗日函数为:
2.拉格朗日函数:
L ( x , λ , ν ) = f 0 ( x ) + ∑ i = 1 m λ ( i ) f i ( x ) + ∑ i = 1 p ν ( i ) h i ( x ) L(x, \lambda, \nu)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{(i)} f_{i}(x)+\sum_{i=1}^{p} \nu_{(i)} h_{i}(x) \quad L(x,λ,ν)=f0(x)+i=1∑mλ(i)fi(x)+i=1∑pν(i)hi(x)
3.拉格朗日对偶函数:
我们再定义这个拉格朗日函数的对偶问题为(inf是下确界的意思): g ( λ , ν ) = inf x ∈ D L ( x , λ , ν ) = inf x ∈ D ( f 0 ( x ) + ∑ i = 1 m λ ( i ) f i ( x ) + ∑ i = 1 p ν ( i ) h i ( x ) ) g(\lambda, \nu)=\inf _{x \in D} L(x, \lambda, \nu)=\inf _{x \in D}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{(i)} f_{i}(x)+\sum_{i=1}^{p} \nu_{(i)} h_{i}(x)\right) g(λ,ν)=x∈DinfL(x,λ,ν)=x∈Dinf(f0(x)+i=1∑mλ(i)fi(x)+i=1∑pν(i)hi(x))那么对于这个对偶函数,一定有:
4.对偶函数一定是凹的:
对偶函数一定是凹的.
简单的说明为什么
因为对偶函数是一族关于(λ,ν)的仿射函数(仿射函数是凹(且凸)的)的逐点下确界,所以一定是凹的.(注意对偶函数是关于(λ,ν)的,没有x.)
关于"几个凹函数的逐点下确界为凹"的一个大概解释:想象几个凹函数(如a<0的二次函数,如下图,取逐点下界,结果肯定是凹的(虚线))
5.最优值的下界:
对偶函数构成了原问题最优解
p
⋆
p^{\star}
p⋆的下界:
g
(
λ
,
ν
)
⩽
p
⋆
g(\lambda, \nu) \leqslant p^{\star}
g(λ,ν)⩽p⋆
因为原问题是
m
i
n
f
0
(
x
)
min f_{0}(x)
minf0(x),
对偶函数是
inf
x
∈
D
(
f
0
(
x
)
+
∑
i
=
1
m
λ
(
i
)
f
i
(
x
)
+
∑
i
=
1
p
ν
(
i
)
h
i
(
x
)
)
\inf _{x \in D}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{(i)} f_{i}(x)+\sum_{i=1}^{p} \nu_{(i)} h_{i}(x)\right)
x∈Dinf(f0(x)+i=1∑mλ(i)fi(x)+i=1∑pν(i)hi(x))
因为要解可行,则必有
（注意 lambda>=0,因为如果<0,求inf g的时候lamdba直接取负无穷的话就是下界,但是取负无穷作为下界没有任何意义,所以排除)
f
i
(
x
)
≤
0
,
h
i
(
x
)
=
0
,
\begin{aligned} \quad f_{i}(x) \leq 0, &h_{i}(x)=0, \end{aligned}
fi(x)≤0,hi(x)=0,
即对偶函数的后面两项小于等于0,所以为原问题的下界
6.对偶问题(上面是对偶函数,下面是对偶问题)
为了从对偶函数获得最好的(最逼近的)原问题下界,我们可以得到这样一个优化问题:
maximize
g
(
λ
,
ν
)
subject to
λ
⪰
0
\begin{array}{ll} \text { maximize } & g(\lambda, \nu) \\ \text { subject to } & \lambda \succeq 0 \end{array}
maximize subject to g(λ,ν)λ⪰0
这个对偶问题一定是一个凸优化的问题,无论原问题是不是.(max g相当于min -g,g为凹,-g为凸,且约束为凸)
对偶问题的最优解记为
b
⋆
b^{\star}
b⋆,由上面可知,
b
⋆
⩽
p
⋆
b^{\star} \leqslant p^{\star}
b⋆⩽p⋆即使原问题不是凸问题,依然有上式成立,称为弱对偶性
7.强对偶性
如果
b
⋆
=
p
⋆
b^{\star} = p^{\star}
b⋆=p⋆,强对偶性成立.
当原问题为凸(目标函数约束函数都为凸,等式约束为仿射),且满足Slater条件时,有
b
⋆
=
p
⋆
b^{\star} = p^{\star}
b⋆=p⋆,强对偶性成立.
下面来说slater条件
8.slater条件
Slater 条件: 对于凸问题,存在一点 x ∈ r e l i n t D x \in relint \mathcal{D} x∈relintD(原问题定义域的相对内部,D见最上面)使得下式成立
f i ( x ) < 0 , i = 1 , ⋯ , m , A x = b f_{i}(x)<0, \quad i=1, \cdots, m, \quad A x=b fi(x)<0,i=1,⋯,m,Ax=b注意slater条件是强对偶的充分条件,不是必要
弱slater条件:若不等式约束为仿射,只要可行域不为空,必有 b ⋆ = p ⋆ b^{\star} = p^{\star} b⋆=p⋆
9.kkt条件
目标函数和约束函数可微且强对偶性成立,那么任何一对原问题/对偶问题的最优解一定满足kkt条件
kkt条件:
f
i
(
x
⋆
)
⩽
0
,
i
=
1
,
⋯
,
m
h
i
(
x
⋆
)
=
0
,
i
=
1
,
⋯
,
p
λ
i
⋆
⩾
0
,
i
=
1
,
⋯
,
m
λ
i
⋆
f
i
(
x
⋆
)
=
0
,
i
=
1
,
⋯
,
m
∇
f
0
(
x
⋆
)
+
∑
i
=
1
m
λ
i
⋆
∇
f
i
(
x
⋆
)
+
∑
i
=
1
p
ν
i
⋆
∇
h
i
(
x
⋆
)
=
0
\begin{aligned} f_{i}\left(x^{\star}\right) & \leqslant 0, \quad i=1, \cdots, m \\ h_{i}\left(x^{\star}\right) &=0, \quad i=1, \cdots, p \\ \lambda_{i}^{\star} & \geqslant 0, \quad i=1, \cdots, m \\ \lambda_{i}^{\star} f_{i}\left(x^{\star}\right) &=0, \quad i=1, \cdots, m \\ \nabla f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} \nabla f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} \nabla h_{i}\left(x^{\star}\right)=0 & \end{aligned}
fi(x⋆)hi(x⋆)λi⋆λi⋆fi(x⋆)∇f0(x⋆)+i=1∑mλi⋆∇fi(x⋆)+i=1∑pνi⋆∇hi(x⋆)=0⩽0,i=1,⋯,m=0,i=1,⋯,p⩾0,i=1,⋯,m=0,i=1,⋯,m
当原问题是凸问题时，满足 KKT 条件的点也是原、对偶最优解。换言之, 如果函 数
f
i
f_{i}
fi是凸函数,
h
i
h_{i}
hi 是仿射函数,
x
~
,
λ
~
,
ν
~
\tilde{x}, \tilde{\lambda}, \tilde{\nu}
x~,λ~,ν~ 是任意满足 KKT 条件的点,那么
x
~
\tilde{x}
x~和
(
λ
~
,
ν
~
)
(\tilde{\lambda}, \tilde{\nu})
(λ~,ν~)
分别是原问题和对偶问题的最优解
10.总结
一个优化问题,无论是否为凸,其对偶函数为凹，对偶问题一定为凸优化问题,此时对偶问题的最优解是原问题的下界.当强对偶性成立(slater条件满足),一定满足kkt条件,此时kkt是强队偶的必要条件.当原问题为凸,kkt是原问题的充要条件
参考文献 凸优化,清华大学出版社,Steven Boyd著,王书宁译
extras
1.relint D:D的相对内部
指集合D除去边缘的集合,相当于是一个开集
2.slater条件一般对于凸问题是本身就已经满足的