Distributed Convex Optimization with Inequality Constraints over Time-varying Unbalanced Digraphs

• The work addresses distributed constrained optimization over time-varying unbalanced digraphs, where each node has access only to its local objective and constraints.The setting includes network congestion, in which routers optimize flow rates to reduce latency along their routes.Source: §I · p. 1
• On unbalanced digraphs, DGD minimizes a weighted sum rather than the intended sum of local objectives, and its balanced-graph requirement limits applicability.The balanced condition is difficult to check in a distributed way, especially for time-varying digraphs.Source: §I · p. 1
• Prior approaches leave the constrained, time-varying unbalanced case open: handles unconstrained optimization, while is not directly applicable to time-varying digraphs.The push-sum updates in do not preserve feasibility; the method in requires an additional algorithm to compensate for unbalancedness.Source: §I · p. 1
• An epigraph reformulation makes the objective linear, and a two-step algorithm combines distributed subgradient descent with a distributed Polyak random projection toward local constraint sets.The method adds a projection toward a fixed direction to improve transient performance and extends the algorithm in [10] to time-varying graphs.Source: §I · pp. 1–2
• Under uniformly jointly strongly connected time-varying unbalanced digraphs, the proposed algorithm converges to an optimal solution.Source: §I · p. 2

A. Distributed Contrained Optimization

• The problem is to collaboratively solve a convex optimization with inequality constraints across n networked nodes.All nodes share a common convex set X; node i alone knows its convex objective f_i and local constraints g_i(x) ⪯ 0.Source: A. Distributed Contrained Optimization · p. 2
• The interaction network is a digraph: an edge (i, j) means node i can directly receive information from node j.The passages define in-neighbors as nodes that send information to i and define out-neighbors similarly; each node belongs to both sets.Source: A. Distributed Contrained Optimization · p. 2
• A graph-adapted weighting matrix assigns a positive weight to each directed edge and zero to nonedges; the graph is balanced when the stated in- and out-weight sums agree.The passage defines a graph as unbalanced otherwise.Source: A. Distributed Contrained Optimization · p. 2
• A weighting matrix is row-stochastic when each column sums to one, and doubly-stochastic when it is also column-stochastic.Source: A. Distributed Contrained Optimization · p. 2
• The time-varying graphs and their associated weighting matrices are denoted by {G_k} and {A_k}.Source: A. Distributed Contrained Optimization · p. 2
• The goal is a recursive distributed algorithm for time-varying unbalanced digraphs, with each node's local iterate converging to a common optimal solution.Nodes communicate with their neighbors and locally update x_i^k.Source: A. Distributed Contrained Optimization · p. 2

B. Distributed Gradient Descend Algorithms

• On a generic unbalanced digraph, standard DGD [4] minimizes a Perron-weighted objective rather than the original objective, so it cannot solve the stated problem.For a strongly connected digraph, the weighting matrix's Perron vector is not uniform in general; the two objectives therefore differ.Source: B. Distributed Gradient Descend… · p. 2
• Estimating each node’s Perron-vector entry can modify DGD, but the method does not directly extend to time-varying graphs, where a constant Perron vector does not exist.The limitation is explicitly noted in.Source: B. Distributed Gradient Descend… · p. 3
• This work takes a different perspective to address constrained optimization over time-varying unbalanced digraphs.The authors state that this perspective can easily address the constrained, time-varying case.Source: B. Distributed Gradient Descend… · p. 3

• The epigraph reformulation gives every node the same linear objective, eliminating the effect of differing Perron-vector elements on the limiting point.Source: §III · p. 3
• DGD on the epigraph problem produces an intermediate state vector, which nodes update toward the negative subgradient direction of a local constraint function.Source: §III · p. 3
• The local constraint-directed updates asymptotically guarantee feasibility of each node’s local estimate.Source: §III · p. 3
• The approach extends the idea proposed in [10], which focused only on time-invariant digraphs, to time-varying digraphs.Source: §III · p. 3

A. Epigraph form of the constrained optimization

• Transforming each local objective fi into common f0 yields a shared gradient update, removing the distinction between balanced and unbalanced digraphs in this formulation.The paper says this makes the distributed gradient method effective for unbalanced graphs.Source: A. Epigraph form of the constrained… · p. 3
• For convex f, its epigraph is convex, and minimizing f is equivalent to minimizing the auxiliary variable t within that epigraph.With multiple functions, the formulation can use multiple auxiliary variables.Source: A. Epigraph form of the constrained… · p. 3
• An auxiliary vector t reformulates the problem over Θ = X × R^n, replacing local objectives with constraints and giving every node the same linear objective f0.The resulting common objective is the sum of identical local objectives, so the aggregate objective is F(y) = n f0(y).Source: A. Epigraph form of the constrained… · p. 3

B. Distributed random-fixed projected algorithm

• D-RFP combines neighbor-state updates and DGD intermediate vectors with Polyak projections toward randomly selected constraint sets and a fixed projection on X0_j × T_j each iteration.The fixed projection ensures both x and t are updated each iteration; the step size ζ_k satisfies a persistent exciting condition.Source: B. Distributed random-fixed projected… · pp. 3–4
• After agreement, each node’s state vector asymptotically converges to a feasible point.The passage states this result without specifying the conditions, which are proved in the next section.Source: B. Distributed random-fixed projected… · p. 4
• Unlike the distributed randomized-projection method [10], D-RFP always projects onto X0_j × T_j, preventing iterations that leave t unchanged and may cause slow convergence or undesirable transients.The paper explains that constraints g_j(x) do not depend on t, so selecting one of them for projection would otherwise leave t unchanged.Source: B. Distributed random-fixed projected… · p. 4
• D-RFP also relates to alternating projection: projections may be repeated within an iteration or directed toward the constraint set farthest from the intermediate vector.The stated rationale is that repeated projections to differently selected sets move the state toward their intersection.Source: B. Distributed random-fixed projected… · p. 4

A. Assumptions and Convergence

• The convergence proof uses the reformulated problem (16), with θ = (x, t) in R^d, d = m + n, and convex local objectives and constraint functions.The paper states that proving convergence of the resulting iteration (17) suffices.Source: A. Assumptions and Convergence · pp. 4–5
• Constraint-component selections are i.i.d., uniform over each node’s components, and independent across nodes; the specified subgradients are uniformly bounded on Θ.These conditions comprise Assumption 1.Source: A. Assumptions and Convergence · p. 5
• The centralized problem must be feasible and have a nonempty set of optimal solutions.These are the solvability conditions in Assumption 2.Source: A. Assumptions and Convergence · p. 5
• The time-varying graphs must be uniformly jointly strongly connected: unions over every B-step window are strongly connected.This condition ensures information can pass directly or indirectly between any nodes during each such window.Source: A. Assumptions and Convergence · p. 5
• Every positive communication weight must be bounded away from zero by a positive interaction-strength constant.The paper explains that this prevents an available interaction from being too weak.Source: A. Assumptions and Convergence · p. 5
• Under Assumptions 1–4, the iterates almost surely converge to a common optimal solution of (16).Theorem 1 places the limit in Θ∗, the set of optimal solutions.Source: A. Assumptions and Convergence · p. 5

Asymptotic consensus

• A consensus lemma shows that node states asymptotically agree when the communication matrices satisfy Assumptions 3–4.The proof bounds disagreement using a stable recursion whose perturbations vanish.Source: B. Proof of Theorem 1 · pp. 5–6

Asymptotic feasibility

• Iterative projections ensure local feasibility by making distance to the intersection of the relevant convex sets nonincreasing.The proof uses this property to show that the state approaches a feasible solution when the auxiliary sequence’s successive differences vanish.Source: B. Proof of Theorem 1 · p. 6

Stochastic decrease

• A stochastic decrease result controls the distance to any optimal point almost surely, using supermartingale convergence.This supplies the optimality component of the proof’s three-part argument.Source: B. Proof of Theorem 1 · pp. 5–6

Theorem 1

• Theorem 1 establishes that the iterates for every agent j ∈ V converge almost surely to the same point θ*₀ in the optimal set Θ*.The proof shows consensus and convergence of the distance to an optimal point, then uses a subsequence converging almost surely to a point in Θ*.Source: B. Proof of Theorem 1 · p. 7

V. CONCLUSION

• The authors developed a structural algorithm to collaboratively solve distributed constrained optimization problems over time-varying unbalanced digraphs.The paper characterizes the algorithm as simple.Source: §V · p. 7
• Convergence results for the proposed algorithm are rigorously established using stochastic theory.Source: §V · p. 7
• The algorithm's number of augmented variables depends on the scale of the topology, consistent with previous research on the topic.Source: §V · p. 7
• Future work will seek to reduce the number of augmented variables and speed up the convergence rate.Source: §V · p. 7