PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Online Optimization for Multi-Agent Networks with Coupled Inequality Constraints

Xiuxian Li, Xinlei Yi, Lihua Xie

arXiv:1805.05573v3math.OC

TL;DR

The paper studies distributed online convex optimization with local set constraints and coupled inequalities when agents receive local cost and constraint information gradually. It proposes a distributed online primal-dual push-sum algorithm, DOPP, for unbalanced networks without bounded-multiplier assumptions. Under the stated conditions, DOPP achieves sublinear dynamic regret and constraint violation when weighted path variation is sublinear.

  • Problem

    Distributed online optimization must handle gradually revealed local costs and coupled inequality constraints without centralized access to all functions.

  • Method

    The paper proposes a modified distributed online primal-dual push-sum algorithm that tracks the needed eigenvector information to address unbalanced communication graphs.

  • Results

    The proposed method achieves sublinear dynamic regret and constraint violation when the weighted path variation of optimal decisions is sublinear.

  • Takeaways & Limitations

    The results extend distributed online optimization to unbalanced graphs without assuming bounded generated Lagrange multipliers.

Abstract

from arXiv · show

This paper investigates the distributed online optimization problem over a multi-agent network subject to local set constraints and coupled inequality constraints, which has a lot of applications in many areas, such as wireless sensor networks, power systems and plug-in electric vehicles. In this problem, the cost function at each time step is the sum of local cost functions with each of them being gradually revealed to its corresponding agent, and meanwhile only local functions in coupled inequality constraints are accessible to each agent. To address this problem, a modified primal-dual algorithm, called distributed online primal-dual push-sum algorithm (DOPP), is developed in this paper, which does not rest on any assumption on parameter boundedness and is applicable to unbalanced networks. It is shown that the proposed algorithm is sublinear for both the dynamic regret and the violation of coupled inequality constraints. Finally, the theoretical results are supported by a simulation example.

I. INTRODUCTION

Distributed online optimization addresses cooperative decision-making when agents hold private information and costs are revealed over time. This paper targets coupled inequality constraints, unbalanced communication graphs, and performance guarantees without bounded-multiplier assumptions.

  • Motivation: Distributed optimization coordinates agents that lack a centralized entity with access to the network’s complete information.Applications include machine learning, sensor networks, resource allocation, formation control, and power systems.
  • Online optimization: Online optimization reveals each time-dependent convex cost function only after the current decision is made, motivating regret against hindsight benchmarks.Sublinear regret is the conventional criterion for a good online algorithm.
  • Distributed setting: Distributed online optimization is motivated by agents’ limited sensing and computation, requiring cooperative treatment of online problems over networks.The paper situates this setting in applications including optimal wireless networking, smart grids, and plug-in electric vehicles.
  • Problem and approach: The paper revisits online optimization with coupled inequality constraints, where objective and constraint functions are gradually revealed and future information is unavailable.Its proposed algorithm achieves sublinear dynamic regret under relaxed conditions.
  • Contributions: The results remove boundedness assumptions on generated Lagrange multipliers and extend the communication setting from balanced to unbalanced graphs.A push-sum idea is used to counteract graph imbalance.
  • Contributions: The paper proves sublinear dynamic regret when weighted path variation is sublinear and also proves sublinear coupled-constraint violation.It additionally provides a convergence speed result for time-invariant distributed optimization.

A. Graph Theory

The paper models communication with directed, possibly time-varying graphs and column-stochastic adjacency matrices. Its assumptions require uniformly positive nonzero weights and repeated strong connectivity, allowing unbalanced graphs.

  • Graph model: G_t=(V,E_t) is a directed graph whose edge (j,i) means node j routes information to node i.The graph may vary with the time slot.
  • Assumptions: The communication assumptions impose positive lower bounds on nonzero weights and self-weights, column-stochastic adjacency matrices, and repeated strong connectivity.The union of edges across every Q-slot window must be strongly connected.
  • Unbalanced graphs: Unlike the doubly stochastic assumption used in prior work, the paper permits column-stochastic graphs that may be unbalanced.This broader graph class motivates the push-sum treatment developed later.

B. Optimization Theory

This section introduces projection, subgradient, convex-concave saddle-point, and Lagrangian-duality concepts used to analyze the constrained optimization problem. Strong duality follows under a condition such as Slater’s condition.

  • Basic concepts: Projection maps a point to the point in a closed convex set with the shortest distance from it.The projection operator is used for feasible-set handling.
  • Basic concepts: A subgradient generalizes the gradient for convex functions, while differentiability makes the subdifferential equal to the singleton containing the gradient.The subdifferential collects all subgradients at a point.
  • Saddle points: A convex-concave Lagrangian is convex in the primal variable and concave in the dual variable, with saddle points defined accordingly.These properties support primal-dual analysis.
  • Lagrangian duality: For convex constrained optimization, the Lagrangian combines the objective with constraints weighted by nonnegative dual variables called Lagrange multipliers.The associated dual function minimizes the Lagrangian over the primal feasible set.
  • Lagrangian duality: Weak duality always holds, while strong duality holds when a constraint qualification such as Slater’s condition is satisfied.Under strong duality, the primal and dual optimal values coincide.

C. Problem Formulation

The problem is distributed online convex optimization with local feasible sets, gradually revealed local costs, and globally coupled inequality constraints. Performance is measured by dynamic regret and cumulative constraint violation, both required to grow sublinearly.

  • Problem formulation: At each time t, the global cost f_t is composed of local functions f_i,t that are unknown beforehand and revealed gradually.Agent i incurs f_i,t(x_i,t) after making its decision, then accesses that local cost information.
  • Problem formulation: Each agent knows its own constraint function g_i, while the collection of these functions imposes global coupled inequalities over the product set X.The feasible product set X is assumed nonempty.
  • Dynamic regret: The algorithm seeks to minimize total incurred cost over horizon T relative to the best time-varying feasible decisions in hindsight.This comparison defines the dynamic regret.
  • Dynamic regret: Dynamic regret is more appropriate than static regret when the decision of interest evolves over time, such as when tracking moving targets.Static regret instead compares against one fixed decision with full prior information.
  • Performance criteria: A good online algorithm should have sublinear regret, Reg(T)=o(T), so average cost approaches the optimum as T grows.Sublinearity is defined by o(T)/T tending to zero.
  • Performance criteria: Because the problem includes coupled inequalities, constraint violation Reg_c(T) must also grow sublinearly with T.The formulation explicitly treats violation control as a second performance requirement.
  • Assumptions: The analysis assumes convex local costs and constraints, compact convex local sets, a Slater point, and uniformly bounded costs and subgradients.The sets’ compactness reflects bounded decision variables in applications such as charging-rate control.

III. MAIN RESULTS

The paper develops DOPP for distributed online optimization with coupled inequality constraints, targeting unbalanced communication graphs without assuming bounded Lagrange multipliers. Its analysis establishes sublinear dynamic regret and constraint violation under stated assumptions, with tradeoffs governed by parameter choices and path variation.

  • Algorithm design: DOPP combines primal-dual updates with push-sum information exchange to address coupled constraints over unbalanced directed graphs.The auxiliary variable w_i,t tracks the right-hand eigenvector of the communication matrix to counteract graph imbalance.
  • Algorithm design: The algorithm removes the boundedness assumption on generated Lagrange multipliers by incorporating an additional penalty term into their updates.Projection onto bounded sets is presented as an alternative, but computing those sets is usually difficult and computationally expensive.
  • Main bounds: Theorem 1 bounds both dynamic regret and coupled-constraint violation under Assumptions 1 and 2, with stepsizes determined by α0 = 1, β0 = 1, and κ ∈ (0, 1/4).The regret bound also depends on the 1/αt-weighted path variation VT of the optimal decisions.
  • Main bounds: Both performance bounds are sublinear when the relevant path variation is sublinear, although choosing κ requires a tradeoff between regret and constraint-violation bounds.The paper notes that rapidly changing optimal decisions cannot generally be tracked by a sublinear dynamic-regret guarantee.
  • Comparison and scope: Compared with prior work, the results handle unbalanced graphs and require no boundedness assumption on the generated multipliers.Under bounded multipliers, the paper states that the same O(·) order can be obtained for static regret and constraint violation under unbalanced graphs.
  • Extensions: For noisy subgradients modeled as i.i.d. unbiased noises with bounded variances, the same bounds hold for expected dynamic regret and expected constraint violation.This extends the stated true-subgradient result in expectation under the specified noise conditions.
  • Open direction: The paper identifies optimal dynamic-regret and constraint-violation bounds matching the centralized case as an open research direction.This limitation concerns the gap between the established distributed rates and centralized online-optimization rates.
  • Time-invariant case: For time-invariant problems, Theorem 2 establishes separate convergence rates for cost and constraint functions under unbalanced graphs, with Corollary 2 giving O(1/T^1/6).The paper characterizes this rate as slower than rates established in some prior constrained results.

IV. A SIMULATION EXAMPLE

The simulation applies the proposed algorithm to an overnight plug-in electric-vehicle charging problem with local vehicle constraints and a network-wide power constraint. For N = 50 vehicles, Figs. 2 and 3 track normalized regret and constraint violation under switching-graph settings Q = 4 and Q = 9.

  • PEV charging model: The experiment models each vehicle’s charging rate over a specified time duration as its decision variable.The local cost is linear and time-varying, with unitary charging costs randomly selected in [0, 10].
  • PEV charging model: The coupled inequality constraint limits the whole network’s aggregate charging power flow.It is represented as Σ_i(D_i x_i − b/N) ≤ 0, where D_i aggregates vehicle rates and b specifies the global limit.
  • Simulation results: For N = 50 vehicles, Fig. 2 reports the evolution of Reg(T)/T for Q = 4 and Q = 9.The caption identifies normalized dynamic regret as the plotted quantity and distinguishes the two switching-graph settings.
  • Simulation setup: Each vehicle has dimension n_i = 24, its feasible set is confined by 197 inequalities, and the problem has m = 48 coupled inequality constraints.The simulation uses κ = 0.2.
  • Simulation results: For N = 50 vehicles, Fig. 3 reports the evolution of Reg_c(T)/T for Q = 4 and Q = 9.The supplied passages identify the metric and settings but do not state a numerical comparison between the trajectories.

V. CONCLUSION

The conclusion presents DOPP for distributed online convex optimization with local set and coupled inequality constraints over directed networks. It states sublinear dynamic regret and constraint violation under sublinear weighted path variation, while identifying convergence-rate improvement as future work.

  • Problem and contribution: The paper studies distributed online convex optimization over directed multi-agent networks with local set and coupled inequality constraints.
  • Problem and contribution: DOPP addresses limitations of prior work by avoiding boundedness assumptions on generated Lagrange multipliers.The conclusion states that the earlier algorithm’s multiplier boundedness dependence limited applicability.
  • Problem and contribution: DOPP accommodates unbalanced communication graphs, which are more general than balanced graph settings.
  • Theoretical results: When the weighted path variation of optimal decision variables is sublinear, DOPP has sublinear dynamic regret and constraint violation.
  • Conclusion and future work: The paper demonstrates the algorithm’s performance through a numerical application and proposes improving the convergence rates of Reg(T)/T and Reg_c(T)/T as future work.

B. Proof of Theorem 1

The proof of Theorem 1 decomposes perturbed push-sum and primal-dual quantities into bounded terms, then combines disagreement, dual-variable, and path-variation estimates. The resulting bounds establish the theorem’s regret and constraint-violation claims.

  • Part 1: proving (34): The proof first establishes a bound for all x ∈ X and μ ∈ R^m using Lemma 6.
  • Part 1: proving (34): The analysis bounds the accumulated terms S_i by applying Cauchy–Schwarz, parameter conditions, and estimates on primal and dual iterates.The proof explicitly uses bounded x_i,t and μ_i,t estimates together with α_t and β_t relations.
  • Part 1: proving (34): The proof uses α_k summed over k to obtain the order estimate Σ_k α_k = O(T^1/2).
  • Part 2: proving (35): The argument for (35) applies the same accumulated-term bounds and parameter inequalities, including κ < 1/4.

C. Proof of Theorem 2

The proof of Theorem 2 specializes the analysis to time-invariant local costs, so the path-variation term becomes zero. Convexity, saddle-point properties, and the earlier bounds then yield the stated static regret and constraint results.

  • Time-invariant costs: When all local costs are time-independent, the proof sets V_T = 0.
  • Proving (40): The proof of (40) reuses the argument from Theorem 1 and applies convexity of the local cost functions f_i.
  • Proving (40) and (41): The saddle-point property of the static Lagrangian provides an inequality involving an optimal primal-dual pair and arbitrary feasible x.
  • Proving (42): The proof combines the static inequality with earlier estimates and convexity of g_i to establish (42).
  • Proving (41): The argument for (41) invokes the preceding bounds before inserting the resulting estimate into the main proof inequality.

D. Proof of Lemma 3

The proof establishes bounds on the push-sum weights and shows that the averaged auxiliary variable remains controlled by the coupled-constraint mapping. These properties provide the boundedness needed for subsequent analysis.

  • Weight bounds: The push-sum weights satisfy r ≤ w_i,t ≤ N for all agents and times.The lower bound follows from Lemma 2, while the conserved sum of weights equals N and nonnegativity give the upper bound.
  • Average auxiliary variable: The network average satisfies ¯y_t = g(x_t)/N for all t ≥ 1.This follows by pre-multiplying the auxiliary-variable recursion by 1^⊤ and using the initialization y_i,0 = g_i(x_i,0).
  • Average auxiliary variable: The averaged auxiliary variable is bounded as ∥¯y_t∥ ≤ B_g.The identity ¯y_t = g(x_t)/N combined with the boundedness condition in (17) yields the result.

E. Proof of Lemma 4

The proof of Lemma 4 establishes boundedness of the primal and dual tracking variables, then derives the inequalities needed for the subsequent regret and constraint-violation analysis.

  • Variable boundedness: The tracking variables y_i,t and ˆy_i,t are uniformly bounded by some B_y.Consensus-error bounds, bounded averages, and bounded push-sum weights together imply ∥y_i,t∥ ≤ B_y and ∥ˆy_i,t∥ ≤ B_y.
  • Dual-variable bounds: The dual estimates satisfy ∥ˆµ_i,t∥ ≤ w_i,t+1 B_y/(β_t r^2) by induction.The induction uses the bound on ˆy_i,t, the lower bound w_i,t+1 ≥ r, and the initialization β_0 = 1 with µ_i,0 = 0.
  • Primal movement: The proof derives a bound on the primal movement from ∥x_i,t+1 − x_i,t∥ ≤ α_t∥s_i,t+1∥.This relation is combined with the assumptions and the dual bounds to obtain the subsequent inequality in (58).
  • Primal inequality: Convexity of f_i,t and g_i, nonnegative dual variables, and the bound on ∥s_i,t+1∥ yield inequality (59).The subgradient bound used is ∥s_i,t+1∥ ≤ C_f + C_g B_y/(β_t r^2).
  • Dual inequality: Averaging the dual recursion and applying the stated assumptions yields inequality (60) for all µ ∈ R^m.The derivation uses the average dual update, the error terms, and Cauchy–Schwarz-type bounds.
Loading 1805.05573v3…