Generalizations of the proximal method of multipliers in convex optimization

The proximal method of multipliers, originally introduced as a way of solving convex programming problems with inequality constraints, is a proximally stabilized alternative to the augmented Lagrangian method that is sometimes called the proximal augmented Lagrangian method. It has gained attention as a vehicle for deriving decomposition algorithms for wider formulations of problems in convex optimization than just convex programming. Here those themes are developed further. The basic algorithm is articulated in several seemingly different formats that are equivalent under exact computations, but diverge when minimization steps are executed only approximately. Stopping criteria are demonstrated to maintain convergence to a particular solution despite such approximations. Q-linear convergence is obtained from a metric regularity property of the Lagrangian mapping at the solution that acts as a mildly enhanced condition for local optimality on top of convexity and is generically available, in a sense. Moreover, all this is brought about with the proximal terms allowed to vary in their underlying metric from one iteration to the next. That generalization enables the results to be translated to the theory of the progressive decoupling algorithm, significantly adding to its versatility and providing linear convergence guarantees in its broad applicability to techniques for problem decomposition.