Saddle-point dynamics: conditions for asymptotic stability of saddle points

DOI10.1137/15M1026924zbMATH Open1364.90326arXiv1510.02145OpenAlexW2962717811MaRDI QIDQ2968544FDOQ2968544

Authors: Ashish Cherukuri, Bahman Gharesifard, J. Cortés 

Publication date: 17 March 2017

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

Abstract: This paper considers continuously differentiable functions of two vector variables that have (possibly a continuum of) min-max saddle points. We study the asymptotic convergence properties of the associated saddle-point dynamics (gradient-descent in the first variable and gradient-ascent in the second one). We identify a suite of complementary conditions under which the set of saddle points is asymptotically stable under the saddle-point dynamics. Our first set of results is based on the convexity-concavity of the function defining the saddle-point dynamics to establish the convergence guarantees. For functions that do not enjoy this feature, our second set of results relies on properties of the linearization of the dynamics, the function along the proximal normals to the saddle set, and the linearity of the function in one variable. We also provide global versions of the asymptotic convergence results. Various examples illustrate our discussion.

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

Recommendations

• Stability and robustness for saddle-point dynamics through monotone mappings
• A continuous algorithm for finding the saddle points of convex-concave functions
• Convergence of approximate saddle points
• scientific article; zbMATH DE number 4049432
• scientific article; zbMATH DE number 774633

zbMATH Keywords

asymptotic convergencecenter manifold theorynonsmooth dynamicssaddle-point dynamicsconvex-concave functionsproximal calculus

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Nonlinear ordinary differential equations and systems (34A34) Asymptotic properties of solutions to ordinary differential equations (34D05) Global stability of solutions to ordinary differential equations (34D23) Normal forms, center manifold theory, bifurcation theory for infinite-dimensional dissipative dynamical systems (37L10) Stability of manifolds of solutions to ordinary differential equations (34D35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Subgradient methods for saddle-point problems
• Geometric theory of semilinear parabolic equations
• Applications of centre manifold theory
• Nonlinear systems.
• Design and Stability of Load-Side Primary Frequency Control in Power Systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discontinuous dynamical systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the stable equilibrium points of gradient systems
• Distributed Continuous-Time Convex Optimization on Weight-Balanced Digraphs
• Title not available (Why is that?)
• An iterative method of Lyapunov function construction for differential inclusions
• Nontangency-Based Lyapunov Tests for Convergence and Stability in Systems Having a Continuum of Equilibria
• Stability of primal-dual gradient dynamics and applications to network optimization
• Asymptotic convergence of constrained primal-dual dynamics
• On the Characterization of Local Nash Equilibria in Continuous Games
• Solutions of Saddle Value Problems by Differential Equations
• A note on strongly convex and quasiconvex functions
• Distributed Bargaining in Dyadic-Exchange Networks
• Basic real analysis
• Robust Distributed Linear Programming

Cited In (24)

• Semi-global exponential stability of augmented primal-dual gradient dynamics for constrained convex optimization
• Continuous-time convergence rates in potential and monotone games
• Local saddles of relaxed averaged alternating reflections algorithms on phase retrieval
• Nonsmooth control barrier function design of continuous constraints for network connectivity maintenance
• An Arrow-Hurwicz-Uzawa type flow as least squares solver for network linear equations
• A unifying convex analysis and switching system approach to consensus with undirected communication graphs
• Stability and robustness for saddle-point dynamics through monotone mappings
• A primal-dual flow for affine constrained convex optimization
• Frequency-driven market mechanisms for optimal dispatch in power networks
• Distributed coordination for nonsmooth convex optimization via saddle-point dynamics
• A concise 4D conservative chaotic system with wide parameter range, offset boosting behavior and high initial sensitivity
• Multivalued perturbations of a saddle dynamics
• A second order primal-dual dynamical system for a convex-concave bilinear saddle point problem
• Title not available (Why is that?)
• Semiglobal exponential stability of the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm for constrained optimization
• Transformed primal-dual methods for nonlinear saddle point systems
• Instability analysis of saddle points by a local minimax method
• Linear-quadratic zero-sum mean-field type games: optimality conditions and policy optimization
• Stochastic programming with primal-dual dynamics: a mean-field game approach
• Relaxed-inertial proximal point algorithms for nonconvex equilibrium problems with applications
• Some adaptive first-order methods for variational inequalities with relatively strongly monotone operators and generalized smoothness
• Convergence rates of inertial primal-dual dynamical methods for separable convex optimization problems
• Title not available (Why is that?)
• Distributed optimization under edge agreements: a continuous-time algorithm

This page was built for publication: Saddle-point dynamics: conditions for asymptotic stability of saddle points

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