Source-linked AI summary
Dual decomposition for multi-agent distributed optimization with coupling constraints
Alessandro Falsone, Kostas Margellos, Simone Garatti, Maria Prandini
TL;DR
The paper addresses convex multi-agent optimization with local objectives and constraints coupled by shared-resource inequalities over time-varying networks. It combines dual decomposition and proximal minimization while exchanging only dual variables. Under convexity and suitable connectivity, dual estimates reach an optimal consensus and primal iterates converge to the set of primal optimizers, with plug-in electric-vehicle charging used as an example.
Problem
Convex multi-agent problems require agents with private local objectives, constraints, and decisions to coordinate shared-resource usage through coupling constraints.
Method
The paper proposes a distributed iterative scheme combining dual decomposition, proximal minimization, and distributed subgradient updates for the dual problem.
Results
Under convexity and suitable network connectivity, dual estimates converge to a common optimal multiplier vector while primal iterates converge to the set of primal minimizers.
Takeaways & Limitations
Exchanging only dual-variable estimates preserves privacy while requiring agents to optimize local variables, with particular communication appeal when coupling constraints are few.
Takeaways & Limitations
The analysis assumes convexity and leaves convergence-rate analysis and extensions to mixed-integer programs for future work.
Abstract
from arXiv · showhide
We study distributed optimization in a cooperative multi-agent setting, where agents have to agree on the usage of shared resources and can communicate via a time-varying network to this purpose. Each agent has its own decision variables that should be set so as to minimize its individual objective function subject to local constraints. Resource sharing is modeled via coupling constraints that involve the non-positivity of the sum of agents' individual functions, each one depending on the decision variables of one single agent. We propose a novel distributed algorithm to minimize the sum of the agents' objective functions subject to both local and coupling constraints, where dual decomposition and proximal minimization are combined in an iterative scheme. Notably, privacy of information is guaranteed since only the dual optimization variables associated with the coupling constraints are exchanged by the agents. Under convexity assumptions, jointly with suitable connectivity properties of the communication network, we are able to prove that agents reach consensus to some optimal solution of the centralized dual problem counterpart, while primal variables converge to the set of optimizers of the centralized primal problem. The efficacy of the proposed approach is demonstrated on a plug-in electric vehicles charging problem.
1 Introduction
The paper targets convex inequality-coupled optimization in time-varying multi-agent networks, combining dual decomposition and proximal minimization to preserve privacy while achieving centralized primal-dual optimality. Its introduction positions the scheme against approaches with fixed networks, constant step sizes, stronger Slater-point requirements, or greater communication and computation costs.
- Motivation: Centralized optimization can be impractical for large systems and requires sharing performance criteria and constraints, whereas distributed optimization separates local computation and information exchange.
- Problem setting: Inequality-coupled problems give each agent separate decision variables, objectives, and constraint sets while coupling agents through the non-positivity of summed convex functions.
- Proposed approach: The proposed scheme combines dual decomposition with proximal minimization and extends dual-decomposition methods to distributed optimization over time-varying communication networks.
- Comparison with prior work: Unlike a compared method using fixed networks and constant step sizes, the proposed algorithm permits time variability and uses a vanishing step size.
- Comparison with prior work: Constant step sizes may converge faster but guarantee only convergence to an optimal neighborhood, while the proposed method is guaranteed to converge to the original problem’s optimum.
- Comparison with prior work: The method requires Slater-point existence but not that agents know or compute such a point, relaxing a distributed applicability condition.
- Privacy: Only local estimates of dual variables are exchanged, avoiding disclosure of agents’ optimal decisions, objectives, local constraints, and coupling contributions.
- Scalability and evaluation: Agents optimize only their local variables and exchange dual estimates, reducing computation and communication when coupling constraints are few relative to primal-variable dimensionality.
2 Distributed constrained optimization
The paper formulates inequality-coupled multi-agent optimization through a separable dual problem and proposes a distributed primal-dual scheme for time-varying networks. Under convexity, compactness, Slater, and connectivity assumptions, dual estimates reach consensus at an optimal dual solution while auxiliary primal iterates approach the primal optimizer set.
- Problem formulation: The centralized problem minimizes the sum of local objectives over local constraints and non-positive coupling constraints, but centralization can be computationally prohibitive and expose private agent information.Each agent contributes a local decision vector, objective, feasible set, and coupling function.
- Problem formulation: Dualizing the coupling constraint yields a separable dual problem in which the common multiplier vector couples agents through agreement on its value.The dual function decomposes into concave local dual functions.
- Distributed algorithm: Algorithm 1 alternates local primal minimization with a proximal dual update after agents form weighted averages of neighboring dual estimates.The dual update is equivalent to a projected subgradient step, with the coupling contribution providing a subgradient and c(k) acting as the step size.
- Distributed algorithm: Only estimates of the dual vector are exchanged, so local primal variables, objectives, constraints, and coupling contributions remain undisclosed during execution.This communication pattern is designed to address privacy requirements.
- Assumptions and guarantees: The assumptions require convex local objectives and coupling components, compact local feasible sets, a Slater point, diminishing nonincreasing positive step sizes, and recurrent strong connectivity.Agents need not compute or know the Slater point, although its existence is required for the theoretical guarantees.
- Assumptions and guarantees: Under Assumptions 1–6, every agent’s dual estimate converges to some optimal multiplier while the auxiliary primal vector approaches the set of primal minimizers.The convergence result establishes consensus in dual variables and primal optimality for the recovered iterates.
3 Convergence and Optimality Analysis
The analysis establishes convergence of the distributed dual updates under the stated assumptions and shows that averaged primal sequences approach optimal solutions of the centralized problem.
- Dual convergence: The dual-vector portion of Algorithm 1 implements a subgradient method for the centralized dual problem, with bounded subgradients under the convexity and compactness assumptions.The correspondence follows from Danskin’s theorem and the boundedness of agent subgradients.
- Dual convergence: Under Assumptions 1–6, the agents’ dual estimates converge to some optimal dual solution λ⋆.The resulting sequences are also bounded.
- Error relations: The error sequence e_i(k) converges to zero for every agent, linking local dual estimates with the network-wide average.This relation is used in the subsequent primal optimality proof.
- Rate characterization: The analysis provides a lower bound on the convergence rate of the dual-objective consensus error, tied to the step-size sequence.The associated result is separate from the proof of primal optimality.
- Primal convergence: The running-average primal sequence remains in each local feasible set because it is formed from convex combinations of feasible iterates.Convexity also supports the corresponding coupling-constraint argument.
- Primal convergence: Every limit point of the averaged primal sequence is feasible and attains the optimal value, hence is optimal for the primal problem.This conclusion follows from continuity of the Lagrangian and the established bounds and error relations.
4 Numerical Example
The numerical study applies the method to a modified plug-in electric-vehicle charging problem with local vehicle constraints and network-wide power limits. In a 100-vehicle simulation, dual estimates reach consensus on the optimal multipliers, while the primal sequences approach feasible optimal behavior; the auxiliary sequence improves numerical behavior but converges slowly.
- Problem setup: The example optimizes charging rates across time slots for a fleet of vehicles subject to local requirements and network-wide power constraints.The resulting formulation is a linear program with bounded convex polytopic local sets.
- Problem setup: The simulation uses m = 100 vehicles, 24 decision variables per vehicle, 197 local inequalities, and p = 48 coupling inequalities.Thus, the dual problem has 48 Lagrange multipliers.
- Network and implementation: The alternating-edge communication network is connected over a period T = 2 and uses doubly stochastic mixing matrices.These choices satisfy the communication assumptions used by the algorithm.
- Results: After 1000 iterations, all agents gradually reach consensus on the optimal Lagrange multipliers; only 3 of the 48 multipliers are positive.The remaining 45 optimal multipliers are zero.
- Results: The auxiliary sequence has an apparent convergence rate no better than O(1/log(k)), slower than the O(1/k) rate reported for the constant-step-size comparison.The vanishing step-size nevertheless supports convergence to the optimum rather than only to a neighborhood.
- Results: The modified auxiliary sequence has the same asymptotic rate as the original sequence but substantially better numerical behavior after multiplier estimates become close to λ⋆.Its re-initialization reduces the effect of inaccurate early multiplier estimates.
5 Concluding remarks
The paper concludes with a distributed algorithm for convex optimization over time-varying multi-agent networks, illustrated through electric-vehicle charging. It identifies convergence-rate analysis, nonconvex extensions, and mixed-integer duality gaps as future directions.
- Concluding remarks: The proposed scheme combines dual decomposition and proximal minimization for convex optimization over time-varying multi-agent networks.It converges to an optimal dual solution, while primal iterates converge to the set of primal minimizers.
- Concluding remarks: Primal iterates converge to the set of primal minimizers while the dual iterates converge to an optimal dual solution of the centralized counterpart.
- Concluding remarks: A realistic electric-vehicle charging example illustrates the features of the proposed methodology.
- Concluding remarks: Future work includes convergence-rate analysis, relaxing convexity, and quantifying duality gaps for mixed-integer programs.
A Appendix
The appendix proves a convergence-related bound by establishing boundedness, Lipschitz continuity, and a telescoping inequality for the relevant dual-function sequences.
- Appendix: The proof uses boundedness of the dual variables and auxiliary sequences generated by the algorithm.A uniform upper bound is introduced for the sequences λ_i(k), v(k), and ℓ_i(k).
- Appendix: Compactness of the local feasible sets makes each dual function finite on a compact domain.
- Appendix: Concavity of the dual functions on that compact domain implies Lipschitz continuity with constants C_i.
- Appendix: The auxiliary sequences ℓ_i(k) and v(k) remain inside the bounded domain for every iteration.
- Appendix: The proof multiplies the resulting inequality by 2c(k), sums over iterations, and applies the triangle inequality and Assumption 5.
- Appendix: Letting N tend to infinity and invoking Proposition 3 part 3 establishes the claimed result.