Distributed coordination for nonsmooth convex optimization via\n saddle-point dynamics

Simon K. Niederländer, Jorge Cortés

Abstract

This paper considers continuous-time coordination algorithms for networks of agents that seek to collectively solve a general class of nonsmooth convex optimization problems with an inherent distributed structure. Our algorithm design builds on the characterization of the solutions of the nonsmooth convex program as saddle points of an augmented Lagrangian. We show that the associated saddle-point dynamics are asymptotically correct but, in general, not distributed because of the presence of a global penalty parameter. This motivates the design of a discontinuous saddle-point-like algorithm that enjoys the same convergence properties and is fully amenable to distributed implementation. Our convergence proofs rely on the identification of a novel global Lyapunov function for saddle-point dynamics. This novelty also allows us to identify mild convexity and regularity conditions on the objective function that guarantee the exponential convergence rate of the proposed algorithms for convex optimization problems subject to equality constraints.

Introduction

In modern engineering and networked systems—ranging from autonomous drone swarms to smart power grids—the ability for a collective of agents to solve large-scale optimization problems is critical. Traditionally, these problems have been approached via consensus-based methods, where every agent in the network attempts to agree on the entire global solution vector. However, as networks scale to hundreds or thousands of nodes, requiring every agent to track every global variable becomes computationally and communicationally prohibitive.

This research addresses a more scalable, partition-based setup: each agent is responsible for finding only its specific component of the optimal solution. These components are coupled through global constraints, such as total resource limits or network flow balances. Furthermore, the objective functions involved are often "nonsmooth," containing sharp corners or absolute values where standard gradient-based calculus fails. The primary challenge in decentralizing these problems has been the reliance on "global penalty parameters"—constants that must be known by all agents simultaneously to ensure convergence. This paper introduces a novel, discontinuous dynamical system that removes this global dependency, allowing for truly distributed coordination.

Methodology

Saddle-Point-Like Dynamics (SPLD)

The proposed solution leverages Saddle-Point Dynamics (SPD), treating the optimization as a competition between primal variables (the agents' solutions) and dual variables (Lagrange multipliers). To handle the nonsmooth nature of the objective functions and the coupling constraints, the authors utilize an Augmented Lagrangian framework. This framework incorporates quadratic regularization and $\ell_1$-exact penalty terms to transform inequality constraints into a manageable dynamical form.

To overcome the "global parameter" bottleneck, the researchers developed Saddle-Point-Like Dynamics (SPLD). This discontinuous algorithm replaces the need for a pre-calculated, global penalty constant with a local projection operator. This operator ensures that agents remain within the feasible region of their inequality constraints throughout the optimization process, making the system fully decentralized.

Nonsmooth Lyapunov Analysis

A central contribution of this work is the identification of a novel nonsmooth Lyapunov function. In control theory, a Lyapunov function acts as a mathematical representation of the system's "energy" that must strictly decrease as the system approaches equilibrium. While previous research often relied on the LaSalle Invariance Principle—which can only guarantee that a system will eventually settle—the new Lyapunov function allows for a more rigorous analysis. It enables the authors to prove not just asymptotic stability, but also to calculate specific convergence rates.

Key Insights and Results

Breaking Global Dependency

The most significant theoretical breakthrough is the realization that a discontinuous, projected dynamical system can effectively mimic the behavior of a system with a "perfect" global penalty parameter. This allows agents to converge to the global optimum using only local interactions and their own state data, making the communication overhead independent of the total number of agents in the network.

Convergence and Feasibility

The paper provides several rigorous guarantees:

  • Asymptotic Correctness: The proposed SPLD is guaranteed to reach the optimal solution set for the nonsmooth convex program.
  • Exponential Convergence: Under mild regularity conditions (such as a strictly monotone gradient) and equality constraints, the algorithm converges at an exponential rate. This is a significant improvement over the sub-linear rates often found in nonsmooth optimization.
  • Feasibility Guarantee: Because the SPLD uses a projection-based approach, it ensures that agents do not violate inequality constraints during the transition, a vital feature for safety-critical applications like power system frequency control.

Numerical Validation

The authors validated the framework using synthetic numerical simulations involving a network of 50 agents. The agents were tasked with solving a nonsmooth problem involving absolute values and power functions. The communication topology was modeled using circulant and Toeplitz matrices to simulate standard network information flows. In these tests, the network successfully converged to the optimal state, confirming the theoretical predictions regarding both correctness and speed.

Limitations and Future Work

While the paper establishes a robust foundation for distributed nonsmooth optimization, several areas for further research remain:

  • Inequality Constraints and Rates: While exponential convergence is proven for equality constraints, extending this specific rate proof to include active inequality constraints remains a technical challenge due to the complexities of nonsmooth penalty terms.
  • Discrete-Time Implementation: The current work is framed in continuous-time (differential equations). Future research is needed to identify optimal "state-triggered" or aperiodic stepsizes to maintain these convergence properties when implemented on digital hardware.
  • Network Robustness: The current model assumes reliable communication. Future studies could explore how the SPLD behaves under conditions of link failure, packet loss, or the presence of adversarial agents.

Summary updated

Abstract

This paper considers continuous-time coordination algorithms for networks of\nagents that seek to collectively solve a general class of nonsmooth convex\noptimization problems with an inherent distributed structure. Our algorithm\ndesign builds on the characterization of the solutions of the nonsmooth convex\nprogram as saddle points of an augmented Lagrangian. We show that the\nassociated saddle-point dynamics are asymptotically correct but, in general,\nnot distributed because of the presence of a global penalty parameter. This\nmotivates the design of a discontinuous saddle-point-like algorithm that enjoys\nthe same convergence properties and is fully amenable to distributed\nimplementation. Our convergence proofs rely on the identification of a novel\nglobal Lyapunov function for saddle-point dynamics. This novelty also allows us\nto identify mild convexity and regularity conditions on the objective function\nthat guarantee the exponential convergence rate of the proposed algorithms for\nconvex optimization problems subject to equality constraints. Various examples\nillustrate our discussion.\n
BibTeX
@article{niederlander2019distributed,
  author = {Simon K. Niederländer and Jorge Cortés},
  title = {{Distributed coordination for nonsmooth convex optimization via\textbackslash\{\}n saddle-point dynamics}},
  journal = {J. Nonlinear Sci.},
  year = {2019},
  url = {https://openreview.net/forum?id=g11foLsEz1},
}
Figure