pith. sign in

arxiv: 1907.10860 · v1 · pith:CGABBORDnew · submitted 2019-07-25 · 🧮 math.OC · cs.SY· eess.SY

Tracking-ADMM for Distributed Constraint-Coupled Optimization

Alessandro Falsone , Ivano Notarnicola , Giuseppe Notarstefano , Maria Prandini This is my paper

Pith reviewed 2026-05-24 16:29 UTC · model grok-4.3

classification 🧮 math.OC cs.SYeess.SY
keywords distributed optimizationADMMdynamic average consensusconstraint-coupled problemsLyapunov analysismulti-agent coordination
0
0 comments X

The pith

Embedding dynamic consensus tracking into parallel ADMM lets networked agents solve shared-constraint optimization problems in a fully distributed manner.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a distributed algorithm for agents to minimize the sum of local objective functions subject to individual constraints and one common linear coupling constraint. It embeds a dynamic average consensus protocol so that each agent can track the current total violation of the shared constraint using only neighbor exchanges. The tracked violation is then used in local dual updates that replicate the steps of centralized parallel ADMM. Under convexity, a Lyapunov argument shows that the primal solution estimates converge to an optimal point while dual variables reach consensus on a dual optimum and the tracking error vanishes. The result is illustrated on the optimal charging schedule of plug-in electric vehicles.

Core claim

Under convexity, all limit points of the agents' primal solution estimates form an optimal solution of the constraint-coupled problem. The proof proceeds by Lyapunov analysis that simultaneously establishes consensus of the dual estimates to a dual optimal solution, convergence of the tracking scheme, and asymptotic optimality of the primal iterates.

What carries the argument

Dynamic average consensus protocol that tracks the time-varying aggregate coupling-constraint violation, enabling each agent to perform a local dual update that mimics the centralized parallel ADMM step.

If this is right

  • All limit points of the primal iterates are optimal for the original problem.
  • Dual estimates reach consensus at a dual optimal solution.
  • The tracking error on the constraint violation converges to zero.
  • The scheme applies directly to coordination problems such as plug-in electric vehicle charging schedules.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the tracking error remains bounded under mild communication imperfections, the method could tolerate packet losses or delays.
  • The same tracking idea might be grafted onto other first-order distributed methods that require global sums.
  • Asynchronous or directed-graph versions would require only a modified consensus protocol while preserving the Lyapunov structure.

Load-bearing premise

The dynamic average consensus protocol can accurately track the time-varying coupling-constraint violation generated by the evolving primal iterates.

What would settle it

Run the algorithm on a small convex test problem whose optimal value is known exactly and check whether every agent's primal estimate converges to that known optimum.

Figures

Figures reproduced from arXiv: 1907.10860 by Alessandro Falsone, Giuseppe Notarstefano, Ivano Notarnicola, Maria Prandini.

Figure 1
Figure 1. Figure 1: Difference between the cost achieved by the primal tenta [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Evolution of Lagrange multipliers across iterations. Red [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proposes Tracking-ADMM, a fully distributed algorithm for constraint-coupled convex optimization over networks. It embeds a dynamic average consensus protocol into parallel ADMM so that each agent tracks the time-varying aggregate constraint violation generated by the evolving primal iterates and uses the tracked quantity to perform a local dual update that mimics the centralized parallel ADMM step. Under convexity, a Lyapunov argument is claimed to establish simultaneously (i) consensus of the dual estimates to a dual optimum, (ii) convergence of the tracking scheme, and (iii) that every limit point of the primal iterates is a primal optimum. The theoretical claims are illustrated by a numerical study on optimal charging schedules for plug-in electric vehicles.

Significance. If the Lyapunov analysis is rigorous, the result supplies a practical, fully distributed method for a class of problems that arise in smart-grid, sensor-network, and multi-agent coordination settings. The simultaneous treatment of tracking, dual consensus, and primal optimality within a single Lyapunov function is a technical strength, as is the absence of free parameters or ad-hoc tuning in the stated convergence statement. The numerical example on EV charging provides concrete corroboration of the claimed behavior.

minor comments (3)
  1. [Abstract / Problem statement] The abstract states that the result holds “under convexity” but does not list the precise standing assumptions on the communication graph (connectedness, undirectedness, or time-invariance). These conditions are load-bearing for the dynamic-average-consensus tracking property and should be stated explicitly in the problem formulation section.
  2. [Numerical study] The numerical study reports convergence behavior but does not specify the network size, the exact communication topology used, or any quantitative comparison against existing distributed ADMM variants. Adding these details would make the experimental validation more informative.
  3. [Algorithm description] Notation for the tracked constraint violation and the local dual variables should be introduced with a single consistent symbol table or list of definitions before the algorithm is presented.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The referee's description accurately captures the Tracking-ADMM algorithm, its embedding of dynamic average consensus, and the Lyapunov-based convergence claims.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces a distributed Tracking-ADMM algorithm that embeds dynamic average consensus into parallel ADMM for constraint-coupled problems. The central result is a Lyapunov-based convergence proof under convexity that simultaneously establishes dual consensus, tracking convergence, and primal optimality. No self-citations, fitted parameters renamed as predictions, self-definitional reductions, or ansatzes smuggled via prior work appear in the derivation chain as described. The proof is presented as an independent technical argument relying on standard Lyapunov techniques and the algorithm's explicit construction, rendering the derivation self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The convergence claim rests on the domain assumption of convexity of the local objectives and on the unstated but load-bearing property that the dynamic average consensus tracker converges for the particular time-varying signal produced by the ADMM iterates.

axioms (1)
  • domain assumption Local objective functions are convex
    Explicitly stated as the condition under which the Lyapunov proof holds.

pith-pipeline@v0.9.0 · 5722 in / 1281 out tokens · 23078 ms · 2026-05-24T16:29:48.840152+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 1 internal anchor

  1. [1]

    Johansson, T

    B. Johansson, T. Keviczky, M. Johansson, K. H. Johansson, Subgradient methods and consensus algorithms for solving con- vex optimization problems, in: IEEE Conference on Decision and Control (CDC), 2008, pp. 4185–4190

    work page 2008

  2. [2]

    Nedi´ c, A

    A. Nedi´ c, A. Ozdaglar, Distributed subgradient methods for multi-agent optimization, IEEE Trans. on Automatic Control 54 (1) (2009) 48–61

    work page 2009

  3. [3]

    Nedi´ c, A

    A. Nedi´ c, A. Ozdaglar, P. A. Parrilo, Constrained consensus and optimization in multi-agent networks, IEEE Trans. on Au- tomatic Control 55 (4)

    work page

  4. [4]

    Zanella, D

    F. Zanella, D. Varagnolo, A. Cenedese, G. Pillonetto, L. Schen- ato, Newton-Raphson consensus for distributed convex opti- mization, in: IEEE Conference on Decision and Control and Eu- ropean Control Conference (CDC-ECC), 2011, pp. 5917–5922

    work page 2011

  5. [5]

    Jakoveti´ c, J

    D. Jakoveti´ c, J. Xavier, J. M. Moura, Fast distributed gradi- ent methods, IEEE Transactions on Automatic Control 59 (5) (2014) 1131–1146. 8

    work page 2014

  6. [6]

    W. Shi, Q. Ling, G. Wu, W. Yin, Extra: An exact first-order algorithm for decentralized consensus optimization, SIAM Jour- nal on Optimization 25 (2) (2015) 944–966

    work page 2015

  7. [7]

    Nedi´ c, A

    A. Nedi´ c, A. Olshevsky, Distributed optimization over time- varying directed graphs, IEEE Transactions on Automatic Con- trol 60 (3) (2015) 601–615

    work page 2015

  8. [8]

    Margellos, A

    K. Margellos, A. Falsone, S. Garatti, M. Prandini, Distributed constrained optimization and consensus in uncertain networks via proximal minimization, IEEE Transactions on Automatic Control 63 (5) (2018) 1372–1387

    work page 2018

  9. [9]

    J. C. Duchi, A. Agarwal, M. J. Wainwright, Dual averaging for distributed optimization: Convergence analysis and network scaling, IEEE Trans. on Autom. Control 57 (3) (2012) 592–606

    work page 2012

  10. [10]

    M. Zhu, S. Mart´ ınez, On distributed convex optimization un- der inequality and equality constraints, IEEE Transactions on Automatic Control 57 (1) (2012) 151–164

    work page 2012

  11. [11]

    J. F. Mota, J. M. Xavier, P. M. Aguiar, M. P¨ uschel, D-ADMM: A communication-efficient distributed algorithm for separable optimization, IEEE Trans. on Signal Processing 61 (10) (2013) 2718–2723

    work page 2013

  12. [12]

    Q. Ling, A. Ribeiro, Decentralized dynamic optimization through the alternating direction method of multipliers, IEEE Trans. on Signal Processing 5 (62) (2014) 1185–1197

    work page 2014

  13. [13]

    W. Shi, Q. Ling, K. Yuan, G. Wu, W. Yin, On the linear con- vergence of the ADMM in decentralized consensus optimization, IEEE Trans. on Signal Processing 62 (7) (2014) 1750–1761

    work page 2014

  14. [14]

    Jakoveti´ c, J

    D. Jakoveti´ c, J. M. Moura, J. M. Xavier, Linear convergence rate of a class of distributed augmented Lagrangian algorithms, IEEE Trans. on Automatic Control 60 (4) (2015) 922–936

    work page 2015

  15. [15]

    Iutzeler, P

    F. Iutzeler, P. Bianchi, P. Ciblat, W. Hachem, Explicit con- vergence rate of a distributed alternating direction method of multipliers, IEEE Trans. on Autom. Control 61 (4) (2016) 892– 904

    work page 2016

  16. [16]

    Makhdoumi, A

    A. Makhdoumi, A. Ozdaglar, Convergence rate of distributed ADMM over networks, IEEE Trans. on Automatic Control 62 (10) (2017) 5082–5095

    work page 2017

  17. [17]

    D. P. Bertsekas, J. N. Tsitsiklis, Parallel and distributed com- putation: numerical methods, Vol. 23, Prentice hall Englewood Cliffs, NJ, 1989

    work page 1989

  18. [18]

    S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, Distributed optimization and statistical learning via the alternating direc- tion method of multipliers, Found. and Trends R⃝ in Machine learning 3 (1) (2011) 1–122

    work page 2011

  19. [19]

    M. Zhu, S. Mart´ ınez, Discrete-time dynamic average consensus, Automatica 46 (2) (2010) 322–329

    work page 2010

  20. [20]

    S. S. Kia, B. Van Scoy, J. Cortes, R. A. Freeman, K. M. Lynch, S. Martinez, Tutorial on dynamic average consensus: The prob- lem, its applications, and the algorithms, IEEE Control Systems Magazine 39 (3) (2019) 40–72

    work page 2019

  21. [21]

    Di Lorenzo, G

    P. Di Lorenzo, G. Scutari, NEXT: In-network nonconvex opti- mization, IEEE Trans. on Signal and Information Process. over Networks 2 (2) (2016) 120–136

    work page 2016

  22. [22]

    Varagnolo, F

    D. Varagnolo, F. Zanella, A. Cenedese, G. Pillonetto, L. Schen- ato, Newton-Raphson consensus for distributed convex opti- mization, IEEE Trans. on Automatic Control 61 (4) (2016) 994– 1009

    work page 2016

  23. [23]

    Nedi´ c, A

    A. Nedi´ c, A. Olshevsky, W. Shi, Achieving geometric conver- gence for distributed optimization over time-varying graphs, SIAM J. on Optimization 27 (4) (2017) 2597–2633

    work page 2017

  24. [24]

    G. Qu, N. Li, Harnessing smoothness to accelerate distributed optimization, IEEE Trans. on Control of Network Systems 5 (3) (2018) 1245–1260

    work page 2018

  25. [25]

    J. Xu, S. Zhu, Y. C. Soh, L. Xie, Convergence of asynchronous distributed gradient methods over stochastic networks, IEEE Trans. on Autom. Control 63 (2) (2018) 434–448

    work page 2018

  26. [26]

    C. Xi, R. Xin, U. A. Khan, ADD-OPT: Accelerated distributed directed optimization, IEEE Trans. on Autom. Control 63 (5) (2018) 1329–1339

    work page 2018

  27. [27]

    Necoara, V

    I. Necoara, V. Nedelcu, On linear convergence of a distributed dual gradient algorithm for linearly constrained separable con- vex problems, Automatica 55 (2015) 209–216

    work page 2015

  28. [28]

    Alghunaim, K

    S. Alghunaim, K. Yuan, A. Sayed, Dual coupled diffusion for distributed optimization with affine constraints, in: IEEE Con- ference on Decision and Control (CDC), 2018, pp. 829–834

    work page 2018

  29. [29]

    Chang, A

    T.-H. Chang, A. Nedi´ c, A. Scaglione, Distributed con- strained optimization by consensus-based primal-dual perturba- tion method, IEEE Trans. on Automatic Control 59 (6) (2014) 1524–1538

    work page 2014

  30. [30]

    Mateos-N´ unez, J

    D. Mateos-N´ unez, J. Cort´ es, Distributed saddle-point subgra- dient algorithms with Laplacian averaging, IEEE Transactions on Automatic Control 62 (6) (2017) 2720–2735

    work page 2017

  31. [31]

    Simonetto, H

    A. Simonetto, H. Jamali-Rad, Primal recovery from consensus- based dual decomposition for distributed convex optimization, Journal of Optimization Theory and Applications 168 (1) (2016) 172–197

    work page 2016

  32. [32]

    Falsone, K

    A. Falsone, K. Margellos, S. Garatti, M. Prandini, Dual decom- position for multi-agent distributed optimization with coupling constraints, Automatica 84 (2017) 149–158

    work page 2017

  33. [33]

    Chang, A proximal dual consensus ADMM method for multi-agent constrained optimization, IEEE Trans

    T.-H. Chang, A proximal dual consensus ADMM method for multi-agent constrained optimization, IEEE Trans. on Signal Processing 64 (14) (2016) 3719–3734

    work page 2016

  34. [34]

    Constraint Coupled Distributed Optimization: a Relaxation and Duality Approach

    I. Notarnicola, G. Notarstefano, Constraint coupled distributed optimization: a relaxation and duality approach, preprint arXiv:1711.09221

    work page internal anchor Pith review Pith/arXiv arXiv

  35. [35]

    S. S. Kia, Distributed optimal in-network resource allocation algorithm design via a control theoretic approach, Systems & Control Letters 107 (2017) 49–57

    work page 2017

  36. [36]

    Zhang, M

    Y. Zhang, M. M. Zavlanos, A consensus-based distributed aug- mented Lagrangian method, in: IEEE Conference on Decision and Control (CDC), 2018, pp. 1763–1768

    work page 2018

  37. [37]

    Vujanic, P

    R. Vujanic, P. M. Esfahani, P. J. Goulart, S. Mari´ ethoz, M. Morari, A decomposition method for large scale MILPs, with performance guarantees and a power system application, Auto- matica 67 (2016) 144–156. Appendix A. Proofs Proof of Lemma 1 We prove (8) by induction. For k = 0, given the initial- ization in Step 3, we have that ¯d0 = 1 N N∑ i=1 di,0 = ...

    work page 2016