凸优化学习（3）——对偶方法、KKT条件、ADMM
🍅 写在前面
👨🎓 博主介绍：大家好，这里是hyk写算法了吗，一枚致力于学习算法和人工智能领域的小菜鸟。
🔎个人主页：主页链接（欢迎各位大佬光临指导）
⭐️近期专栏：机器学习与深度学习
LeetCode算法实例
张量分解
凸优化系列知识，详见下方链接：
凸优化学习(1)——什么是凸优化、凸集、凸函数
凸优化学习（2）——梯度类方法求解(gradient descent)
凸优化学习（3）——对偶方法、KKT条件、ADMM
本系列文章主要参考：卡耐基梅隆 凸优化系列课程
目录
- 综述
- 强弱对偶需要满足的条件
- 线性规划对偶
- 拉格朗日对偶
- ADMM
综述
对偶方法在优化问题中非常重要，实际上就是实质相同但从不同角度提出不同提法的一对问题。有时候原问题 (Primal Problem) 不太好解，但是对偶问题 (Dual Problem) 却很好解，我们就可以通过求解对偶问题来迂回地解答原问题。其中对偶方法又分为强对偶定理和弱对偶定理。弱对偶定理只能确定出原问题的上下界。强对偶定理指的是，在满足某下条件的情况下，可以通过求出对偶问题的解推断出原问题的解。
强弱对偶需要满足的条件
- 弱对偶：不论原问题是否为凸问题均成立，没有需要满足的特别条件。
- 强对偶：满足强对偶的条件有很多，这里只介绍常用的几种。
1、Convex+Slater（强对偶的充分条件）
（1）原问题必须为一个凸问题，凸问题的定义在第一节已经讲过，大家可以回顾查询一下。
（2）Slater条件，对于一个凸优化问题，该条件描述如下：
min x f ( x ) s . t . g i ( x ) ≤ 0 , i = 1... , m h j ( x ) = 0 , j = 1... , r \begin{array}{l} {\min _x}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} f(x)\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {g_i}(x) \le 0,i = 1...,m\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {h_j}(x) = 0,j = 1...,r\\ \end{array} minxf(x)s.t.gi(x)≤0,i=1...,mhj(x)=0,j=1...,r
对于以上式子，存在可行解x，使得 g i ( x ) < 0 {g_i}(x) <0 gi(x)<0恒成立，并且满足第二个条件
h j ( x ) = 0 {h_j}(x) = 0 hj(x)=0。那么称该问题满足Slater条件，并且强对偶也成立。
2、KKT条件
KKT条件的形式如下：
需要指出，KKT条件在问题凹凸性不同性质也有所不同。KKT条件对于凸问题是一个充分必要条件，对于非凸问题则是一个必要条件，无法作为一个充分条件来用。
线性规划对偶
对于形如下方的线性规划问题：
min
x
c
T
x
s
.
t
.
A
x
=
b
G
x
≤
h
\begin{array}{l} {\min _x}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {c^T}x\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} Ax = b\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} Gx \le h \end{array}
minxcTxs.t.Ax=bGx≤h
其对偶问题形式为：
min
u
.
v
−
b
T
u
−
h
T
v
s
.
t
.
−
A
T
u
−
G
T
v
=
c
v
≥
0
\begin{array}{l} {\min _{u.v}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} - {b^T}u - {h^T}v\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} - {A^T}u - {G^T}v = c\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} v \ge 0 \end{array}
minu.v−bTu−hTvs.t.−ATu−GTv=cv≥0
对于LP问题，其对偶性的特性就是只要原问题存在，那么强对偶条件1就一定成立，因此强对偶也成立。
拉格朗日对偶
对于形如下方的凸问题：
min
x
f
(
x
)
s
.
t
.
g
i
(
x
)
≤
0
,
i
=
1...
,
m
h
j
(
x
)
=
0
,
j
=
1...
,
r
\begin{array}{l} {\min _x}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} f(x)\\ s.{\kern 1pt} {\kern 1pt} t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {g_i}(x) \le 0,i = 1...,m\\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {h_j}(x) = 0,j = 1...,r\\ \end{array}
minxf(x)s.t.gi(x)≤0,i=1...,mhj(x)=0,j=1...,r
则其增广拉格朗日函数为：
L
(
x
,
u
,
v
)
=
f
(
x
)
+
∑
i
=
1
m
u
i
g
i
(
x
)
+
∑
j
=
1
r
v
j
h
j
(
x
)
(
u
i
≥
0
)
L(x,u,v) = f(x) + \sum\limits_{i = 1}^m {{u_i}{g_i}(x)} + \sum\limits_{j = 1}^r {{v_j}{h_j}(x)({u_i} \ge 0)}
L(x,u,v)=f(x)+i=1∑muigi(x)+j=1∑rvjhj(x)(ui≥0)
原问题拉格朗日对偶形式为：
inf
(
L
(
x
,
u
,
v
)
)
\inf (L(x,u,v))
inf(L(x,u,v))
这里的inf指的是求函数的上界。这里有一个重要性质，任何函数的拉格朗日对偶函数都是凹函数，大家有兴趣可以自己证明一下，比较简单，证明过程如下。
为什么要求出这个拉格朗日对偶函数呢？它和原函数的关系如下：
∀ u ≥ 0 inf ( L ( x , u , v ) ) ≤ f ( x ) \forall u \ge 0{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \inf (L(x,u,v)) \le f(x) ∀u≥0inf(L(x,u,v))≤f(x)
证明起来也很容易，因为u不小于0，g(x)小于等于0，相乘小于0。h(x)又等于0。加上f(x)肯定小于等于f(x)。
所以原问题求f(x)的最小值可转变为求解以下式子：
min
inf
(
L
(
x
,
u
,
v
)
)
\min {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \inf (L(x,u,v))
mininf(L(x,u,v))
使用拉格朗日对偶法求解问题的好处有：
1、参数约束减少了很多，只需要u大于等于0
2、拉格朗日对偶函数一定是一个凹函数，则很多凸优化问题的手段都能用上。
ADMM
ADMM (Alternating Direction Method of Multipliers) 是解决带约束的凸优化问题的一种迭代解法，当初提出这个算法最主要的目的是为了在分布式环境 (Hadoop, MPI 等) 中迭代求解这个问题。
ADMM要解决问题的形式如下：
min
x
=
f
1
(
x
1
)
+
f
2
(
x
2
)
s
.
t
.
A
1
x
1
+
A
2
X
2
=
b
\begin{array}{l} {\min _x} = {f_1}({x_1}) + {f_2}({x_2})\\ s.t.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {A_1}{x_1} + {A_2}{X_2} = b \end{array}
minx=f1(x1)+f2(x2)s.t.A1x1+A2X2=b
则ADMM的迭代公式为：
x
1
(
k
)
=
arg
min
x
1
f
1
(
x
1
)
+
ρ
2
∥
A
1
X
1
+
A
2
X
2
(
k
−
1
)
−
b
+
w
(
k
−
1
)
∥
2
2
x
2
(
k
)
=
arg
min
x
2
f
2
(
x
2
)
+
ρ
2
∥
A
1
X
1
(
k
−
1
)
+
A
2
X
2
−
b
+
w
(
k
−
1
)
∥
2
2
w
(
k
)
=
w
(
k
−
1
)
+
A
1
x
1
(
k
)
+
A
2
X
2
(
k
)
−
b
\begin{array}{l} {x_1}^{(k)} = \arg {\min _{x1}}{f_1}({x_1}) + \frac{\rho }{2}{\left\| {{A_1}{X_1} + {A_2}{X_2}^{(k - 1)} - b + {w^{(k - 1)}}} \right\|_2}^2\\ {x_2}^{(k)} = \arg {\min _{x2}}{f_2}({x_2}) + \frac{\rho }{2}{\left\| {{A_1}{X_1}^{(k - 1)} + {A_2}{X_2} - b + {w^{(k - 1)}}} \right\|_2}^2\\ {w^{(k)}} = {w^{(k - 1)}} + {A_1}{x_1}^{(k)} + {A_2}{X_2}^{(k)} - b\\ \\ \end{array}
x1(k)=argminx1f1(x1)+2ρ
A1X1+A2X2(k−1)−b+w(k−1)
22x2(k)=argminx2f2(x2)+2ρ
A1X1(k−1)+A2X2−b+w(k−1)
22w(k)=w(k−1)+A1x1(k)+A2X2(k)−b
其中ρ是事先选定的参数，可以选择定值和定值，和前一节讲过的学习率性质差不多。