CaltechAUTHORS
  A Caltech Library Service

Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems

Tang, Yujie and Dall'Anese, Emiliano and Bernstein, Andrey and Low, Steven (2022) Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems. SIAM Journal on Control and Optimization, 60 (4). pp. 1970-1990. ISSN 0363-0129. doi:10.1137/20m1371063. https://resolver.caltech.edu/CaltechAUTHORS:20220811-235221000

[img] PDF - Published Version
See Usage Policy.

727kB
[img] PDF - Submitted Version
See Usage Policy.

2MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220811-235221000

Abstract

This paper focuses on a time-varying constrained nonconvex optimization problem, and considers the synthesis and analysis of online regularized primal-dual gradient methods to track a Karush--Kuhn--Tucker (KKT) trajectory. The proposed regularized primal-dual gradient method is implemented in a running fashion, in the sense that the underlying optimization problem changes during the execution of the algorithms. In order to study its performance, we first derive its continuous-time limit as a system of differential inclusions. We then study sufficient conditions for tracking a KKT trajectory, and also derive asymptotic bounds for the tracking error (as a function of the time-variability of a KKT trajectory). Further, we provide a set of sufficient conditions for the KKT trajectories not to bifurcate or merge, and also investigate the optimal choice of the parameters of the algorithm. Illustrative numerical results for a time-varying nonconvex problem are provided.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/20M1371063DOIArticle
https://arxiv.org/abs/1812.00613arXivDiscussion Paper
ORCID:
AuthorORCID
Tang, Yujie0000-0002-4921-8372
Low, Steven0000-0001-6476-3048
Additional Information:© 2022 Society for Industrial and Applied Mathematics. Submitted: 19 October 2020. Accepted: 01 March 2022. Published Online: 07 July 2022. This work was supported by the ARPA-E through grant DE-AR0000699, and by the NSF through grants CCF 1637598, ECCS 1619352, CPS 1739355.
Funders:
Funding AgencyGrant Number
Advanced Research Projects Agency-Energy (ARPA-E)DE-AR0000699
NSFCCF-1637598
NSFECCS-1619352
NSFECCS-1739355
Subject Keywords:time-varying optimization; primal-dual dynamics; tracking; nonconvex optimization; gradient methods; differential inclusion
Issue or Number:4
Classification Code:AMS subject classifications. 34A60, 49M37, 90C30, 90C31
DOI:10.1137/20m1371063
Record Number:CaltechAUTHORS:20220811-235221000
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220811-235221000
Official Citation:Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems. Yujie Tang, Emiliano Dall'Anese, Andrey Bernstein, and Steven Low. SIAM Journal on Control and Optimization 2022 60:4, 1970-1990; DOI: 10.1137/20m1371063
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116263
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:12 Aug 2022 22:51
Last Modified:12 Aug 2022 22:52

Repository Staff Only: item control page