A distributed Newton's method for joint multi-hop routing and flow control: Theory and algorithm
A distributed Newton's method for joint multi-hop routing and flow control: Theory and algorithm
复制标题
DOI：
10.1109/infcom.2012.6195640
复制
发表时间：
2012-03
期刊：
影响因子：
--
通讯作者：
Jia Liu;H. Sherali
中科院分区：
文献类型：
--
作者：
Jia Liu;H. Sherali
当前通信网络快速增长的规模和异构性要求设计分布式跨层优化算法。目前，分布式跨层设计的标准方法是基于对偶分解和子梯度算法，这是一种收敛速度慢的一阶方法。本文设计了一种新的分布式牛顿方法，该方法是一种二阶方法，具有二次收敛速度，主要用于解决联合多路径路由和流量控制问题。开发分布式牛顿方法的主要挑战在于分散原始牛顿方向和对偶变量更新的Hessian矩阵及其逆的计算。通过适当地重新表述、重新安排和利用特殊的问题结构，我们表明可以将这些计算分解为网络中的源节点和链接，从而消除对全局信息的需求。此外，我们导出了原始牛顿方向和对偶变量更新的封闭表达式，从而大大降低了计算复杂度。我们提出的分布式牛顿方法最吸引人的特点是，它需要与一阶方法几乎相同的信息交换规模，同时实现与集中式牛顿方法相同的二次收敛率。我们提供了大量的数值结果来证明我们提出的算法的有效性。我们的工作有助于跨层网络设计的先进范式转变，从一阶方法发展到二阶方法。
The fast growing scale and heterogeneity of current communication networks necessitate the design of distributed cross-layer optimization algorithms. So far, the standard approach of distributed cross-layer design is based on dual decomposition and the subgradient algorithm, which is a first-order method that has a slow convergence rate. In this paper, we focus on solving a joint multi-path routing and flow control (MRFC) problem by designing a new distributed Newton's method, which is a second-order method and enjoys a quadratic rate of convergence. The major challenges in developing a distributed Newton's method lie in decentralizing the computation of the Hessian matrix and its inverse for both the primal Newton direction and dual variable updates. By appropriately reformulating, rearranging, and exploiting the special problem structures, we show that it is possible to decompose such computations into source nodes and links in the network, thus eliminating the need for global information. Furthermore, we derive closed-form expressions for both the primal Newton direction and dual variable updates, thus significantly reducing the computational complexity. The most attractive feature of our proposed distributed Newton's method is that it requires almost the same scale of information exchange as in first-order methods, while achieving a quadratic rate of convergence as in centralized Newton methods. We provide extensive numerical results to demonstrate the efficacy of our proposed algorithm. Our work contributes to the advanced paradigm shift in cross-layer network design that is evolving from first-order to second-order methods.