A practical general approximation criterion for methods of multipliers based on Bregman distances

Jonathan Eckstein (jecksteirutcor.rutgers.edu)

Abstract: This paper demonstrates that for generalized methods of multipliers for convex programming based on Bregman distance kernels --- including the classical quadratic method of multipliers --- the minimization of the augmented Lagrangian can be truncated using a simple, generally implementable stopping criterion based only on the norms of the primal iterate and the gradient (or a subgradient) of the augmented Lagrangian at that iterate. Previous results in this and related areas have required conditions that are much harder to verify, such as $\epsilon$-optimality with respect to the augmented Lagrangian, or strong conditions on the convex program to be solved. Here, only existence of a KKT pair is required, and the convergence properties of the exact form of the method are preserved. The key new element in the analysis is the use of a full conjugate duality framework, as opposed to mainly examining the action of the method on the standard dual function of the convex program. An existence result for the iterates, stronger than those possible for the exact form of the algorithm, is also included.

Keywords: Augmented Lagrangians, Proximal Algorithms, Convex Programming, Conjugate Duality

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: RUTCOR Research Report RRR 61-2000, December 2000, revised July 2002

Download: [Postscript]

Entry Submitted: 02/08/2001
Entry Accepted: 02/08/2001
Entry Last Modified: 07/12/2002

Modify/Update this entry