Weight design of distributed approximate Newton algorithms for constrained optimization
Tor Anderson, Chin-Yao Chang, Sonia Martı́nez · 2017 IEEE Conference on Control Technology and Applications (CCTA) · 2017
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.