Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming

Abstract

The theory of the proximal point algorithm for maximal monotone operators is applied to three algorithms for solving convex programs, one of which has not previously been formulated. Rate-of-convergence results for the “method of multipliers,” of the strong sort already known, are derived in a generalized form relevant also to problems beyond the compass of the standard second-order conditions for oplimality. The new algorithm, the “proximal method of multipliers,” is shown to have much the same convergence properties, but with some potential advantages.