Convergence Rate of a Penalty Method for Strongly Convex Problems with Linear Constraints

Angelia Nedic; Tatiana Tatarenko

doi:10.1109/CDC42340.2020.9303832

Convergence Rate of a Penalty Method for Strongly Convex Problems with Linear Constraints

Angelia Nedic, Tatiana Tatarenko

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

4 Scopus citations

Abstract

We consider an optimization problem with strongly convex objective and linear inequalities constraints. To be able to deal with a large number of constraints we provide a penalty reformulation of the problem. As penalty functions we use a version of the one-sided Huber losses. The smoothness properties of these functions allow us to choose time-varying penalty parameters in such a way that the incremental procedure with the diminishing step-size converges to the exact solution with the rate \mathcal{O}(1/\sqrt k ). To the best of our knowledge, we present the first result on the convergence rate for the penalty-based gradient method, in which the penalty parameters vary with time.

Original language	English (US)
Title of host publication	2020 59th IEEE Conference on Decision and Control, CDC 2020
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	372-377
Number of pages	6
ISBN (Electronic)	9781728174471
DOIs	https://doi.org/10.1109/CDC42340.2020.9303832
State	Published - Dec 14 2020
Event	59th IEEE Conference on Decision and Control, CDC 2020 - Virtual, Jeju Island, Korea, Republic of Duration: Dec 14 2020 → Dec 18 2020

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
Volume	2020-December
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	59th IEEE Conference on Decision and Control, CDC 2020
Country/Territory	Korea, Republic of
City	Virtual, Jeju Island
Period	12/14/20 → 12/18/20

ASJC Scopus subject areas

Control and Systems Engineering
Modeling and Simulation
Control and Optimization

Access to Document

10.1109/CDC42340.2020.9303832

Cite this

Nedic, A., & Tatarenko, T. (2020). Convergence Rate of a Penalty Method for Strongly Convex Problems with Linear Constraints. In 2020 59th IEEE Conference on Decision and Control, CDC 2020 (pp. 372-377). Article 9303832 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2020-December). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC42340.2020.9303832

Convergence Rate of a Penalty Method for Strongly Convex Problems with Linear Constraints. / Nedic, Angelia; Tatarenko, Tatiana.
2020 59th IEEE Conference on Decision and Control, CDC 2020. Institute of Electrical and Electronics Engineers Inc., 2020. p. 372-377 9303832 (Proceedings of the IEEE Conference on Decision and Control; Vol. 2020-December).

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

Nedic, A & Tatarenko, T 2020, Convergence Rate of a Penalty Method for Strongly Convex Problems with Linear Constraints. in 2020 59th IEEE Conference on Decision and Control, CDC 2020., 9303832, Proceedings of the IEEE Conference on Decision and Control, vol. 2020-December, Institute of Electrical and Electronics Engineers Inc., pp. 372-377, 59th IEEE Conference on Decision and Control, CDC 2020, Virtual, Jeju Island, Korea, Republic of, 12/14/20. https://doi.org/10.1109/CDC42340.2020.9303832

@inproceedings{dcba05ca1b754e57ad35190c5d850ca9,

title = "Convergence Rate of a Penalty Method for Strongly Convex Problems with Linear Constraints",

abstract = "We consider an optimization problem with strongly convex objective and linear inequalities constraints. To be able to deal with a large number of constraints we provide a penalty reformulation of the problem. As penalty functions we use a version of the one-sided Huber losses. The smoothness properties of these functions allow us to choose time-varying penalty parameters in such a way that the incremental procedure with the diminishing step-size converges to the exact solution with the rate \mathcal{O}(1/\sqrt k ). To the best of our knowledge, we present the first result on the convergence rate for the penalty-based gradient method, in which the penalty parameters vary with time.",

author = "Angelia Nedic and Tatiana Tatarenko",

note = "Publisher Copyright: {\textcopyright} 2020 IEEE.; 59th IEEE Conference on Decision and Control, CDC 2020 ; Conference date: 14-12-2020 Through 18-12-2020",

year = "2020",

month = dec,

day = "14",

doi = "10.1109/CDC42340.2020.9303832",

language = "English (US)",

series = "Proceedings of the IEEE Conference on Decision and Control",

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

pages = "372--377",

booktitle = "2020 59th IEEE Conference on Decision and Control, CDC 2020",

}

TY - GEN

T1 - Convergence Rate of a Penalty Method for Strongly Convex Problems with Linear Constraints

AU - Nedic, Angelia

AU - Tatarenko, Tatiana

PY - 2020/12/14

Y1 - 2020/12/14

N2 - We consider an optimization problem with strongly convex objective and linear inequalities constraints. To be able to deal with a large number of constraints we provide a penalty reformulation of the problem. As penalty functions we use a version of the one-sided Huber losses. The smoothness properties of these functions allow us to choose time-varying penalty parameters in such a way that the incremental procedure with the diminishing step-size converges to the exact solution with the rate \mathcal{O}(1/\sqrt k ). To the best of our knowledge, we present the first result on the convergence rate for the penalty-based gradient method, in which the penalty parameters vary with time.

AB - We consider an optimization problem with strongly convex objective and linear inequalities constraints. To be able to deal with a large number of constraints we provide a penalty reformulation of the problem. As penalty functions we use a version of the one-sided Huber losses. The smoothness properties of these functions allow us to choose time-varying penalty parameters in such a way that the incremental procedure with the diminishing step-size converges to the exact solution with the rate \mathcal{O}(1/\sqrt k ). To the best of our knowledge, we present the first result on the convergence rate for the penalty-based gradient method, in which the penalty parameters vary with time.

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

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

U2 - 10.1109/CDC42340.2020.9303832

DO - 10.1109/CDC42340.2020.9303832

M3 - Conference contribution

AN - SCOPUS:85099881571

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 372

EP - 377

BT - 2020 59th IEEE Conference on Decision and Control, CDC 2020

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 59th IEEE Conference on Decision and Control, CDC 2020

Y2 - 14 December 2020 through 18 December 2020

ER -

Convergence Rate of a Penalty Method for Strongly Convex Problems with Linear Constraints

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this