PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Convex Optimization for Continuous-Time Dynamics with Time-Varying Cost Function

Salar Rahili, Wei Ren

arXiv:1507.04878v2math.OC

TL;DR

The paper studies distributed minimization of time-varying team costs when each agent knows only its local cost and follows continuous-time single- or double-integrator dynamics. It proposes discontinuous signum-based controllers, continuous boundary-layer approximations for double-integrator systems, and swarm-tracking formulations; simulations show optimization or trajectory tracking alongside consensus, connectivity, and collision avoidance.

  • Problem

    The paper addresses distributed convex optimization with time-varying local costs, continuous-time dynamics, and swarm behavior rather than convergence only to a common optimal point.

  • Method

    It designs discontinuous signum-based algorithms for single- and double-integrator agents, continuous time-varying and fixed boundary-layer approximations for double-integrator systems, and swarm-tracking controllers.

  • Results

    Simulations show agents tracking the optimal trajectory with bounded error, while swarm-tracking cases maintain connectivity and avoid collisions.

  • Takeaways & Limitations

    The framework combines distributed optimization with continuous-time motion coordination and swarm tracking using local information and interaction.

Abstract

from arXiv · show

In this paper, a time-varying distributed convex optimization problem is studied for continuous-time multi-agent systems. Control algorithms are designed for the cases of single-integrator and double-integrator dynamics. Two discontinuous algorithms based on the signum function are proposed to solve the problem in each case. Then in the case of double-integrator dynamics, two continuous algorithms based on, respectively, a time-varying and a fixed boundary layer are proposed as continuous approximations of the signum function. Also, to account for inter-agent collision for physical agents, a distributed convex optimization problem with swarm tracking behavior is introduced for both single-integrator and double-integrator dynamics.

I. INTRODUCTION

The paper addresses distributed convex optimization for continuous-time multi-agent systems when local costs vary over time and agents may require single- or double-integrator dynamics. It also introduces swarm tracking with collision avoidance and connectivity maintenance as an optimization objective.

  • Distributed optimization minimizes the sum of local cost functions, with each local function known only to its corresponding agent.
  • Prior distributed optimization methods were primarily discrete-time, motivating continuous-time algorithms for motion coordination.
  • Time-varying local costs transform the objective from finding a fixed optimum into tracking an optimal trajectory, while prior work established bounded errors in such settings.
  • Swarm tracking extends optimization beyond convergence to a common point by requiring coordinated motion, connectivity maintenance, and inter-agent collision avoidance.
  • The proposed framework supports motion coordination while optimizing a time-varying team objective using only local information and interaction.
  • The paper targets four challenges: time-varying costs, local-information implementation, single- and double-integrator dynamics, and signum-based compensation for inconsistent internal time-varying effects.

B. Distributed Time-Varying Convex Optimization Using Neighbors’ Positions

For single-integrator agents, the paper combines local sensing, consensus, and optimization to track the time-varying optimum. Under connectivity and stated regularity conditions, the discontinuous controller achieves consensus and team-cost minimization, while an estimator-based variant relaxes identical-Hessian assumptions.

  • Agents use only their own positions and neighbors’ relative positions, which can be obtained through local sensing without communication.
  • The controller deforms the task into coupled consensus and team-cost minimization, using a local internal signal and signum-based interaction.
  • Under a connected graph and bounded differences in the internal signals, the agents reach consensus asymptotically.
  • With identical Hessians and the stated assumptions, the distributed algorithm achieves the optimization goal and minimizes the convex team cost along the common trajectory.
  • An estimator-based algorithm relaxes the identical-Hessian assumption but requires communication between neighboring agents.

C. Estimator-Based Distributed Time-Varying Convex Optimization

The estimator-based algorithm lets agents generate a shared signal for the centralized optimization condition using distributed average tracking, then track it while reaching consensus. Under connectivity and boundedness assumptions, the time-varying team optimization goal is achieved.

  • Algorithm: Distributed average tracking generates each agent’s estimate of the centralized optimization signal, while a controller guarantees consensus.The estimator and controller form separate parts, enabling a finite-time estimator convergence argument before consensus analysis.
  • Algorithm: The proposed algorithm consists of estimator dynamics and a controller using local internal states, neighbor information, and projected positive-definite matrix estimates.Projection keeps the matrix estimate nonsingular, while the estimator states are initialized subject to specified conditions.
  • Guarantee: Under graph connectivity, Assumptions 3.1, 3.2, and 3.12, and the required initial condition, the algorithm achieves the optimization goal.The coefficient conditions require bounds on relevant time derivatives of Hessians and gradients.
  • Guarantee: After finite-time estimator convergence, all agents generate the same internal signal, and subsequent consensus yields the optimization objective.The proof establishes shared signals, position consensus, and motion along the optimization direction before invoking the centralized condition.
  • Assumptions: For quadratic time-varying costs, the required boundedness conditions reduce to boundedness of g_i(t), its first derivative, and its second derivative.The framework includes functions such as sin(t), e^-tcos(t), 1/(1+t), and tanh(t).

IV. TIME-VARYING CONVEX OPTIMIZATION FOR DOUBLE-INTEGRATOR DYNAMICS

The double-integrator formulation addresses time-varying convex optimization when agents’ inertia matters, requiring both positions and velocities to be coordinated while only acceleration is directly controlled.

  • Problem setting: Double-integrator dynamics provide a more realistic model for some vehicles because they account for inertia.In this setting, both agent positions and velocities must be determined appropriately to minimize the team cost, while control acts directly on acceleration.

A. Centralized Time-Varying Convex Optimization

This section develops centralized and distributed approaches for time-varying convex optimization with double-integrator agents. The distributed position- and velocity-based algorithm reaches consensus and minimizes the team cost under connectivity, gain, boundedness, and Hessian-structure assumptions.

  • A. Centralized Time-Varying Convex Optimization: The centralized double-integrator problem controls acceleration so that position converges to the time-varying minimizer of the cost function.The result follows from a Lyapunov argument and convergence of the cost gradient to zero.
  • Problem formulation: The distributed formulation uses double-integrator dynamics, with each agent’s position derivative equal to velocity and velocity derivative equal to control input.The optimization objective is distributed because the centralized minimization condition depends on all local cost functions.
  • B. Distributed Time-Varying Convex Optimization Using Neighbors’ Positions and Velocities: The adaptive-gain distributed controller uses each agent’s position and relative position and velocity information from neighbors.The controller is designed for agents that do not require neighbors’ absolute states.
  • B. Distributed Time-Varying Convex Optimization Using Neighbors’ Positions and Velocities: The position- and velocity-based controller reaches consensus when the graph is connected, Assumption 4.2 holds, and γ/(αζ) < λ2[L].The proof establishes convergence of both position and velocity consensus errors using a Lyapunov function and Barbalat’s Lemma.
  • B. Distributed Time-Varying Convex Optimization Using Neighbors’ Positions and Velocities: Under identical Hessians, connectivity, Assumptions 3.1, 3.3, and 4.2, and γ/(αζ) < λ2[L], the distributed algorithm achieves the optimization goal.The result combines consensus with convergence of the summed gradients, yielding minimization of the team cost.
  • B. Distributed Time-Varying Convex Optimization Using Neighbors’ Positions and Velocities: The identical-Hessian requirement can be relaxed to a common Hessian structure with additional boundedness assumptions, while estimator-based methods handle nonidentical Hessians.The relaxation still requires bounded gradients and specified derivative-related terms.

C. Estimator-Based Distributed Time-Varying Convex Optimization

For double-integrator agents, the estimator-based algorithm distributes the centralized optimization calculation through average tracking and then controls agents to track the shared estimate while reaching consensus. Under connectivity and stated assumptions, it achieves the optimization goal.

  • Algorithm: Each agent uses distributed average tracking to estimate the centralized optimization signal and a control input to track that estimate while reaching consensus.The estimator and controller jointly implement the distributed solution for double-integrator dynamics.
  • Algorithm: The estimator uses distributed variables and positive coefficients satisfying κ > sup_t ||ψ_i||∞ and ρ > sup_t ||θ_i||∞.A projection can maintain nonsingularity of the matrix estimate used by the estimator.
  • Guarantee: After finite-time estimator convergence, all agents share the estimated signal; later, their positions and velocities reach consensus and the optimization objective follows.The proof connects common internal signals and consensus dynamics to the centralized optimization condition.
  • Comparison: Unlike the neighbor-sensing algorithm, the estimator-based method does not require identical Hessians but requires communication of two variables with neighbors.This trades the restrictive Hessian condition for additional communication and estimator assumptions.

D. Distributed Time-Varying Convex Optimization Using Time-Varying Approximation of Signum Function

This section introduces a continuous double-integrator controller using a time-varying boundary-layer approximation of the signum function. Under stated assumptions, the algorithm achieves distributed optimization and consensus.

  • Time-varying approximation: The controller replaces the discontinuous signum function with a continuous approximation whose boundary layer εe^-ct shrinks over time.As t →∞, the approximation approaches the signum function; agents use positions, velocities, and relative neighbor states.
  • Algorithm: The time-varying approximation preserves the signum-based analysis needed to compensate for inconsistent internal time-varying optimization signals.Replacing signum with a continuous approximation removes the direct validity of the discontinuous-case results unless the approximation converges appropriately.
  • Algorithm: The adaptive-gain control algorithm is proposed for double-integrator dynamics under connectivity and parameter conditions.The gains include positive coefficients μ, α, γ, ζ and varying neighbor gains βij.
  • Guarantees: Under the theorem’s assumptions, the agents reach consensus and the optimization goal is achieved asymptotically.The proof establishes positive definiteness of the Lyapunov function and convergence of the summed gradients before invoking convexity.
  • Guarantees: Increasing the parameter ψ accelerates consensus, although its selection affects convergence speed and must satisfy the stated inequalities.The paper gives sufficient gain conditions involving the graph’s algebraic connectivity and controller parameters.

E. Distributed Time-Varying Convex Optimization Using Time-Invariant Approximation of Signum Function

This section replaces signum with a fixed boundary-layer approximation for double-integrator dynamics. The resulting controller is easier to implement but provides bounded tracking and optimization error under a restricted cost-function class.

  • Fixed approximation: The fixed approximation uses a constant boundary layer ε instead of the time-varying boundary layer.This choice is presented as a continuous approximation of signum for the double-integrator controller.
  • Assumptions: The controller’s analysis assumes gradients of the form ∇f_i(x_i,t) = σx_i + g_i(t), with σ positive and g_i(t) time varying.The theorem also requires the graph, optimization, and regularity assumptions and the stated gain conditions.
  • Guarantees: Agents track the optimal trajectory with bounded position and velocity errors rather than exact consensus.The proof separately bounds consensus errors and the errors between agent states and the optimal trajectory.
  • Guarantees: The summed gradients converge asymptotically to zero, supporting convergence toward the optimal trajectory under the stated assumptions.The analysis establishes this property regardless of whether exact consensus is reached.
  • Trade-offs: The fixed approximation simplifies implementation but does not exactly minimize the team cost and restricts admissible cost functions.The global optimal trajectory is not an equilibrium of the closed-loop system with a time-invariant continuous approximation.

V. DISTRIBUTED TIME-VARYING CONVEX OPTIMIZATION WITH SWARM TRACKING BEHAVIOR

The paper introduces distributed optimization with swarm tracking behavior for both single- and double-integrator agents. The swarm center tracks the optimal trajectory while agents avoid collisions and maintain connectivity.

  • Swarm tracking: Two distributed algorithms make the agents’ center track the optimal trajectory while preserving connectivity and avoiding inter-agent collisions.The framework covers both single-integrator and double-integrator dynamics.

A. Distributed Convex Optimization with Swarm Tracking behavior for Single-Integrator Dynamics

This section develops a single-integrator swarm-tracking algorithm using pairwise potential functions and local relative-position information. Under the stated gain and cost assumptions, the swarm center tracks the optimizer while connectivity and collision avoidance are maintained.

  • Algorithm: Each agent uses its own position and relative neighbor positions, with a pairwise potential function incorporated into the control input.Neighbors are defined through a communication or sensing radius R.
  • Potential function: The potential function has a unique minimum at the desired inter-agent distance and diverges as agents collide or existing links approach the sensing radius.These properties encode formation spacing, collision avoidance, and preservation of initially existing connectivity.
  • Guarantees: If the initial graph is connected and β exceeds the bound on φ_i, the control law guarantees connectivity maintenance and collision avoidance.Bounded potential values imply that inter-agent distances cannot reach collision or link-loss conditions.
  • Optimization: The swarm center tracks the team cost-function minimizer under gradients of the form ∇f_i(x_i,t) = σx_i + g_i(t).The proof uses asymptotic convergence of the summed gradients and the optimality condition for the team cost.
  • Assumptions: A constant β can be selected when g_i(t) and its time derivative remain bounded.The paper states that this gain can be determined at t = 0 using initial states and bounds on these functions.

B. Distributed Convex Optimization with Swarm Tracking Behavior for Double-Integrator Dynamics

For double-integrator agents, the proposed distributed algorithm combines time-varying optimization with swarm tracking using local state and neighbor information. Under stated connectivity, gradient, and gain conditions, the agents track the optimal trajectory while preserving connectivity and avoiding collisions.

  • Algorithm: The algorithm uses each agent’s position and the relative positions and velocities of its neighbors.It is designed for distributed time-varying optimization with swarm tracking behavior under double-integrator dynamics.
  • Guarantees: If the graph and regularity assumptions hold and β exceeds the stated spectral bound, the center of the agents tracks the optimal trajectory and their velocities track the optimal velocity.The theorem also includes connectivity maintenance and collision avoidance.
  • Stability analysis: The analysis models the closed-loop system using position and velocity consensus errors.The error dynamics are then used to construct and analyze a positive semidefinite Lyapunov function candidate.
  • Guarantees: The Lyapunov analysis establishes bounded pairwise potential terms and square-integrable velocity errors, leading to asymptotic velocity consensus.Barbalat’s Lemma is used to conclude that the agents’ velocities converge to consensus.
  • Swarm safety: Bounded pairwise potential terms guarantee that inter-agent collisions are avoided and connectivity is maintained.These properties hold alongside the asymptotic velocity-consensus result.
  • Scope: For non-convex cost functions, the proposed algorithms guarantee convergence only to a local optimal trajectory of the team cost function.This extends applicability beyond convex functions but weakens the optimality guarantee.

VI. SIMULATION AND DISCUSSION

Simulations illustrate the proposed algorithms across single-integrator and double-integrator systems, including continuous approximations and swarm tracking. The agents reach consensus or track the optimal trajectory while minimizing the team cost, with bounded error in the fixed-boundary-layer case.

  • Single-integrator dynamics: Six agents on an undirected ring reach consensus and track the circular optimal trajectory under algorithm (9).The optimal trajectory has center at the origin and radius 2.
  • Double-integrator dynamics: Under algorithm (29), double-integrator agents reach consensus and minimize the team cost for local cost functions (69).The result is illustrated in Fig. 2.
  • Continuous approximations: Algorithm (38)-(41) is illustrated for local cost functions with nonidentical Hessians, whose optimal trajectory is circular with radius 1.64.The example uses local Hessians H_i(x_i,t)=2i^2I_2.
  • Continuous approximations: The invariant approximation using algorithms (48) and (59) makes agents track the optimal trajectory with a bounded error.The coefficients are μ=5, α=10, γ=5, ζ=5, ϵ=2.
  • Swarm tracking: The swarm-tracking algorithm makes the agents’ position center follow the optimal trajectory while maintaining connectivity and avoiding collisions.The example uses R=5 and β=20.
  • Discussion: The paper concludes that its algorithms address time-varying distributed optimization for continuous-time single-integrator and double-integrator dynamics.The simulations provide illustrations of the theoretical results.

APPENDIX A

The appendix explains how boundedness assumptions used in the main theorems can be guaranteed from bounded cost-function terms and agent initial states. It uses conservative bounds and contradiction arguments to preserve bounded relative states and connectivity.

  • Assumption 4.2: A finite bound φ̄ can be determined at t=0 so algorithm (29) keeps relative positions and velocities bounded for all t≥0.The construction uses conservative bounds β_x and β_v derived from initial states.
  • Assumption 4.2: Under Condition (⋆), bounded relative positions and velocities imply bounded gradient differences, satisfying Assumption 4.2.The appendix treats cost functions with identical Hessians.
  • Assumption 4.2: The contradiction argument rules out any time when the Lyapunov derivative becomes positive, proving uniform bounds on relative positions and velocities.Continuity of the agents’ states supplies the contradiction at a boundary crossing.
  • Assumption 3.8: For identical-Hessian costs f_i(x_i,t)=(ax_i+g_i(t))^2, bounded g_i(t) and ġ_i(t) are sufficient for Assumption 3.8.The same condition also supports the corresponding bounded gradient terms.
  • Theorem 5.2: For Theorem 5.2, bounded g_i and ġ_i guarantee a constant β exceeding each φ_i norm, with β computable from initial states and upper bounds.The appendix again establishes the required bound through a Lyapunov contradiction argument.
Loading 1507.04878v2…