An Exponentially Convergent Primal-Dual Algorithm for Nonsmooth Composite Minimization

Dongsheng Ding, Bin Hu, Neil K. Dhingra, Mihailo R. Jovanovic

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a class of nonsmooth convex composite optimization problems, where the objective function is given by the sum of a continuously differentiable convex term and a potentially non-differentiable convex regularizer. In [1], the authors introduced the proximal augmented Lagrangian method and derived the resulting continuous-time primal-dual dynamics that converge to the optimal solution. In this paper, we extend these dynamics from continuous to discrete time via the forward Euler discretization. We prove explicit bounds on the exponential convergence rates of our proposed algorithm with a sufficiently small step size. Since a larger step size can improve the convergence speed, we further develop a linear matrix inequality (LMI) condition which can be numerically solved to provide rate certificates with general step size choices. In addition, we prove that a large range of step size values can guarantee exponential convergence. We close the paper by demonstrating the performance of the proposed algorithm via computational experiments.

Original languageEnglish (US)
Title of host publication2018 IEEE Conference on Decision and Control, CDC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4927-4932
Number of pages6
ISBN (Electronic)9781538613955
DOIs
StatePublished - Jan 18 2019
Event57th IEEE Conference on Decision and Control, CDC 2018 - Miami, United States
Duration: Dec 17 2018Dec 19 2018

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume2018-December
ISSN (Print)0743-1546

Conference

Conference57th IEEE Conference on Decision and Control, CDC 2018
CountryUnited States
CityMiami
Period12/17/1812/19/18

Fingerprint

Primal-dual Algorithm
Composite
Exponential Convergence
Composite materials
Linear matrix inequalities
Augmented Lagrangian Method
Explicit Bounds
Primal-dual
Continuously differentiable
Convergence Speed
Certificate
Computational Experiments
Matrix Inequality
Convergence Rate
Euler
Continuous Time
Linear Inequalities
Discrete-time
Objective function
Optimal Solution

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Cite this

Ding, D., Hu, B., Dhingra, N. K., & Jovanovic, M. R. (2019). An Exponentially Convergent Primal-Dual Algorithm for Nonsmooth Composite Minimization. In 2018 IEEE Conference on Decision and Control, CDC 2018 (pp. 4927-4932). [8619760] (Proceedings of the IEEE Conference on Decision and Control; Vol. 2018-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2018.8619760

An Exponentially Convergent Primal-Dual Algorithm for Nonsmooth Composite Minimization. / Ding, Dongsheng; Hu, Bin; Dhingra, Neil K.; Jovanovic, Mihailo R.

2018 IEEE Conference on Decision and Control, CDC 2018. Institute of Electrical and Electronics Engineers Inc., 2019. p. 4927-4932 8619760 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2018-December).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Ding, D, Hu, B, Dhingra, NK & Jovanovic, MR 2019, An Exponentially Convergent Primal-Dual Algorithm for Nonsmooth Composite Minimization. in 2018 IEEE Conference on Decision and Control, CDC 2018., 8619760, Proceedings of the IEEE Conference on Decision and Control, vol. 2018-December, Institute of Electrical and Electronics Engineers Inc., pp. 4927-4932, 57th IEEE Conference on Decision and Control, CDC 2018, Miami, United States, 12/17/18. https://doi.org/10.1109/CDC.2018.8619760
Ding D, Hu B, Dhingra NK, Jovanovic MR. An Exponentially Convergent Primal-Dual Algorithm for Nonsmooth Composite Minimization. In 2018 IEEE Conference on Decision and Control, CDC 2018. Institute of Electrical and Electronics Engineers Inc. 2019. p. 4927-4932. 8619760. (Proceedings of the IEEE Conference on Decision and Control). https://doi.org/10.1109/CDC.2018.8619760
Ding, Dongsheng ; Hu, Bin ; Dhingra, Neil K. ; Jovanovic, Mihailo R. / An Exponentially Convergent Primal-Dual Algorithm for Nonsmooth Composite Minimization. 2018 IEEE Conference on Decision and Control, CDC 2018. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 4927-4932 (Proceedings of the IEEE Conference on Decision and Control).
@inproceedings{427d081aadee4022bc3d3e75da534ca7,
title = "An Exponentially Convergent Primal-Dual Algorithm for Nonsmooth Composite Minimization",
abstract = "We consider a class of nonsmooth convex composite optimization problems, where the objective function is given by the sum of a continuously differentiable convex term and a potentially non-differentiable convex regularizer. In [1], the authors introduced the proximal augmented Lagrangian method and derived the resulting continuous-time primal-dual dynamics that converge to the optimal solution. In this paper, we extend these dynamics from continuous to discrete time via the forward Euler discretization. We prove explicit bounds on the exponential convergence rates of our proposed algorithm with a sufficiently small step size. Since a larger step size can improve the convergence speed, we further develop a linear matrix inequality (LMI) condition which can be numerically solved to provide rate certificates with general step size choices. In addition, we prove that a large range of step size values can guarantee exponential convergence. We close the paper by demonstrating the performance of the proposed algorithm via computational experiments.",
author = "Dongsheng Ding and Bin Hu and Dhingra, {Neil K.} and Jovanovic, {Mihailo R.}",
year = "2019",
month = "1",
day = "18",
doi = "10.1109/CDC.2018.8619760",
language = "English (US)",
series = "Proceedings of the IEEE Conference on Decision and Control",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "4927--4932",
booktitle = "2018 IEEE Conference on Decision and Control, CDC 2018",
address = "United States",

}

TY - GEN

T1 - An Exponentially Convergent Primal-Dual Algorithm for Nonsmooth Composite Minimization

AU - Ding, Dongsheng

AU - Hu, Bin

AU - Dhingra, Neil K.

AU - Jovanovic, Mihailo R.

PY - 2019/1/18

Y1 - 2019/1/18

N2 - We consider a class of nonsmooth convex composite optimization problems, where the objective function is given by the sum of a continuously differentiable convex term and a potentially non-differentiable convex regularizer. In [1], the authors introduced the proximal augmented Lagrangian method and derived the resulting continuous-time primal-dual dynamics that converge to the optimal solution. In this paper, we extend these dynamics from continuous to discrete time via the forward Euler discretization. We prove explicit bounds on the exponential convergence rates of our proposed algorithm with a sufficiently small step size. Since a larger step size can improve the convergence speed, we further develop a linear matrix inequality (LMI) condition which can be numerically solved to provide rate certificates with general step size choices. In addition, we prove that a large range of step size values can guarantee exponential convergence. We close the paper by demonstrating the performance of the proposed algorithm via computational experiments.

AB - We consider a class of nonsmooth convex composite optimization problems, where the objective function is given by the sum of a continuously differentiable convex term and a potentially non-differentiable convex regularizer. In [1], the authors introduced the proximal augmented Lagrangian method and derived the resulting continuous-time primal-dual dynamics that converge to the optimal solution. In this paper, we extend these dynamics from continuous to discrete time via the forward Euler discretization. We prove explicit bounds on the exponential convergence rates of our proposed algorithm with a sufficiently small step size. Since a larger step size can improve the convergence speed, we further develop a linear matrix inequality (LMI) condition which can be numerically solved to provide rate certificates with general step size choices. In addition, we prove that a large range of step size values can guarantee exponential convergence. We close the paper by demonstrating the performance of the proposed algorithm via computational experiments.

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

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

U2 - 10.1109/CDC.2018.8619760

DO - 10.1109/CDC.2018.8619760

M3 - Conference contribution

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 4927

EP - 4932

BT - 2018 IEEE Conference on Decision and Control, CDC 2018

PB - Institute of Electrical and Electronics Engineers Inc.

ER -