PaperlayerView exact revision on arXiv

Source-linked AI summary

Tracking-ADMM for Distributed Constraint-Coupled Optimization

Alessandro Falsone, Ivano Notarnicola, Giuseppe Notarstefano, Maria Prandini

arXiv:1907.10860v1math.OCcs.SYeess.SY

TL;DR

The paper studies distributed minimization with local constraints and a common linear coupling constraint. It embeds dynamic tracking in parallel ADMM, proving asymptotic optimality of primal limit points and reporting numerical corroboration.

  • Problem

    The paper addresses minimizing summed local costs under local and common linear constraints in a network where agents communicate only with neighbors.

    Source: §1 · p. 1, §3.1 · p. 3

  • Method

    Tracking-ADMM embeds dynamic average tracking in parallel ADMM so agents track coupling-constraint violation and use it in local dual updates.

    Source: §1 · p. 2, §2.2 · p. 3, §3.2 · p. 4

  • Results

    The proof establishes that primal limit points are optimal and agents asymptotically compute optimal dual solutions; numerical computations corroborate the theoretical results.

    Source: §5 · p. 8

  • Takeaways & Limitations

    Agents asymptotically compute their portion of a primal optimum and obtain a local measure of coupling-constraint violation.

    Source: §5 · p. 8

    The communication graph is assumed not to change across iterations.

    Source: §3.1 · p. 3

Abstract

from arXiv · show

We consider constraint-coupled optimization problems in which agents of a network aim to cooperatively minimize the sum of local objective functions subject to individual constraints and a common linear coupling constraint. We propose a novel optimization algorithm that embeds a dynamic average consensus protocol in the parallel Alternating Direction Method of Multipliers (ADMM) to design a fully distributed scheme for the considered set-up. The dynamic average mechanism allows agents to track the time-varying coupling constraint violation (at the current solution estimates). The tracked version of the constraint violation is then used to update local dual variables in a consensus-based scheme mimicking a parallel ADMM step. Under convexity, we prove that all limit points of the agents' primal solution estimates form an optimal solution of the constraint-coupled (primal) problem. The result is proved by means of a Lyapunov-based analysis simultaneously showing consensus of the dual estimates to a dual optimal solution, convergence of the tracking scheme and asymptotic optimality of primal iterates. A numerical study on optimal charging schedule of plug-in electric vehicles corroborates the theoretical results.

1. Introduction

Distributed optimization addresses the computational and privacy challenges of large interacting systems, but coupling constraints are difficult to handle without a central authority. The paper embeds tracking in parallel ADMM and proves asymptotic optimality for its distributed algorithm.

1. Introduction

  • Large, interacting systems strain a single processing unit, and requiring agents to disclose sensitive information can raise privacy issues.These challenges motivate distributed algorithms for optimal control problems.Source: §1 · p. 1
  • Earlier distributed methods mainly addressed common-decision problems; adapting them to coupling constraints would require each agent to store the full solution estimate and know the global constraint.Direct approaches to constraint-coupled problems typically have slow local-decision convergence, while some alternatives impose narrower cost assumptions or require tuned communication rounds.Source: §1 · p. 2
  • Tracking-ADMM embeds a tracking mechanism in parallel ADMM to solve constraint-coupled problems fully distributed over networks.The method is designed for agents that communicate with neighbors rather than through a central authority.Source: §1 · pp. 1–2
  • The algorithm needs no parameter tuning, computes only each agent’s portion of an optimal feasible solution, and provides a local measure of coupling-constraint infeasibility.That local measure may be useful in distributed receding-horizon control schemes.Source: §1 · p. 2
  • The Lyapunov-based proof establishes exact convergence of dual variables to a dual optimum and optimality of every limit point of the primal sequences.It uses a constrained solution to a discrete Lyapunov equation to derive an aggregate descent condition.Source: §1 · p. 2

2. Constraint-Coupled Optimization

The section formulates a convex constraint-coupled optimization problem and reviews a parallel ADMM solution. The centralized aggregation required by that ADMM motivates the distributed setting developed later.

2.1. Optimization Problem and Assumptions

  • Agents minimize the sum of local costs over local feasible sets, subject to a linear constraint coupling their decision variables.Each coupling contribution is specified by A_i and b, with the contributions summing to b.Source: §2.1 · pp. 2–3
  • The stated regularity conditions require convex local costs and convex compact local sets, alongside existence of primal and dual optimal solutions.These conditions support the convergence result for the parallel ADMM reviewed here.Source: §2.1 · p. 3

2.2. The ADMM Parallel Algorithm

  • Under the stated assumptions, every limit point of the primal sequence is optimal, the dual sequence converges to a dual optimum, and no penalty-parameter requirement is needed.The averaged residual measures infeasibility and converges to zero as primal limit points are feasible.Source: §2.2 · p. 3
  • Parallel ADMM has agents minimize local objectives, then sends their constraint contributions to a central unit to aggregate the residual and update the multiplier.The central unit computes and broadcasts quantities required by the update, making this scheme unsuitable for fully distributed neighbor-only communication.Source: §2.2 · p. 3

3. Tracking-ADMM Distributed Algorithm

Tracking-ADMM combines local optimization, neighbor communication, and dynamic average tracking to solve constraint-coupled problems without a central coordinator. Under Assumptions 1–5, its primal iterates are asymptotically optimal, while the analysis establishes convergence of the tracking and dual-consensus mechanisms.

3.1. Distributed Computation Framework

  • The framework assumes a fixed, undirected, connected communication graph and symmetric, doubly stochastic weights; positive semidefiniteness can be obtained with two update rounds.The two-round construction is equivalent to one round using W^2.Source: §3.1 · pp. 3–4, §3.3.2 · p. 5

3.2. Algorithm Description

  • Tracking-ADMM embeds dynamic average consensus in parallel ADMM, replacing unavailable network-wide coupling-violation and dual quantities with local estimates.Agents use local information and neighbor communications for their updates.Source: §3.2 · p. 4
  • Each local tracker estimates the network-average, time-varying coupling-constraint signal, allowing the algorithm to use the violation in distributed dual updates.The tracker is initialized from each agent's local constraint contribution.Source: §3.2 · p. 4

3.3.1. Aggregate Reformulation of Tracking-ADMM

  • The aggregate reformulation separates the algorithm into a nonlinear optimization update and linear consensus-based tracker and dual updates.This decomposition lets the analysis study the two dynamics separately before combining them.Source: §3.3.1 · p. 5

3.3.2. Discussion on Assumption 5

  • Two consecutive communication rounds with a consensus matrix satisfying Assumption 4 are equivalent to one round with W^2, which satisfies Assumption 5.The resulting graph connects agents linked by a two-edge path in the original graph.Source: §3.3.2 · p. 5

3.3.3. Network Average Quantities; 3.3.4. Consensus Errors as Linear Dynamical Systems

  • The network averages of tracker and dual variables evolve like parallel ADMM, while the local quantities remain near those averages as consensus errors decay.The consensus-error dynamics are asymptotically stable under the stated assumptions.Source: §3.3.3 · p. 5, §3.3.4 · p. 6

3.3.5. Optimality Characterization; 3.3.6. Tracking-ADMM Convergence

  • The convergence proof combines a Lyapunov function for the consensus system with the local optimality inequality to offset terms of indeterminate sign.The local optimality inequality alone is insufficient because its additional cross term depends on dual consensus error.Source: §3.3.5 · pp. 6–7, §3.3.6 · p. 7

3.3.6. Tracking-ADMM Convergence

  • The primal iterates are asymptotically optimal, and the convergence results establish dual optimality without restricting the constant penalty parameter.The algorithm works with convex, not necessarily strictly convex, primal costs and needs no primal recovery procedure.Source: §3.3.6 · p. 7

4. Numerical Study

The study evaluates Tracking-ADMM on a modified plug-in electric-vehicle charging problem and reports convergence to feasibility and optimality without a recovery procedure.

4. Numerical Study

  • The model minimizes total charging cost subject to vehicle-level constraints and a grid power limit; slack variables convert its inequality coupling constraint into an equality.The local constraint sets are bounded polyhedral sets.Source: §4 · p. 7
  • In the simulation, N = 100 vehicles each had 24 decision variables and 24 slack variables (48 total), with 24 coupling constraints and 245 local inequalities.Tracking-ADMM ran for 200 iterations, initialized as suggested in Section 3.2, with c = 10^-4.Source: §4 · p. 8
  • Tracking-ADMM reaches feasibility and optimality, with primal iterates satisfying the coupling constraint without a recovery procedure.Figure 1 tracks the cost gap and joint-constraint violation across iterations.Source: §4 · p. 8
  • Local multiplier estimates reach consensus and optimality relative to the optimal dual solution.Figure 2 plots their evolution across iterations, with the optimal dual solution marked by red triangles.Source: §4 · p. 8

5. Conclusions

The paper concludes that Tracking-ADMM combines parallel ADMM with dynamic tracking for distributed constraint-coupled optimization. Its analysis establishes optimality properties, and numerical computations corroborate the theory.

5. Conclusions

  • Tracking-ADMM combines parallel ADMM with dynamic tracking for convex problems with individual constraints and a common linear coupling constraint.The method asymptotically computes an optimal dual solution and each agent’s portion of an optimal primal solution.Source: §5 · p. 8
  • The tracking scheme gives agents a local measure of coupling-constraint violation, and numerical computations corroborate the theoretical results.Source: §5 · p. 8
  • Figure 1 plots cost difference from the optimal cost and maximum joint-constraint violation across iterations.Source: Figure 1 · p. 8
  • Figure 2 plots Lagrange multipliers across iterations, marking the optimal dual solution with red triangles.Source: Figure 2 · p. 8

Proof of Lemma 1

The proof establishes the stated relation by induction, using the initialization for the base case and an algebraic inductive step.

Proof of Lemma 1

  • The proof uses induction, with the initialization establishing the base case k = 0.Source: Proof of Lemma 1 · p. 9
  • Assuming (8) holds through k, the proof aims to establish it at k + 1 to complete the induction.Source: Proof of Lemma 1 · p. 9
  • The inductive algebra uses Steps 9 and 6, exchanges summations, and applies column stochasticity, the definition of average d, and the induction hypothesis.Source: Proof of Lemma 1 · p. 10

Proof of Lemma 2

The proof continues by elaborating an expression and justifying the algebra of the multiplier update.

Proof of Lemma 2

Proof of Lemma 3

The proof establishes boundedness of the primal iterates, the average constraint-violation estimate, and the auxiliary sequence. Input-to-state stability then gives boundedness of the tracking-error sequences.

Proof of Lemma 3

  • The primal iterates x_k are bounded because they remain in bounded X under Assumption 1.The proof also establishes boundedness of the average constraint-violation estimate and z_k.Source: Proof of Lemma 3 · p. 10
  • Under Assumption 4, the average constraint-violation estimate is bounded, which also makes z_k bounded.The proof uses the relation between z_k, A_d x_k, and the average estimate.Source: Proof of Lemma 3 · p. 10
  • Input-to-state stability of the systems in (12) and (13), with Assumptions 3 and 4, yields bounded tracking-error sequences.The argument first uses bounded increments of z_k to establish boundedness for the first tracking error.Source: Proof of Lemma 3 · p. 10

Proof of Proposition 1

The proof applies a saddle-point inequality and the algorithm’s update relations at an optimal primal solution. Algebraic rearrangement yields inequality (A.5), which is identified with Proposition 1’s inequality (14).

Proof of Proposition 1

  • Applying [17, Lemma 4.1] to (6a) gives an inequality for x_{k+1}, which the proof combines with the algorithm’s update relations.The updates cited are d_{k+1}=Wd_k+A_d x_{k+1}−A_d x_k and λ_{k+1}=Wλ_k+c d_{k+1}.Source: Proof of Proposition 1 · p. 10
  • The saddle-point theorem supplies an inequality for all x in X and λ, which the proof specializes using an optimal primal solution.The subsequent argument sets b=A x⋆ and uses the relation between A and A_d.Source: Proof of Proposition 1 · p. 10
  • Using (A.3) and (A.4) in (A.2) and multiplying by 2c gives (A.5): 2[¯λk+1 − λ⋆]⊤[¯λk+1 − ¯λk] + 2c[λk+1 − ¯λk+1]⊤[zk+1 − Adx⋆] ≤ 0.Source: Proof of Proposition 1 · p. 11

Proof of Theorem 1

The proof constructs a Lyapunov condition for the algorithm’s dynamical system and uses it to establish vanishing tracking errors and constraint-violation estimates. It also proves convergence of the associated dual and auxiliary sequences.

Proof of Theorem 1

  • The tracking-system states are arranged as a dynamical system whose stability is certified by the constructed Lyapunov condition.The proof partitions P into blocks and uses the spectral properties of the mixing matrix to satisfy the matrix conditions.Source: Proof of Theorem 1 · p. 11
  • The Lyapunov argument chooses P so that P−FᵀPF is positive definite, making the resulting condition non-expansive for the algorithm’s state sequence.The proof selects P_1=2I and verifies the required matrix condition using Assumption 5.Source: Proof of Theorem 1 · pp. 11–12
  • The Lyapunov analysis establishes that the average dual estimate’s increments and the tracking error e_k vanish asymptotically.The proof derives this from a summed inequality and positive definiteness of Q.Source: Proof of Theorem 1 · p. 12
  • The cited passage establishes that the norm of the average dual increment ¯d_k converges to zero, identifying this result as proving point (iii).Source: Proof of Theorem 1 · p. 12
  • The proof shows that the sequence combining distance to an optimal dual solution and a weighted auxiliary-state term converges.It uses boundedness and norm equivalence to establish convergence of the component sequence.Source: Proof of Theorem 1 · p. 12

Proof of Theorem 2

The proof establishes that every limit point of the primal iterates is feasible and achieves the optimal objective value. It also shows that the dual estimates converge to an optimal dual solution and that local dual estimates agree asymptotically.

Proof of Theorem 2

  • Every limit point of x_k is feasible for P and attains the optimal objective value, so it is a primal optimal solution.The proof combines feasibility with the established bound on the objective value.Source: Proof of Theorem 2 · p. 13
  • A convergent subsequence of average dual estimates has a limit that is optimal for the dual problem D.The proof derives this using the limiting inequality and weak duality.Source: Proof of Theorem 2 · pp. 13–14
  • The local dual estimates approach the average dual estimate, so their disagreement vanishes.The proof uses vanishing dual tracking error to obtain this result.Source: Proof of Theorem 2 · pp. 13–14
  • The convergent primal-dual sequence has a primal optimal and dual optimal limit pair, yielding the stated limiting relation for the iterates.The proof applies Theorem 1(iv) to that pair.Source: Proof of Theorem 2 · p. 14
Loading 1907.10860v1…