2017

Linearized ADMM for Non-convex Non-smooth Optimization with Convergence Analysis

Liu, Qinghua, Shen, Xinyue, Gu, Yuantao

Understand

Linearized alternating direction method of multipliers (ADMM) as an extension of ADMM has been widely used to solve linearly constrained problems in signal processing, machine leaning, communications, and many other fields.

Despite its broad applications in nonconvex optimization, for a great number of nonconvex and nonsmooth objective functions, its theoretical convergence guarantee is still an open problem.
In this paper, we propose a two-block linearized ADMM and a multi-block parallel linearized ADMM for problems with nonconvex and nonsmooth objectives.
Mathematically, we present that the algorithms can converge for a broader class of objective functions under less strict assumptions compared with previous works.

Built on

Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires
Roland Glowinski and A Marroco · 1975
Earlier work this paper cites.
Strong and weak convexity of sets and functions
Jean-Philippe Vial · 1983
Earlier work this paper cites.
Future paths for integer programming and links to artificial intelligence
Fred Glover · 1986
Earlier work this paper cites.
Parallel and distributed computation: numerical methods
Dimitri P Bertsekas and John N Tsitsiklis · 1989
Earlier work this paper cites.
Assignment of cells to switches in pcs networks
Arif Merchant and Bhaskar Sengupta · 1995
Earlier work this paper cites.
Data clustering: a review
Anil K Jain, M Narasimha Murty, and Patrick J Flynn · 1999
Earlier work this paper cites.
Nonlinear programming
Dimitri P Bertsekas · 1999
Earlier work this paper cites.
Algorithms for non-negative matrix factorization
Daniel D Lee and H Sebastian Seung · 2001
Earlier work this paper cites.
Conflict resolution problems for air traffic management systems solved with mixed integer programming
Lucia Pallottino, Eric M Feron, and Antonio Bicchi · 2002
Earlier work this paper cites.
Convex optimization
Stephen Boyd and Lieven Vandenberghe · 2004
Earlier work this paper cites.
Scalable density-based distributed clustering
Eshref Januzaj, Hans-Peter Kriegel, and Martin Pfeifle · 2004
Earlier work this paper cites.
Price-based unit commitment: A case of lagrangian relaxation versus mixed integer programming
Tao Li and Mohammad Shahidehpour · 2005
Earlier work this paper cites.
An introduction to convex optimization for communications and signal processing
Zhi-Quan Luo and Wei Yu · 2006
Earlier work this paper cites.
Compressed sensing
David L Donoho · 2006
Earlier work this paper cites.
Exact reconstruction of sparse signals via nonconvex minimization
Rick Chartrand · 2007
Earlier work this paper cites.
Linear coherent decentralized estimation
Jin-Jun Xiao, Shuguang Cui, Zhi-Quan Luo, and Andrea J Goldsmith · 2008
Earlier work this paper cites.
Bregman iterative algorithms for ℓ 1 \ell_{1} -minimization with applications to compressed sensing
Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon · 2008
Earlier work this paper cites.
Variational analysis
R Tyrrell Rockafellar and Roger J-B Wets · 2009
Earlier work this paper cites.
Recovering sparse signals with a certain family of nonconvex penalties and dc programming
Gilles Gasso, Alain Rakotomamonjy, and Stéphane Canu · 2009
Earlier work this paper cites.
ℓ 1 \ell_{1} - ℓ 2 \ell_{2} optimization in signal and image processing
Michael Zibulevsky and Michael Elad · 2010
Earlier work this paper cites.
Discriminative k-svd for dictionary learning in face recognition
Qiang Zhang and Baoxin Li · 2010
Earlier work this paper cites.
Sparse inverse covariance selection via alternating linearization methods
Katya Scheinberg, Shiqian Ma, and Donald Goldfarb · 2010
Earlier work this paper cites.

Similar

Sparse recovery by non-convex optimization–instance optimality
Rayan Saab and Özgür Yılmaz · 2010
Cited alongside, same era.
Large-scale matrix factorization with distributed stochastic gradient descent
Rainer Gemulla, Erik Nijkamp, Peter J Haas, and Yannis Sismanis · 2011
Cited alongside, same era.
Distributed optimization and statistical learning via the alternating direction method of multipliers
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein · 2011
Cited alongside, same era.
A unified primal-dual algorithm framework based on bregman iteration
Xiaoqun Zhang, Martin Burger, and Stanley Osher · 2011
Cited alongside, same era.
Linearized alternating direction method with adaptive penalty for low-rank representation
Zhouchen Lin, Risheng Liu, and Zhixun Su · 2011
Cited alongside, same era.
Inexact alternating direction methods for image recovery
Michael K Ng, Fan Wang, and Xiaoming Yuan · 2011
Cited alongside, same era.
Distributed optimization and statistical learning via the alternating direction method of multipliers
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein · 2011
Cited alongside, same era.
Linearized alternating direction method of multipliers for constrained linear least-squares problem
Raymond H Chan, Min Tao, and Xiaoming Yuan · 2012
Cited alongside, same era.
An admm algorithm for a class of total variation regularized estimation problems
Bo Wahlberg, Stephen Boyd, Mariette Annergren, and Yang Wang · 2012
Cited alongside, same era.
Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization
Junfeng Yang and Xiaoming Yuan · 2013
Cited alongside, same era.
Frame-based poisson image restoration using a proximal linearized alternating direction method
T Jeong, H Woo, and S Yun · 2013
Cited alongside, same era.
Proximal linearized alternating direction method for multiplicative denoising
Hyenkyun Woo and Sangwoon Yun · 2013
Cited alongside, same era.

Then

Global convergence of admm in nonconvex nonsmooth optimization
Yu Wang, Wotao Yin, and Jinshan Zeng · 2015
Later among the works it cites.
Convergence of multi-block bregman admm for nonconvex composite problems
Fenghui Wang, Wenfei Cao, and Zongben Xu · 2015
Later among the works it cites.
Global convergence of splitting methods for nonconvex composite optimization
Guoyin Li and Ting Kei Pong · 2015
Later among the works it cites.
An accelerated linearized alternating direction method of multipliers
Yuyuan Ouyang, Yunmei Chen, Guanghui Lan, and Eduardo Pasiliao Jr · 2015
Later among the works it cites.
Dlm: Decentralized linearized alternating direction method of multipliers
Qing Ling, Wei Shi, Gang Wu, and Alejandro Ribeiro · 2015
Later among the works it cites.
Fast linearized alternating direction method of multipliers for the augmented ℓ 1 \ell_{1} -regularized problem
Zhen-Zhen Yang and Zhen Yang · 2015
Later among the works it cites.
Fast x-ray ct image reconstruction using a linearized augmented lagrangian method with ordered subsets
Hung Nien and Jeffrey A Fessler · 2015
Later among the works it cites.
Efficient machine learning for big data: A review
Omar Y Al-Jarrah, Paul D Yoo, Sami Muhaidat, George K Karagiannidis, and Kamal Taha · 2015
Later among the works it cites.
Multi-agent distributed optimization via inexact consensus admm
Tsung-Hui Chang, Mingyi Hong, and Xiangfeng Wang · 2015
Later among the works it cites.
A note on augmented lagrangian-based parallel splitting method
Kai Wang, Jitamitra Desai, and Hongjin He · 2015
Later among the works it cites.
The direct extension of admm for multi-block convex minimization problems is not necessarily convergent
Caihua Chen, Bingsheng He, Yinyu Ye, and Xiaoming Yuan · 2016
Later among the works it cites.
Square-root lasso with nonconvex regularization: An admm approach
Xinyue Shen, Laming Chen, Yuantao Gu, and HC So · 2016
Later among the works it cites.
Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
Mingyi Hong, Zhi-Quan Luo, and Meisam Razaviyayn · 2016
Later among the works it cites.
Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
Original
Bo Jiang, Tianyi Lin, Shiqian Ma, and Shuzhong Zhang · 2016
Later among the works it cites.
Parallel and distributed methods for nonconvex optimization–part ii: Applications
Original
Gesualdo Scutari, Francisco Facchinei, Lorenzo Lampariello, Peiran Song, and Stefania Sardellitti · 2016
Later among the works it cites.
On the proximal jacobian decomposition of alm for multiple-block separable convex minimization problems and its relationship to admm
Bingsheng He, Hong-Kun Xu, and Xiaoming Yuan · 2016
Later among the works it cites.
Admm algorithmic regularization paths for sparse statistical machine learning
Yue Hu, Eric C Chi, and Genevera I Allen · 2016
Later among the works it cites.
An alternating direction method approach to cloud traffic management
Chen Feng, Hong Xu, and Baochun Li · 2017
Closest in time.
Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints
Ke Guo, DR Han, and TT Wu · 2017
Closest in time.
Alternating direction method of multipliers for a class of nonconvex and nonsmooth problems with applications to background/foreground extraction
Lei Yang, Ting Kei Pong, and Xiaojun Chen · 2017
Closest in time.
An extragradient-based alternating direction method for convex minimization
Tianyi Lin, Shiqian Ma, and Shuzhong Zhang · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…