Weight Design of Distributed Approximate Newton Algorithms for Constrained Optimization
This work addresses the need for faster distributed optimization in resource allocation problems, but the improvement is incremental over existing methods.
The paper proposes a Distributed Approximate Newton algorithm for constrained optimization problems like economic dispatch, requiring only constant-size message exchanges. The proposed weight design yields superior convergence compared to distributed first-order gradient descent methods.
Motivated by economic dispatch and linearly-constrained resource allocation problems, this paper proposes a novel Distributed Approx-Newton algorithm that approximates the standard Newton optimization method. A main property of this distributed algorithm is that it only requires agents to exchange constant-size communication messages. 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 weighted and distributed first-order gradient descent methods.