×

Linear rate convergence of the alternating direction method of multipliers for convex composite programming. (English) Zbl 1440.90047

Summary: In this paper, we aim to prove the linear rate convergence of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex composite optimization problems. Under a mild calmness condition, which holds automatically for convex composite piecewise linear-quadratic programming, we establish the global Q-linear rate of convergence for a general semi-proximal ADMM with the dual step-length being taken in \((0, (1+5^{1/2})/2)\). This semi-proximal ADMM, which covers the classic one, has the advantage to resolve the potentially nonsolvability issue of the subproblems in the classic ADMM and possesses the abilities of handling the multi-block cases efficiently. We demonstrate the usefulness of the obtained results when applied to two- and multi-block convex quadratic (semidefinite) programming.

MSC:

90C25 Convex programming
90C20 Quadratic programming
90C22 Semidefinite programming
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Boley D (2013) Local linear convergence of ADMM on quadratic or linear programs. SIAM J. Optim. 23(4):2183-2207.Crossref, Google Scholar · Zbl 1288.65086 · doi:10.1137/120878951
[2] Bonnans JF, Shapiro A (2000) Perturbation Analysis of Optimization Problems (Springer, New York).Crossref, Google Scholar · Zbl 0966.49001 · doi:10.1007/978-1-4612-1394-9
[3] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1):1-122.Crossref, Google Scholar · Zbl 1229.90122 · doi:10.1561/2200000016
[4] Chen CH, He BS, Ye YY, Yuan XM (2016) The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Programming 155(1-2):57-79.Crossref, Google Scholar · Zbl 1332.90193 · doi:10.1007/s10107-014-0826-5
[5] Chen L, Sun DF, Toh K-C (2017) An efficient inexact symmetric Gauss-Seidel-based majorized ADMM for high-dimensional convex composite conic programming. Math. Programming 161(1-2):237-270.Crossref, Google Scholar · Zbl 1356.90105 · doi:10.1007/s10107-016-1007-5
[6] Chen L, Sun DF, Toh K-C (2017) A note on the convergence of ADMM for linearly constrained convex optimization problems. Comput. Optim. Appl. 66:327-343.Crossref, Google Scholar · Zbl 1367.90083 · doi:10.1007/s10589-016-9864-7
[7] Cui Y, Sun DF, Toh K-C (2016) On the asymptotic superlinear convergence of the augmented Lagrangian method for semidefinite programming with multiple solutions. Preprint arXiv:1610.00875.Google Scholar
[8] Cui Y, Li XD, Sun DF, Toh K-C (2016) On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions. J. Optim. Theory Appl. 169(3):1013-1041.Crossref, Google Scholar · Zbl 1342.90130 · doi:10.1007/s10957-016-0877-2
[9] Deng W, Yin WT (2016) On the global and linear convergence of the generalized alternating direction method of multipliers. J. Scientific Comput. 66(3):889-916.Crossref, Google Scholar · Zbl 1379.65036 · doi:10.1007/s10915-015-0048-x
[10] Ding C, Sun DF, Zhang LW (2017) Characterization of the robust isolated calmness for a class of conic programming problems. SIAM J. Optim. 27(1):67-90.Crossref, Google Scholar · Zbl 1357.49100 · doi:10.1137/16M1058753
[11] Dontchev AL, Rockafellar RT (2009) Implicit Functions and Solution Mappings (Springer, New York).Crossref, Google Scholar · Zbl 1178.26001 · doi:10.1007/978-0-387-87821-8
[12] Eckstein J (1989) Splitting Methods for Monotone Operators with Applications to Parallel Optimization. PhD Thesis, MIT, Cambridge, MA.Google Scholar
[13] Eckstein J (1994) Some saddle-function splitting methods for convex programming. Optim. Methods and Software 4(1):75-83.Crossref, Google Scholar · doi:10.1080/10556789408805578
[14] Eckstein J, Bertsekas DP (1992) On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Programming 55(1-3):293-318.Crossref, Google Scholar · Zbl 0765.90073 · doi:10.1007/BF01581204
[15] Eckstein J, Yao W (2015) Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives. Pacific J. Optim. 11(4):619-644.Google Scholar · Zbl 1330.90074
[16] Fazel M, Pong TK, Sun DF, Tseng P (2013) Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 34(3):946-977.Crossref, Google Scholar · Zbl 1302.90127 · doi:10.1137/110853996
[17] Fortin M, Glowinski R (1983) On decomposition-coordination methods using an augmented Lagrangian. Fortin M, Glowinski R, eds. Augmented Lagrangian Methods: Applications to the Solution of Boundary Problems. Studies in Mathematics And its Applications, Vol. 15 (Elsevier, Amsterdam), 97-146.Crossref, Google Scholar · Zbl 0525.65045 · doi:10.1016/S0168-2024(08)70028-6
[18] Fujiwara O, Han S-P, Mangasarian OL (1984) Local duality of nonlinear programs. SIAM J. Control Optim. 22(1):162-169.Crossref, Google Scholar · Zbl 0533.49008 · doi:10.1137/0322012
[19] Gabay D (1983) Applications of the method of multipliers to variational inequalities. Fortin M, Glowinski R, eds. Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems. Studies in Mathematics And its Applications, Vol. 15 (Elsevier, Amsterdam), 299-331.Crossref, Google Scholar · Zbl 0525.65045 · doi:10.1016/S0168-2024(08)70034-1
[20] Gabay D, Mercier B (1976) A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2:17-40.Crossref, Google Scholar · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[21] Glowinski R (1980) Lectures on numerical methods for nonlinear variational problems. (Springer, Berlin).Google Scholar · Zbl 0456.65035
[22] Glowinski R (2014) On alternating direction methods of multipliers: A historical perspective. Fitzgibbon W, Kuznetsov YA, Neittaanmaki P, Pironneau O, eds. Modeling, Simulation and Optimization for Science and Technology (Springer, Netherlands), 59-82.Crossref, Google Scholar · Zbl 1320.65098 · doi:10.1007/978-94-017-9054-3_4
[23] Glowinski R, Marroco A (1975) 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. Revue française d’atomatique, informatique recherche opérationelle. Analyse Numérique 9(R2):41-76.Google Scholar · Zbl 0368.65053
[24] Han DR, Yuan XM (2013) Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J. Numerical Anal. 51(6):3446-3457.Crossref, Google Scholar · Zbl 1285.90033 · doi:10.1137/120886753
[25] Han DR, Sun DF, Zhang LW (2015) On the isolated calmness and strong regularity for convex composite quadratic semidefinite programming, November 2016; revised from the second part of arXiv:1508.02134, August.Google Scholar
[26] He BS, Liao LZ, Han DR, Yang H (2002) A new inexact alternating directions method for monotone variational inequalities. Math. Programming 92(1):103-118.Crossref, Google Scholar · Zbl 1009.90108 · doi:10.1007/s101070100280
[27] Hong M, Luo ZQ (2017) On the linear convergence of alternating direction method of multipliers. Math. Programming 162(1-2):165-199.Crossref, Google Scholar · Zbl 1362.90313 · doi:10.1007/s10107-016-1034-2
[28] Li M, Sun DF, Toh K-C (2016) A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization. SIAM J. Optim. 26(2):922-950.Crossref, Google Scholar · Zbl 1338.90305 · doi:10.1137/140999025
[29] Li XD (2015) A two-phase augmented Lagrangian method for convex composite quadratic programming. PhD Thesis, Department of Mathematics, National University of Singapore.Google Scholar
[30] Li XD, Sun DF, Toh K-C (2016) A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Programming 155(1-2):333-373.Crossref, Google Scholar · Zbl 1342.90134 · doi:10.1007/s10107-014-0850-5
[31] Lions PL, Mercier B (1979) Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numerical Anal. 16(6):964-979.Crossref, Google Scholar · Zbl 0426.65050 · doi:10.1137/0716071
[32] Luque FJ (1984) Asymptotic convergence analysis of the proximal point algorithm. SIAM J. Control Optim. 22(2):277-293.Crossref, Google Scholar · Zbl 0533.49028 · doi:10.1137/0322019
[33] Qi HD (2009) Local duality of nonlinear semidefinite programming. Math. Oper. Res. 34(1):124-141.Link, Google Scholar · Zbl 1218.90193
[34] Robinson SM (1976) An implicit-function theorem for generalized variational inequalties. Technical Summary Report 1672, Mathematics Research Center, University of Wisconsin-Madison; available from National Technical Information Service under Accession ADA031952.Google Scholar
[35] Robinson SM (1981) Some continuity properties of polyhedral multifunctions. König H, Korte B, Ritter K, eds. Mathematical Programming at Oberwolfach. Mathematical Programming Studies, Vol. 14 (Springer, Berlin), 206-214.Crossref, Google Scholar · Zbl 0449.90090 · doi:10.1007/BFb0120929
[36] Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar · Zbl 0932.90001 · doi:10.1515/9781400873173
[37] Rockafellar RT (1976) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97-116.Link, Google Scholar · Zbl 0402.90076
[38] Rockafellar RT (1976) Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5):877-898.Crossref, Google Scholar · Zbl 0358.90053 · doi:10.1137/0314056
[39] Rockafellar RT, Wets RJ-B (1998) Variational Analysis (Springer, Berlin).Crossref, Google Scholar · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[40] Shefi R, Teboulle M (2014) Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization. SIAM J. Optim. 24(1):269-297.Crossref, Google Scholar · Zbl 1291.90176 · doi:10.1137/130910774
[41] Sun DF, Toh K-C, Yang LQ (2015) A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J. Optim. 25(2):882-915.Crossref, Google Scholar · Zbl 1328.90083 · doi:10.1137/140964357
[42] Sun J (1986) On monotropic piecewise qudratic programming. PhD Thesis, Department of Mathematics, University of Washington, Seattle.Google Scholar
[43] Xu MH, Wu T (2011) A class of linearized proximal alternating direction methods. J. Optim. Theory Appl. 151(2):321-337.Crossref, Google Scholar · Zbl 1242.90168 · doi:10.1007/s10957-011-9876-5
[44] Yang WH, · Zbl 1342.90138 · doi:10.1137/140974237
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.