Convergence Analysis of Inexact Over-Relaxed ADMM via Dissipativity Theory

Abstract

We present a new convergence analysis for the over-relaxed alternating direction method of multipliers (ADMM) when the subproblem cannot be exactly solved, \ie, inexact over-relaxed ADMM. Our method builds on \citep{hu2017dissipativity} that relates the convergence analysis of optimization algorithms to the stability of a discrete-time linear dynamic system. By expressing the inexact over-relaxed ADMM as a discrete-time linear dynamic system, we show that both the linear and sublinear convergence of inexact over-relaxed ADMM can be obtained by solving or verifying the feasibility of a small semidefinite program (SDP). More importantly, we prove that the associated SDP has an analytical solution for various parameters. We demonstrate the theoretical result by applying the inexact over-relaxed ADMM to solve a distributed $\ell_1$-norm regularized logistic regression problem.