S. Cipolla and J. Gondzio
Abstract
Embedding randomization procedures in the Alternating Direction Method
of Multipliers (ADMM) has recently attracted an increasing amount
of interest as a remedy to the fact that the direct n-block generalization
of ADMM is not necessarily convergent (n > 2). Even if, in practice,
the introduction of such techniques could mitigate the diverging
behaviour of the n-block extension of ADMM, from the theoretical
point of view, it can ensure just the convergence in expectation,
which may not be a good indicator of its robustness and efficiency.
In this work, analysing the strongly convex quadratic programming case,
we interpret the n-block Gauss-Seidel sweep performed by ADMM in the
context of the inexact Augmented Lagrangian Method. Using the proposed
analysis, we are able to outline an alternative technique to those
present in literature which, supported from stronger theoretical
guarantees, is able to ensure the convergence of the n-block
generalization of the ADMM method.
Key words: Alternating Direction Method of Multipliers, inexact Augmented Lagrangian Method, Randomly Shuffled Gauss-Seidel