Source-linked AI summary
Distributed Continuous-Time Algorithm for Constrained Convex Optimizations via Nonsmooth Analysis Approach
Xianlin Zeng, Peng Yi, Yiguang Hong
TL;DR
The paper studies distributed minimization of sums of nonsmooth convex costs when each agent has its own local constraint set. It proposes a projected continuous-time primal-dual algorithm using local information and analyzes it with nonsmooth Lyapunov functions for differential inclusions. The analysis proves common optimal convergence with bounded states, including problems having a continuum of optimal solutions.
Problem
Constrained distributed optimization is difficult when agents must minimize global costs using only local cost functions and local constraint sets.
Method
The paper combines primal-dual saddle-point seeking, projection methods for set constraints, and nonsmooth Lyapunov analysis of differential inclusions.
Results
The proposed algorithm is proved convergent to a common optimal solution while keeping its states bounded.
Takeaways & Limitations
The convergence analysis also covers general convex problems with a continuum of optimal solutions.
Abstract
from arXiv · showhide
This technical note studies the distributed optimization problem of a sum of nonsmooth convex cost functions with local constraints. At first, we propose a novel distributed continuous-time projected algorithm, in which each agent knows its local cost function and local constraint set, for the constrained optimization problem. Then we prove that all the agents of the algorithm can find the same optimal solution, and meanwhile, keep the states bounded while seeking the optimal solutions. We conduct a complete convergence analysis by employing nonsmooth Lyapunov functions for the stability analysis of differential inclusions. Finally, we provide a numerical example for illustration.
I. INTRODUCTION
The note addresses constrained distributed optimization with nonsmooth convex costs and local constraints by proposing a continuous-time projected algorithm. It establishes convergence to a common optimum with bounded states using nonsmooth analysis.
- Motivation: Local constraints are important for network applications because agents may face limited computation, communication, privacy, security, or task-specific feasible ranges.Examples include multi-robot motion planning, communication-network resource allocation, and economic dispatch in power grids.
- Method: The paper proposes a distributed continuous-time algorithm for nonsmooth convex optimization in which agents use only local cost functions and local constraint sets.The design combines primal-dual saddle-point seeking with projection methods for set constraints.
- Results: General convexity is handled, and convergence is guaranteed even when convexity yields a continuum of optimal solutions.The algorithm is also consistent with earlier unconstrained continuous-time designs when constraints are absent.
- Analysis: Nonsmooth Lyapunov functions and differential-inclusion stability theory support a complete convergence analysis for the proposed algorithm.The nonsmooth formulation extends the analysis beyond the smooth-cost setting considered in many existing continuous-time designs.
- Results: The algorithm is proved to solve the optimization problem while keeping its states bounded as agents seek optimal solutions.This addresses a contrast with a recent algorithm whose states may become asymptotically unbounded.
- Results: A complete proof establishes bounded algorithm states and convergence of agents’ estimates to the same optimal solution, with simulations provided for illustration.The note concludes by reporting convergence, bounded states, support for a continuum of optima, and algorithm-performance simulation studies.
II. MATHEMATICAL PRELIMINARIES
The preliminaries define notation for vectors, matrices, sets, distances, cones, norms, and graph structure used in the subsequent analysis.
- A. Notations: The section introduces real-vector and matrix notation, identity and transpose operators, Euclidean norms, matrix rank, range, kernel, eigenvalues, and Kronecker products.It also defines positive-definite and positive-semidefinite matrix notation.
- A. Notations: For a set S, the normal cone, tangent cone, closure, interior, open ball, and distance-to-set notation are defined.Approach of a trajectory to a set is expressed through the distance becoming arbitrarily small after a sufficiently large time.
- B. Graph Theory: A weighted undirected graph is represented by nodes, edges, and a symmetric weighted adjacency matrix, with its Laplacian defined from the degree matrix and adjacency matrix.The graph notation is used for the network structure underlying distributed optimization.
- B. Graph Theory: For a connected weighted undirected graph, the Laplacian is positive semidefinite, has rank n−1, and has kernel consisting of multiples of the all-ones vector.These properties characterize the graph’s consensus subspace.
C. Projection Operator
The paper formulates distributed optimization over a connected undirected graph, with a global cost formed from local convex costs and feasibility defined by intersecting local constraint sets. A projection-based optimality condition links consensus, local subgradients, network coupling, and constraint normal cones.
- Projection-based optimality: The projection operator onto a closed convex set selects the nearest feasible point, and tangent-cone projections express constrained stationarity.
- Problem formulation: The network contains n agents, each with a local cost function f_i and local feasible constraint set Ω_i.
- Problem formulation: The global objective is the sum of the local costs, while the feasible set is the intersection of the local constraint sets.
- Distributed structure: Each agent uses its own cost and constraint information together with shared neighbor information through constant local communications.
- Problem formulation: The model extends unconstrained and homogeneous-constraint formulations by incorporating local, potentially heterogeneous constraints.
- Projection-based optimality: An optimal solution is characterized by a consensus state and multipliers satisfying a projected condition involving subgradients, the graph Laplacian, and the feasible-set normal cone.
B. Distributed Continuous-Time Projected Algorithm
The proposed continuous-time projected algorithm combines local nonsmooth optimization, neighbor coupling, and tangent-cone projection to handle local constraints. It is motivated by primal-dual algorithms and is designed to preserve bounded states while seeking a common optimum.
- Algorithm: The algorithm is a distributed continuous-time projected scheme for the constrained optimization problem.
- Distributed implementation: The method uses local costs and constraints together with neighbor information communicated over the graph.
- Constraint handling: Tangent-cone projection keeps each primal update compatible with the agent’s local constraint set.
- Relation to prior work: When state constraints are removed, the algorithm is consistent with a previously proposed unconstrained continuous-time algorithm.
- Claimed advantage: Unlike a related method that may produce unbounded states, the proposed algorithm handles local constraints and guarantees boundedness of states.
IV. MAIN RESULTS
The paper introduces additional nonsmooth-analysis preliminaries and then analyzes convergence of the proposed algorithm, supported by an illustrative simulation.
- Section scope: The section first develops additional preliminaries for nonsmooth analysis.
- Section scope: It then presents convergence analysis for the proposed algorithm together with an illustrative simulation.
A. Nonsmooth Analysis
The analysis uses differential-inclusion concepts, invariant sets, Lyapunov stability, and nonsmooth Lyapunov functions to establish convergence properties of trajectories.
- Differential inclusions: Solutions of the differential inclusion are absolutely continuous functions satisfying the inclusion almost everywhere in time.
- Differential inclusions: The framework assumes right maximal solutions exist for all t ≥ 0 and distinguishes weak from strong invariance of sets.
- Almost cluster points: An almost cluster point is defined through infinite-measure recurrence within every ε-neighborhood of the point.
- Lyapunov analysis: Under compact invariant-set and semicontinuity assumptions, a trajectory and its derivative have almost cluster points satisfying W(x*, v*) = 0.
- Lyapunov analysis: If W(x, v) > 0 whenever v ≠ 0, the trajectory’s almost cluster point is an equilibrium of the differential inclusion.
- Convergence: An almost cluster point that is Lyapunov stable is the trajectory’s limit as t → ∞.
B. Convergence Analysis
The proposed projected dynamics is analyzed as a differential inclusion using nonsmooth Lyapunov functions. Under the stated assumptions, trajectories remain bounded and converge to consensus at an optimal solution, including when optimal solutions are nonunique.
- Algorithm formulation: Algorithm (5) can be written in compact projected-dynamics form, with projection preserving the constraint set through the tangent-cone operator.
- Spectral analysis: The analysis factors the graph Laplacian as Ln = QΛQT and uses the eigenvalue structure to establish properties for algorithm (7) when 0 < k < 1.
- Lyapunov construction: Nonsmooth Lyapunov functions V ∗ 1 and V ∗ 2 are constructed for convex costs that may have infinitely many critical points or optimal solutions.
- Lyapunov construction: αλmax(Ln), ˙V ∗(x(t), λ(t)) ≤ −k∥˙x(t)∥2 − ˙λT(t)Q˙λ(t) ≤ 0, with Q positive definite, providing nonincreasing Lyapunov behavior.
- Convergence theorem: Theorem 4.1 establishes Lyapunov stability, bounded trajectories, and convergence of every trajectory to an equilibrium of the algorithm.
- Convergence theorem: The limiting equilibrium has the consensus form ¯x = 1n ⊗¯x, where ¯x is an optimal solution of the constrained problem.
- Scope of result: The analysis extends prior smooth-Lyapunov approaches to convex problems with a continuum of optimal solutions.
C. Numerical Simulation
The numerical example illustrates the algorithm on a scalar constrained problem with five agents and nonsmooth local costs. The agents converge to a common feasible optimizer, while auxiliary variables and Lyapunov functions remain bounded or nonincreasing as described.
- Problem setup: The example considers x ∈ R with five local constraint sets Ωi = {x ∈ R : i − 12 ≤ x ≤ i − 2} and nonsmooth local cost functions.
- Problem setup: When set constraints are removed, every point in [0, 6] is an optimal solution, illustrating a continuum of optima.
- Trajectory results: Fig. 1 presents trajectories of the agents’ estimates for x over time.
- Stability diagnostics: Fig. 2 shows trajectories of the auxiliary variables λi and verifies boundedness of the algorithm trajectories.
- Trajectory results: The agents converge to the same optimal solution satisfying all local constraints and minimizing the sum of local cost functions without knowing other agents’ constraints or feasible sets.
- Stability diagnostics: Fig. 3 shows trajectories of the Lyapunov functions V ∗ 1 (x, λ) and V ∗ 2 (x, λ).
V. CONCLUSIONS
The note proposes a distributed projected continuous-time algorithm for nonsmooth convex optimization with local set constraints. Projected differential inclusions and nonsmooth analysis establish convergence with bounded states, including problems having a continuum of optimal solutions, and simulation illustrates the behavior.
- Contribution: The proposed method is a distributed projected continuous-time algorithm for nonsmooth optimization under local set constraints.
- Analysis: Projected differential inclusions and nonsmooth analysis are used to prove convergence while keeping the states bounded.
- Scope: The stability and convergence results for nonsmooth Lyapunov functions show that the algorithm solves convex problems with a continuum of optimal solutions.
- Illustration: Algorithm performance is illustrated through a numerical simulation.
PROOF OF LEMMA 4.4
The proof analyzes trajectories of the projected continuous-time algorithm using convexity, normal-cone properties, and a nonsmooth Lyapunov function. It shows the Lyapunov function is nonnegative and has a nonpositive derivative along trajectories.
- Trajectory dynamics: The algorithm trajectory satisfies projected primal dynamics and dual dynamics given by ˙x(t) = PTΩ(x(t))[−αLx(t) − αLλ(t) − g(x(t))] and ˙λ(t) = αLx(t).The subgradient g(x(t)) is selected from ∂f(x(t)), while NΩ(x(t)) denotes the normal cone of Ω.
- Derivative analysis: Convexity of f and the normal-cone characterization are used to derive inequalities for the Lyapunov derivative along almost every trajectory time.The proof applies subgradient inequalities and projection properties after dividing inequalities by h and taking h → 0.
- Lyapunov construction: The Lyapunov function is shown nonnegative by proving its component terms J1(x, λ), J2(x), and J3(x) are nonnegative.Positive semidefiniteness of L and convexity-related inequalities support these componentwise bounds.
- Matrix properties: The Kronecker-product structure preserves the Laplacian maximum eigenvalue, so λmax(Ln) = λmax(L).The eigenvalues of L = Ln ⊗ Iq are the eigenvalues of Ln repeated across the identity factor.
- Convergence inequality: ˙V ∗(x(t), λ(t)) ≤ −xT(t)[αL − kα2L2]x(t) − k∥˙x(t)∥2 for almost all t ≥ 0.Using Q = Qn ⊗ Iq and ˙λ(t) = αLx(t), the proof further obtains ˙V ∗ ≤ −k∥˙x(t)∥2 − ˙λT(t)Q˙λ(t) ≤ 0.