赞
踩
以下内容摘自北京大学文再文老师的《最优化:建模、算法与理论》课件
考虑以下凸问题:
min
x
1
,
x
2
f
1
(
x
1
)
+
f
2
(
x
2
)
s
.
t
.
A
1
x
1
+
A
2
x
2
=
b
(1)
要求
f
1
f_1
f1,
f
2
f_2
f2是适当的闭凸函数,但不要求是光滑的。
x
1
∈
R
n
x_1\in\mathbb{R}^n
x1∈Rn,
x
2
∈
R
m
x_2\in\mathbb{R}^m
x2∈Rm,
A
1
∈
R
p
×
n
A_1\in\mathbb{R}^{p\times n}
A1∈Rp×n,
A
2
∈
R
p
×
m
A_2\in\mathbb{R}^{p\times m}
A2∈Rp×m,
b
∈
R
p
b\in\mathbb{R}^{p}
b∈Rp
问题的特点在于目标函数可以分为彼此分离的两块。但是变量都被线性约束结合在一起。常见的一些无约束和带约束的问题可以表现为这一形式。
可以分为两块的无约束优化问题:
min
x
f
1
(
x
)
+
f
2
(
x
)
\min\limits_x\quad f_1(x)+f_2(x)
xminf1(x)+f2(x)
引入新的变量
z
z
z,令
x
=
z
x=z
x=z, 将问题转换为:
min
x
,
z
f
1
(
x
)
+
f
2
(
z
)
s
.
t
.
x
−
z
=
0
带线性变换的无约束优化问题:
min
x
f
1
(
x
)
+
f
2
(
A
x
)
\min\limits_x\quad f_1(x)+f_2(Ax)
xminf1(x)+f2(Ax)
引入新的变量
z
z
z,令
z
=
A
x
z=Ax
z=Ax, 将问题转换为:
min
x
,
z
f
1
(
x
)
+
f
2
(
z
)
s
.
t
.
A
x
−
z
=
0
凸集
C
⊂
R
n
C\subset\mathbb{R}^n
C⊂Rn上的约束优化问题
min
x
f
(
x
)
s
.
t
.
A
x
∈
C
I
C
(
z
)
I_C(z)
IC(z)是集合
C
C
C的示性函数,引入约束
z
=
A
x
z=Ax
z=Ax,则问题转化为:
min
x
,
z
f
(
x
)
+
I
C
(
z
)
s
.
t
.
A
x
−
z
=
0
(Here is a problem: 示性函数是什么东西)
全局一致性问题
min
x
∑
i
=
1
N
ϕ
i
(
x
)
\min\limits_x\quad\sum_{i=1}^N\phi_i(x)
xmini=1∑Nϕi(x)
令
x
=
z
x=z
x=z,并将x复制
N
N
N份,分别为
x
i
x_i
xi, 那么问题转换为:
min
x
,
z
∑
i
=
1
N
ϕ
i
(
x
i
)
s
.
t
.
x
i
−
z
=
0
这个例4和文章中所显示的形式上比较相似。
写出前述问题(1)的增广拉格朗日函数
L
ρ
(
x
1
,
x
2
,
y
)
=
f
1
(
x
1
)
+
f
2
(
x
2
)
+
y
T
(
A
1
x
1
+
A
2
x
2
−
b
)
+
ρ
2
∥
A
1
x
1
+
A
2
x
2
−
b
∥
2
2
(2)
其中, ρ > 0 \rho>0 ρ>0是二次罚项的系数。
常见求解带约束问题的增广拉格朗日函数法为如下更新:
(
x
1
k
+
1
,
x
2
k
+
1
)
=
a
r
g
m
i
n
x
1
,
x
2
L
ρ
(
x
1
,
x
2
,
y
k
)
,
y
k
+
1
=
y
k
+
τ
ρ
(
A
1
x
1
k
+
1
+
A
2
x
2
k
+
1
−
b
)
交替方向乘子法的基本思路:
第一步迭代(3)的同时对 x 1 x_1 x1和 x 2 x_2 x2进行优化有时候比较困难,而固定一个变量求解关于另一个变量的极小化问题有时候可能比较简单,因此可以考虑:对 x 1 x_1 x1和 x 2 x_2 x2交替求极小值:
迭代格式可以总结如下:
x
1
k
+
1
=
a
r
g
m
i
n
x
1
L
ρ
(
x
1
,
x
2
k
,
y
k
)
x
2
k
+
1
=
a
r
g
m
i
n
x
1
L
ρ
(
x
1
k
+
1
,
x
2
,
y
k
)
y
k
+
1
=
y
k
+
τ
ρ
(
A
1
x
1
k
+
1
+
A
2
x
2
k
+
1
−
b
)
其中, τ \tau τ为步长,其取值范围通常为 ( 0 , 1 + 5 2 ] (0,\frac{1+\sqrt{5}}{2}] (0,21+5 ]
因为
f
1
,
f
2
f_1,f_2
f1,f2均为闭凸函数,约束为线性函数,所以当Slater条件成立的时候,可以使用凸优化问题的KKT条件作为交替方向乘子法的收敛准则。问题(1)的拉格朗日函数为
L
(
x
1
,
x
2
,
y
)
=
f
1
(
x
1
)
+
f
2
(
x
2
)
+
y
T
(
A
1
x
1
+
A
2
x
2
−
b
)
根据最优性条件定理,若
x
1
∗
,
x
2
∗
x_1^*,x_2^*
x1∗,x2∗为问题(1)的最优解,
y
∗
y^*
y∗为对应的拉格朗日乘子,则满足以下条件:
0
∈
∂
x
1
L
(
x
1
∗
,
x
2
∗
,
y
∗
)
=
∂
f
1
(
x
1
∗
)
+
A
1
T
y
∗
,
0
∈
∂
x
2
L
(
x
1
∗
,
x
2
∗
,
y
∗
)
=
∂
f
2
(
x
2
∗
)
+
A
2
T
y
∗
,
A
1
x
1
∗
+
A
2
x
2
∗
=
b
其中,前两者成为原始可行性条件,后两者称为对偶可行性条件。
x
2
x_2
x2的更新步骤:
x
2
k
=
a
r
g
m
i
n
x
f
2
(
x
)
+
ρ
2
∥
A
1
x
1
k
+
A
2
x
−
b
+
y
k
−
1
ρ
∥
2
根据最优性条件不难推出,
0
∈
∂
f
2
(
x
2
k
)
+
A
2
T
[
y
k
−
1
+
ρ
(
A
1
x
1
k
+
A
2
x
2
k
−
b
)
]
(9)
当
τ
=
1
\tau=1
τ=1时候,根据(7)可知上式方括号中的表达式就是
y
k
y^k
yk,最终有:
0
∈
∂
f
2
(
x
2
k
)
+
A
2
T
y
k
由
x
1
x_1
x1的更新公式
x
1
k
=
a
r
g
m
i
n
x
{
f
1
(
x
)
+
ρ
2
∥
A
1
x
+
A
2
x
2
k
−
1
−
b
+
y
k
−
1
ρ
∥
2
}
假设子问题能够精确求解,根据最优性条件,
0
∈
∂
f
1
(
x
1
k
)
+
A
1
T
[
ρ
(
A
1
x
1
k
+
A
2
x
2
k
−
1
−
b
)
+
y
k
−
1
]
根据ADMM的第三式(7)取
τ
=
1
\tau=1
τ=1有
0
∈
∂
f
1
(
x
1
k
)
+
A
1
T
(
y
k
+
ρ
A
2
(
x
2
k
−
1
−
x
2
k
)
)
(10)
对比(8a)可知多出来的项为
A
1
T
A
2
(
x
2
k
−
1
−
x
2
k
)
A_1^TA_2(x_2^{k-1}-x_2^k)
A1TA2(x2k−1−x2k)。因此要检测对偶可行性只需要检测残差
s
k
=
A
1
T
A
2
(
x
2
k
−
1
−
x
2
k
)
s^k = A^T_1A_2(x_2^{k-1}-x_2^k)
sk=A1TA2(x2k−1−x2k)
综上,当
x
2
x_2
x2更新取到精确解且
τ
=
1
\tau=1
τ=1时候,判断ADMM收敛只需要检测前述两个残差
r
k
,
s
k
r^k, s^k
rk,sk是否充分小:
0
≈
∣
∣
r
k
∣
∣
=
∥
A
1
x
1
k
+
A
2
x
2
k
−
b
∥
原始可行性
0
≈
∣
∣
s
k
∣
∣
=
∥
A
1
T
A
2
(
x
2
k
−
1
−
x
2
k
)
∥
对偶可行性
(11)
线性化技巧使用近似点项对子问题目标函数进行二次近似。
不失一般性,我们考虑第一个子问题,即:
min
x
1
f
1
(
x
1
)
+
ρ
2
∥
A
1
x
1
−
v
k
∥
2
(12)
其中:
v
k
=
b
−
A
2
x
2
k
−
1
ρ
y
k
v^k = b-A_2x_2^k-\frac{1}{\rho}y^k
vk=b−A2x2k−ρ1yk
当子问题目标函数可微的时候,线性化将问题(12)变为:
x
1
k
+
1
=
a
r
g
m
i
n
x
1
(
∇
f
1
(
x
1
k
)
+
ρ
A
1
T
(
A
1
x
1
k
−
v
k
)
)
T
x
1
+
1
2
η
k
∥
x
1
−
x
2
2
∥
2
2
其中,
η
k
\eta_k
ηk是步长参数,这等价于做一步梯度下降。
当目标函数不可微的时候,可以考虑只将二次项线性化,即:
x
1
k
+
1
=
a
r
g
m
i
n
x
1
(
f
1
(
x
1
k
)
+
ρ
A
1
T
(
A
1
x
1
k
−
v
k
)
)
T
x
1
+
1
2
η
k
∥
x
1
−
x
2
2
∥
2
2
这等价于做一步近似点梯度步。
如果目标函数中含有二次函数,例如
f
1
(
x
1
)
=
1
2
∥
C
x
1
−
d
∥
2
2
f_1(x_1) = \frac{1}{2}{\Vert Cx_1-d\Vert}^2_2
f1(x1)=21∥Cx1−d∥22,那么针对
x
1
x_1
x1的更新(5)等价于求解线性方程组
(
C
T
C
+
ρ
A
1
T
A
1
)
x
1
=
C
T
d
+
ρ
A
1
T
v
k
(C^TC+\rho A^T_1A_1)x_1=C^Td+\rho A_1^Tv^k
(CTC+ρA1TA1)x1=CTd+ρA1Tvk
虽然子问题有显式解,但是每步求解的复杂度仍然比较高,这时候可以考虑用缓存分解的方法,首先对
C
T
C
+
ρ
A
1
T
A
1
C^TC+\rho A^T_1A_1
CTC+ρA1TA1进行Cholesky分解,并缓存分解的结果,在每步迭代中,只需要求解简单的三角形方程组
当
ρ
\rho
ρ发生更新的时候,就要重新进行分解,特别地,当
C
T
C
+
ρ
A
1
T
A
1
C^TC+\rho A^T_1A_1
CTC+ρA1TA1一部分容易求逆,另一部分是低秩的情形时,可以使用矩阵辅助求逆公式(SMW)进行求逆。
有时候为了方便求解子问题,可以用一个性质好的矩阵
D
D
D近似二次项
A
1
T
A
1
A_1^TA_1
A1TA1,此时子问题(12)替换为
x
1
k
+
1
=
a
r
g
m
i
n
x
1
f
1
(
x
1
)
+
ρ
2
∥
A
1
x
1
−
v
k
∥
2
+
ρ
2
(
x
1
−
x
k
)
T
(
D
−
A
1
T
A
1
)
(
x
1
−
x
k
)
x_1^{k+1} = \mathop{argmin}\limits_{x_1}{f_1(x_1)+\frac{\rho}{2}{\Vert{A_1x_1-v^k}\Vert}^2 +\frac{\rho}{2}(x_1-x^k)^T(D-A_1^TA_1)(x_1-x^k)}
x1k+1=x1argminf1(x1)+2ρ∥A1x1−vk∥2+2ρ(x1−xk)T(D−A1TA1)(x1−xk)
这种方法也被称为优化转移。
通过选取合适的
D
D
D,当计算
a
r
g
m
i
n
x
1
{
f
1
(
x
1
)
+
ρ
2
x
1
T
D
x
1
}
\mathop{argmin}\limits_{x_1}\{f_1(x_1)+\frac{\rho}{2}x_1^TDx_1\}
x1argmin{f1(x1)+2ρx1TDx1}明显比计算
a
r
g
m
i
n
x
1
{
f
1
(
x
1
)
+
ρ
2
x
1
T
A
1
T
A
1
x
1
}
\mathop{argmin}\limits_{x_1}\{f_1(x_1)+\frac{\rho}{2}x_1^TA_1TA_1x_1\}
x1argmin{f1(x1)+2ρx1TA1TA1x1}要容易的时候,优化转移可以极大地简化子问题的计算。特别地,当
D
=
η
k
ρ
I
D=\frac{\eta_k}{\rho}I
D=ρηkI时,优化转移等价于做单步的近似点梯度步。
原始可行性和对偶可行性分别用 ∥ r k ∥ \Vert r^k\Vert ∥rk∥和 ∥ s k ∥ \Vert s^k\Vert ∥sk∥度量。
求解过程中二次罚项系数
ρ
\rho
ρ太大会导致原始可行性
∥
r
k
∥
\Vert r^k\Vert
∥rk∥下降很快,但是对偶可行性
∥
s
k
∥
\Vert s^k\Vert
∥sk∥下降很慢;二次罚项系数太小,则会有相反的效果,这样都会导致收敛比较慢或者得到的解的可行性很差。
一个自然的想法是在每次迭代的时候动态调节惩罚系数
ρ
\rho
ρ的大小,从而使得原始可行性和对偶可行行能够以比较一致的速度下降到0.一个简单有效的方式是令
ρ
k
+
1
=
{
γ
p
ρ
k
,
∥
r
k
∥
>
μ
∥
s
k
∥
ρ
k
γ
p
,
∥
s
k
∥
>
μ
∥
r
k
∥
ρ
k
,
其他
\rho^{k+1} =
其中,
μ
>
1
\mu>1
μ>1,
γ
p
>
1
\gamma_p>1
γp>1,
γ
d
>
1
\gamma_d>1
γd>1是参数,常见的选择
为
μ
=
10
,
γ
p
=
γ
d
=
2
\mu=10, \gamma_p=\gamma_d=2
μ=10,γp=γd=2.在迭代过长中将原始可行性
∣
∣
r
k
∣
∣
||r^k||
∣∣rk∣∣和对偶可行性
∣
∣
s
k
∣
∣
||s^k||
∣∣sk∣∣保持在彼此的
μ
\mu
μ倍内,如果发现
∣
∣
r
k
∣
∣
||r^k||
∣∣rk∣∣或
∣
∣
s
k
∣
∣
||s^k||
∣∣sk∣∣下降过慢就应该相应增大或者减小二次罚项系数
ρ
k
\rho^k
ρk.
考虑有多块变量的情形
min
x
1
,
x
2
,
…
,
x
N
f
1
(
x
1
)
+
f
2
(
x
2
)
+
⋯
+
f
N
(
x
N
)
,
s
.
t
.
A
1
x
1
+
A
2
x
2
+
⋯
+
A
N
x
N
=
b
.
(13)
这里,
f
i
(
x
i
)
f_i(x_i)
fi(xi)是闭函数,
x
i
∈
R
n
i
x_i\in \mathbb{R}^{n_i}
xi∈Rni,
A
i
∈
R
m
×
n
i
A_i\in \mathbb{R}^{m\times n_i}
Ai∈Rm×ni
同样写出增广拉格朗日函数
L
ρ
(
x
1
,
x
2
,
…
,
x
N
,
y
)
L_{\rho}(x_1, x_2, \dots, x_N, y)
Lρ(x1,x2,…,xN,y),相应的多块ADMM迭代格式为
x
1
k
+
1
=
a
r
g
m
i
n
x
1
L
ρ
(
x
,
x
2
k
,
…
,
x
N
k
,
y
k
)
x
2
k
+
1
=
a
r
g
m
i
n
x
1
L
ρ
(
x
1
k
+
1
,
x
,
…
,
x
N
k
,
y
k
)
…
x
N
k
+
1
=
a
r
g
m
i
n
x
1
L
ρ
(
x
1
k
+
1
,
x
2
k
+
1
,
…
,
x
N
,
y
k
)
y
k
+
1
=
y
k
+
τ
ρ
(
A
1
x
1
k
+
1
+
A
2
x
2
k
+
1
+
⋯
+
A
N
x
N
k
+
1
−
b
)
其中,
τ
∈
(
0
,
5
+
1
2
)
\tau\in(0, \frac{\sqrt{5}+1}{2})
τ∈(0,25
+1)为步长参数。
限于篇幅和内容需要,部分应用举例已折叠。
原问题为:
min
x
i
,
z
∑
i
=
1
N
ϕ
i
(
x
i
)
,
s
.
t
.
x
i
−
z
=
0
,
i
=
1
,
2
,
…
,
N
.
增广拉格朗日函数:
L
(
x
1
,
…
,
x
N
,
z
,
y
1
,
…
,
y
N
)
=
∑
i
=
1
N
ϕ
i
(
x
i
)
+
∑
i
=
1
N
y
i
T
(
x
i
−
z
)
+
ρ
2
∑
i
=
1
N
∥
x
i
−
z
∥
2
L(x_1,\dots, x_N, z, y_1,\dots, y_N) = \sum_{i=1}^N\phi_i(x_i) +\sum_{i=1}^N y_i^T(x_i-z)+\frac{\rho}{2}\sum_{i=1}^N{\Vert x_i-z\Vert}^2
L(x1,…,xN,z,y1,…,yN)=i=1∑Nϕi(xi)+i=1∑NyiT(xi−z)+2ρi=1∑N∥xi−z∥2
固定
z
k
z^k
zk,
y
i
k
y_i^k
yik,更新
x
i
x_i
xi的公式为
x
i
k
+
1
=
a
r
g
m
i
n
x
{
ϕ
i
(
x
)
+
ρ
2
∥
x
i
−
z
+
y
i
k
ρ
∥
2
}
(21)
注意:虽然表面上看,增广拉格朗日函数有
(
N
+
1
)
(N+1)
(N+1)个变量块,但本质上还是两个变量块,这是因为在更新某个
x
i
x_i
xi时候并未利用其他
x
i
x_i
xi,所有
x
i
x_i
xi可以看成一个整体。相应地,所有的乘子
y
i
y_i
yi也可以看成一个整体。
迭代式(21)的具体计算依赖于
ψ
i
\psi_i
ψi的形式,在一般情况下,更新
x
i
x_i
xi的表达式为
x
i
k
+
1
=
p
r
o
x
ϕ
i
/
ρ
(
z
k
−
y
i
k
/
ρ
)
x_i^{k+1}=prox_{\phi_i/\rho}(z^k-y_i^k/\rho)
xik+1=proxϕi/ρ(zk−yik/ρ)
固定
x
i
k
+
1
x_{i}^{k+1}
xik+1,
y
i
k
y_i^k
yik,问题关于
z
z
z时二次函数,因此可以直接写出显式解:
z
k
+
1
=
1
N
∑
i
=
1
N
(
x
i
k
+
1
+
y
i
k
/
ρ
)
.
z^{k+1} = \frac{1}{N}\sum_{i=1}^N(x_i^{k+1}+y_i^k/\rho).
zk+1=N1i=1∑N(xik+1+yik/ρ).
综上,该问题的交替方向乘子法迭代格式为
x
i
k
+
1
=
p
r
o
x
ϕ
i
/
ρ
(
z
k
−
y
i
k
/
ρ
)
,
,
i
=
1
,
2
,
…
,
N
.
z
k
+
1
=
1
N
∑
i
=
1
N
(
x
i
k
+
1
+
y
i
k
/
ρ
)
.
y
i
k
+
1
=
y
i
k
+
τ
ρ
(
x
i
k
+
1
−
z
k
+
1
)
,
i
=
1
,
2
,
…
,
N
.
因此,在上一篇文章中所提到的
Minimized
{
−
∑
j
=
0
n
L
j
(
x
j
)
}
subject to
y
−
z
j
=
0
j
=
0
,
…
,
n
(23)
应用ADMM解决这一问题:
y
k
+
1
:
=
a
r
g
m
i
n
y
{
⟨
∑
j
=
0
n
p
j
k
,
y
⟩
+
ρ
2
∑
j
=
0
n
∥
y
−
z
j
k
∥
2
}
z
j
k
+
1
:
=
a
r
g
m
i
n
z
j
{
−
L
j
(
z
j
)
−
⟨
p
j
k
,
z
j
⟩
+
ρ
2
∑
j
=
0
n
∥
y
k
+
1
−
z
j
∥
2
}
p
j
k
+
1
:
=
p
j
k
+
ρ
(
y
k
+
1
−
z
j
k
+
1
)
迭代过程为:
y
k
+
1
=
1
n
+
1
∑
n
+
1
n
z
j
k
+
−
1
(
n
+
1
)
ρ
∑
j
=
0
n
p
j
k
y^{k+1} = \frac{1}{n+1}\sum_{n+1}^nz_j^k+-\frac{1}{(n+1)\rho}\sum_{j=0}^np_j^k
yk+1=n+11n+1∑nzjk+−(n+1)ρ1j=0∑npjk
{
x
i
∗
,
i
∈
A
j
}
:
=
a
r
g
m
i
n
x
i
∈
χ
i
,
i
∈
A
j
{
∑
i
∈
A
j
g
i
(
x
i
)
+
ρ
2
∥
[
m
a
x
{
0
,
λ
y
k
+
1
+
1
ρ
(
∑
i
∈
A
j
ψ
i
(
x
i
)
+
λ
p
j
k
)
}
ν
y
k
+
1
+
1
ρ
(
∑
i
∈
A
j
A
i
(
x
i
)
+
λ
p
j
k
)
]
∥
2
}
z
j
=
[
λ
z
j
ν
z
j
]
=
[
m
a
x
{
0
,
λ
y
k
+
1
+
1
ρ
(
∑
i
∈
A
j
ψ
i
(
x
i
)
+
λ
p
j
k
)
}
ν
y
k
+
1
+
1
ρ
(
∑
i
∈
A
j
A
i
(
x
i
)
+
λ
p
j
k
)
]
z_j = \left[
p
j
k
+
1
:
=
p
j
k
+
ρ
(
y
k
+
1
−
z
j
k
+
1
)
可见,复现论文中提到的是具有两个量的ADMM,因此,具体的编程内容,也需要从具有两个量的ADMM展开,这比前面课件提到的内容更为复杂。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。