Optimization Online


Improved pointwise iteration-complexity of a regularized ADMM and of a regularized non-Euclidean HPE framework

Max L. N. Goncalves (maxlng***at***ufg.br)
Renato D.C. Monteiro (renato.monteiro***at***isye.gatech.edu)
Jefferson G. Melo (jefferson.ufg***at***gmail.com)

Abstract: This paper describes a regularized variant of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex programs. It is shown that the pointwise iteration-complexity of the new method is better than the corresponding one for the standard ADMM method and that, up to a logarithmic term, is identical to the ergodic iteration-complexity of the latter method. Our analysis is based on first presenting and establishing the pointwise iteration-complexity of a regularized non-Euclidean hybrid proximal extragradient framework whose error condition at each iteration includes both a relative error and a summable error. It is then shown that the new method is a special instance of the latter framework where the sequence of summable errors is identically zero when the ADMM stepsize is less than one or a nontrivial sequence when the stepsize is in the interval [1, (1 +\sqrt{5})/2).

Keywords: alternating direction method of multipliers, hybrid proximal extragradient method, non-Euclidean Bregman distances, convex program, pointwise iteration-complexity, first-order methods, inexact proximal point method, regularization.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )


Download: [PDF]

Entry Submitted: 01/05/2016
Entry Accepted: 01/05/2016
Entry Last Modified: 01/06/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society