Source-linked AI summary
On distributed convex optimization under inequality and equality constraints via primal-dual subgradient methods
Minghui Zhu, Sonia Martinez
TL;DR
The paper studies distributed multi-agent optimization with intersected local constraint sets and develops two primal-dual subgradient algorithms. Under connectivity assumptions, both algorithms asymptotically converge to primal solutions and optimal values, with the DLPDS algorithm also converging to primal-dual solutions.
Problem
The paper studies multi-agent optimization in which agents minimize a sum of local objectives over globally coupled constraints and an intersection of local constraint sets.
Method
It introduces distributed Lagrangian and penalty primal-dual subgradient algorithms, including the DLPDS algorithm.
Results
The algorithms asymptotically converge to primal solutions and optimal values; DLPDS also converges to a pair of primal-dual solutions.
Takeaways & Limitations
The proposed distributed algorithms provide asymptotic primal optimization guarantees for the studied multi-agent problem.
Takeaways & Limitations
The convergence results are tied to a periodic strong connectivity assumption on the network graphs.
Abstract
from arXiv · showhide
We consider a general multi-agent convex optimization problem where the agents are to collectively minimize a global objective function subject to a global inequality constraint, a global equality constraint, and a global constraint set. The objective function is defined by a sum of local objective functions, while the global constraint set is produced by the intersection of local constraint sets. In particular, we study two cases: one where the equality constraint is absent, and the other where the local constraint sets are identical. We devise two distributed primal-dual subgradient algorithms which are based on the characterization of the primal-dual optimal solutions as the saddle points of the Lagrangian and penalty functions. These algorithms can be implemented over networks with changing topologies but satisfying a standard connectivity property, and allow the agents to asymptotically agree on optimal solutions and optimal values of the optimization problem under the Slater's condition.
I. INTRODUCTION
The paper studies distributed convex optimization with local objectives and constraint sets, global inequality and equality constraints, and changing network topologies. It develops two primal-dual subgradient algorithms that asymptotically recover optimal solutions and values under Slater’s condition and periodic strong connectivity.
- Problem: The problem minimizes a sum of locally known convex objectives over intersected local constraint sets, subject to global inequality and equality constraints.The global decision vector must be coordinated through local information exchange.
- Motivation: The paper extends distributed optimization to settings where network topologies change while satisfying periodic strong connectivity.This addresses coordination without centralized authority.
- Methods: When the equality constraint is absent, DLPDS uses Lagrangian saddle-point characterization with consensus, subgradient, and projection steps.Agents update primal-dual saddle-point estimates using local constraint projections or dual compact supersets.
- Results: DLPDS asymptotically converges to primal-dual optimal solutions and enables agents to agree on the optimal value under Slater’s condition.The result assumes periodic strong connectivity and uses dynamic average consensus to track time-varying averages.
- Methods: For identical local constraint sets, DPPDS uses penalty relaxation to handle the case without the additional equality constraint.Its dual optimal set may be unbounded, so the algorithm omits dual projections and instead uses carefully chosen step-sizes.
- Results: DPPDS asymptotically converges to a primal optimal solution and the optimal value under Slater’s condition and periodic strong connectivity.The paper extends earlier results to changing topologies and different local constraint sets in the unconstrained special case.
B. Network model
The paper models synchronous agents communicating over time-varying directed weighted graphs and analyzes distributed optimization through subgradients and saddle-point characterizations. Under Slater’s condition and the stated connectivity assumptions, saddle points correspond to primal-dual optima and support the proposed algorithms’ convergence.
- Network model: Agents interact synchronously through time-varying directed weighted graphs whose edges and in-neighbors define local communication.The network assumptions include non-degeneracy, balanced communication, and periodic strong connectivity.
- Network assumptions: Periodic strong connectivity requires the union of network topologies over each bounded time period to be strongly connected.This is the connectivity property used in the convergence analysis.
- Preliminaries: A saddle point of φ satisfies φ(x*, μ) ≤ φ(x*, μ*) ≤ φ(x, μ*) for every feasible pair (x, μ).This definition underpins the Lagrangian characterization.
- Preliminaries: The paper uses subgradients for convex functions and supgradients for concave functions when differentiability is not assumed.These generalized derivatives replace gradients at nondifferentiable points.
- Lagrangian algorithm: The Lagrangian algorithm is built from this characterization and its convergence properties are summarized after the supporting preliminaries.The associated dual problem maximizes the dual function over nonnegative multipliers.
- Lagrangian characterization: Under Slater’s condition, Lagrangian saddle points characterize primal and dual optimal solutions and yield the minimax equality.The paper establishes existence of saddle points over suitable multiplier supersets.
- Lagrangian characterization: A saddle point over a multiplier superset has the primal optimal value and a Lagrangian dual optimal multiplier.The paper notes that the converse implication need not hold because a dual-optimal pair may have an infeasible primal component.
2) A upper estimate of the Lagrangian dual optimal set:
This section defines local Lagrangian dual problems and constructs distributed upper estimates of their dual optimal sets. Under convexity, Slater’s condition, and periodic strong connectivity, agents reach common bounds in finite time.
- Local dual problems: Each agent’s local problem minimizes f[i](x) subject to g(x) ≤ 0 over X[i], with dual function q[i](µ) defined through the local Lagrangian.The local Lagrangian is L[i](x, µ) = f[i](x) + µ^Tg(x), and q[i](µ) = inf over x in X[i] of L[i](x, µ).
- Local dual problems: The global Lagrangian decomposes into a sum of convex-concave local functions, motivating distributed primal-dual subgradient methods.Convexity in x and concavity in µ support extending primal-dual methods to networked agents.
- Dual-set boundedness: For any Slater vector, the relevant dual-solution set Q(µ̃) is bounded, with an explicit norm bound on its elements.The boundedness result supplies the finite upper estimate used in the distributed construction.
- Distributed upper estimate: A distributed Slater-vector computation algorithm lets agents compute a superset of the local dual bounds needed to estimate the global dual optimal set.The algorithm addresses the need for agents to agree on a common Slater vector and computes a superset of M̄[i](x̄, µ̃).
- Distributed upper estimate: After at most (N −1)B steps, all agents reach consensus on b* and c* through max-consensus and min-consensus updates.The common values are b* = max over j of b[j](0) and c* = min over j of c[j](0).
B. Distributed Lagrangian primal-dual subgradient algorithm
The distributed Lagrangian primal-dual subgradient algorithm seeks saddle points of the Lagrangian while tracking the optimal value. Under stated convexity, connectivity, and regularity assumptions, agents asymptotically agree on primal-dual solutions and the optimal value.
- Algorithm and objective: DLPDS is introduced as a distributed algorithm for finding a saddle point of the Lagrangian over X × M and the optimal value.It generalizes primal-dual subgradient methods to networked multi-agent optimization with inequality constraints.
- Algorithm and objective: Each agent combines neighboring estimates, takes subgradient and supgradient steps, and projects primal and dual variables onto local feasible sets.The updates minimize or maximize the local Lagrangian while maintaining the relevant primal and dual constraints.
- Convergence: Under the theorem’s assumptions, agent estimates x[i](k) and µ[i](k) converge to a pair of primal and Lagrangian dual optimal solutions.The assumptions include non-degeneracy, balanced communication, periodic strong connectivity, and Slater-type regularity where required.
- Convergence: The value estimates y[i](k) converge to the optimal value p* for every agent, establishing asymptotic agreement on the objective value.DLPDS therefore targets both saddle-point variables and distributed optimal-value estimation.
- Penalty extension: The paper also treats the absence of equality constraints with identical local constraint sets through a penalty relaxation and a penalty primal-dual subgradient algorithm.The penalty saddle-point theorem links penalty saddle points to primal and penalty-dual optimal solutions.
- Penalty extension: Slater’s condition yields zero duality gap and existence of penalty dual optimal solutions, supporting the penalty saddle-point characterization.The penalty minimax equality identifies primal and penalty-dual optimality through the saddle-point conditions.
2) Convexity of H:
The penalty function H is constructed as a sum of local functions that are convex in the primal variable and concave in the dual variables. This convex-concave structure supports the distributed penalty primal-dual subgradient algorithm and its convergence analysis.
- Convex-concave structure: H is the sum of local functions that are convex in x and concave in w.The local functions are affine, hence concave, in w.
- Choice of relaxation: The Lagrangian relaxation is unsuitable because allowing negative λ entries destroys convexity in x.The paper therefore uses penalty relaxation instead.
- Algorithm: DPPDS is based on the penalty saddle-point theorem and generates primal and dual estimates through distributed updates.Agents combine dual estimates with those of their neighbors and use step-size sequence {α(k)} satisfying Assumption 4.1.
- Convergence: Under the stated communication, non-degeneracy, and step-size assumptions, DPPDS estimates converge to a common primal optimum and optimal value.The primal estimates converge to ˜x and the value estimates converge to p∗ for every agent.
- Convergence conditions: The absence of dual projection steps can prevent uniform boundedness of primal subgradients, requiring a stronger step-size policy.The paper identifies this as a key difference from standard diminishing step-size schemes.
V. CONVERGENCE ANALYSIS
The convergence analysis establishes consensus, saddle-point characterization, and optimality for the distributed algorithms. It uses weighted-sequence properties, iteration inequalities, and network assumptions to show that agent estimates converge to shared optimal quantities.
- Weighted sequences: Weighted-sequence lemmas transfer divergence or convergence of a sequence ρ(k) to its weighted counterpart δ(k).These properties are used repeatedly in the convergence proofs.
- DLPDS consensus: Under balanced communication and periodic strong connectivity, DLPDS primal, dual, and value estimates asymptotically reach consensus.Primal estimates converge to a common point in X, while dual and value estimates also agree across agents.
- DLPDS saddle points: Each limit point of the DLPDS estimates is a saddle point of the Lagrangian over X × M.This characterization links consensus limits to primal-dual optimality.
- DLPDS optimality: The DLPDS limit is feasible and achieves the optimal value, so it is a primal optimal solution.The proof combines feasibility, the saddle-point relation, and convergence of weighted primal estimates.
B. Proofs of Theorem 4.2
The proof of Theorem 4.2 establishes DPPDS convergence by controlling dual and primal deviations, proving consensus, and showing that the common limit is feasible and optimal.
- Proof assumptions: The proof assumes bounded subgradients for objective, inequality-penalty, and equality-penalty terms over the common compact constraint set.These bounds support the summability and diminishing-error arguments.
- Error control: Lemma 5.6 shows that selected scaled dual quantities vanish and key error sequences are summable under the step-size assumptions.These properties control the growth of dual estimates and accumulated primal errors.
- Consensus: Lemma 5.8 establishes primal convergence and pairwise consensus for primal, inequality-dual, equality-dual, and value estimates.The result relies on non-degeneracy, balanced communication, periodic strong connectivity, and step-size conditions.
- Feasibility: The proof shows that the common primal limit satisfies the inequality and equality constraints.It derives [gℓ(˜x)]+ = 0 for every inequality constraint and |h(˜x)| = 0 for the equality constraints.
- Optimality: The feasible common limit has objective value p∗ and therefore belongs to X∗.This completes the primal-optimality part of Theorem 4.2.
VI. DISCUSSION
The discussion points toward possible extensions and interesting special cases of the framework. It marks this material as a continuation beyond the main convergence analysis.
- Extensions: The paper identifies possible extensions of the distributed optimization framework.
- Special cases: The paper also identifies interesting special cases for further consideration.
- Scope: These extensions and special cases are presented after the main analysis of the algorithms and their convergence properties.
A. Discussion on the periodic strong connectivity assumption in Theorem 3.2
For undirected time-varying networks, the periodic strong connectivity requirement in Theorem 3.2 can be weakened to alternative connectivity conditions.
- Undirected graphs permit weakening the periodic strong connectivity assumption in Theorem 3.2.
- One alternative requires the union graph over each time interval to remain connected.
- Another alternative requires an agent connected to all others in the relevant union graph.
B. A generalized step-size scheme
The DLPDS step-size scheme can be generalized when agents’ step-sizes do not differ excessively at a given time.
- The DLPDS step-size scheme allows limited deviations between agents’ step-sizes at each time.
- This generalization is specifically tied to keeping the maximum step-size deviation between agents sufficiently small.
- The lower-bound condition is Cα maxi∈V α[i](k), with α[i](k) the step-size of agent i and Cα ∈(0, 1].
C. Discussion on the Slater’s condition in Theorem 4.2
For linear inequality constraints, the Slater condition can be weakened to a relative-interior feasibility condition while retaining DPPDS convergence results. Numerical examples illustrate both algorithms’ asymptotic behavior and compare their convergence with centralized subgradient methods.
- C. Discussion on the Slater’s condition in Theorem 4.2: When gℓ is linear, Slater’s condition can be replaced by a relative interior point satisfying h(¯x) = 0 and g(¯x) ≤0.
- C. Discussion on the Slater’s condition in Theorem 4.2: Under this weakened condition, strong duality and a nonempty penalty dual optimal set remain ensured, so DPPDS convergence results still hold.
- Numerical examples: The DLPDS example models five agents allocating rates under the shared capacity constraint z1 + z2 + z3 + z4 + z5 ≤5.
- Numerical examples: After 104 iterates, all agents agree on the optimal solution [1 1 1 1 1]T, whereas the centralized method requires 200 iterates with the same step-size.
- Numerical examples: The DPPDS example uses identical local constraint sets and a global equality constraint h(x) := a + b + c + d + e −5.
- Numerical examples: In the DPPDS simulation, all agents asymptotically achieve the optimal solution [1 1 1 1 1]T, but convergence is slower than centrally.
IX. APPENDIX
The appendix records supporting consensus and projection results used in the distributed algorithms, including convergence under standard network assumptions and bounded subgradients.
- Dynamic average consensus reaches agreement when communication is balanced and periodically strongly connected, provided input differences vanish.
- Projection onto a nonempty closed convex set satisfies a squared-distance inequality useful for analyzing projected subgradient updates.
- A distributed projected subgradient lemma establishes constants γ > 0 and β ∈(0, 1) under the network assumptions and uniformly bounded subgradients.