多块可分离凸优化问题的邻近ADMM算法及收敛性

Proximal ADMMs for Multi-block Separable Convex Optimizations and Convergences

摘要

交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）是求解两模块可分离凸优化问题的重要方法之一，近年来取得了较大进展。文献[24]提出了一种求解多块可分离凸优化问题的twisted邻近交替方向乘子法（Twisted version of the proximal Alternating Direction Method of Multipliers，TADMM），并证明了算法的收敛性和迭代复杂度。基于文献[24]的算法，文章提出两种推广的TADMM，分别证明其收敛性和迭代复杂度。最后，将LASSO模型应用到手写数字识别问题，并运用上述三种TADMM求解。数值实验表明，三种算法均收敛，并且文章提出的第一种TADMM表现最好。

Abstract

The Alternating Direction Method of Multipliers （ADMM） is one of the important methods for solving two-block separable convex optimization problems and has made significant progress in recent years. Recently，Wang et al. proposed a Twisted version of the proximal Alternating Direction Method of Multipliers （TADMM） to solve multi-block separable problems （involving three or more blocks）. Building on this work，the present study introduces two new TADMM variants，and systematically analyzes their convergence behaviors and iteration complexities. Finally，these algorithms are implemented to solve LASSO models in the handwritten digit recognition problems. Numerical experiments confirm the convergence of all three methods （the original TADMM and the two proposed variants） and further demonstrate the first variant proposed herein outperforms the other two by a significant margin.

关键词

可分离凸优化 / 增广拉格朗日函数 / 邻近交替方向乘子法 / 收敛性 / 手写数字识别

Key words

Separable convex optimization / Augmented Lagrangian function / Proximal ADMM / Convergence / Handwritten digit recognition problem

参考文献

[1] GLOWINSKI R, MARROCCO A. Sur L'approximation,Par Éléments Finis D'ordren,et La Résolution,Par Pénalisation-Dualité D'une Classe de Problèmes de Dirichlet Nonlinéares[J]. Revue Française d'Automatique,Informatique,Recherche Opérationnelle. Analyse Numérique, 1975, 9(R2): 41-76.

[2] BOYD S, PARIKH N, CHU E, et al. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers[J]. Foundations and Trends^® in Machine Learning, 2011, 3(01): 1-122.

[3] RYU E K, YIN W. Large-scale Convex Optimization:Algorithms and Analyses via Monotone Operators[M]. Cambridge: Cambridge University Press, 2023.

[4] FORTIN M, GLOWINSKI R. Augmented Lagrangian Methods[M]. Amsterdam: North-Holland, 1983.

[5] GLOWINSKI R. Lectures on Numerical Methods for Nonlinear Variational Problems[M]. Bombay: Tata Institute of Fundamental Research, 1980.

[6] CHAN T F, GLOWINSKI R. Finite Element Approximation and Iterative Solution of a Class of Mildly Nonlinear Elliptic Equations[R]. Stanford:Stanford University, 1978.

[7] ECKSTEIN J. Augmented Lagrangian and Alternating Direction Methods for Convex Optimization:A Tutorial and Some Illustrative Computational Results[R]. New Jersey: Rutgers University, 2012.

[8] GABAY D, MERCIER B. A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite-element Approximations[J]. Computers & Mathematics with Applications, 1976, 2: 17-40.

[9] HE B S, LIU H, WANG Z R, et al. A Strictly Peaceman-Rachford Splitting Method for Convex Programming[J]. SIAM Journal on Optimization, 2014, 24: 1011-1040.

[10] LIN Z, CHEN M, WU L, et al. The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-rank Matrices[J]. Mathematical Programming, 2010.

[11] SUN H, TAI X C, YUAN J. Efficient and Convergent Preconditioned ADMM for the Potts Models[J]. SIAM Journal on Scientific Computing, 2021: B455-B478. doi: 10.1137/20M1343956.

[12] XIONG Z, KANG J, NIYATO D, et al. Cloud/edge Computing Service Management in Blockchain Networks:Multi-leader Multi-follower Game-based ADMM for Pricing[J]. IEEE Transactions on Services Computing, 2019: 1.

[13] 刘浩洋, 卢将, 李勇锋, 等. 最优化:建模,算法与理论[M]. 北京: 高等教育出版社, 2020.

[14] CHEN C H, HE B S, YE Y Y, et al. The Direct Extension of ADMM for Multi-block Convex Minimization Problems is not Necessarily Convergent[J]. Mathematical Programming, 2016, 155(1-2): 57-79.

[15] HE B S, TAO M, YUAN X M. Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming[J]. SIAM Journal on Optimization, 2012, 22: 313-340.

[16] HE B S, TAO M, YUAN X M. Convergence Rate and Iteration Complexity on the Alternation Direction Method of Multipliers with a Substitution Procedure for Separable Convex Programming[R]. Manuscript.

[17] ECKSTEIN J. Some Saddle-function Splitting Methods for Convex Programming[J]. Optimization Methods and Software, 1994, 4: 75-83.

[18] HE B S, LIAO L Z, HAN D, et al. A New Inexact Alternating Direction Method for Monotone Variational Inequalities[J]. Mathematical Programming, 2002, 92: 103-118.

[19] XU M H, WU T. A Class of Linearized Proximal Alternating Direction Methods[J]. Journal of Optimization Theory and Applications, 2011, 155: 321-337.

[20] FAZEL M, PONG T K, SUN D F, et al. Hankel Matrix Rank Minimization with Application to System Identification and Realization[J]. SIAM Journal on Matrix Analysis and Applications, 2013, 34: 946-977.

[21] CHEN G, TEBOULLE M. A Proximal-based Decomposition Method for Convex Minimization Problems[J]. Mathematical Programming, 1994, 64: 81-101.

[22] HONG M Y, LUO Z Q. On the Linear Convergence of the Alternating Direction Method of Multipliers[R]. arXiv:1208.3922, 2012.

[23] YANG J, ZHANG Y. Alternating Direction Algorithms for Problems in Compressive Sensing[J]. SIAM Journal on Scientific Computing, 2011, 33: 250-278.

[24] WANG J J, SONG W. An Algorithm Twisted from Generalized ADMM for Multi-block Separable Convex Minimization Models[J]. Journal of Computational and Applied Mathematics, 2017, 309: 342-358.

[25] ROCKAFELLAR R T. Convex Analysis[M]. Princeton: Princeton University Press, 1970.

[26] BOYD S, VANDENBERGHE L. Convex Optimization[M]. Cambridge: Cambridge University Press, 2004.

[27] TIBSHIRANI R, SAUNDERS M, ROSSET S, et al. Sparsity and Smoothness via the Fused Lasso[J]. Journal of the Royal Statistical Society Series B:Statistical Methodology, 2005, 67(01): 91-108.

基金资助

国家自然科学基金项目(12161017)

国家自然科学基金项目(12561953)