A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications

Zhang, Ning; Wu, Jia; Zhang, Liwei

doi:10.1090/mcom/3506

A linearly convergent majorized ADMM with indefinite proximal terms for convex composite programming and its applications
HTML articles powered by AMS MathViewer

by Ning Zhang, Jia Wu and Liwei Zhang HTML | PDF

Math. Comp. 89 (2020), 1867-1894 Request permission

Abstract:

This paper aims to study a majorized alternating direction method of multipliers with indefinite proximal terms (iPADMM) for convex composite optimization problems. We show that the majorized iPADMM for 2-block convex optimization problems converges globally under weaker conditions than those used in the literature and exhibits a linear convergence rate under a local error bound condition. Based on these, we establish the linear rate convergence results for a symmetric Gauss-Seidel based majorized iPADMM, which is designed for multiblock composite convex optimization problems. Moreover, we apply the majorized iPADMM to solve different types of regularized logistic regression problems. The numerical results on both synthetic and real datasets demonstrate the efficiency of the majorized iPADMM and also illustrate the effectiveness of the introduced indefinite proximal terms.

References

S. Banert, R. I. Bot, and E. R. Csetnek, Fixing and extending some recent results on the admm algorithm, arXiv preprint arXiv:1612.05057, (2016).
Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183–202. MR 2486527, DOI 10.1137/080716542
C.-C. Chang and C.-J. Lin, LIBSVM: A library for support vector machines, ACM Transactions on Intelligent Systems and Technology, 2(3):Article 27, 2011. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
Liang Chen, Defeng Sun, and Kim-Chuan Toh, An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming, Math. Program. 161 (2017), no. 1-2, Ser. A, 237–270. MR 3592778, DOI 10.1007/s10107-016-1007-5
H.-Y. Chuang, E. Lee, Y.-T. Liu, D. Lee, and T. Ideker, Network-based classification of breast cancer metastasis, Molecular Systems Biology, 3(1):140, 2007.
Frank H. Clarke, Optimization and nonsmooth analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1983. A Wiley-Interscience Publication. MR 709590
L. Condat. A direct algorithm for 1-D total variation denoising. IEEE Signal Processing Letters, 20(11):1054–1057, 2013.
Laurent Condat, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl. 158 (2013), no. 2, 460–479. MR 3084386, DOI 10.1007/s10957-012-0245-9
Chao Ding, Defeng Sun, and Liwei Zhang, Characterization of the robust isolated calmness for a class of conic programming problems, SIAM J. Optim. 27 (2017), no. 1, 67–90. MR 3594330, DOI 10.1137/16M1058753
Yunda Dong, An extension of Luque’s growth condition, Appl. Math. Lett. 22 (2009), no. 9, 1390–1393. MR 2536820, DOI 10.1016/j.aml.2007.07.037
A. L. Dontchev and R. T. Rockafellar, Regularity and conditioning of solution mappings in variational analysis, Set-Valued Anal. 12 (2004), no. 1-2, 79–109. MR 2069353, DOI 10.1023/B:SVAN.0000023394.19482.30
Asen L. Dontchev and R. Tyrrell Rockafellar, Implicit functions and solution mappings, Springer Monographs in Mathematics, Springer, Dordrecht, 2009. A view from variational analysis. MR 2515104, DOI 10.1007/978-0-387-87821-8
Dmitriy Drusvyatskiy and Adrian S. Lewis, Error bounds, quadratic growth, and linear convergence of proximal methods, Math. Oper. Res. 43 (2018), no. 3, 919–948. MR 3846078, DOI 10.1287/moor.2017.0889
J. Eckstein, Splitting methods for monotone operators with applications to parallel optimization, Ph.D. thesis, Massachusetts Institute of Technology, 1989.
J. Eckstein, Some saddle-function splitting methods for convex programming, Optimization Methods and Software, 4(1):75–83, 1994.
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
Maryam Fazel, Ting Kei Pong, Defeng Sun, and Paul Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM J. Matrix Anal. Appl. 34 (2013), no. 3, 946–977. MR 3073649, DOI 10.1137/110853996
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
J. Friedman, T. Hastie, and R. Tibshirani, Regularization paths for generalized linear models via coordinate descent, Journal of Statistical Software, 33(1):1, 2010.
D. Gabay and M. Bertrand, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers $\&$ Mathematics with Applications, 2(1):17–40, 1976.
Roland Glowinski, Numerical methods for nonlinear variational problems, Scientific Computation, Springer-Verlag, Berlin, 2008. Reprint of the 1984 original. MR 2423313
Roland Glowinski, On alternating direction methods of multipliers: a historical perspective, Modeling, simulation and optimization for science and technology, Comput. Methods Appl. Sci., vol. 34, Springer, Dordrecht, 2014, pp. 59–82. MR 3330832, DOI 10.1007/978-94-017-9054-3_{4}
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
Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
Deren Han, Defeng Sun, and Liwei Zhang, Linear rate convergence of the alternating direction method of multipliers for convex composite programming, Math. Oper. Res. 43 (2018), no. 2, 622–637. MR 3801109, DOI 10.1287/moor.2017.0875
J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I: Fundamentals, volume 305. Springer Science & Business Media, 2013.
G. M. James, C. Paulson, and P. Rusmevichientong, Penalized and constrained optimization: An application to high-dimensional website advertising, Journal of the American Statistical Association, 2019. Available at https://doi.org/10.1080/01621459.2019.1609970.
Rodolphe Jenatton, Jean-Yves Audibert, and Francis Bach, Structured variable selection with sparsity-inducing norms, J. Mach. Learn. Res. 12 (2011), 2777–2824. MR 2854347
Xin Yee Lam, J. S. Marron, Defeng Sun, and Kim-Chuan Toh, Fast algorithms for large-scale generalized distance weighted discrimination, J. Comput. Graph. Statist. 27 (2018), no. 2, 368–379. MR 3816272, DOI 10.1080/10618600.2017.1366915
Claude Lemaréchal and Claudia Sagastizábal, Practical aspects of the Moreau-Yosida regularization: theoretical preliminaries, SIAM J. Optim. 7 (1997), no. 2, 367–385. MR 1443624, DOI 10.1137/S1052623494267127
Min Li, Defeng Sun, and Kim-Chuan Toh, A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization, SIAM J. Optim. 26 (2016), no. 2, 922–950. MR 3484404, DOI 10.1137/140999025
Xudong Li, Defeng Sun, and Kim-Chuan Toh, A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions, Math. Program. 155 (2016), no. 1-2, Ser. A, 333–373. MR 3439805, DOI 10.1007/s10107-014-0850-5
Xudong Li, Defeng Sun, and Kim-Chuan Toh, A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications, Math. Program. 175 (2019), no. 1-2, Ser. A, 395–418. MR 3942895, DOI 10.1007/s10107-018-1247-7
Xudong Li, Defeng Sun, and Kim-Chuan Toh, A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems, SIAM J. Optim. 28 (2018), no. 1, 433–458. MR 3763098, DOI 10.1137/16M1097572
M. Lichman, UCI machine learning repository, 2013. Available at http://archive.ics.uci.edu/ml.
J. Liu, J. Chen, and J. Ye, Large-scale sparse logistic regression, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 547–556. ACM, 2009.
J. Liu, L. Yuan, and J. Ye, An efficient algorithm for a class of fused lasso problems, Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 323–332. ACM, 2010.
Jean-Jacques Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965), 273–299 (French). MR 201952
Yurii Nesterov, Introductory lectures on convex optimization, Applied Optimization, vol. 87, Kluwer Academic Publishers, Boston, MA, 2004. A basic course. MR 2142598, DOI 10.1007/978-1-4419-8853-9
Yu. E. Nesterov, A method for solving the convex programming problem with convergence rate $O(1/k^{2})$, Dokl. Akad. Nauk SSSR 269 (1983), no. 3, 543–547 (Russian). MR 701288
Stephen M. Robinson, Some continuity properties of polyhedral multifunctions, Math. Programming Stud. 14 (1981), 206–214. MR 600130, DOI 10.1007/bfb0120929
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, volume 317. Springer Science & Business Media, 2009.
Jie Sun, ON MONOTROPIC PIECEWISE QUADRATIC PROGRAMMING (NETWORK, ALGORITHM, CONVEX PROGRAMMING, DECOMPOSITION METHOD), ProQuest LLC, Ann Arbor, MI, 1986. Thesis (Ph.D.)–University of Washington. MR 2635493
Robert Tibshirani, Regression shrinkage and selection via the lasso, J. Roy. Statist. Soc. Ser. B 58 (1996), no. 1, 267–288. MR 1379242
R. Tibshirani, The lasso method for variable selection in the Cox model, Statistics in Medicine, 16(4):385–395, 1997.
Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight, Sparsity and smoothness via the fused lasso, J. R. Stat. Soc. Ser. B Stat. Methodol. 67 (2005), no. 1, 91–108. MR 2136641, DOI 10.1111/j.1467-9868.2005.00490.x
J. J. Ye, Constraint qualifications and necessary optimality conditions for optimization problems with variational inequality constraints, SIAM J. Optim. 10 (2000), no. 4, 943–962. MR 1777074, DOI 10.1137/S105262349834847X
X. Yuan, S. Zeng, and J. Zhang. Discerning the linear convergence of admm for structured convex optimization through the lens of variational analysis. 2018. Available at http://www.optimization-online.org/DB HTML/2018/10/6882.html.