Iteration-complexity of first-order augmented Lagrangian methods for convex programming

详细信息    查看全文

• 作者：Guanghui Lan ; Renato D. C. Monteiro
• 关键词：Penalty ; First ; order ; Augmented Lagrangian method ; Convex programming ; Lagrange multiplier ; 90C25 ; 90C06 ; 90C22 ; 49M37
• 刊名：Mathematical Programming
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：155
• 期：1-2
• 页码：511-547
• 全文大小：740 KB
• 参考文献：1.Bertsekas, D.: Constrained Optimization and Lagrange Multiplier Methods, 1st edn. Academic Press, New York (1982)MATH
  2.Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, New York (1984)
  3.Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. Series B 95, 329–357 (2003)MATH MathSciNet CrossRef
  4.Burer, S., Monteiro, R.D.C.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103, 427–444 (2005)MATH MathSciNet CrossRef
  5.Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, I: a generic algorithmic framework. SIAM J. Optim. 22, 1469–1492 (2012)MATH MathSciNet CrossRef
  6.Golshtein, E.G., Tretyakov, N.V.: Modified Lagrangians and Monotone Maps in Optimization. Springer, New York (1996)MATH
  7.Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Appl. 4, 303–320 (1969)MATH MathSciNet CrossRef
  8.Jarre, F., Rendl, F.: An augmented primal-dual method for linear conic programs. Manuscript, Institut fur Mathematik, Universit at Dusseldorf, Germany, Austria, (2007)
  9.Lan, G.: Convex optimization under inexact first-order information. Ph.D. Dissertation, School of Industrial Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA, (2009)
  10.Lan, G.: Bundle-level type methods uniformly optimal for smooth andnon-smooth convex optimization. Manuscript, Department of Industrialand Systems Engineering, University of Florida, Gainesville, FL32611, USA, January 2013. Revision submitted to MathematicalProgramming
  11.Lan, G., Monteiro, R.D.C.: Iteration-complexity of first-order penalty methods for convex programming. Math. Program. 138, 115–139 (2013)MATH MathSciNet CrossRef
  12.Monteiro, R.D.C., Svaiter, B.F.: Complexity of variants of tseng’s modified f-b splitting and korpelevich’s methods for hemi-variational inequalities with applications to saddle-point and convex optimization problems. Manuscript, School of ISyE, Georgia Tech, Atlanta, GA, 30332, USA, (2010)
  13.Nemirovski, A.: Prox-method with rate of convergence \(o(1/t)\) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15, 229–251 (2004)MATH MathSciNet CrossRef
  14.Nemirovski, A.S., Yudin, D.: Problem complexity and method efficiency in optimization. Wiley-Interscience Series in Discrete Mathematics. John Wiley, XV, (1983)
  15.Nesterov, Y.E.: A method for unconstrained convex minimization problem with the rate of convergence \(O(1/k^2)\) . Dokl. AN SSSR 269, 543–547 (1983)MathSciNet
  16.Nesterov, Y.E.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Massachusetts (2004)CrossRef
  17.Nesterov, Y.E.: Smooth minimization of nonsmooth functions. Math. Program. 103, 127–152 (2005)MATH MathSciNet CrossRef
  18.Nesterov, Y.E.: Gradient methods for minimizing composite objective functions. Technical report, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain (2007)
  19.Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999)MATH CrossRef
  20.Pillo, G.D., Lucidi, S.: An augmented lagrangian function with improved exactness properties. SIAM J. Optim. 12, 376–406 (2002)CrossRef
  21.Powell, M.M.D.: An efficient method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic Press, London (1969)
  22.Ruszczynski, A.: Nonlinear Optimization, 1st edn. Princeton University Press, Princeton (2006)MATH
  23.Zhao, X., Sun, D., Toh, K.: A Newton-CG augmented Lagrangian method for semidefinite programming. Manuscript, National University of Singapore, Singapore (2008)
  
• 作者单位：Guanghui Lan (1)
  Renato D. C. Monteiro (2)
  
  1. Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611, USA
  2. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332-0205, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

This paper considers a special class of convex programming (CP) problems whose feasible regions consist of a simple compact convex set intersected with an affine manifold. We present first-order methods for this class of problems based on an inexact version of the classical augmented Lagrangian (AL) approach, where the subproblems are approximately solved by means of Nesterov’s optimal method. We then establish a bound on the total number of Nesterov’s optimal iterations, i.e., the inner iterations, performed throughout the entire inexact AL method to obtain a near primal-dual optimal solution. We also present variants with possibly better iteration-complexity bounds than the original inexact AL method, which consist of applying the original approach directly to a perturbed problem obtained by adding a strongly convex component to the objective function of the CP problem. Keywords Penalty First-order Augmented Lagrangian method Convex programming Lagrange multiplier