CaltechAUTHORS
  A Caltech Library Service

The Role of Convexity on Saddle-Point Dynamics: Lyapunov Function and Robustness

Cherukuri, Ashish and Mallada, Enrique and Low, Steven and Cortés, Jorge (2018) The Role of Convexity on Saddle-Point Dynamics: Lyapunov Function and Robustness. IEEE Transactions on Automatic Control, 63 (8). pp. 2449-2464. ISSN 0018-9286. https://resolver.caltech.edu/CaltechAUTHORS:20171204-104144520

Full text is not posted in this repository. Consult Related URLs below.

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

Abstract

This paper studies the projected saddle-point dynamics associated to a convex–concave function, which we term saddle function. The dynamics consists of gradient descent of the saddle function in variables corresponding to convexity and (projected) gradient ascent in variables corresponding to concavity. We examine the role that the local and/or global nature of the convexity–concavity properties of the saddle function plays in guaranteeing convergence and robustness of the dynamics. Under the assumption that the saddle function is twice continuously differentiable, we provide a novel characterization of the omega-limit set of the trajectories of this dynamics in terms of the diagonal blocks of the Hessian. Using this characterization, we establish global asymptotic convergence of the dynamics under local strong convexity–concavity of the saddle function. When strong convexity–concavity holds globally, we establish three results. First, we identify a Lyapunov function (that decreases strictly along the trajectory) for the projected saddle-point dynamics when the saddle function corresponds to the Lagrangian of a general constrained convex optimization problem. Second, for the particular case when the saddle function is the Lagrangian of an equality-constrained optimization problem, we show input-to-state stability (ISS) of the saddle-point dynamics by providing an ISS Lyapunov function. Third, we use the latter result to design an opportunistic state-triggered implementation of the dynamics. Various examples illustrate our results.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/TAC.2017.2778689DOIArticle
http://ieeexplore.ieee.org/document/8123914PublisherArticle
http://resolver.caltech.edu/CaltechAUTHORS:20170217-154230896Related ItemConference Paper
ORCID:
AuthorORCID
Cherukuri, Ashish0000-0002-7609-5080
Mallada, Enrique0000-0003-1568-1833
Low, Steven0000-0001-6476-3048
Additional Information:© 2017 IEEE. Manuscript received April 18, 2017; revised August 23, 2017; accepted October 13, 2017. Date of publication November 29, 2017; date of current version July 26, 2018. Recommended by Associate Editor F. R. Wirth. This paper was presented in part at the 2016 Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, [1]. This work was supported in part by the ARPA-e Network Optimized Distributed Energy Systems (NODES) program, in part by the Cooperative Agreement DE-AR0000695, in part by the NSF Award ECCS-1307176, in part by the AFOSR Award FA9550-15-1-0108, and in part by the Army Research Office grant W911NF-17-1-0092.
Funders:
Funding AgencyGrant Number
Department of Energy (DOE)DE-AR0000695
NSFECCS-1307176
Air Force Office of Scientific Research (AFOSR)FA9550-15-1-0108
Army Research Office (ARO)W911NF-17-1-0092
Subject Keywords:Asymptotic stability, constrained convex optimization, input-to-state stability, primal-dual dynamics, saddle-point dynamics
Issue or Number:8
Record Number:CaltechAUTHORS:20171204-104144520
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20171204-104144520
Official Citation:A. Cherukuri, E. Mallada, S. Low and J. Cortés, "The Role of Convexity in Saddle-Point Dynamics: Lyapunov Function and Robustness," in IEEE Transactions on Automatic Control, vol. 63, no. 8, pp. 2449-2464, Aug. 2018. doi: 10.1109/TAC.2017.2778689
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:83659
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:13 Dec 2017 05:10
Last Modified:03 Oct 2019 19:09

Repository Staff Only: item control page