Weight design of distributed approximate Newton algorithms for constrained optimization
Weight design of distributed approximate Newton algorithms for constrained optimization
复制标题
约束优化分布式近似牛顿算法的权重设计
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Martínez
中科院分区：
文献类型：
--
作者：
Tor Anderson;Chin;S. Martínez
本文提出了一种分布式算法来解决经济调度问题，该问题的形式为线性约束资源分配问题。分布式基于梯度的方法通常用于解决这种形式的问题，它继承了缓慢的收敛。牛顿法是一种集中式方法，它使用二阶信息来提供更快的收敛速度。然而，在分布式环境中计算牛顿步长是困难的，并且通常需要所有对所有代理通信。在本文中，我们提出了分布式近似牛顿算法来近似牛顿步骤，只有分布式通信。对算法的收敛性进行了讨论和严格的分析。此外，我们的目标是解决问题的设计通信拓扑结构和权重是最佳的二阶方法。为此，我们提出了一种有效的近似，该近似松散地基于完成平方来解决设计中涉及的NP难双线性优化问题。仿真结果表明，我们提出的权重设计应用于分布式近似牛顿算法具有上级收敛性能相比，现有的梯度启发的权重设计应用于分布式梯度下降方法。
This paper presents a distributed algorithm to solve an economic dispatch problem, which takes the form of a linearly-constrained resource allocation problem. Distributed gradient-based methods are commonly used to solve problems of this form, which inherit slow convergence. The Newton method is a centralized alternative which uses second-order information to provide faster convergence. However, computing a Newton step is difficult in distributed settings and typically requires all-to-all agent communication. In this paper, we propose the distributed approx-Newton algorithm to approximate the Newton step with only distributed communication. The convergence of this algorithm is discussed and rigorously analyzed. In addition, we aim to address the problem of designing communication topologies and weightings that are optimal for second-order methods. To this end, we propose an effective approximation which is loosely based on completing the square to address the NP-hard bilinear optimization involved in the design. Simulations demonstrate that our proposed weight design applied to the distributed approx-Newton algorithm has a superior convergence property compared to existing gradient-inspired weight design applied to the Distributed Gradient Descent method.