Linear Rate Convergence of the Alternating Direction Method of Multipliers for Convex Composite Programming

References

• Boley D (2013) Local linear convergence of ADMM on quadratic or linear programs. SIAM J. Optim. 23(4):2183–2207.Crossref, Google Scholar
• Bonnans JF, Shapiro A (2000) Perturbation Analysis of Optimization Problems (Springer, New York).Crossref, Google Scholar
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Dontchev AL, Rockafellar RT (2009) Implicit Functions and Solution Mappings (Springer, New York).Crossref, Google Scholar
• Eckstein J (1989) Splitting Methods for Monotone Operators with Applications to Parallel Optimization. PhD Thesis, MIT, Cambridge, MA.Google Scholar
• Eckstein J (1994) Some saddle-function splitting methods for convex programming. Optim. Methods and Software 4(1):75–83.Crossref, Google Scholar
• 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
• 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
• 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
• 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
• Fujiwara O, Han S-P, Mangasarian OL (1984) Local duality of nonlinear programs. SIAM J. Control Optim. 22(1):162–169.Crossref, Google Scholar
• 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
• 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
• Glowinski R (1980) Lectures on numerical methods for nonlinear variational problems. (Springer, Berlin).Google Scholar
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• Luque FJ (1984) Asymptotic convergence analysis of the proximal point algorithm. SIAM J. Control Optim. 22(2):277–293.Crossref, Google Scholar
• Qi HD (2009) Local duality of nonlinear semidefinite programming. Math. Oper. Res. 34(1):124–141.Link, Google Scholar
• 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
• 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
• Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• 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
• Rockafellar RT (1976) Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5):877–898.Crossref, Google Scholar
• Rockafellar RT, Wets RJ-B (1998) Variational Analysis (Springer, Berlin).Crossref, Google Scholar
• 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
• 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
• Sun J (1986) On monotropic piecewise qudratic programming. PhD Thesis, Department of Mathematics, University of Washington, Seattle.Google Scholar
• Xu MH, Wu T (2011) A class of linearized proximal alternating direction methods. J. Optim. Theory Appl. 151(2):321–337.Crossref, Google Scholar
• Yang WH, Han DR (2016) Linear convergence of alternating direction method of multipliers for a class of convex optimization problems. SIAM J. Numerical Anal. 54(2):625–640.Crossref, Google Scholar