On the Nonergodic Convergence Rate of an Inexact Augmented Lagrangian Framework for Composite Convex Programming

References

• [1] Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Crossref, Google Scholar
• [2] Bertsekas DP (1996) Constrained Optimization and Lagrange Multiplier Methods (Athena Scientific, Belmont, MA).Google Scholar
• [3] Bertsekas DP (1999) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• [4] Bertsekas DP, Tsitsiklis JN (2000) Gradient convergence in gradient methods with errors. SIAM J. Optim. 10(3):627–642.Crossref, Google Scholar
• [5] Buys JD (1972) Dual algorithms for constrained optimization problems. PhD thesis, University of Leiden, Leiden, Netherlands.Google Scholar
• [6] Devolder O, Glineur F, Nesterov Y (2014) First-order methods of smooth convex optimization with inexact oracle. Math. Programming 146(1–2):37–75.Crossref, Google Scholar
• [7] Eckstein J, Silva PJS (2013) A practical relative error criterion for augmented Lagrangians. Math. Programming 141(1–2):319–348.Crossref, Google Scholar
• [8] Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• [9] Goldstein T, Osher S (2009) The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2(2):323–343.Crossref, Google Scholar
• [10] Harchaoui Z, Juditsky A, Nemirovski A (2015) Conditional gradient algorithms for norm-regularized smooth convex optimization. Math. Programming 152(1–2):75–112.Crossref, Google Scholar
• [11] Hestenes MR (1969) Multiplier and gradient methods. J. Optim. Theory Appl. 4(5):303–330.Crossref, Google Scholar
• [12] Iusem AN, Teboulle M (1995) Convergence rate analysis of nonquadratic proximal methods for convex and linear programming. Math. Oper. Res. 20(3):657–677.Link, Google Scholar
• [13] Jaggi M (2011) Sparse convex optimization methods for machine learning. PhD thesis, ETH Zurich, Zurich.Google Scholar
• [14] Jaggi M (2013) Revisiting Frank-Wolfe: Projection-free sparse convex optimization. Proc. Machine Learn. Res. 28(1):427–435.Google Scholar
• [15] Lan G (2016) Gradient sliding for composite optimization. Math. Programming 159(1–2):201–235.Crossref, Google Scholar
• [16] Lan G, Monteiro RDC (2016) Iteration-complexity of first-order augmented Lagrangian methods for convex programming. Math. Programming 155(1–2):511–547.Crossref, Google Scholar
• [17] Lan G, Zhou Y (2016) Conditional gradient sliding for convex optimization. SIAM J. Optim. 26(2):1379–1409.Crossref, Google Scholar
• [18] Li C, Yin W, Jiang H, Zhang Y (2013) An efficient augmented Lagrangian method with applications to total variation minimization. Comput. Optim. Appl. 56(3):507–530.Crossref, Google Scholar
• [19] Li X, Sun D, Toh KC (2018) A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems. SIAM J. Optim. 28(1):433–458.Crossref, Google Scholar
• [20] Luo ZQ, Tseng P (1993) Error bounds and convergence analysis of feasible descent methods: A general approach. Ann. Oper. Res. 46(1):157–178.Crossref, Google Scholar
• [21] Mu C, Zhang Y, Wright J, Goldfarb D (2016) Scalable robust matrix recovery: Frank–Wolfe meets proximal methods. SIAM J. Sci. Comput. 38(5):3291–3317.Crossref, Google Scholar
• [22] Necoara I, Patrascu A (2016) Iteration complexity analysis of dual first-order methods for conic convex programming. Optim. Methods Software 31(3):645–678.Crossref, Google Scholar
• [23] Necoara I, Patrascu A, Glineur F (2019) Complexity of first order inexact Lagrangian and penalty methods for conic convex programming. Optim. Methods Software 34(2):305–335.Google Scholar
• [24] Nedelcu V, Necoara I, Tran-Dinh Q (2014) Computational complexity of inexact gradient augmented Lagrangian methods: Application to constrained MPC. SIAM J. Control Optim. 52(5):3109–3134.Crossref, Google Scholar
• [25] Nesterov Y (1983) A method of solving a convex programming problem with convergence rateO(1/k2). Soviet Math. Doklady 27(2):372–376.Google Scholar
• [26] Nesterov Y (2005) Smooth minimization of non-smooth functions. Math. Programming 103(1):127–152.Crossref, Google Scholar
• [27] Nesterov Y (2013) Gradient methods for minimizing composite functions. Math. Programming 140(1):125–161.Crossref, Google Scholar
• [28] Nesterov Y (2018) Complexity bounds for primal-dual methods minimizing the model of objective function. Math. Programming 171(1/2):311–330.Crossref, Google Scholar
• [29] Osher S, Burger M, Goldfarb D, Xu J, Yin W (2005) An iterative regularization method for total variation-based image restoration. Multiscale Model. Simulation 4(2):460–489.Crossref, Google Scholar
• [30] Powell MJD (1969) A method for nonlinear constraints in minimization problems. Fletcher R, ed. Optimization (Academic Press, New York), 283–298.Google Scholar
• [31] Rockafellar RT (1973) The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12(6):555–562.Crossref, Google Scholar
• [32] Rockafellar RT (1976) Augmented Lagrangian and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97–116.Link, Google Scholar
• [33] So AMC, Zhou Z (2017) Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity. Optim. Methods Software 32(4):963–992.Crossref, Google Scholar
• [34] Tapia RA (1974) Newton’s method for problems with equality constraints. SIAM J. Numer. Anal. 11(5):874–886.Crossref, Google Scholar
• [35] Yang L, Sun D, Toh KC (2015) SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Programming Comput. 7(3):331–366.Crossref, Google Scholar
• [36] Yin W, Osher S (2013) Error forgetting of Bregman iteration. J. Sci. Comput. 54(2–3):684–695.Crossref, Google Scholar
• [37] Yin W, Osher S, Goldfarb D, Darbon J (2008) Bregman iterative algorithms forℓ1-minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1):143–168.Crossref, Google Scholar
• [38] Yuan Y (2014) Analysis on a superlinearly convergent augmented Lagrangian method. Acta Math. Sinica 30(1):1–10.Crossref, Google Scholar