- 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/2001Entry Accepted: 02/08/2001Entry Last Modified: 07/12/2002Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.