Distributed Optimization with Coupled Constraints over Time-Varying Digraph

1. Problem Statement

The paper addresses a class of distributed convex optimization problems where a network of $N$ agents collaboratively minimizes a global objective function subject to network-wide coupled constraints.

• Objective: Minimize the sum of local objective functions:
  $$\min_{x_i} \sum_{i \in \mathcal{V}} f_i(x_i)$$
• Constraints:
  1. Coupled Equality: $\sum_{i \in \mathcal{V}} A_i x_i = \sum_{i \in \mathcal{V}} b_i$
  2. Coupled Inequality: $\sum_{i \in \mathcal{V}} g_i(x_i) \leq 0$
• Network Topology: The agents communicate over a time-varying directed graph (digraph).
• Privacy & Information: Each agent $i$ only knows its local data ($f_i, A_i, b_i, g_i$). The algorithm must not require the exchange of sensitive primal variables ($x_i$) or gradients, only dual information.
• Assumptions:
  • Local objectives $f_i$ are $\mu$-strongly convex.
  • Local inequality functions $g_i$ are convex with bounded subgradients.
  • Slater's condition holds (strict feasibility exists).
  • The communication graph is strongly connected and aperiodic (has self-loops) at every time step.

2. Methodology

The authors propose a novel distributed algorithm that integrates Right-Hand Side (RHS) Allocation decomposition with Primal-Dual methods and Augmented Lagrangian techniques.

A. Problem Reformulation (Decomposition)

To handle the dense coupling constraints, the authors introduce auxiliary variables $v_i$ and $z_i$ to decouple the constraints:

• $A_i x_i - b_i = v_i$
• $g_i(x_i) \leq z_i$
• Global zero-sum constraints: $\sum v_i = 0$ and $\sum z_i = 0$.

This transforms the original problem into a master problem (optimizing $v_i, z_i$) and local subproblems (optimizing $x_i$ given $v_i, z_i$).

B. Algorithm Design (Algorithm 1)

The proposed algorithm operates in a fully distributed manner using a doubly stochastic matrix $W^k$ to handle the time-varying directed graph. It avoids the need for global information or complex consensus protocols for primal variables.

Key Steps per Iteration $k$ for Agent $i$:

1. Local Primal Update: Solve a local subproblem to update $x_i^{k+1}$ by minimizing an Augmented Lagrangian function $L_i^\rho$. This function incorporates the local constraints and the current estimates of dual variables.
2. Dual Variable Update: Update local Lagrange multipliers ($u_i, y_i$) based on the constraint violations.
3. Consensus (Synchronization): Agents exchange and average their dual variables using the doubly stochastic matrix $W^k$:
   • $p_i^{k+1} = \sum_j W_{ij}^{k+1} u_j^{k+1}$
   • $q_i^{k+1} = \sum_j W_{ij}^{k+1} y_j^{k+1}$
4. Auxiliary Variable Update: Update the auxiliary variables ($v_i, z_i$) using a gradient-like step that ensures they remain in the zero-sum space (using the property $1^T(I-W)=0$).

Key Features:

• Privacy-Preserving: Agents only exchange dual variables ($u, y$), not primal variables ($x$) or gradients.
• Simplicity: Requires only one communication round per iteration with a fixed step size $\gamma$.
• Robustness: Designed specifically for time-varying directed graphs without requiring push-sum protocols or weight balancing.

3. Key Contributions

1. Novel Algorithm for Time-Varying Digraphs: The paper presents a distributed algorithm capable of solving constraint-coupled optimization problems over time-varying directed graphs, a significantly more challenging setting than static or undirected graphs.
2. Privacy Preservation: The algorithm eliminates the need to share primal variables or gradients, making it suitable for privacy-sensitive applications (e.g., economic dispatch, demand response).
3. Convergence Rate Guarantee: The authors rigorously prove that the algorithm achieves an $O(1/k)$ convergence rate in terms of dual optimality. This is a significant result, as many distributed algorithms over directed graphs only achieve sublinear rates or require stronger assumptions.
4. Unified Framework: It successfully combines RHS allocation, augmented Lagrangian methods, and dual decomposition into a single coherent framework.

4. Theoretical Results

• Convergence Analysis:
  • Under the assumptions of strong convexity and bounded subgradients, the algorithm is proven to converge to the optimal solution.
  • The dual gap (difference between the optimal dual value and the current dual value) converges at a rate of $O(1/k)$.
  • Consequently, the primal variables $x^k$ converge to the optimal solution $x^*$.
• Proof Technique: The proof utilizes a Lyapunov-based analysis combined with an Aggregate Lower-Bounding (ALB) method. It involves establishing the smoothness of the dual function and analyzing the aggregate error terms over iterations using telescopic cancellation and cyclic monotonicity properties.

5. Numerical Results

The authors validated the algorithm through simulations with $N=20$ agents.

• Setup: Randomly generated parameters for a nonsmooth convex problem (involving $L_1$ norms) with coupled equality and inequality constraints.
• Performance:
  • Primal Error: The error $\|x_i - x^*\|$ decreased rapidly.
  • Objective Value: The global objective function converged to the optimal value.
  • Feasibility: The constraint violations (both equality and inequality) converged to zero.
• Conclusion: The simulation demonstrated "remarkable performance" in terms of both optimality and feasibility on time-varying directed networks.

6. Significance and Future Work

• Significance: This work bridges a critical gap in distributed optimization by providing a robust, privacy-preserving solution for complex, coupled constraints over realistic, dynamic, and directed network topologies. The $O(1/k)$ rate is competitive with state-of-the-art methods for undirected graphs, extending these guarantees to more complex directed settings.
• Future Directions: The authors plan to extend the algorithm to asynchronous time-varying networks and investigate methods to relax the strict doubly stochastic matrix assumption (which can be difficult to construct in directed graphs without global knowledge).

In summary, this paper offers a mathematically rigorous and practically efficient solution for distributed resource allocation and control problems where agents must collaborate under strict privacy and dynamic communication constraints.