An LQP-Based Symmetric Alternating Direction Method of Multipliers with Larger Step Sizes

doi:10.1007/s40305-019-00247-y

Abstract

Abstract: Symmetric alternating direction method of multipliers (ADMM) is an efficient method for solving a class of separable convex optimization problems. Thismethod updates the Lagrange multiplier twice with appropriate step sizes at each iteration. However, such step sizes were conservatively shrunk to guarantee the convergence in recent studies. In this paper, we are devoted to seeking larger step sizes whenever possible. The logarithmic-quadratic proximal (LQP) terms are applied to regularize the symmetric ADMM subproblems, allowing the constrained subproblems to then be converted to easier unconstrained ones. Theoretically, we prove the global convergence of such LQP-based symmetric ADMM by specifying a larger step size domain. Moreover, the numerical results on a traffic equilibrium problem are reported to demonstrate the advantage of the method with larger step sizes.

Key words: Convex optimization, Symmetric alternating direction method of multipliers, Logarithmic-quadratic proximal regularization, Larger step sizes, Global convergence

CLC Number:

Zhong-Ming Wu, Min Li. An LQP-Based Symmetric Alternating Direction Method of Multipliers with Larger Step Sizes[J]. Journal of the Operations Research Society of China, 2019, 7(2): 365-383.

TrendMD

References 24

[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. 3, 1-122(2011)
[2]	He, B., Xu, Y., Yuan, X.:A logarithmic-quadratic proximal prediction-correction method for structured monotone variational inequalities. Comput. Optim. Appl. 35, 19-46(2006)
[3]	Yang, H., Huang, H.:Mathematical and Economic Theory of Road Pricing. Elsevier, Amsterdam (2005)
[4]	He, B., Ma, F., Yuan, X.:Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J. Imaging Sci. 9, 1467-1501(2016)
[5]	Gabay, D., Mercier, B.:A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2, 17-40(1976)
[6]	Glowinski, R., Marroco, A.: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. Francaise Automat. Inform. Rech. Opér. Sér. Rouge Anal. Numér 9, 41-76(1975)
[7]	Eckstein, J., Yao, W.:Understanding the convergence of the alternating direction method of multipliers:theoretical and computational perspectives. Pac. J. Optim. 11, 619-644(2015)
[8]	He, B., Yuan, X.:On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J. Numer. Anal. 50, 700-709(2012)
[9]	He, B., Liu, H., Wang, Z., Yuan, X.:A strictly contractive Peaceman-Rachford splitting method for convex programming. SIAM J. Optim. 24, 1011-1040(2014)
[10]	Auslender, A., Teboulle, M., Ben-Tiba, S.:A logarithmic-quadratic proximal method for variational inequalities. In:Computational Optimization, pp. 31-40. Springer (1999)
[11]	Li, M., Yuan, X.:A strictly contractive Peaceman-Rachford splitting method with logarithmicquadratic proximal regularization for convex programming. Math. Oper. Res. 40, 842-858(2015)
[12]	Yuan, X., Li, M.:An LQP-based decomposition method for solving a class of variational inequalities. SIAM J. Optim. 21, 1309-1318(2011)
[13]	Auslender, A., Teboulle, M.:Entropic proximal decomposition methods for convex programs and variational inequalities. Math. Program. 91, 33-47(2001)
[14]	Auslender, A., Teboulle, M.:The log-quadratic proximal methodology in convex optimization algorithms and variational inequalities. In:Equilibrium Problems and Variational Models, pp. 19-52. Springer (2003)
[15]	Han, D.:A hybrid entropic proximal decomposition method with self-adaptive strategy for solving variational inequality problems. Comput. Math. Appl. 55, 101-115(2008)
[16]	Bai, J., Zhang, H., Li, J., Xu, F.:Generalized symmetric ADMM for separable convex optimization. Comput. Optim. Appl. 70(1), 129-170(2018)
[17]	Gu, Y., Jiang, B., Han, D.:A semi-proximal-based strictly contractive Peaceman-Rachford splitting method. arXiv:1506.02221(2015)
[18]	Chen, C., Li, M., Yuan, X.:Further study on the convergence rate of alternating direction method of multipliers with logarithmic-quadratic proximal regularization. J. Optim. Theory Appl. 166, 906-929(2015)
[19]	Li, M., Li, X., Yuan, X.:Convergence analysis of the generalized alternating direction method of multipliers with logarithmic-quadratic proximal regularization. J. Optim. Theory Appl. 164, 218-233(2015)
[20]	Kontogiorgis, S., Meyer, R.:A variable-penalty alternating directions method for convex optimization. Math. Program. 83, 29-53(1998)
[21]	Tao, M., Yuan, X.:On the O(1/t) convergence rate of alternating direction method with logarithmicquadratic proximal regularization. SIAM J. Optim. 22, 1431-1448(2012)
[22]	He, H., Wang, K., Cai, X., Han, D.:An LQP-based two-step method for structured variational inequalities. J. Oper. Res. Soc. China 5, 301-317(2017)
[23]	Nagurney, A., Zhang, D.:Projected Dynamical Systems and Variational Inequalities with Applications. International Series in Operations Research and Management Science. Springer, New York (1996)
[24]	Li, M.:A hybrid LQP-based method for structured variational inequalities. Int. J. Comput. Math. 89(10), 1412-1425(2012)