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
![]() |
PDF
- Published Version
See Usage Policy. 727kB |
![]() |
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: |
| ||||||||||
ORCID: |
| ||||||||||
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: |
| ||||||||||
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