ADMM and inexact ALM: the QP case

Stefano Cipolla, Jacek Gondzio

Published 2020-12-16Version 1

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 \geq 3$). 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.