Iteration-Complexity of a Linearized Proximal Multiblock ADMM Class for Linearly Constrained Nonconvex Optimization Problems
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: firstname.lastname@example.org). 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: email@example.com). The work of this author was partially supported by NSF Grant CMMI-1300221. ￼
Entry Submitted: 04/14/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|