Source-linked AI summary
Distributed continuous-time convex optimization on weight-balanced digraphs
Bahman Gharesifard, Jorge Cortes
TL;DR
The paper asks whether continuous-time consensus-based optimization dynamics for undirected graphs also works on directed graphs. It characterizes the optimization problem through saddle points, identifies nonconvergence on a strongly connected weight-balanced digraph, and introduces a parameterized generalization that converges under differentiability and globally Lipschitz gradients.
Problem
Consensus-based continuous-time optimization dynamics that work for undirected graphs do not necessarily carry over to directed scenarios.
Method
The paper combines saddle-point modeling with invariance, cocoercivity, and graph-matrix analysis to design a generalized dynamics with a tunable parameter.
Results
For appropriate parameter choices, the generalized dynamics converges to the minimizers on any strongly connected, weight-balanced digraph when the functions are differentiable convex with globally Lipschitz gradients.
Takeaways & Limitations
The analysis provides a continuous-time distributed optimization dynamics for the stated directed-graph setting where the undirected saddle-point dynamics can fail.
Abstract
from arXiv · showhide
This paper studies the continuous-time distributed optimization of a sum of convex functions over directed graphs. Contrary to what is known in the consensus literature, where the same dynamics works for both undirected and directed scenarios, we show that the consensus-based dynamics that solves the continuous-time distributed optimization problem for undirected graphs fails to converge when transcribed to the directed setting. This study sets the basis for the design of an alternative distributed dynamics which we show is guaranteed to converge, on any strongly connected weight-balanced digraph, to the set of minimizers of a sum of convex differentiable functions with globally Lipschitz gradients. Our technical approach combines notions of invariance and cocoercivity with the positive definiteness properties of graph matrices to establish the results.
I. INTRODUCTION
The paper shows that continuous-time distributed optimization dynamics that succeed on undirected graphs may fail on directed graphs, then develops a convergent alternative under stronger smoothness and graph conditions.
- The study addresses continuous-time distributed optimization of sums of convex functions over directed graphs, motivated by applications including sensor networks, source localization, and robust estimation.
- The paper first characterizes solutions of the directed optimization problem as saddle points of a graph-dependent aggregate objective.The objective is convex in one argument and linear in the other; its gradient is distributed in the undirected case.
- The authors establish convergence of saddle-point dynamics for locally Lipschitz convex functions, extending prior results for continuously differentiable strictly convex functions.
- A strongly connected, weight-balanced digraph provides a counterexample where the distributed saddle-point dynamics does not converge.
- A generalized dynamics with a design parameter converges to the objective minimizers on any strongly connected, weight-balanced digraph when functions are differentiable convex with globally Lipschitz gradients.The analysis combines set-valued stability, algebraic graph theory, and convex analysis.
A. Graph theory
This section introduces directed and weighted graphs, connectivity, Laplacians, and weight balance, highlighting the graph-matrix properties used later.
- A directed graph is defined by a finite vertex set and directed edge set; undirected graphs contain both orientations of every edge.
- Strong connectivity requires a path between every pair of distinct vertices, while connectivity is the corresponding term for undirected graphs.
- A weighted digraph assigns positive adjacency weights to edges, from which weighted degrees and the Laplacian matrix are constructed.
- For a strongly connected digraph, zero is a simple eigenvalue of its Laplacian; weight balance additionally gives key symmetry and positive-semidefiniteness properties.
B. Nonsmooth analysis
The section develops nonsmooth-analysis tools for locally Lipschitz convex functions, including generalized gradients, cocoercivity, and a smoothness characterization.
- Locally Lipschitz functions are differentiable almost everywhere, and their generalized gradients are set-valued objects with regularity properties used in the analysis.
- The generalized gradient map of a locally Lipschitz function is upper semicontinuous with nonempty, compact, convex values.
- For convex locally Lipschitz functions, generalized gradients satisfy a first-order convexity condition, and finite-sum generalized gradients obey an inclusion that becomes equality under regularity.
- Cocoercivity is introduced for locally Lipschitz functions and identified as a key technical notion for the later convergence analysis.
- For differentiable convex functions, the gradient is globally Lipschitz with constant K if and only if the function is 1/K-cocoercive.
C. Set-valued dynamical systems
This section formalizes continuous-time set-valued dynamics and supplies existence, invariance, and LaSalle-type convergence tools for analyzing their solutions.
- A continuous-time set-valued dynamical system is a differential inclusion whose absolutely continuous solutions satisfy the inclusion almost everywhere.
- The equilibrium set consists of states x satisfying 0 ∈ Ψ(x), and upper semicontinuity with nonempty compact convex values guarantees a solution from every initial condition.
- Weak and strong positive invariance distinguish whether at least one or every solution starting in a set remains there.
- The set-valued Lie derivative collects directional derivatives of a differentiable Lyapunov function along all vectors in the dynamics map.
- Under strong invariance, bounded evolutions, and a nonpositive Lie derivative, LaSalle’s principle gives convergence to the largest weakly invariant subset of the zero-derivative set.
III. PROBLEM STATEMENT AND EQUIVALENT FORMULATIONS
The paper reformulates the network-wide convex optimization problem as an agreement-constrained problem over agent estimates, then characterizes its solutions through saddle points of an augmented Lagrangian.
- Each agent maintains an estimate of the global optimization solution while only accessing its own locally Lipschitz convex objective function.
- The original optimization problem is equivalent to minimizing the lifted sum of local objectives subject to the linear agreement constraint Lx = 0.For a strongly connected graph, Lx = 0 implies all agent estimates agree.
- The function F combines the lifted objective, graph coupling, and a quadratic agreement penalty that vanishes when consensus holds.It is locally Lipschitz and convex in x, and linear in the auxiliary variable z.
- Saddle points of F correspond exactly to solutions of the constrained distributed optimization problem, up to an additive agreement-direction shift in z.
- Weight balance makes L + L^T positive semidefinite, supporting convexity of F in its first argument and the saddle-point characterization.
IV. CONTINUOUS-TIME DISTRIBUTED OPTIMIZATION ON UNDIRECTED NETWORKS
For undirected networks, the distributed dynamics can be interpreted through the saddle-point structure of F and converges asymptotically under locally Lipschitz convex objectives.
- The result extends earlier undirected-network convergence from strictly convex differentiable objectives to sums of locally Lipschitz convex functions.
- The dynamics converges asymptotically in its first component to the set of solutions of the constrained optimization problem.If the objective has finitely many critical points, each trajectory’s first-component projection converges to a solution.
- The proof uses a smooth Lyapunov function whose set-valued Lie derivative is nonpositive, which also establishes bounded trajectories.
- LaSalle invariance reduces the limiting behavior to a weakly positively invariant set, whose points satisfy agreement and solve the constrained problem.
- On the invariant set, the common estimate follows the original centralized optimization dynamics and is constant at equilibrium.
- The proof cannot use standard saddle-point convergence results requiring a positive-definite Hessian because the paper’s general hypotheses do not ensure those conditions.Instead, the argument relies on careful invariance analysis of the flow.
V. CONTINUOUS-TIME DISTRIBUTED OPTIMIZATION ON DIRECTED NETWORKS
In directed networks, the undirected distributed dynamics loses its saddle-point interpretation because transpose-Laplacian terms require unavailable in-neighbor information, motivating an alternative dynamics.
- When the graph is directed, the gradient of F contains L^T terms that are not distributed over the communication graph.
- Consequently, the dynamics distributed over the directed graph no longer coincides with the saddle-point dynamics of F.
- The paper tests whether the undirected convergence behavior persists on directed graphs and finds that it does not.
- This failure motivates an alternative distributed dynamics that is provably correct on weight-balanced directed graphs.
A. Counterexample
A necessary spectral condition shows that the transferred dynamics can fail even on strongly connected weight-balanced digraphs, and an explicit example demonstrates nonconvergence.
- A. Counterexample: For zero local objectives, stability of the agreement set requires every nonzero Laplacian eigenvalue λ to satisfy the stated spectral condition.
- A. Counterexample: The condition follows by linearizing the dynamics around agreement and relating the resulting eigenvalues to those of the graph Laplacian.
- A. Counterexample: The counterexample is established by the value 3|Im(λ)| − Re(λ) = 0.0171 > 0, which violates the necessary convergence criterion.
B. Provably correct distributed dynamics on directed graphs
The paper introduces a parameterized continuous-time distributed dynamics for strongly connected, weight-balanced digraphs, addressing convergence problems that arise when undirected-graph dynamics are transferred to directed networks. Under convex differentiable objectives with globally Lipschitz gradients and suitable parameter choices, the dynamics converges to minimizers.
- Proof strategy: The analysis uses an invariant set and LaSalle’s invariance principle after establishing nonpositive Lyapunov decrease and bounded trajectories.For the trivial-objective case, the transformed quadratic Lyapunov analysis identifies consensus equilibria.
- Motivation: The proposed dynamics incorporates a parameter α to overcome indefinite Lie-derivative terms involving L − L^T.A suitable coordinate transformation and parameter choice yield a valid quadratic Lyapunov function.
- Convergence result: For convex differentiable local functions with globally Lipschitz gradients, appropriately choosing the parameter guarantees convergence on strongly connected, weight-balanced digraphs.The proof combines invariance, cocoercivity, Lyapunov analysis, and graph-matrix spectral properties.
- Convergence result: The projection onto the first component of every trajectory asymptotically converges to the set of solutions of the aggregate optimization problem.If the objective has finitely many critical points, the first-component projection converges to a solution point.
- Scope and design: The simulations illustrate Theorem 5.4, while extension to locally Lipschitz objectives remains supported only by simulations because the proof would require globally Lipschitz generalized gradients.The authors also note that suitable parameter ranges depend on network connectivity and gradient variability.
VI. CONCLUSIONS AND FUTURE WORK
The conclusions establish that undirected-network convergence results do not generally transfer to directed graphs, but a parameterized dynamics solves the stated optimization problem under specified graph and function assumptions. Future work targets broader objectives and graph classes, constraints, parameter selection, discretization, and dynamic consensus connections.
- Conclusions: Consensus-based convergence results for undirected networks do not carry over to the directed scenario.The conclusion identifies this failure even though the considered directed graphs are strongly connected and weight-balanced.
- Conclusions: A generalized saddle-point dynamics with a design parameter solves distributed optimization for differentiable convex functions with globally Lipschitz gradients on strongly connected, weight-balanced digraphs.The result holds for appropriate parameter choices.
- Conclusions: The technical approach combines stability analysis, algebraic graph theory, and convex analysis.
- Future work: Future work includes extending convergence results to locally Lipschitz functions and general digraphs.
- Future work: Additional open directions include constraints, distributed selection of the optimal design parameter, algorithm discretization, and connections with dynamic consensus.
APPENDIX
The appendix establishes that globally Lipschitz generalized gradients imply differentiability and proves that generalized gradient flow cannot leave a minimizer. It also concludes that the differentiability assumption in Proposition 2.3 cannot be relaxed.
- Scope of the result: The differentiability hypothesis of Proposition 2.3 cannot be relaxed.This is stated as the next result's conclusion.
- Differentiability: Any locally Lipschitz function with a globally Lipschitz generalized gradient is differentiable.The proof shows that the generalized gradient is singleton-valued.
- Differentiability: Approximating a point by differentiability points and applying the set-valued Lipschitz condition forces every generalized-gradient element to coincide.The argument bounds generalized-gradient elements near gradients at convergent differentiability points, then takes the limit.
- Generalized gradient flow: Starting from a minimizer, the only solution of the generalized gradient flow is the constant trajectory x(t) = x∗.The proof uses monotonic nonincrease of f along the flow to keep the trajectory among minimizers, then derives a contradiction from any nonzero velocity.
- Generalized gradient flow: A nonzero velocity at a minimizer contradicts the flow's constant objective value.The contradiction is obtained after identifying the velocity with an element of −∂f(x∗).