A block coordinate descent method of multipliers: Convergence analysis and applications

Mingyi Hong; Tsung Hui Chang; Xiangfeng Wang; Meisam Razaviyayn; Shiqian Ma; Zhi Quan Luo

doi:10.1109/ICASSP.2014.6855096

A block coordinate descent method of multipliers: Convergence analysis and applications

Mingyi Hong
, Tsung Hui Chang
, Xiangfeng Wang
, Meisam Razaviyayn
, Shiqian Ma
, Zhi Quan Luo

University of Minnesota Twin Cities
National Taiwan University of Science and Technology
Nanjing University
Chinese University of Hong Kong

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

7 Scopus citations

Abstract

In this paper, we consider a nonsmooth convex problem with linear coupling constraints. Problems of this form arise in many modern large-scale signal processing applications including the provision of smart grid networks. In this work, we propose a new class of algorithms called the block coordinate descent method of multipliers (BCDMM) to solve this family of problems. The BCDMM is a primal-dual type of algorithm. It optimizes an (approximate) augmented Lagrangian of the original problem one block variable per iteration, followed by a gradient update for the dual variable. We show that under certain regularity conditions, and when the order for which the block variables are either updated in a deterministic or a random fashion, the BCDMM converges to the set of optimal solutions. The effectiveness of the algorithm is illustrated using large-scale basis pursuit and smart grid problems.

Original language	English
Title of host publication	2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	7689-7693
Number of pages	5
ISBN (Print)	9781479928927
DOIs	https://doi.org/10.1109/ICASSP.2014.6855096
State	Published - 2014
Externally published	Yes
Event	2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014 - Florence, Italy Duration: 4 May 2014 → 9 May 2014

Publication series

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

Conference

Conference	2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014
Country/Territory	Italy
City	Florence
Period	4/05/14 → 9/05/14

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Access to Document

10.1109/ICASSP.2014.6855096

Cite this

Hong, M., Chang, T. H., Wang, X., Razaviyayn, M., Ma, S., & Luo, Z. Q. (2014). A block coordinate descent method of multipliers: Convergence analysis and applications. In 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014 (pp. 7689-7693). Article 6855096 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASSP.2014.6855096

Hong, Mingyi ; Chang, Tsung Hui ; Wang, Xiangfeng et al. / A block coordinate descent method of multipliers : Convergence analysis and applications. 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014. Institute of Electrical and Electronics Engineers Inc., 2014. pp. 7689-7693 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

@inproceedings{005afef198194dc5b33218e9963eaf48,

title = "A block coordinate descent method of multipliers: Convergence analysis and applications",

abstract = "In this paper, we consider a nonsmooth convex problem with linear coupling constraints. Problems of this form arise in many modern large-scale signal processing applications including the provision of smart grid networks. In this work, we propose a new class of algorithms called the block coordinate descent method of multipliers (BCDMM) to solve this family of problems. The BCDMM is a primal-dual type of algorithm. It optimizes an (approximate) augmented Lagrangian of the original problem one block variable per iteration, followed by a gradient update for the dual variable. We show that under certain regularity conditions, and when the order for which the block variables are either updated in a deterministic or a random fashion, the BCDMM converges to the set of optimal solutions. The effectiveness of the algorithm is illustrated using large-scale basis pursuit and smart grid problems.",

author = "Mingyi Hong and Chang, \{Tsung Hui\} and Xiangfeng Wang and Meisam Razaviyayn and Shiqian Ma and Luo, \{Zhi Quan\}",

year = "2014",

doi = "10.1109/ICASSP.2014.6855096",

language = "英语",

isbn = "9781479928927",

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

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

pages = "7689--7693",

booktitle = "2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014",

address = "美国",

note = "2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014 ; Conference date: 04-05-2014 Through 09-05-2014",

}

Hong, M, Chang, TH, Wang, X, Razaviyayn, M, Ma, S & Luo, ZQ 2014, A block coordinate descent method of multipliers: Convergence analysis and applications. in 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014., 6855096, ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 7689-7693, 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014, Florence, Italy, 4/05/14. https://doi.org/10.1109/ICASSP.2014.6855096

A block coordinate descent method of multipliers: Convergence analysis and applications. / Hong, Mingyi; Chang, Tsung Hui; Wang, Xiangfeng et al.
2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 7689-7693 6855096 (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings).

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

TY - GEN

T1 - A block coordinate descent method of multipliers

T2 - 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014

AU - Hong, Mingyi

AU - Chang, Tsung Hui

AU - Wang, Xiangfeng

AU - Razaviyayn, Meisam

AU - Ma, Shiqian

AU - Luo, Zhi Quan

PY - 2014

Y1 - 2014

N2 - In this paper, we consider a nonsmooth convex problem with linear coupling constraints. Problems of this form arise in many modern large-scale signal processing applications including the provision of smart grid networks. In this work, we propose a new class of algorithms called the block coordinate descent method of multipliers (BCDMM) to solve this family of problems. The BCDMM is a primal-dual type of algorithm. It optimizes an (approximate) augmented Lagrangian of the original problem one block variable per iteration, followed by a gradient update for the dual variable. We show that under certain regularity conditions, and when the order for which the block variables are either updated in a deterministic or a random fashion, the BCDMM converges to the set of optimal solutions. The effectiveness of the algorithm is illustrated using large-scale basis pursuit and smart grid problems.

AB - In this paper, we consider a nonsmooth convex problem with linear coupling constraints. Problems of this form arise in many modern large-scale signal processing applications including the provision of smart grid networks. In this work, we propose a new class of algorithms called the block coordinate descent method of multipliers (BCDMM) to solve this family of problems. The BCDMM is a primal-dual type of algorithm. It optimizes an (approximate) augmented Lagrangian of the original problem one block variable per iteration, followed by a gradient update for the dual variable. We show that under certain regularity conditions, and when the order for which the block variables are either updated in a deterministic or a random fashion, the BCDMM converges to the set of optimal solutions. The effectiveness of the algorithm is illustrated using large-scale basis pursuit and smart grid problems.

UR - https://www.scopus.com/pages/publications/84905270262

U2 - 10.1109/ICASSP.2014.6855096

DO - 10.1109/ICASSP.2014.6855096

M3 - 会议稿件

AN - SCOPUS:84905270262

SN - 9781479928927

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

SP - 7689

EP - 7693

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

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 4 May 2014 through 9 May 2014

ER -

Hong M, Chang TH, Wang X, Razaviyayn M, Ma S, Luo ZQ. A block coordinate descent method of multipliers: Convergence analysis and applications. In 2014 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 7689-7693. 6855096. (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). doi: 10.1109/ICASSP.2014.6855096

A block coordinate descent method of multipliers: Convergence analysis and applications

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this