A rank-two relaxed parallel splitting version of the augmented Lagrangian method with step size in (0,2) for separable convex programming

He, Bingsheng; Ma, Feng; Xu, Shengjie; Yuan, Xiaoming

doi:10.1090/mcom/3822

A rank-two relaxed parallel splitting version of the augmented Lagrangian method with step size in $(0,2)$ for separable convex programming
HTML articles powered by AMS MathViewer

by Bingsheng He, Feng Ma, Shengjie Xu and Xiaoming Yuan HTML | PDF

Math. Comp. 92 (2023), 1633-1663 Request permission

Abstract:

The augmented Lagrangian method (ALM) is classic for canonical convex programming problems with linear constraints, and it finds many applications in various scientific computing areas. A major advantage of the ALM is that the step for updating the dual variable can be further relaxed with a step size in $(0,2)$, and this advantage can easily lead to numerical acceleration for the ALM. When a separable convex programming problem is discussed and a corresponding splitting version of the classic ALM is considered, convergence may not be guaranteed and thus it is seemingly impossible that a step size in $(0,2)$ can be carried on to the relaxation step for updating the dual variable. We show that for a parallel splitting version of the ALM, a step size in $(0,2)$ can be maintained for further relaxing both the primal and dual variables if the relaxation step is simply corrected by a rank-two matrix. Hence, a rank-two relaxed parallel splitting version of the ALM with a step size in $(0,2)$ is proposed for separable convex programming problems. We validate that the new algorithm can numerically outperform existing algorithms of the same kind significantly by testing some applications.

References

R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim. 18 (2007), no. 4, 1286–1309. MR 2373302, DOI 10.1137/060654797
R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program. 111 (2008), no. 1-2, Ser. B, 5–32. MR 2322882, DOI 10.1007/s10107-006-0077-1
A. Beck, First-Order Methods in Optimization, vol. 25, SIAM, Philadelphia, 2017.
D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Athena Scientific, Belmont, MA, 1996.
E. G. Birgin and J. M. Martínez, Practical Augmented Lagrangian Methods for Constrained Optimization, SIAM, 2014.
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn. 3(1), 1–122 (2010).
Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright, Robust principal component analysis?, J. ACM 58 (2011), no. 3, Art. 11, 37. MR 2811000, DOI 10.1145/1970392.1970395
Emmanuel J. Candès, Carlos A. Sing-Long, and Joshua D. Trzasko, Unbiased risk estimates for singular value thresholding and spectral estimators, IEEE Trans. Signal Process. 61 (2013), no. 19, 4643–4657. MR 3105401, DOI 10.1109/TSP.2013.2270464
Antonin Chambolle and Thomas Pock, An introduction to continuous optimization for imaging, Acta Numer. 25 (2016), 161–319. MR 3509209, DOI 10.1017/S096249291600009X
Venkat Chandrasekaran, Pablo A. Parrilo, and Alan S. Willsky, Latent variable graphical model selection via convex optimization, Ann. Statist. 40 (2012), no. 4, 1935–1967. MR 3059067, DOI 10.1214/11-AOS949
Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev. 43 (2001), no. 1, 129–159. Reprinted from SIAM J. Sci. Comput. 20 (1998), no. 1, 33–61 (electronic) [ MR1639094 (99h:94013)]. MR 1854649, DOI 10.1137/S003614450037906X
Caihua Chen, Bingsheng He, Yinyu Ye, and Xiaoming Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program. 155 (2016), no. 1-2, Ser. A, 57–79. MR 3439797, DOI 10.1007/s10107-014-0826-5
Wei Deng, Ming-Jun Lai, Zhimin Peng, and Wotao Yin, Parallel multi-block ADMM with $o(1/k)$ convergence, J. Sci. Comput. 71 (2017), no. 2, 712–736. MR 3627538, DOI 10.1007/s10915-016-0318-2
J. Eckstein, Parallel alternating direction multiplier decomposition of convex programs, J. Optim. Theory Appl. 80 (1994), no. 1, 39–62. MR 1256136, DOI 10.1007/BF02196592
Jonathan Eckstein and Dimitri P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Programming 55 (1992), no. 3, Ser. A, 293–318. MR 1168183, DOI 10.1007/BF01581204
Ethan X. Fang, Bingsheng He, Han Liu, and Xiaoming Yuan, Generalized alternating direction method of multipliers: new theoretical insights and applications, Math. Program. Comput. 7 (2015), no. 2, 149–187. MR 3347621, DOI 10.1007/s12532-015-0078-2
Michel Fortin and Roland Glowinski, Augmented Lagrangian methods, Studies in Mathematics and its Applications, vol. 15, North-Holland Publishing Co., Amsterdam, 1983. Applications to the numerical solution of boundary value problems; Translated from the French by B. Hunt and D. C. Spicer. MR 724072
R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, 1984.
R. Glowinski and A. Marrocco, Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non linéaires, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér. 9 (1975), no. R-2, 41–76 (French, with English summary). MR 388811, DOI 10.1051/m2an/197509R200411
R. Glowinski and P. Le. Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989.
E. G. Gol’shtein, and N.V. Tret’yakov, Modified Lagrangians in convex programming and their generalizations, Math. Progr. Study 10 (1979), 86–97.
Bingsheng He, Liusheng Hou, and Xiaoming Yuan, On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM J. Optim. 25 (2015), no. 4, 2274–2312. MR 3424071, DOI 10.1137/130922793
Bingsheng He, Feng Ma, and Xiaoming Yuan, Optimal proximal augmented Lagrangian method and its application to full Jacobian splitting for multi-block separable convex minimization problems, IMA J. Numer. Anal. 40 (2020), no. 2, 1188–1216. MR 4092283, DOI 10.1093/imanum/dry092
Bingsheng He, Min Tao, and Xiaoming Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim. 22 (2012), no. 2, 313–340. MR 2968856, DOI 10.1137/110822347
Bingsheng He, Min Tao, and Xiaoming Yuan, A splitting method for separable convex programming, IMA J. Numer. Anal. 35 (2015), no. 1, 394–426. MR 3335210, DOI 10.1093/imanum/drt060
Bingsheng He, Min Tao, and Xiaoming Yuan, Convergence rate analysis for the alternating direction method of multipliers with a substitution procedure for separable convex programming, Math. Oper. Res. 42 (2017), no. 3, 662–691. MR 3685261, DOI 10.1287/moor.2016.0822
Bingsheng He, Hong-Kun Xu, and Xiaoming Yuan, On the proximal Jacobian decomposition of ALM for multiple-block separable convex minimization problems and its relationship to ADMM, J. Sci. Comput. 66 (2016), no. 3, 1204–1217. MR 3456970, DOI 10.1007/s10915-015-0060-1
B. S. He, S. J. Xu, X. M. Yuan, Extensions of ADMM for separable convex optimization problems with linear equality or inequality constraints, arXiv preprint, arXiv:2107.01897, 2021.
Bingsheng He and Xiaoming Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Numer. Anal. 50 (2012), no. 2, 700–709. MR 2914282, DOI 10.1137/110836936
Bingsheng He and Xiaoming Yuan, On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numer. Math. 130 (2015), no. 3, 567–577. MR 3347463, DOI 10.1007/s00211-014-0673-6
Magnus R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), 303–320. MR 271809, DOI 10.1007/BF00927673
Kazufumi Ito and Karl Kunisch, Lagrange multiplier approach to variational problems and applications, Advances in Design and Control, vol. 15, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. MR 2441683, DOI 10.1137/1.9780898718614
Krzysztof C. Kiwiel, Charles H. Rosa, and Andrzej Ruszczyński, Proximal decomposition via alternating linearization, SIAM J. Optim. 9 (1999), no. 3, 668–689. MR 1681047, DOI 10.1137/S1052623495288064
B. Martinet, Regularisation, d’inéquations variationelles par approximations succesives, Rev. Francaise d’Inform. Rech. Oper. 4 (1970), 154–159.
G. J. McLachlan, Discriminant Analysis and Statistical Pattern Recognition, vol. 544, Wiley Interscience, New York, 2004.
N. Parikh and S. Boyd, Proximal algorithms, Found. Trends Optim. 1 (2014), no. 3, 127–239.
Y. G. Peng, A. Ganesh, J. Wright, W. L. Xu, and Y. Ma, Robust alignment by sparse and low-rank decomposition for linearly correlated images, IEEE Trans. Pattern Anal. Mach. Intell. 34 (2012), 2233–2246.
M. J. D. Powell, A method for nonlinear constraints in minimization problems, In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic Press, New York, 1969.
R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1 (1976), no. 2, 97–116. MR 418919, DOI 10.1287/moor.1.2.97
Min Tao and Xiaoming Yuan, Recovering low-rank and sparse components of matrices from incomplete and noisy observations, SIAM J. Optim. 21 (2011), no. 1, 57–81. MR 2765489, DOI 10.1137/100781894
Min Tao and Xiaoming Yuan, On the optimal linear convergence rate of a generalized proximal point algorithm, J. Sci. Comput. 74 (2018), no. 2, 826–850. MR 3761279, DOI 10.1007/s10915-017-0477-9
Min Tao and Xiaoming Yuan, On Glowinski’s open question on the alternating direction method of multipliers, J. Optim. Theory Appl. 179 (2018), no. 1, 163–196. MR 3846938, DOI 10.1007/s10957-018-1338-x
Zaiwen Wen, Donald Goldfarb, and Wotao Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput. 2 (2010), no. 3-4, 203–230. MR 2741485, DOI 10.1007/s12532-010-0017-1