Iteration-complexity analysis of a generalized alternating direction method of multipliers

V. A. Adona (), M. L. N. Gonçalves () and J. G. Melo ()
Additional contact information
V. A. Adona: Universidade Federal de Goias
M. L. N. Gonçalves: Universidade Federal de Goias
J. G. Melo: Universidade Federal de Goias

Journal of Global Optimization, 2019, vol. 73, issue 2, No 4, 348 pages

Abstract: Abstract This paper analyzes the iteration-complexity of a generalized alternating direction method of multipliers (G-ADMM) for solving separable linearly constrained convex optimization problems. This ADMM variant, first proposed by Bertsekas and Eckstein, introduces a relaxation parameter $$\alpha $$ α into the second ADMM subproblem in order to improve its computational performance. It is shown that, for a given tolerance $$\varepsilon >0$$ ε > 0 , the G-ADMM with $$\alpha \in (0, 2)$$ α ∈ ( 0 , 2 ) provides, in at most $${\mathcal {O}}(1/\varepsilon ^2)$$ O ( 1 / ε 2 ) iterations, an approximate solution of the Lagrangian system associated to the optimization problem under consideration. It is further demonstrated that, in at most $${\mathcal {O}}(1/\varepsilon )$$ O ( 1 / ε ) iterations, an approximate solution of the Lagrangian system can be obtained by means of an ergodic sequence associated to a sequence generated by the G-ADMM with $$\alpha \in (0, 2]$$ α ∈ ( 0 , 2 ] . Our approach consists of interpreting the G-ADMM as an instance of a hybrid proximal extragradient framework with some special properties. Some preliminary numerical experiments are reported in order to confirm that the use of $$\alpha >1$$ α > 1 can lead to a better numerical performance than $$\alpha =1$$ α = 1 (which corresponds to the standard ADMM).

Keywords: Generalized alternating direction method of multipliers; Hybrid extragradient method; Convex program; Pointwise iteration-complexity; Ergodic iteration-complexity; 47H05; 49M27; 90C25; 90C60; 65K10 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0697-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:73:y:2019:i:2:d:10.1007_s10898-018-0697-z

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0697-z

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().