Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems

Mingyi Hong; Zhi-Quan Luo; Meisam Razaviyayn

doi:10.1109/ICASSP.2015.7178689

Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems

Mingyi Hong, Zhi-Quan Luo, Meisam Razaviyayn

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

44 Scopus citations

Abstract

In this paper, we analyze the behavior of the alternating direction method of multipliers (ADMM), for solving a family of nonconvex problems. Our focus is given to the well-known consensus and sharing problems, both of which have wide applications in signal processing. We show that in the presence of nonconvex objective function, classical ADMM is able to reach the set of stationary solutions for these problems, if the stepsize is chosen large enough. An interesting consequence of our analysis is that the ADMM is convergent for a family of sharing problems, regardless of the number of blocks or the convexity of the objective function. Our analysis is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.

Original language	English (US)
Title of host publication	2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3836-3840
Number of pages	5
ISBN (Electronic)	9781467369978
DOIs	https://doi.org/10.1109/ICASSP.2015.7178689
State	Published - Aug 4 2015
Event	40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Brisbane, Australia Duration: Apr 19 2014 → Apr 24 2014

Publication series

Name	ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume	2015-August
ISSN (Print)	1520-6149

Other

Other	40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015
Country	Australia
City	Brisbane
Period	4/19/14 → 4/24/14

Access

10.1109/ICASSP.2015.7178689

Fingerprint Dive into the research topics of 'Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems'. Together they form a unique fingerprint.

Cite this

Hong, M., Luo, Z-Q., & Razaviyayn, M. (2015). Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. In 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings (pp. 3836-3840). [7178689] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2015-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2015.7178689

Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. / Hong, Mingyi; Luo, Zhi-Quan; Razaviyayn, Meisam.

2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2015. p. 3836-3840 7178689 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 2015-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hong, M, Luo, Z-Q & Razaviyayn, M 2015, Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. in 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings., 7178689, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, vol. 2015-August, Institute of Electrical and Electronics Engineers Inc., pp. 3836-3840, 40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015, Brisbane, Australia, 4/19/14. https://doi.org/10.1109/ICASSP.2015.7178689

Hong M, Luo Z-Q, Razaviyayn M. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. In 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings. Institute of Electrical and Electronics Engineers Inc. 2015. p. 3836-3840. 7178689. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2015.7178689

Hong, Mingyi ; Luo, Zhi-Quan ; Razaviyayn, Meisam. / Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 3836-3840 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{4f3bbfb3fa99404a9faf24946539bdae,

title = "Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems",

abstract = "In this paper, we analyze the behavior of the alternating direction method of multipliers (ADMM), for solving a family of nonconvex problems. Our focus is given to the well-known consensus and sharing problems, both of which have wide applications in signal processing. We show that in the presence of nonconvex objective function, classical ADMM is able to reach the set of stationary solutions for these problems, if the stepsize is chosen large enough. An interesting consequence of our analysis is that the ADMM is convergent for a family of sharing problems, regardless of the number of blocks or the convexity of the objective function. Our analysis is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.",

author = "Mingyi Hong and Zhi-Quan Luo and Meisam Razaviyayn",

year = "2015",

month = aug,

day = "4",

doi = "10.1109/ICASSP.2015.7178689",

language = "English (US)",

series = "ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "3836--3840",

booktitle = "2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings",

note = "40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 ; Conference date: 19-04-2014 Through 24-04-2014",

}

TY - GEN

T1 - Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems

AU - Hong, Mingyi

AU - Luo, Zhi-Quan

AU - Razaviyayn, Meisam

PY - 2015/8/4

Y1 - 2015/8/4

N2 - In this paper, we analyze the behavior of the alternating direction method of multipliers (ADMM), for solving a family of nonconvex problems. Our focus is given to the well-known consensus and sharing problems, both of which have wide applications in signal processing. We show that in the presence of nonconvex objective function, classical ADMM is able to reach the set of stationary solutions for these problems, if the stepsize is chosen large enough. An interesting consequence of our analysis is that the ADMM is convergent for a family of sharing problems, regardless of the number of blocks or the convexity of the objective function. Our analysis is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.

AB - In this paper, we analyze the behavior of the alternating direction method of multipliers (ADMM), for solving a family of nonconvex problems. Our focus is given to the well-known consensus and sharing problems, both of which have wide applications in signal processing. We show that in the presence of nonconvex objective function, classical ADMM is able to reach the set of stationary solutions for these problems, if the stepsize is chosen large enough. An interesting consequence of our analysis is that the ADMM is convergent for a family of sharing problems, regardless of the number of blocks or the convexity of the objective function. Our analysis is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.

UR - http://www.scopus.com/inward/record.url?scp=84946091392&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84946091392&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2015.7178689

DO - 10.1109/ICASSP.2015.7178689

M3 - Conference contribution

AN - SCOPUS:84946091392

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 3836

EP - 3840

BT - 2015 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 40th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2015

Y2 - 19 April 2014 through 24 April 2014

ER -