Optimization Online


Iteration-Complexity of a Linearized Proximal Multiblock ADMM Class for Linearly Constrained Nonconvex Optimization Problems

Jefferson Melo(jefferson***at***ufg.br)
Renato Monteiro(monteiro***at***isye.gatech.edu)

Abstract: This paper analyzes the iteration-complexity of a class of linearized proximal multiblock alternating direction method of multipliers (ADMM) for solving linearly constrained nonconvex optimization problems. The subproblems of the linearized ADMM are obtained by partially or fully linearizing the augmented Lagrangian with respect to the corresponding minimizing block variable. The derived complexity bounds do not depend on the specific forms of the actual linearizations but only on some Lipschitz constants which quantify the approximation errors. Iteration-complexity is then established by showing that the linearized ADMM class is a subclass of a general non-Euclidean ADMM for which a general iteration-complexity analysis is also obtained. Both ADMM classes allow the choice of a relaxation parameter in the interval (0, 2) as opposed to being equal to one as in many of the previous papers on this topic.

Keywords: Multiblock ADMM, nonconvex program, pointwise iteration-complexity, first-order methods.

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 2: Nonlinear Optimization (Other )

Citation: Instituto de Matematica e Estatistica, Universidade Federal de Goias, Campus II- Caixa Postal 131, CEP 74001- 970, Goiaˆnia-GO, Brazil. (E-mail: jefferson@ufg.br). The work of this author was partially supported by CNPq Grants 406250/2013-8, 444134/2014-0 and 406975/2016-7. †School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, 30332-0205. (email: monteiro@isye.gatech.edu). The work of this author was partially supported by NSF Grant CMMI-1300221. 

Download: [PDF]

Entry Submitted: 04/14/2017
Entry Accepted: 04/14/2017
Entry Last Modified: 04/14/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