Alternating Direction Method for Separable Variables Under Pair-Wise Constraints

Abstract

While the convergence of alternating direction method (ADM) for two separable variables has been established for years, the validity of its direct generalization to more than two blocks has been studying now. In this paper, we propose an additional requirement on the constraints, i.e., the pair-wise linear constraints and establish the convergence of ADM for more than two blocks. Then we apply our approach to two kinds of optimization problems. We also show several numerical experiments to verify the rationality of proposed algorithm.

Keywords

Alternating direction method / Convergence analysis / Pair-wise constraints / $\ell _1$-Analysis problem')">$\ell _1$-Analysis problem

References

[1] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn.. 2011, 3 1 1-122

[2] Chen C, He B, Ye Y, Yuan X. The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program.. 2016, 155 1–2 57-79

[3] Deng, W., Lai, M., Peng, Z., Yin, W.: Parallel multi-block ADMM with o (1/k) convergence. arXiv preprint arXiv:1312.3040 (2013)

[4] Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. Rice University CAAM Technical Report, (TR12-14) (2012)

[5] Deng W, Yin W. On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput.. 2016, 66 3 889-916

[6] He, B., Tao, M., Yuan, X.: A splitting method for separate convex programming with linking linear constraints. Optimization Online (2010)

[7] He B, Tao M, Yuan X. Alternating direction method with gaussian back substitution for separable convex programming. SIAM J. Optim.. 2012, 22 2 313-340

[8] He B, Tao M, Yuan X. A splitting method for separable convex programming. IMA J. Numer. Anal.. 2015, 35 1 394-426

[9] He, B., Yuan, X.: Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond. SMAI J. Comput. Math. 1, 145–175 (2015)

[10] Hong, M., Luo, Z.-Q.: On the linear convergence of the alternating direction method of multipliers. arXiv preprint arXiv:1208.3922 (2012)

[11] Malioutov D, Çetin M, Willsky AS. A sparse signal reconstruction perspective for source localization with sensor arrays. IEEE Trans. Signal Process.. 2005, 53 8 3010-3022

[12] Peng Y, Ganesh A, Wright J, Wenli X, Ma Y. Rasl: Robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Trans. Pattern Anal. Mach. Intell.. 2012, 34 11 2233-2246

[13] Tao M, Yuan X. Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim.. 2011, 21 1 57-81

[14] Yan, M., Yin, W.: Self equivalence of the alternating direction method of multipliers. arXiv preprint arXiv:1407.7400 (2014)

[15] Yao, H., Gerstoft, P., Shearer, P.M., Mecklenbräuker, C.: Compressive sensing of the Tohoku-Oki Mw 9.0 earthquake: Frequency-dependent rupture modes. Geophys. Res. Lett. 38(20), L20310 (2011)

[16] Yuan M, Lin Y. Model selection and estimation in regression with grouped variables. J. R. Stat. Soc. Ser. B. 2006, 68 1 49-67

Funding

National Natural Science Foundation of China(No. 11626253)

Fundamental Research Funds for the Central Universities