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

DOI10.1137/20M1371063zbMATH Open1496.90068arXiv1812.00613OpenAlexW2903451074MaRDI QIDQ5093264FDOQ5093264

Authors: Yujie Tang, Emiliano Dall'Anese, Andrey Bernstein, Steven H. Low 

Publication date: 26 July 2022

Published in: SIAM Journal on Control and Optimization (Search for Journal in Brave)

Abstract: This paper considers a nonconvex optimization problem that evolves over time, and addresses the synthesis and analysis of regularized primal-dual gradient methods to track a Karush-Kuhn-Tucker (KKT) trajectory. The proposed regularized primal-dual gradient methods are implemented in a running fashion, in the sense that the underlying optimization problem changes during the iterations of the algorithms. For a problem with twice continuously differentiable cost and constraints, and under a generalization of the Mangasarian-Fromovitz constraint qualification, sufficient conditions are derived for the running algorithm to track a KKT trajectory. Further, asymptotic bounds for the tracking error (as a function of the time-variability of a KKT trajectory) are obtained. A continuous-time version of the algorithm, framed as a system of differential inclusions, is also considered and analytical convergence results are derived. For the continuous-time setting, a set of sufficient conditions for the KKT trajectories not to bifurcate or merge is proposed. Illustrative numerical results inspired by a real-world application are provided.

Full work available at URL: https://arxiv.org/abs/1812.00613

Recommendations

• Primal-dual incremental gradient method for nonsmooth and convex optimization problems
• Non-stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates
• Primal-dual extragradient methods for nonlinear nonsmooth PDE-constrained optimization
• A stochastic primal-dual method for a class of nonconvex constrained optimization
• An efficient primal dual prox method for non-smooth optimization
• Primal-Dual Stochastic Gradient Method for Convex Programs with Many Functional Constraints
• Primal-Dual Interior Methods for Nonconvex Nonlinear Programming
• Online Primal-Dual Methods With Measurement Feedback for Time-Varying Convex Optimization
• A fast continuous time approach with time scaling for nonsmooth convex optimization
• Accelerated primal-dual gradient descent with linesearch for convex, nonconvex, and nonsmooth optimization problems

zbMATH Keywords

nonconvex optimizationgradient methodsdifferential inclusiontrackingtime-varying optimizationprimal-dual dynamics

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Numerical methods based on nonlinear programming (49M37) Sensitivity, stability, parametric optimization (90C31) Ordinary differential inclusions (34A60)

Cites Work

• Multiuser optimization: distributed algorithms and error analysis
• Title not available (Why is that?)
• Implicit Functions and Solution Mappings
• On the equivalence between complementarity systems, projected systems and differential inclusions
• Distributed Continuous-Time Convex Optimization on Weight-Balanced Digraphs
• Evolution equations governed by the sweeping process
• Convex sweeping process in the framework of measure differential inclusions and evolution variational inequalities
• On LICQ and the uniqueness of Lagrange multipliers
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• On the discrete analogues of some generalizations of Gronwall's inequality
• Gradient methods for nonstationary unconstrained optimization problems
• BV periodic solutions of an evolution problem associated with continuous moving convex sets
• Title not available (Why is that?)
• An Euler-Newton continuation method for tracking solution trajectories of parametric variational inequalities
• Real-time nonlinear optimization as a generalized equation
• Accelerated methods for nonconvex optimization
• The Role of Convexity in Saddle-Point Dynamics: Lyapunov Function and Robustness
• Semi-global exponential stability of augmented primal-dual gradient dynamics for constrained convex optimization
• Convergence Analysis of Saddle Point Problems in Time Varying Wireless Systems— Control Theoretical Approach
• Online Learning With Inexact Proximal Online Gradient Descent Algorithms
• Prediction-Correction Algorithms for Time-Varying Constrained Optimization
• Distributed Continuous-Time Convex Optimization With Time-Varying Cost Functions
• Online Primal-Dual Methods With Measurement Feedback for Time-Varying Convex Optimization
• A Contraction Analysis of Primal-Dual Dynamics in Distributed and Time-Varying Implementations
• Discrete and Continuous-Time Soft-Thresholding for Dynamic Signal Recovery
• Second-Order Online Nonconvex Optimization

Cited In (5)

• Discrete-time Euler-smoothing methods for time-varying convex constrained optimization
• Nonlinear optimization filters for stochastic time-varying convex optimization
• Primal-dual method for optimization problems with changing constraints
• Bounds for the tracking error of first-order online optimization methods
• Variable metric primal-dual method for convex optimization problems with changing constraints

This page was built for publication: Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5093264)