Decomposition for structured convex programs with smooth multiplier methods

摘要

One drawback associated with the classical quadratic multiplier method (augmented Lagrangian) is the fact that it is only differentiable once even when the problem’s data process higher differentiability, and therefore efficient Newton type methods cannot be applied. In fact such a lack of continuity in the second derivative can seriously slow down the rate of convergence of these methods and cause algorithmic failure. One way of coping with this difficulty is to use the recently developed non-quadratic multiplier methods based on entropy-like proximal methods, and leading to multiplier methods which as opposed to the classical quadratic multiplier are twice continuously differentiable (if the original problem is also C2). This is an important advantage since Newton type methods can then be applied.The second drawback associated with multiplier methods is the lack of its separability, even when the original problem is separable. However, some careful reformulation of the problem (e.g., by introducing additional variables) may preserve some of the given separable structure, thus giving to the augmented Lagrangian framework, still an important role to play in the development of efficient decomposition schemes. Examples of such methods include splitting/alternating direction type algorithms.We combine here these two ideas to develop decomposition schemes for solving structured convex programs with smooth Lagrangians, allowing the use of Newton types methods. We will concentrate our numerical analysis on an exponential and modified logarithmic barrier type of augmented Lagrangians leading to an alternating direction type algorithm. Numerical examples illustrating the performance of this algorithm versus classical quadratic alternating direction methods will be presented.