Optimization Online


A Practical Relative Error Criterion for Augmented Lagrangians

Jonathan Eckstein (jeckstei***at***rci.rutgers.edu)
Paulo J.S. Silva (pjssilva***at***ime.usp.br)

Abstract: This paper develops a new error criterion for the approximate minimization of augmented Lagrangian subproblems. This criterion is practical in the sense that it requires only information that is ordinarily readily available, such as the gradient (or a subgradient) of the augmented Lagrangian. It is also “relative” in the sense of relative error criteria for proximal point algorithms, in that it is based on the relative magnitude of two quantities and requires only a single parameter, not the choice of an theoretically infinite sequences of parameters. It involves a novel auxiliary sequence that appears only in the approximation criterion, and not in the augmented Lagrangian minimand, nor in the multiplier update. We give a proof of the global convergence of our method in the setting of the abstract convex duality framework of Rockafellar, along with some more concrete applications. The dual convergence result is slightly weaker than usually obtained for multiplier methods, but may be strengthened by enforcing an additional condition in the algorithm. We give some computational results drawn from the CUTE test set, indicating that our approach works well in practice.

Keywords: Augmented Lagrangians, Convex Programming, Nonlinear Programming, Proximal Algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: RUTCOR Research Report RRR 11-2010, RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854 USA, July 2010.

Download: [PDF]

Entry Submitted: 07/20/2010
Entry Accepted: 07/20/2010
Entry Last Modified: 07/20/2010

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