【论文阅读】ADMM算法及其变形

Zephus · 发表于 2022-8-25 09:17

如果优化问题具有可分离性，一个常用的办法就是使用ADMM求解，但是有时候用ADMM求解子问题不能得到闭式解，就会考虑添加一项近邻项【proximal term】。为了使子问题的求解更简单，有时候会考虑线性化技术。由于ADMM算法的高效性，其应用非常广，因此关于ADMM的变形也非常多，但受于知识有限，只能简单介绍其中几种变形

如果优化问题具有如下可分离的形式
\begin{aligned} \min \quad & f(x) + g(y)\\ {\rm s.t} \quad &Ax+By=c\\ \end{aligned}\\就可以采用ADMM算法求解，具体如何实现ADMM算法可参考[1]。但是有时候子问题的闭式解求解是困难的，考虑如下Hankel矩阵核范数最小化问题[2] \min_{y}\frac{1}{2}\|\mathcal{A}(y)-b\|^2+\mu\|\mathcal{H}(y)\|_{*}\\ 其中 \mathcal{A}:\mathbb{R}^{m \times n(j+k-1)} \to \mathbb{R}^p 是一个线性映射， b \in \mathbb{R}^p ， y=(y_0...y_{j+k-2}) 是一个 m \times n(j+k-1) 的矩阵，其中 y_i,i=1,...,j+k-2 是一个 m \times n 的矩阵。通过引入一个辅助变量，上述优化问题等价于 \begin{aligned} \min\quad &\frac{1}{2}\|\mathcal{A}(y)-b\|^2+\mu\|Y\|_{*} \\ {\rm s.t} \quad & Y+\mathcal{H}(y)=0 \end{aligned}\\ 其对应的增广拉格朗日函数为
L_{\beta}(Y,y,\Lambda)=\frac{1}{2}\|\mathcal{A}(y)-b\|^2+\mu\|Y\|_{*} -\left<\Lambda ,Y+\mathcal{H}(y) \right>+\frac{\beta}{2}\|Y+\mathcal{H}(y)\|^{2}\\
y 子问题为
\begin{aligned} y^{k+1} &=\arg \min \ L_{\beta}(Y^{k+1},y,\Lambda^{k})\\ &=\arg \min \ y^T(\frac{1}{2}\mathcal{A}^{*}\mathcal{A}+\frac{\beta}{2}\mathcal{H}^*\mathcal{H})y-\left<\mathcal{A}^*(b),y\right>-\left<\mathcal{H}^{*}(\Lambda^k),y\right>+\beta \left<\mathcal{H}^{*}(Y^{k+1}),y\right> \end{aligned}\\ 关于y求导得到 (\mathcal{A}^*\mathcal{A}+\beta \mathcal{H}^*\mathcal{H})y=\mathcal{A}^*(b)+\mathcal{H}^*(\Lambda^k)+\beta \mathcal{H}^*(Y^{k+1})\\ 无法得到y的闭式解，因此在文章[2]中提出通过添加一项近邻项将子问题的求解变得简单，y 子问题的求解变为 y^{k+1} = {\arg\min} \ L_{\beta}(Y^{k+1},y,\Lambda^{k})+\frac{\beta}{2}\|y-y^k\|_{Q_0}^2\\\ 其中 \frac{\beta}{2}\|y-y^k\|_{Q_0}^2 是添加的近邻项， Q_0 是半正定矩阵，通过 Q_0 将影响求解子问题的复杂项 \mathcal{A}^*\mathcal{A}+\beta \mathcal{H}^*\mathcal{H} 给消去，并给定一个简单的正定项。这里通过简单简单计算可以得到 Q_0=\left(r+\frac{(\sigma_{\max}(\mathcal{A}))^2}{\beta}\right)\mathcal{I}-(\mathcal{H}^*\mathcal{H}+\frac{1}{\beta}\mathcal{A}^*\mathcal{A})\\
添加近邻项的ADMM的算法被称为近邻ADMM【Proximal ADMM】，其算法框架为
\begin{aligned} x^{k+1}&=\arg \min \ f(x)-\left<z^k,Ax\right>+\frac{\lambda}{2}\|Ax+By^k-c\|^2+\frac{1}{2}\|x-x^k\|_{S}^2\\ y^{k+1}&=\arg \min \ g(y)-\left<z^k,By\right>+\frac{\lambda}{2}\|Ax^{k+1}+By-c\|^2+\frac{1}{2}\|y-y^k\|^2_{T}\\ z^{k+1}&=z^k-\tau \lambda(Ax^{k+1}+By^{k+1}-c) \end{aligned}\\其中 \tau \in (0,(1+\sqrt{5})/2) 是步长，其中 S,T 是自伴随半正定算子，当 S=T=0 时，该算法变为经典ADMM【classical ADMM】。当步长的选择在 (0,(1+\sqrt{5})/2) 时，算法收敛到最优解。该篇文章是针对两块的，对于3块的近邻ADMM算法是否也有类似的收敛性呢，在文章[3]中证明了三块近邻ADMM算法的收敛性。对ADMM算法的改进还有很多种，目前只接触这些，将在后续的学习过程中不断补充
参考

^https://zhuanlan.zhihu.com/p/377178217
^abhttp://home.ustc.edu.cn/~qingling/pdf/2017-15.pdf
^https://arxiv.org/pdf/1410.7933.pdf

		自动登录	找回密码
密码			立即注册