PaperlayerView exact revision on arXiv

Source-linked AI summary

A Distributed Newton Method for Network Utility Maximization

Ermin Wei, Asuman Ozdaglar, Ali Jadbabaie

arXiv:1005.2633v2math.OCcs.SYeess.SY

TL;DR

Distributed NUM methods based on dual decomposition and subgradients can converge slowly. This paper develops a distributed Newton method using matrix splitting and limited information exchange. Even with errors in direction and stepsize computation, it achieves superlinear convergence to an error neighborhood, with simulations showing improvement over traditional distributed methods.

  • Problem

    Existing distributed NUM methods commonly use dual decomposition and subgradients, which have slow convergence.

    Source: §1 · p. 2

  • Method

    The paper uses matrix splitting to compute Newton updates in a decentralized manner with limited information exchange.

    Source: §1 · p. 2

  • Results

    With errors in the Newton direction and stepsize, primal iterations converge superlinearly to an error neighborhood, and simulations show significant improvement over traditional distributed NUM algorithms.

    Source: §1 · p. 3, §7 · p. 47

  • Takeaways & Limitations

    The method uses an information-exchange mechanism similar to first-order NUM methods while retaining distributed Newton updates.

    Source: §7 · pp. 46–47

    The convergence setup assumes bounded, strictly positive primal iterates so the Hessian remains invertible.

    Source: §3.2 · p. 8

Abstract

from arXiv · show

Most existing work uses dual decomposition and subgradient methods to solve Network Utility Maximization (NUM) problems in a distributed manner, which suffer from slow rate of convergence properties. This work develops an alternative distributed Newton-type fast converging algorithm for solving network utility maximization problems with self-concordant utility functions. By using novel matrix splitting techniques, both primal and dual updates for the Newton step can be computed using iterative schemes in a decentralized manner with limited information exchange. Similarly, the stepsize can be obtained via an iterative consensus-based averaging scheme. We show that even when the Newton direction and the stepsize in our method are computed within some error (due to finite truncation of the iterative schemes), the resulting objective function value still converges superlinearly to an explicitly characterized error neighborhood. Simulation results demonstrate significant convergence rate improvement of our algorithm relative to the existing subgradient methods based on dual decomposition.

1 Introduction

The paper addresses slow convergence in distributed NUM methods based on dual decomposition and subgradients. It develops a distributed Newton approach whose inexact computations still yield superlinear convergence to a controllable error neighborhood.

1 Introduction

  • Standard dual-decomposition and subgradient methods are distributed but converge slowly for NUM problems.They use price exchanges between sources and links.Source: §1 · p. 2
  • A matrix-splitting scheme enables decentralized Newton-direction computation through limited scalar information exchange between sources and links.Destinations send route prices to sources, which send Hessian-scaled route prices to links.Source: §1 · p. 2
  • A distributed inexact Newton decrement is computed in finitely many steps using the information-exchange mechanism of first-order methods.The stepsize uses the inverse decrement above a threshold and a pure Newton step otherwise.Source: §1 · pp. 2–3
  • Inexact Newton directions and stepsizes still yield superlinear convergence to an explicitly characterized neighborhood of the optimal objective value.The neighborhood size depends on the computation errors and their bounds.Source: §1 · p. 3
  • The method uses an inexact-Newton analysis that permits fixed per-step direction error, unlike analyses requiring error to vanish for convergence to the exact optimum.The resulting error neighborhood can be controlled by algorithm parameters.Source: §1 · p. 4

2 Network Utility Maximization Problem

The paper formulates wireline rate control as maximizing summed source utilities subject to link capacities. It uses self-concordant utilities and a slack-variable, logarithmic-barrier reformulation to obtain an equality-constrained problem for Newton methods.

2 Network Utility Maximization Problem

  • NUM chooses nonnegative source rates to maximize summed utilities subject to link-capacity constraints.Each source sends information over a predetermined route through a network of finite-capacity links.Source: §2 · p. 5
  • The utility assumptions are strict concavity, monotonic nondecrease, and self-concordance of the negative utilities.The paper notes that logarithmic and concave quadratic utilities satisfy the self-concordance assumption.Source: §2 · p. 6
  • Nonnegative slack variables convert link-capacity inequalities into equalities, while logarithmic barriers handle nonnegativity constraints.The resulting objective is separable and has a positive definite diagonal Hessian for barrier coefficient µ ≥ 1.Source: §2 · pp. 6–7
  • As barrier coefficient µ approaches zero, the reformulated problem's solution approaches the original problem's solution; two instances can bound the resulting objective error.The paper develops its Newton method for µ ≥ 1 to preserve self-concordance.Source: §2 · p. 7

3 Exact Newton Method

The exact method applies a feasible-start equality-constrained Newton method to the barrier reformulation. Its iterates preserve feasibility, starting from a feasible positive vector, but computing the dual direction centrally requires a global matrix inverse.

3 Exact Newton Method

  • For the feasible barrier problem, strong duality and full row rank support use of a feasible-start equality-constrained Newton method.The problem has no duality gap and admits a dual optimal solution.Source: §3 · p. 7

3.1 Feasible Initialization

  • The algorithm starts from a feasible, strictly positive vector; the paper gives an initialization using link capacities, the source count, and the routing matrix.The stated initialization is an example, not the only feasible start.Source: §3.1 · p. 7

3.2 Iterative Update Rule

  • Each update takes a positive stepsize along a primal Newton direction, with the dual vector representing prices for link-capacity constraints.Computing the dual-step vector directly requires a global matrix inverse, motivating the following distributed inexact method.Source: §3.2 · p. 8

4 Distributed Inexact Newton Method

The section describes a distributed inexact Newton method that uses iterative schemes to compute dual variables and primal updates while preserving feasibility. It also presents a stepsize rule and error bounds designed to maintain strict positivity and support local superlinear convergence to an error neighborhood.

4 Distributed Inexact Newton Method

  • The section introduces a distributed Newton method that computes each dual vector through matrix-splitting iteration.The method’s dual computation is implemented through iterative updates.Source: §4 · p. 9

4.1 Preliminaries on Matrix Splitting

  • Matrix-splitting iteration solves a linear system when the iteration matrix has spectral radius below 1; strict diagonal dominance with positive diagonal entries supplies a sufficient condition.For the dual computation, the authors use this condition to establish convergence of their chosen splitting.Source: §4.1 · pp. 9–10

4.2 Distributed Computation of the Dual Vector

  • The dual iteration converges to the solution of Eq. (11), with the splitting chosen to ensure a spectral radius below 1.Its diagonal matrix splitting avoids global information for the inverse; the dual routing graph’s spectral properties govern convergence speed.Source: §4.2 · pp. 10–12

4.3 Distributed Computation of the Primal Newton Direction

  • The feasible inexact Newton update combines an iteratively computed dual vector with a two-stage primal direction that enforces AΔ˜xk = 0.The first stage computes source components using the iterated dual variables; the second computes slack-variable components to satisfy the equality constraint.Source: §4.3 · p. 16

4.4 Stepsize Rule

  • The distributed stepsize rule uses an approximate inexact Newton decrement and is designed to maintain positive primal iterates while achieving local superlinear convergence to an error neighborhood.The rule allows errors from both the iterative dual computation and the approximate decrement used to set the stepsize.Source: §4.4 · p. 17
  • Distributed iteration counts can ensure the Newton-direction error meets its bound, while average-consensus steps can bound decrement error; Appendix A yields zero decrement error, and the consensus rate uses,.The direction-error bound includes a positive constant ϵ, avoiding a requirement that the error vanish near the optimum.Source: §4.4 · p. 18
  • For θk ≥ V, Lemma 4.5 bounds the stepsize factor bθk + 1 in terms of the inexact Newton decrement and b.The bound is used to establish positivity of the primal iterates.Source: §4.4 · pp. 18–19
  • Starting from a strictly positive feasible x0, the method keeps every primal vector strictly positive when it uses the specified stepsize rule and b satisfies the theorem’s stated interval.This ensures the Hessian and inexact Newton direction remain well-defined at each iteration.Source: §4.4 · pp. 18–20

5 Convergence Analysis

This section analyzes convergence of the dual iterations and the primal sequence generated by the inexact Newton method, including its damped and quadratic phases and convergence to an error neighborhood. It also bounds suboptimality relative to the barrier parameter µ and shows how two algorithm runs can make the barrier-induced relative error arbitrarily small.

5.1 Convergence in Dual Iterations

  • The dual iteration’s convergence speed is determined by λ1, the eigenvalue of its iteration matrix M with largest magnitude.Source: §5.1 · p. 21
  • A large weighted maximum cut gives a large lower bound on λ1, while a small maximum weighted out-degree gives a small upper bound and suggests faster convergence.Source: §5.1 · p. 22
  • The less-congested Figure 7 network had λ1 bounds [0.096, 0.19] and numerical value 0.12, versus [0.30, 0.92] and 0.47 for Figure 5.Source: §5.1 · p. 22, Figure 5 · p. 23, Figure 7 · p. 24

5.2 Convergence in Primal Iterations

  • For primal iterates, the self-concordant objective along the Newton direction measures each iteration’s objective decrease.Source: §5.2 · p. 25

5.2.1 Preliminaries

  • An isomorphism maps equality-constrained Newton directions to an unconstrained problem; an inexact-direction decrement lemma captures step-error effects and supports a quadratic convergence guarantee.Source: §5.2.1 · pp. 25, 27, 30
  • For self-concordant objectives, a sufficiently small exact Newton decrement, λ(x) ≤ 0.68, enables suboptimality-gap bounds used in the two-phase convergence analysis.The damped phase bounds per-step improvement, while the quadratic phase reduces suboptimality quadratically to an error level.Source: §5.2.1 · p. 30

5.2.2 Basic Relations

  • The basic relations bound Newton-direction computation error and show that a careful stepsize choice guarantees a constant lower bound on objective improvement.These relations support both phases of the convergence analysis.Source: §5.2.2 · pp. 31–32

5.2.3 Damped Convergent Phase

  • In the damped phase, each iteration has a lower-bounded objective improvement; the bound improves as b approaches 1, provided decrement-computation error tends to zero.The algorithm’s stepsize d θk+1 approximates 1/(˜λ(xk) + 1), with bounded stepsize error.Source: §5.2.3 · p. 34

5.2.4 Quadratically Convergent Phase

  • With unit stepsizes after θ̄k < V, the primal objective converges quadratically to an explicitly characterized error neighborhood under Assumption 4.The analysis uses φ ≤ 0.267 to support the conditions for maintaining the decrement bound and establishing the quadratic rate.Source: §5.2.4 · pp. 35, 36, 38
  • The objective value converges quadratically in the primal iterations to a neighborhood of the optimum of size ξ + δ; exact Newton gives a zero-size neighborhood.For exact Newton, p = ϵ = 0, so ξ = 0 and δ can be chosen as 0.Source: §5.2.4 · p. 40

5.3 Convergence with respect to Design Parameter µ

  • Using a lemma and an argument similar to that in, the analysis establishes a result that bounds sub-optimality as a function of µ.Source: §5.3 · p. 40
  • Two runs of the algorithm can bound the barrier-induced relative error by any positive scalar, at the cost of running the fast Newton-type algorithm twice.The procedure first runs problem (4) with an arbitrary µ, then runs a rescaled version with µ = 1.Source: §5.3 · pp. 41–42

6 Simulation Results

Across 50 random networks, the distributed Newton method required substantially fewer iterations than the two comparison methods. On a sample network, it also outperformed them in objective-value convergence and maintained link feasibility throughout its iterations.

6 Simulation Results

  • The comparison used the subgradient method in and diagonal-scaling dual method in, both with constant stepsizes, and counted primal and dual iterations for Newton.The distributed Newton runs used specified error tolerances and counted the sum of dual iterations at each generated primal iterate.Source: §6 · pp. 42–43
  • The distributed Newton method significantly outperformed the subgradient and diagonal-scaling methods in objective-value convergence on the sample problem.Figure 10 plots objective values against log-scaled iteration count; the dotted lines mark the ±5% interval around the optimum.Source: §6 · p. 43, Figure 10 · p. 44
  • Distributed Newton iterates remained link-feasible throughout, while the other two methods became feasible only at the end.Figure 11 plots minimum link-capacity slack; negative slack indicates a capacity violation.Source: §6 · pp. 43, 46, Figure 11 · p. 45
  • 924, 20286, and 29315 mean termination iterations were reported for distributed Newton, Newton-type diagonal scaling, and subgradient methods, respectively.The means are over 50 randomly generated networks; Figure 12 presents the iteration counts on a log scale.Source: §6 · p. 46, Figure 12 · p. 46

7 Conclusions

The paper concludes that its distributed Newton method achieves superlinear convergence in primal iterations to an error neighborhood, even with errors in the computed Newton direction and stepsize. It identifies further analysis of network topology and fixed finite truncation as future directions.

7 Conclusions

  • The method achieves superlinear convergence in primal iterations to an error neighborhood when the Newton direction and stepsize are computed with some error.The conclusion also identifies decentralized computation of the dual Newton step through matrix splitting.Source: §7 · pp. 46–47
  • The scheme uses an information-exchange mechanism similar to that of first-order methods for this problem.The paper describes the dual Newton step as implementable in a decentralized manner using matrix splitting.Source: §7 · pp. 46–47
  • Future work includes analyzing how dual-iteration convergence relates to network topology and studying convergence with fixed finite truncation of dual iterations.Source: §7 · p. 47

A Distributed Stepsize Computation

The section presents a finite, decentralized procedure for computing the stepsize by aggregating the inexact Newton decrement from source- and link-local information, using an auxiliary graph to avoid over-counting. It makes the resulting value available to sources and links through route-based exchange, contrasting this approach with spanning-tree methods that rely on a designated root.

A Distributed Stepsize Computation

  • The stepsize computation reduces to distributed summation of the inexact Newton decrement, with an auxiliary graph construction designed to avoid over-counting.The procedure aggregates information available on sources and links using the feedback mechanism of first-order methods.Source: A Distributed Stepsize Computation · pp. 47, 52
  • The auxiliary graph connects sources that share links and is constructed in S −1 iterations; its topology depends only on the network and need be computed once.It is independent of utility functions and link capacities.Source: A Distributed Stepsize Computation · pp. 47, 48, 52
  • The auxiliary graph is connected, and its only possible simple cycles consist of edges with the same label; merging those cycles yields a tree.The proof establishes that the resulting connected graph has N −1 edges and is acyclic.Source: A Distributed Stepsize Computation · pp. 49, 52
  • The summation procedure runs for S iterations: sources send route values, links use values from sources on them, and sources aggregate information from inducing links.The procedure uses local route and link information to compute the required values.Source: A Distributed Stepsize Computation · pp. 53–54
  • For distinct sources i and j in Θ_l, their t-hop neighborhoods intersect exactly in the union of the (t −1)-hop neighborhoods of sources in Θ_l.This auxiliary-graph identity is used to establish that the distributed summation procedure yields correct values.Source: A Distributed Stepsize Computation · p. 54
  • For distinct l and m in L∗(i), the corresponding unions of neighborhoods intersect exactly at N_i(t).This overlap relation supports the inclusion-exclusion argument used to establish the summation iterates.Source: A Distributed Stepsize Computation · p. 54
  • After S−1 iterations, the summation procedure makes (˜λ(x^k))^2 available to all sources and links.At termination, each source i has y_i(S) and each link l has z_l(S−1) equal to this value.Source: A Distributed Stepsize Computation · pp. 56, 58
  • The iteration bound can be reduced to the auxiliary graph’s diameter plus one when that diameter or an upper bound is known.A complete auxiliary graph needs 2 iterations, whereas a line takes S iterations.Source: A Distributed Stepsize Computation · p. 58
  • Unlike spanning-tree methods, the procedure aggregates scalar information along routes and feeds it back independently to sources, without requiring predecessor or successor information.Links need only maintain their sets Θ_l, obtained from the auxiliary graph.Source: A Distributed Stepsize Computation · pp. 58–59

B Distributed Error Checking

The distributed error-checking procedure uses two stages to determine when dual iterations have met the prescribed error tolerance. It relies on aggregate network information and distributed computations to test the required conditions.

B Distributed Error Checking

  • The method assumes a known bound F < 1 on the spectral radius of a matrix formed from the dual iteration matrices.The paper states that this bound can be obtained from the dual-graph structure, requiring only aggregate information.Source: B Distributed Error Checking · p. 59
  • The error-checking procedure first runs a predetermined number of dual iterations, then continues with further iterations if its termination criterion is not yet met.Stage 1 applies Theorem B.2; Stage 2 applies Theorem B.3 and continues until its criterion is satisfied.Source: B Distributed Error Checking · pp. 59, 63
  • Stage 2 terminates after finitely many iterations for any positive h, given convergence of the dual-iterate sequence.The paper notes that Stage 1 is more efficient to check and recommends choosing p relatively large to reduce entry into Stage 2.Source: B Distributed Error Checking · pp. 63, 65
  • Stage 1 checks the relative-error term, while Stage 2 checks the additional tolerance term when Stage 1 has not terminated the dual iterations.If Stage 1 terminates, the stated assumption is satisfied for any positive ϵ.Source: B Distributed Error Checking · p. 64
  • The error-checking quantities can be computed distributively using local Hessian information, route prices, and maximum consensus.The procedure uses maximum consensus to obtain the change in the dual iterate and to compute its checking values.Source: B Distributed Error Checking · p. 64
Loading 1005.2633v2…