Weight design of distributed approximate Newton algorithms for constrained optimization

Tor Anderson, Chin-Yao Chang and Sonia Martínez
Proceedings of the 1st IEEE Conference on Control Technology and Applications, Maui, HW, USA, August 2017 MN, USA, August 2017

Abstract:

This paper presents a distributed algorithm to solve a class of separable, linearly-constrained resource allocation problems. 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 a novel algorithm to approximate the Newton step with only distributed communication. The convergence of this algorithm is discussed and rigorously analyzed. In addition, we 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. demonstrate that our proposed weight design has a superior convergence property compared to existing gradient-inspired weight design applied to the Distributed Gradient Descent method.

File: main.pdf

Bib-tex entry:

@InProceedings{TA-CYC-SM:17-ccta},
author = {T. Anderson and C.-Y. Chang and S. Mart{\'\i}nez},
booktitle = {IEEE Conference on Control Technology and Applications},
title = { Weight design of distributed approximate Newton algorithms for constrained optimization},
pages ={632--637},
month = {August},
year = {2017},
address ={Maui, HW}
}