A partially inexact ADMM with o(1/n) asymptotic convergence rate, 𝒪(1/n) complexity, and immediate relative error tolerance

Abstract

In this work, we propose a new partially inexact Alternating Direction Method of Multipliers (ADMM) with relative error tolerance. This method departs from previous semi-inexact variants of the ADMM by allowing the second subproblem to be solved inexactly, instead of the first one. Relative error tolerance criteria for inexact ADMM methods require, to be verified, the solution of the two proximal subproblems in each iteration; therefore, by allowing for inexactness in the approximate solutions of the second subproblem, the error criterion is immediately testable during the computation of that approximate solution and no backtracking is required. In this sense, the proposed method uses an immediate error criterion. We also establish $\mathcal{O}\left(1/n\right)$ iteration complexity and $o\left(1/n\right)$ asymptotic convergence rate for a modified ergodic mean, with respect to the residuals in Karush–Kuhn–Tucker conditions. As far as we know, this is the first $o\left(1/n\right)$ asymptotic convergence rate, with respect to this error measure, for ADMM applied to a general problem.

Keywords:

• Alternating direction method of multipliers
• relative error criterion
• iteration-complexity

2000 Mathematics Subject Classifications:

• 47H05
• 49M27
• 65K05
• 65K10
• 65G99
• 90C25
• 90C60

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

Partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq [grant numbers 306247/2015-1, 430868/2018-9) and Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ) [grant Cientistas de Nosso Estado E-26/203.318/2017].