A distributed line search for network optimization

Michael Zargham, Alejandro Ribeiro, Ali Jadbabaie

Abstract

Dual descent methods are used to solve network optimization problems because descent directions can be computed in a distributed manner using information available either locally or at neighboring nodes. However, choosing a stepsize in the descent direction remains a challenge because its computation requires global information. This work presents an algorithm based on a local version of the Armijo rule that allows for the computation of a stepsize using only local and neighborhood information. We show that when our distributed line search algorithm is applied with a descent direction computed according to the Accelerated Dual Descent method, key properties of standard backtracking line search using the Armijo rule are recovered. We use simulations to demonstrate that our algorithm is a practical substitute for its centralized counterpart.

The Challenge of Distributed Stepsize Selection

In network optimization tasks, such as managing data flow across a graph, dual descent methods are favored for their ability to allow nodes to calculate descent directions using local information. However, a significant bottleneck persists: the selection of an appropriate stepsize. Standard techniques, such as the Armijo rule, typically require knowledge of the global objective value to determine the optimal distance to move in a given direction.

In a distributed environment, gathering this global information necessitates expensive consensus iterations. These iterations are often slow and can negate the performance benefits of advanced Newton-type algorithms. Consequently, many distributed systems rely on fixed, sub-optimal stepsizes, which leads to sluggish convergence. This research aims to bridge this gap by introducing a line search mechanism that is as distributed as the descent direction itself.

The proposed algorithm is a Distributed Backtracking Line Search based on a localized version of the Armijo rule. The methodology involves several key components:

  1. Objective Decomposition: The global dual objective function is decomposed into a sum of local objectives for each individual node.
  2. Local Armijo Rule: Rather than evaluating a global exit condition, each node $i$ executes its own backtracking loop. It verifies a local condition using only information from its $N$-hop neighbors (nodes reachable within $N$ steps).
  3. Step Selection: Each node computes a local stepsize $\alpha_i$. The final stepsize for the entire network is determined as the minimum of these local values ($\alpha = \min \alpha_i$), which can be efficiently calculated via a simple minimum consensus protocol.
  4. Integration with ADD-N: The method is specifically designed to pair with the Accelerated Dual Descent (ADD-N) algorithm. By aligning the information requirements of both the descent direction and the line search (both using $N$-hop information), communication overhead is minimized.

Experimental Evaluation and Key Insights

The algorithm was evaluated using synthetic simulations of network flow problems across various topologies and scales, ranging from small (25 nodes) to large (100 nodes). A convex cost function was utilized to model edge capacities.

Comparison of centralized and distributed line search performance across objective value, feasibility, and stepsize.

The simulations revealed a high degree of functional equivalence between the distributed line search and its centralized counterpart. As shown in the performance trajectories above, the distributed approach achieves nearly identical results in terms of primal objective optimization and feasibility.

A critical insight of this work is the preservation of the "Unit Stepsize Phase." In second-order methods like Newton's method, achieving a stepsize of 1 near the optimum is essential for quadratic convergence. The authors proved that their distributed version retains this property, ensuring that the speed of second-order methods is not sacrificed.

Average iterations required to reach unit stepsize for various network sizes and algorithm parameters.

As illustrated in the experimental results, the algorithm typically requires only 2 to 3 iterations to reach a unit stepsize across most test cases, regardless of network size. This efficiency highlights the algorithm's scalability and its potential as a practical substitute for centralized methods.

Conclusion and Future Directions

The distributed line search algorithm provides a formal guarantee of a strict decrease in the optimization objective at every step when outside the optimal neighborhood. While the method demonstrates strong performance, its theoretical proofs currently rely on the sparsity structure of the Hessian approximation in the ADD-N algorithm.

Future work may explore the application of this framework to other descent directions and investigate the potential of non-monotone line searches in distributed contexts. Additionally, while the minimum consensus step for determining the global stepsize is faster than a full objective evaluation, its scaling with network diameter remains an area for potential optimization.

Summary updated

BibTeX
@inproceedings{zargham2012distributed,
  author = {Michael Zargham and Alejandro Ribeiro and Ali Jadbabaie},
  title = {{A distributed line search for network optimization}},
  booktitle = {ACC},
  year = {2012},
  doi = {10.1109/acc.2012.6314986},
}
Figure