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.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 Paper
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.
Funding AgencyGrant Number
Advanced Research Projects Agency-Energy (ARPA-E)DE-AR0000699
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
Record Number:CaltechAUTHORS:20220811-235221000
Persistent URL:
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
Deposited By: George Porter
Deposited On:12 Aug 2022 22:51
Last Modified:12 Aug 2022 22:52

Repository Staff Only: item control page