Some Saddle-function splitting methods for convex programming

Abstract

Consider two variations of the method of multipliers, or classical augmented Lagrangian method for convex programming. The proximal method of multipliers adjoins quadratic primal proximal terms to the augmented Lagrangian, and has a stronger primal convergence theory than the standard method. On the other hand, the alternating direction method of multipliers, which uses a special kind of partial minimization of the augmented Lagrangian, is conducive to the derivation of decomposition methods finding application in parallel computing. This note shows convergence a method combining the features of these two variations. The method is closely related to some algorithms of Gols'shtein. A comparison of the methods helps illustrate the close relationship between previously separate bodies of Western and Soviet literature.