Title | ||
---|---|---|
Iteration-complexity analysis of a generalized alternating direction method of multipliers |
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\), the G-ADMM with \(\alpha \in (0, 2)\) provides, in at most \({\mathcal {O}}(1/\varepsilon ^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 )\) 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]\). 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\) can lead to a better numerical performance than \(\alpha =1\) (which corresponds to the standard ADMM). |
Year | DOI | Venue |
---|---|---|
2019 | 10.1007/s10898-018-0697-z | Journal of Global Optimization |
Keywords | Field | DocType |
Generalized alternating direction method of multipliers,Hybrid extragradient method,Convex program,Pointwise iteration-complexity,Ergodic iteration-complexity,47H05,49M27,90C25,90C60,65K10 | Ergodic sequence,Applied mathematics,Lagrangian system,Mathematical analysis,Separable space,Approximate solution,Optimization problem,Convex optimization,Mathematics | Journal |
Volume | Issue | ISSN |
73.0 | 2 | 1573-2916 |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
V. A. Adona | 1 | 0 | 0.34 |
M. L. N. Gonçalves | 2 | 45 | 5.93 |
Jefferson G. Melo | 3 | 49 | 5.63 |