PaperlayerView exact revision on arXiv

Source-linked AI summary

Passivity-Based Distributed Optimization with Communication Delays Using PI Consensus Algorithm

Takeshi Hatanaka, Nikhil Chopra, Takayuki Ishizaki, Na Li

arXiv:1609.04666v1eess.SYcs.SY

TL;DR

Communication delays can slow or destabilize distributed optimization, motivating a passivity-based treatment. The paper develops a PI-consensus perspective, incorporates delays using scattering transformation, and extends the approach to constrained problems. It reports exact convergence results and applies the algorithm to visual human localization.

  • Problem

    Communication delays in distributed optimization may slow convergence or destabilize solution processes, and their effects have not been fully explored in the cited work.

    Source: §I · p. 1

  • Method

    The paper treats PI-consensus optimization as a feedback connection of passive systems, incorporates delays using scattering transformation, and extends the approach to constrained problems with an added passive feedback loop.

    Source: §I · p. 2, A. Consensus-Based Distributed… · p. 3

  • Results

    The paper proves exact convergence to the optimum for the unconstrained delay treatment and reports extensions to constrained optimization with and without delays.

    Source: §I · p. 2, §VII · p. 13

  • Takeaways & Limitations

    The paper applies its distributed optimization algorithm to visual human localization using pedestrian detection.

    Source: §VII · p. 13

Abstract

from arXiv · show

In this paper, we address a class of distributed optimization problems in the presence of inter-agent communication delays based on passivity. We first focus on unconstrained distributed optimization and provide a passivity-based perspective for distributed optimization algorithms. This perspective allows us to handle communication delays while using scattering transformation. Moreover, we extend the results to constrained distributed optimization, where it is shown that the problem is solved by just adding one more feedback loop of a passive system to the solution of the unconstrained ones. We also show that delays can be incorporated in the same way as the unconstrained problems. Finally, the algorithm is applied to a visual human localization problem using a pedestrian detection algorithm.

I. INTRODUCTION

The introduction frames communication delays as a threat to distributed optimization and presents passivity as a basis for handling them. It outlines a PI-consensus approach, extensions to constrained problems, and an application to visual human localization.

I. INTRODUCTION

  • Communication delays in distributed optimization may slow convergence or destabilize solution processes, a problem not fully explored in prior work –.The introduction distinguishes this problem setting from resource-allocation work and notes that comparison with delay-focused studies –[33] is difficult because their settings differ.Source: §I · pp. 1–2
  • The paper presents a passivity-based perspective in which PI-consensus optimization is a feedback connection of passive systems.This framing is intended to bring established passivity-based control methods to the algorithm.Source: §I · pp. 1–2
  • Scattering transformation integrates communication delays into the passivity-based distributed algorithm, and the paper proves exact convergence to the optimum.The introduction also extends the delay treatment to constrained optimization using the same procedure as for the unconstrained case.Source: §I · p. 2
  • For constrained optimization, adding a feedback loop for the Lagrange-multiplier update yields exact convergence without barrier-function gain tuning.The paper contrasts this with, which it says converges only approximately with nonlinear inequality constraints because it uses barrier functions.Source: §I · p. 2
  • The algorithm is applied to visual human localization using a pedestrian detection algorithm.The introduction also situates passivity in applications including physical systems and networked control –.Source: §I · pp. 1–2

II. PRELIMINARY

  • The preliminaries introduce passivity and incremental passivity, and state that a convex function’s gradient is incrementally passive.They also note that passivity is preserved under feedback interconnections, with closed-loop stability requiring additional assumptions.Source: §II · p. 2

III. PASSIVITY-BASED PERSPECTIVE FOR UNCONSTRAINED DISTRIBUTED OPTIMIZATION

The section recasts unconstrained distributed optimization in passivity terms, under convex-cost and connected, undirected-graph assumptions. It identifies a mismatch in ordinary consensus-gradient feedback and introduces PI consensus dynamics that are passive from u to x.

III. PASSIVITY-BASED PERSPECTIVE FOR UNCONSTRAINED DISTRIBUTED OPTIMIZATION

  • The optimization setup uses private, convex, continuously differentiable agent costs and assumes an undirected, connected communication graph.The costs have locally Lipschitz gradients, and the optimal solution set is assumed nonempty with finite minimum value.Source: §III · pp. 2–3, A. Consensus-Based Distributed… · p. 3

A. Consensus-Based Distributed Optimization

  • Ordinary consensus-gradient feedback combines a passive network system with an incrementally passive gradient block, but input-output mismatch prevents convergence to the goal state.At the candidate consensus state, individual agent gradients need not vanish even though their sum is zero.Source: A. Consensus-Based Distributed… · p. 3

B. PI Consensus-Based Distributed Optimization

  • PI consensus adds an integral state for the neighbor-consensus input, making the system passive from u to x.The integral state is paired with the gradient-based feedback law u = −αφ(x).Source: B. PI Consensus-Based Distributed… · pp. 3–4

C. Equilibrium/Convergence Analysis: Unconstrained Case

The unconstrained PI consensus system has an equilibrium associated with an optimal solution, and under the stated assumptions each agent’s state converges asymptotically to the optimal-solution set. The paper’s contribution here is a passivity-based interpretation of the algorithm, rather than a new convergence result.

C. Equilibrium/Convergence Analysis: Unconstrained Case

  • An optimizer-consensus state x* has an associated ξ* that makes the pair an equilibrium of the PI consensus system.The equilibrium input is u* = −αφ(x*).Source: C. Equilibrium/Convergence Analysis:… · p. 4
  • Under Assumptions 1 and 2, each agent state asymptotically converges to the set of optimal solutions.The result applies to system (13).Source: C. Equilibrium/Convergence Analysis:… · p. 4
  • The convergence proof uses passivity with incremental inputs and outputs and LaSalle’s invariance principle to show trajectories remain in the optimal-solution set.On trajectories where the storage derivative is zero, consensus and the optimality condition imply f(c(t)) = f(z*).Source: C. Equilibrium/Convergence Analysis:… · p. 4
  • The section’s contribution is a passivity-based perspective on an algorithm and convergence result already presented in.The perspective treats the algorithm as a feedback connection of two passive systems with incremental inputs and outputs.Source: C. Equilibrium/Convergence Analysis:… · p. 4

IV. UNCONSTRAINED DISTRIBUTED OPTIMIZATION WITH COMMUNICATION DELAY

The section models constant, heterogeneous communication delays in the unconstrained PI consensus algorithm and uses passivity to analyze the resulting agent dynamics. Under strict convexity and regularity assumptions, the open-loop agent dynamics and a controller map have passive properties.

IV. UNCONSTRAINED DISTRIBUTED OPTIMIZATION WITH COMMUNICATION DELAY

  • Constant, heterogeneous delays are assumed between communicating agents, and the section begins with strictly convex local objectives with locally Lipschitz gradients.The authors describe this strict-convexity assumption as restrictive and say it will later be relaxed.Source: §IV · p. 4

A. Individual Dynamics as A Feedback System with Passive Dynamics and A Collection of Passive Controllers

B. Scattering Transformation

The communication strategy uses a scattering transformation to exchange controller signals through delayed links while preserving a passivity basis for the synchronization analysis. Agents send transformed signals and recover received signals for their controllers.

B. Scattering Transformation

  • Because the passivity-oriented controller outputs include unavailable optimal-solution biases, agents exchange v_ij signals instead.The section identifies this choice as the motivation for the scattering transformation strategy.Source: B. Scattering Transformation · p. 6
  • The scattering transformation is applied to messages sent between neighbors and is used to passify communication blocks that include delays.The links are modeled with constant delays in each direction.Source: B. Scattering Transformation · p. 6
  • Each agent computes r_ij from the received transformed signal and adds it to its controller, with operation coordinated by agent IDs.The algorithm description notes that the operations differ by agent ordering.Source: B. Scattering Transformation · p. 6
  • The transformed communication system with delay blocks is passive, providing the link-level property used in the convergence analysis.Lemma 5 states passivity from the paired negative v̄ inputs to the paired r̄ outputs.Source: B. Scattering Transformation · p. 6

C. Convergence Analysis

The convergence analysis proves asymptotic convergence to the optimizer for the delayed unconstrained algorithm. It first uses strict convexity across all coordinates, then relaxes that condition to strict convexity only on coordinates used by each local objective.

C. Convergence Analysis

  • Under Assumptions 2 and 3, the system with scattering transformation and delays also converges asymptotically to the optimizer for every agent.Lemma 6 establishes this result under the initial strict-convexity condition.Source: C. Convergence Analysis · p. 7
  • The proof uses LaSalle’s principle for time-delay systems, with the zero-derivative invariant set yielding convergence under the stated assumptions.The analysis notes that strict convexity across every coordinate is strong and may limit applications; it relaxes this to strict convexity on the coordinates each local objective depends on.Source: C. Convergence Analysis · p. 7
  • If Assumptions 2 and 4 hold, then for every agent i = 1, 2, ..., n, xi asymptotically converges to the optimal solution z* to (5).Source: C. Convergence Analysis · p. 7

V. EXTENSION TO CONSTRAINED DISTRIBUTED OPTIMIZATION

The constrained extension formulates distributed optimization with private local objectives and inequality constraints. Its stated setup assumes convexity and regularity, a strictly feasible point, and a strictly convex aggregate objective.

V. EXTENSION TO CONSTRAINED DISTRIBUTED OPTIMIZATION

  • The constrained problem minimizes the aggregate objective over z subject to each agent’s inequality constraints.The functions f_i and g_i are local to agent i and unavailable to the other agents.Source: §V · p. 8
  • The setup assumes convex local objectives and constraints, differentiable constraint functions with locally Lipschitz gradients, and a point strictly satisfying every inequality constraint.The local objectives are assumed twice differentiable.Source: §V · p. 8
  • The aggregate objective is strictly convex, so the stated assumptions make the constrained optimizer unique and characterize it through KKT conditions.The paper states uniqueness and the KKT characterization under Assumptions 5 and 6.Source: §V · p. 8

A. PI Consensus-Based Distributed Optimization for Constrained Problem

The constrained method combines PI consensus optimization with a gradient-based multiplier update for local inequality constraints. The added feedback path uses local variables and private constraint functions.

A. PI Consensus-Based Distributed Optimization for Constrained Problem

  • Each agent can run the multiplier dynamics using its local estimate and private constraint function, without other agents’ constraint functions.The method replaces the optimizer estimate with the agent’s estimate and uses local variables.Source: A. PI Consensus-Based Distributed… · p. 8
  • For a fixed multiplier, each agent runs the PI consensus algorithm with the resulting cost-function definition.The passage describes this as taking the same form as the unconstrained problem, except for the cost functions.Source: A. PI Consensus-Based Distributed… · p. 8
  • An outer feedback path adds a gradient-based Lagrange-multiplier update to the unconstrained PI consensus solution.The resulting architecture is a feedback interconnection of passive systems.Source: A. PI Consensus-Based Distributed… · p. 8

B. Equilibrium/Convergence Analysis: Constrained Case

The constrained dynamics are analyzed as passive systems connected in feedback. Under the stated assumptions, the unconstrained-delay-free constrained system’s agent estimates asymptotically converge to the optimal solution.

B. Equilibrium/Convergence Analysis: Constrained Case

  • Under Assumptions 2, 5, and 6, system (63) is passive from shifted multiplier input μ~ = μ − μ* to shifted output ξ − ξ*, as stated in Lemma 8.Lemma 7 states that (1_n ⊗ z*) and ξ* form an equilibrium pair of (63) for equilibrium input μ* := Γ(x*)λ*, where (z*, λ*) uniquely solves (51)–(53).Source: B. Equilibrium/Convergence Analysis:… · p. 9
  • The inequality-constraint dynamics are passive from the shifted estimate to the shifted multiplier output when the initial multipliers are nonnegative.The proof treats mode switches using an upper Dini derivative.Source: B. Equilibrium/Convergence Analysis:… · p. 9
  • The closed-loop constrained system is formed by interconnecting the two passive systems in feedback.The paper notes that equality-constraint extensions are possible but omits them to reduce complexity.Source: B. Equilibrium/Convergence Analysis:… · p. 10
  • Under Assumptions 2, 5, and 6, every agent’s estimate asymptotically converges to the constrained problem’s optimal solution.The result applies to system (61) and (62).Source: B. Equilibrium/Convergence Analysis:… · p. 10

C. Constrained Distributed Optimization with Delay

The constrained optimization results are extended to delayed communication by replacing each agent’s passive dynamics with constrained dynamics that preserve the input-output passivity property. With scattering transformation, the estimates asymptotically converge to the optimum under the stated assumptions.

C. Constrained Distributed Optimization with Delay

  • The delayed constrained agent system is passive from its input v̄_i to its stacked estimate and auxiliary-state output under Assumptions 2, 4, and 5.Its storage function combines the terms identified in Lemmas 4 and 9.Source: C. Constrained Distributed… · p. 11
  • The constrained agent dynamics replace the earlier passive dynamics while preserving the same input-output pair, allowing the same inter-agent communication strategy.The delayed received neighbor signals are denoted r^x_ij and r^ξ_ij.Source: C. Constrained Distributed… · pp. 10–11
  • With scattering transformation and delays, each agent’s estimate asymptotically converges to the constrained optimum under Assumptions 2, 3, and 5.The theorem applies to the specified systems (76), (77), and (78) for all agents and neighbors.Source: C. Constrained Distributed… · p. 11
  • A second convergence result allows Assumption 4 in place of Assumption 3 when delays are homogeneous, the derived graph is connected, and b_ij is common among each agent’s neighbors.Under Assumptions 4, 5, and 7, all estimates asymptotically converge to the optimum.Source: C. Constrained Distributed… · p. 11

VI. APPLICATION TO HUMAN LOCALIZATION USING PEDESTRIAN DETECTION ALGORITHM

The paper applies its constrained algorithm to estimate a 3-D ellipsoid around a human from detections by five networked cameras. In the simulation, estimates converge without delays, diverge with random delays, and converge when scattering transformation is used.

VI. APPLICATION TO HUMAN LOCALIZATION USING PEDESTRIAN DETECTION ALGORITHM

  • Five cameras use pedestrian detections to define viewing cones, and the optimization estimates an ellipsoid containing the human.The application assumes all five cameras detect the person; the paper refers elsewhere for the case where some cameras do not.Source: §VI · p. 12
  • The local constraints require the ellipsoid to lie within each camera’s viewing cone and its shape matrix to be positive definite.The paper adds a 10^-5∥q∥2 term to the local cost function for preciseness in this simulation.Source: §VI · p. 12
  • With random communication delays in [0,1], the estimates diverge and the simulation stops with errors; scattering transformation stabilizes the system and restores convergence.Without delays, the estimates converge to the optimal solution; with scattering, each camera’s final ellipsoid tightly encloses the human.Source: §VI · p. 12
  • The authors leave the problem of slow convergence for future work.They identify applying the technique in as a possible option.Source: §VI · p. 12

VII. CONCLUSION

The paper extends a passivity-based perspective on PI consensus optimization to inter-agent communication delays and local inequality constraints. It uses scattering transformation to incorporate delays and applies the algorithm to visual human localization.

VII. CONCLUSION

  • The paper extends its passivity-based PI consensus approach to unconstrained and locally inequality-constrained distributed optimization with and without communication delays.Scattering transformation is used to integrate delays while ensuring convergence; the algorithm is also applied to visual human localization.Source: §VII · p. 13
Loading 1609.04666v1…