前置章节：数学分析 Chapter 9 多元函数微分学 ↗
优化算法做的事情就是为了求出满足 KKT 条件的解
凸优化，指的是目标函数为凸函数、不等式约束为凸函数、等式约束为线性函数或仿射函数≥ \ge ≥
惩罚函数与 dual ascent#
考虑对于优化问题
min x f ( x ) s . t . g k ( x ) ≤ 0 , k = 1 , ⋯ , K h ℓ ( x ) = 0 , ℓ = 1 , ⋯ , L \begin{aligned}
\min\limits_{x}\quad &f(x)\\
s.t.\quad &g_k(x)\leq0,\quad k=1,\cdots,K\\
\quad & h_\ell(x)=0,\quad \ell =1,\cdots,L
\end{aligned} x min s . t . f ( x ) g k ( x ) ≤ 0 , k = 1 , ⋯ , K h ℓ ( x ) = 0 , ℓ = 1 , ⋯ , L 我们把约束当成惩罚项。定义
f ~ ( x ) = f ( x ) + ∑ I k ( g k ( x ) ) + ∑ J ℓ ( h ℓ ( x ) ) \tilde{f}(x)=f(x)+\sum\limits I_{k}(g_k(x))+\sum\limits J_{\ell }(h_\ell(x)) f ~ ( x ) = f ( x ) + ∑ I k ( g k ( x )) + ∑ J ℓ ( h ℓ ( x )) 其中 I I I J J J
I k ( ⋅ ) I_k(\cdot) I k ( ⋅ ) ≤ 0 \leq0 ≤ 0 > 0 >0 > 0 + ∞ +\infty + ∞ J ℓ ( ⋅ ) J_\ell(\cdot) J ℓ ( ⋅ ) = 0 =0 = 0 ≠ 0 \neq0 = 0 + ∞ +\infty + ∞
这样我们相当于在无约束条件下做 min f ~ ( x ) \min\tilde{f}(x) min f ~ ( x ) f ~ \tilde{f} f ~
对比原问题的 Lagrange 函数：L ( x , α , β ) = f ( x ) + α T g ( x ) + β T h ( x ) L(x,\alpha ,\beta )=f(x)+\alpha ^Tg(x)+\beta ^Th(x) L ( x , α , β ) = f ( x ) + α T g ( x ) + β T h ( x ) I k I_k I k α k \alpha_k α k g k g_k g k α k \alpha_k α k α k \alpha_k α k g k ( x ) ≤ 0 g_k(x)\leq0 g k ( x ) ≤ 0 g k ( x ) g_k(x) g k ( x ) f ~ \tilde{f} f ~ f ( x ) f(x) f ( x ) α k \alpha_k α k + ∞ +\infty + ∞
一个自然的实现方式是，把惩罚从 α k g k ( x ) \alpha_kg_k(x) α k g k ( x ) max α k g k ( x ) \max \alpha_kg_k(x) max α k g k ( x ) α k \alpha_k α k 这里其实是 sup，但我们假定存在严格可行点 ）。这样，在负半轴 α k \alpha_k α k α k \alpha_k α k → ∞ \to\infty → ∞
I k ( g k ( x ) ) = max α k ≥ 0 α k g k ( x ) I_k(g_k(x))=\max\limits_{\alpha_k\geq0}\alpha_kg_k(x) I k ( g k ( x )) = α k ≥ 0 max α k g k ( x ) 同理地，对于等式约束，也可以用同样的推理过程得到惩罚函数的表达式
J ℓ ( h ℓ ( x ) ) = max β ℓ β ℓ h ℓ ( x ) J_\ell(h_\ell(x))=\max\limits_{\beta_\ell}\beta_\ell h_\ell(x) J ℓ ( h ℓ ( x )) = β ℓ max β ℓ h ℓ ( x ) 注意 β ℓ \beta_\ell β ℓ h ℓ = 0 h_\ell=0 h ℓ = 0 h > 0 h>0 h > 0 β > 0 \beta>0 β > 0 h < 0 h<0 h < 0 β < 0 \beta<0 β < 0
所以原始问题其解与下面这个问题的解是相同的：其中 α ≥ 0 \alpha\geq0 α ≥ 0
min x max α ≥ 0 , β f ( x ) + α T g ( x ) + β T h ( x ) \min\limits_{x}\max\limits_{\alpha\geq0 ,\,\beta }f(x)+\alpha ^Tg(x)+\beta ^Th(x) x min α ≥ 0 , β max f ( x ) + α T g ( x ) + β T h ( x ) 进一步地，如果原问题是凸优化 ，那么 max 和 min 可以互换（称为强对偶性），得到对偶问题
max α ≥ 0 , β min x f ( x ) + α T g ( x ) + β T h ( x ) \max\limits_{\alpha\geq0 ,\,\beta }\min\limits_{x}f(x)+\alpha ^Tg(x)+\beta ^Th(x) α ≥ 0 , β max x min f ( x ) + α T g ( x ) + β T h ( x ) 这样相当于把主元从 x x x α \alpha α β \beta β α \alpha α β \beta β x x x
这给出了一个求解方法，称为 dual ascent ：轮流更新自变量和对偶变量，一步 min 一步 max：注意 不等式约束的乘子 α \alpha α
min : x ( i + 1 ) = arg min x L ( x , α ( i ) , β ( i ) ) max : α ( i + 1 ) = [ α ( i ) + η ( i ) g ( x ( i + 1 ) ) ] + β ( i + 1 ) = β ( i ) + η ( i ) h ( x ( i + 1 ) ) \begin{aligned}
\min:\quad x^{(i+1)} &= \arg\min_x L(x, \alpha^{(i)}, \beta^{(i)})\\
\max:\quad \alpha^{(i+1)} &= \big[\alpha^{(i)} + \eta^{(i)} g(x^{(i+1)})\big]^+\\
\beta^{(i+1)} &= \beta^{(i)} + \eta^{(i)} h(x^{(i+1)})\\
\end{aligned} min : x ( i + 1 ) max : α ( i + 1 ) β ( i + 1 ) = arg x min L ( x , α ( i ) , β ( i ) ) = [ α ( i ) + η ( i ) g ( x ( i + 1 ) ) ] + = β ( i ) + η ( i ) h ( x ( i + 1 ) ) 增广 Lagrange 函数法#
dual ascent 要求每一步的 arg min \arg\min arg min g , h g,h g , h f f f arg min \arg\min arg min
所以要通过某种方式，修改 Lagrange 函数，强行变成凸的，但不改变最优化的结果。最简单的凸因子就是二次函数。因此增加二次惩罚项：
对于等式约束 h ℓ ( x ) = 0 h_\ell(x)=0 h ℓ ( x ) = 0 β ℓ h ℓ ( x ) + ρ 2 ( h ℓ ( x ) ) 2 \beta_\ell h_\ell (x)+\dfrac{\rho}2\big(h_\ell (x)\big)^2 β ℓ h ℓ ( x ) + 2 ρ ( h ℓ ( x ) ) 2 ρ > 0 \rho>0 ρ > 0 ρ \rho ρ h ℓ = 0 h_\ell =0 h ℓ = 0
对于不等式约束 g k ( x ) ≤ 0 g_k(x)\leq0 g k ( x ) ≤ 0 g k < 0 g_k<0 g k < 0 s k ≥ 0 s_k\geq0 s k ≥ 0 g k ( x ) + s k = 0 g_k(x)+s_k=0 g k ( x ) + s k = 0 α k ( g k ( x ) + s k ) + ρ 2 ( g k ( x ) + s k ) 2 \alpha_k(g_k(x)+s_k)+\dfrac\rho2\big(g_k(x)+s_k\big)^2 α k ( g k ( x ) + s k ) + 2 ρ ( g k ( x ) + s k ) 2 s k s_k s k s ^ k \hat{s}_k s ^ k s ^ k = α k + ρ g k ( x ) ρ \hat{s}_k=\dfrac{\alpha_k+\rho g_k(x)}{\rho} s ^ k = ρ α k + ρ g k ( x ) s k ≥ 0 s_k\geq0 s k ≥ 0
当轴 ≤ 0 \leq0 ≤ 0 s k = 0 s_k=0 s k = 0 = ( α k + ρ g k ( x ) ) 2 − α k 2 2 ρ =\dfrac{\big(\alpha_k+\rho g_k(x)\big)^2-\alpha_k^2}{2\rho} = 2 ρ ( α k + ρ g k ( x ) ) 2 − α k 2
当轴 > 0 >0 > 0 s k = s_k= s k = = − α k 2 2 ρ =-\dfrac{\alpha_k^2}{2\rho} = − 2 ρ α k 2
统一表达式为 1 2 ρ ( ( [ α k + ρ g k ( x ) ] + ) 2 − α k 2 ) \dfrac{1}{2\rho} \bigg( \big(\left[ \alpha_k + \rho g_k(x)\right]^+\big)^2 - \alpha_k^2 \bigg) 2 ρ 1 ( ( [ α k + ρ g k ( x ) ] + ) 2 − α k 2 ) 三个人名首字母 ）
于是问题转化为：其中 [ ⋅ ] + [\,\cdot\,]^+ [ ⋅ ] + ∥ ⋅ ∥ 2 \|\cdot\|^2 ∥ ⋅ ∥ 2
min x max α ≥ 0 , β f ( x ) + 1 2 ρ ( ∥ [ α + ρ g ( x ) ] + ∥ 2 − ∥ α ∥ 2 ) + ( β T h ( x ) + ρ 2 ∥ h ( x ) ∥ 2 ) \min\limits_{x}\max\limits_{\alpha\geq0 ,\,\beta }\,f(x) + \dfrac{1}{2\rho} \bigg( \big\|\ [ \alpha + \rho g(x)]^+\big\|^2 - \|\alpha\|^2 \bigg) + \left( \beta^T h(x) + \frac{\rho}{2} \|h(x)\|^2 \right) x min α ≥ 0 , β max f ( x ) + 2 ρ 1 ( [ α + ρ g ( x ) ] + 2 − ∥ α ∥ 2 ) + ( β T h ( x ) + 2 ρ ∥ h ( x ) ∥ 2 ) 特别地 ，当只有等式约束的时候，通常令 u = ( 1 / ρ ) β u=(1/\rho )\beta u = ( 1/ ρ ) β
L ( x , β ) = f ( x ) + β T h ( x ) + ρ 2 ∥ h ( x ) ∥ 2 = f ( x ) + ρ 2 ∥ h ( x ) + 1 ρ β ∥ 2 − 1 2 ρ ∥ β ∥ 2 = f ( x ) + ρ 2 ( ∥ h ( x ) + u ∥ 2 − ∥ u ∥ 2 ) \begin{aligned}
L(x,\beta )&=f(x)+\beta^T h(x) + \frac{\rho}{2}\|h(x)\|^2 \\
&= f(x)+\frac{\rho}{2} \left\| h(x) + \frac{1}{\rho}\beta \right\|^2 - \frac{1}{2\rho}\|\beta\|^2\\
&=f(x)+\frac{\rho}{2}\left(\|h(x)+u\|^2-\|u\|^2\right)
\end{aligned} L ( x , β ) = f ( x ) + β T h ( x ) + 2 ρ ∥ h ( x ) ∥ 2 = f ( x ) + 2 ρ h ( x ) + ρ 1 β 2 − 2 ρ 1 ∥ β ∥ 2 = f ( x ) + 2 ρ ( ∥ h ( x ) + u ∥ 2 − ∥ u ∥ 2 ) 然后对它做 dual ascent 就行了，更新方法是一样的。这称为增广 Lagrange 函数法（ALM）
ADMM#
对于一个优化问题，当问题规模很大的时候，通常有两种优化方式：要么一次只取一小部分样本来优化（例如 mini-batch 梯度下降），要么一次只优化 x \mathbf{x} x
考虑一类优化问题，它的自变量是由两组物理意义完全不同的变量拼起来的，分别对应目标函数的两个部分。也即问题可以写成
x = ( u , v ) min x f 1 ( u ) + f 2 ( v ) s . t . A u + B v = c \begin{aligned}
x&=(u,v)\\
\min\limits_{x}\quad &f_1(u) + f_2(v)\\
s.t.\quad &Au+Bv=c
\end{aligned} x x min s . t . = ( u , v ) f 1 ( u ) + f 2 ( v ) A u + B v = c 比如 u u u f 1 f_1 f 1 v v v f 2 f_2 f 2 α f 1 + β f 2 \alpha f_1+\beta f_2 α f 1 + β f 2
我们使用 dual ascent 来求解。Lagrange 函数
L ( u , v , β ) = f 1 ( u ) + f 2 ( v ) + β T ( A u + B v − c ) L(u, v, \beta) = f_1(u) + f_2(v) + \beta^T(Au + Bv - c) L ( u , v , β ) = f 1 ( u ) + f 2 ( v ) + β T ( A u + B v − c ) 在做 minimize 步骤时，由于使用线性惩罚，我们有
min x L = min u , v f 1 ( u ) + f 2 ( v ) + β T ( A u + B v − c ) = ( min u [ f 1 ( u ) + β T A u ] ) + ( min v [ f 2 ( v ) + β T B v ] ) − β T c \begin{aligned}
\min_{x} L&=\min_{u, v}\ f_1(u) + f_2(v) + \beta^T(Au + Bv - c) \\
&= \left( \min_u\ [f_1(u) + \beta^T A u] \right) + \left( \min_v \ [f_2(v) + \beta^T B v] \right) - \beta^T c
\end{aligned} x min L = u , v min f 1 ( u ) + f 2 ( v ) + β T ( A u + B v − c ) = ( u min [ f 1 ( u ) + β T A u ] ) + ( v min [ f 2 ( v ) + β T B v ] ) − β T c 这说明，寻找 x = ( u , v ) x=(u,v) x = ( u , v ) u u u v v v
但 dual ascent 需要目标函数足够凸。刚才的解决方法是 ALM，也即把惩罚改成二次的强行凸化：
L ρ ( u , v , β ) = f 1 ( u ) + f 2 ( v ) + β T ( A u + B v − c ) + ρ 2 ∥ A u + B v − c ∥ 2 L_\rho(u, v, \beta) = f_1(u) + f_2(v) + \beta^T(Au + Bv - c) + \frac{\rho}{2}\|Au + Bv - c\|^2 L ρ ( u , v , β ) = f 1 ( u ) + f 2 ( v ) + β T ( A u + B v − c ) + 2 ρ ∥ A u + B v − c ∥ 2 这就出问题了，因为这里引入了二次项，其中存在 u u u v v v
然而解决方法非常简单，只需要交替更新 u u u v v v 交替方向乘子法（ADMM） ，相当于宏观上并行、微观上串行
min : u ( i + 1 ) = arg min u L ( u , v ( i ) , β ( i ) ) v ( i + 1 ) = arg min v L ( u ( i + 1 ) , v , β ( i ) ) max : β ( i + 1 ) = β ( i ) + η ( i ) ( A u ( i + 1 ) + B v ( i + 1 ) − c ) \begin{aligned}
\min:\quad u^{(i+1)} &= \arg\min_u L(u, v^{(i)}, \beta^{(i)})\\
v^{(i+1)} &= \arg\min_v L(u^{(i+1)}, v, \beta^{(i)})\\
\max:\quad
\beta^{(i+1)} &= \beta^{(i)} + \eta^{(i)}(Au^{(i+1)} + Bv^{(i+1)} - c)\\
\end{aligned} min : u ( i + 1 ) v ( i + 1 ) max : β ( i + 1 ) = arg u min L ( u , v ( i ) , β ( i ) ) = arg v min L ( u ( i + 1 ) , v , β ( i ) ) = β ( i ) + η ( i ) ( A u ( i + 1 ) + B v ( i + 1 ) − c ) 对于不等式约束，直接沿用 ALM 的结论，用 PHR 罚函数就行了，因为本质上 ADMM 只是把可分的两个部分交替来做。至于收不收敛，那是数学家的事。
非线性约束#
需要注意，从头到尾我们讨论的都是线性约束情形，因为 dual ascent 要求凸优化，但实际当中大量的约束是非线性的，而且 ALM 还得对它平方，这导致增广 Lagrange 函数很扭曲，argmin 不好做。
而 ADMM 的形式给出了一种解决思路，称为变量拆分，也即用两个变量，分别解决目标函数和约束函数。类似最开始讲的惩罚函数的想法，把约束写成惩罚项，只不过那会儿惩罚函数的自变量是 x x x I S ( z ) = { 0 , z ∈ S + ∞ , others I_{\mathcal{S}}(z)=\begin{cases}0,&z\in \mathcal{S}\\+\infty,& \text{others}\end{cases} I S ( z ) = { 0 , + ∞ , z ∈ S others S \mathcal{S} S x x x
min x , z f ( x ) + I S ( z ) s . t . x − z = 0 \begin{aligned}
\min\limits_{x, z}\quad &f(x) + I_{\mathcal{S}}(z)\\
s.t.\quad &x - z = 0
\end{aligned} x , z min s . t . f ( x ) + I S ( z ) x − z = 0 然后就是交替更新步骤了。还是令 u = ( 1 / ρ ) β u=(1/\rho )\beta u = ( 1/ ρ ) β
x ( k + 1 ) = arg min x ( f ( x ) + ρ 2 ∥ x − z ( k ) + u ( k ) ∥ 2 2 ) z ( k + 1 ) = arg min z ( I S ( z ) + ρ 2 ∥ x ( k + 1 ) − z + u ( k ) ∥ 2 2 ) u ( k + 1 ) = u ( k ) + x ( k + 1 ) − z ( k + 1 ) \begin{aligned}
x^{(k+1)} &= \arg\min_x \left( f(x) + \frac{\rho}{2}\|x - z^{(k)} + u^{(k)}\|_2^2 \right) \\
z^{(k+1)} &= \arg\min_z \left( I_{\mathcal{S}}(z) + \frac{\rho}{2}\|x^{(k+1)} - z + u^{(k)}\|_2^2 \right) \\
u^{(k+1)} &= u^{(k)} + x^{(k+1)} - z^{(k+1)}
\end{aligned} x ( k + 1 ) z ( k + 1 ) u ( k + 1 ) = arg x min ( f ( x ) + 2 ρ ∥ x − z ( k ) + u ( k ) ∥ 2 2 ) = arg z min ( I S ( z ) + 2 ρ ∥ x ( k + 1 ) − z + u ( k ) ∥ 2 2 ) = u ( k ) + x ( k + 1 ) − z ( k + 1 ) 观察 z z z S \mathcal{S} S x ( k + 1 ) + u ( k ) x^{(k+1)}\!+\!u^{(k)} x ( k + 1 ) + u ( k ) S \mathcal{S} S
ADMM-Net#
Deep Unfolding 是一种迭代算法的网络化方法，我们把所有涉及到的这些变量 x x x z z z u u u ρ \rho ρ
