Optimization Online


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

Guanghui Lan(glan***at***isye.gatech.edu)
Renato D.C. Monteiro(monteiro***at***isye.gatech.edu)

Abstract: 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 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

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: Technical Report, School of Industrial & Systems Engineering, Georgia Institute of Technology, April 2009.

Download: [PDF]

Entry Submitted: 05/14/2009
Entry Accepted: 05/14/2009
Entry Last Modified: 05/14/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society