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

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-019-00247-y

https://www.jorsc.shu.edu.cn/EN/Y2019/V7/I2/365

[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)

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

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Rui-Jin Zhang, Zhao-Wei Wang, Xin-Wei Liu, Yu-Hong Dai. IPRSOCP: A Primal-Dual Interior-Point Relaxation Algorithm for Second-Order Cone Programming [J]. Journal of the Operations Research Society of China, 2026, 14(1): 1-31.
[2]	Wei-Yi Shao, Jin-Yan Fan. Global Convergence of a Stochastic Levenberg-Marquardt Algorithm Based on Trust Region [J]. Journal of the Operations Research Society of China, 2026, 14(1): 32-54.
[3]	Hao-Yang Liu, Xian-Tao Xiao, Li-Wei Zhang. Augmented Lagrangian Methods for Time-Varying Constrained Online Convex Optimization [J]. Journal of the Operations Research Society of China, 2025, 13(2): 364-392.
[4]	Jin-Bao Jian, Guo-Dong Ma, Xiao Xu, Dao-Lan Han. Monotone Splitting SQP Algorithms for Two-block Nonconvex Optimization Problems with General Linear Constraints and Applications [J]. Journal of the Operations Research Society of China, 2025, 13(1): 114-141.
[5]	Qiao Chen, Xin-Min Yang, Qian Yan. A New Class of Filled Functions with Two Parameters for Solving Unconstrained Global Optimization Problems [J]. Journal of the Operations Research Society of China, 2024, 12(4): 921-936.
[6]	Ya Zhang, Cong Sun. Cyclic Gradient Methods for Unconstrained Optimization [J]. Journal of the Operations Research Society of China, 2024, 12(3): 809-828.
[7]	Peng-Jie Liu, Jin-Bao Jian, Hu Shao, Xiao-Quan Wang, Jia-Wei Xu, Xiao-Yu Wu. A Bregman-Style Improved ADMM and its Linearized Version in the Nonconvex Setting: Convergence and Rate Analyses [J]. Journal of the Operations Research Society of China, 2024, 12(2): 298-340.
[8]	Gabrie Aníbal Carrizo, Nadia Soledad Fazzio, María Laura Schuverdt. A Nonmonotone Projected Gradient Method for Multiobjective Problems on Convex Sets [J]. Journal of the Operations Research Society of China, 2024, 12(2): 410-427.
[9]	Gong-Lin Yuan, Ying-Jie Zhou, Meng-Xiang Zhang. A Hybrid Conjugate Gradient Algorithm for Nonconvex Functions and Its Applications in Image Restoration Problems [J]. Journal of the Operations Research Society of China, 2023, 11(4): 759-781.
[10]	Jian-Chao Bai, Feng-Miao Bian, Xiao-Kai Chang, Lin Du. Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization [J]. Journal of the Operations Research Society of China, 2023, 11(4): 783-807.
[11]	Xin-Xin Li, Xiao-Ya Zhang. A New Stopping Criterion for Eckstein and Bertsekas’s Generalized Alternating Direction Method of Multipliers [J]. Journal of the Operations Research Society of China, 2023, 11(4): 941-955.
[12]	Ru-Jun Jiang, Zhi-Shuo Zhou, Zi-Rui Zhou. Cubic Regularization Methods with Second-Order Complexity Guarantee Based on a New Subproblem Reformulation [J]. Journal of the Operations Research Society of China, 2022, 10(3): 471-506.
[13]	De-Ren Han. A Survey on Some Recent Developments of Alternating Direction Method of Multipliers [J]. Journal of the Operations Research Society of China, 2022, 10(1): 1-52.
[14]	Julien Collonge. Necessary Optimality Conditions for Semi-vectorial Bi-level Optimization with Convex Lower Level: Theoretical Results and Applications to the Quadratic Case [J]. Journal of the Operations Research Society of China, 2021, 9(3): 691-712.
[15]	Xiao-Liang Dong, Zhi-Feng Dai, Reza Ghanbari, Xiang-Li Li. An Adaptive Three-Term Conjugate Gradient Method with Sufficient Descent Condition and Conjugacy Condition [J]. Journal of the Operations Research Society of China, 2021, 9(2): 411-425.