Distributed Approximate Newton Algorithms and Weight Design for Constrained Optimization

Chin-Yao Chang, Tor Anderson, Sonia Martinez

Research output: Contribution to journalArticlepeer-review

23 Scopus Citations

Abstract

Motivated by economic dispatch and linearly-constrained resource allocation problems, this paper proposes a class of novel distributedapprox − Newton algorithms that approximate the standard Newton optimization method. We first develop the notion of an optimal edge weighting for the communication graph over which agents implement the second-order algorithm, and propose a convex approximation for the nonconvex weight design problem. We next build on the optimal weight design to develop a DISCRETE DISTRIBUTED APPROX-NEWTON algorithm which converges linearly to the optimal solution for economic dispatch problems with unknown cost functions and relaxed local box constraints. For the full box-constrained problem, we develop a CONTINUOUS DISTRIBUTED APPROX-NEWTON algorithm which is inspired by first-order saddle-point methods and rigorously prove its convergence to the primal and dual optimizers. A main property of each of these distributed algorithms is that they only require agents to exchange constant-size communication messages, which lends itself to scalable implementations. Simulations demonstrate that the distributedapprox − Newton algorithms with our weight design have superior convergence properties compared to existing weighting strategies for first-order saddle-point and gradient descent methods.

Original languageAmerican English
Article number108538
Number of pages14
JournalAutomatica
Volume109
DOIs
StatePublished - 2019

Bibliographical note

Publisher Copyright:
© 2019 Elsevier Ltd

NREL Publication Number

  • NREL/JA-5D00-74927

Keywords

  • Distributed optimization
  • Multi-agent systems
  • Networked systems
  • Resource allocation
  • Second-order methods

Fingerprint

Dive into the research topics of 'Distributed Approximate Newton Algorithms and Weight Design for Constrained Optimization'. Together they form a unique fingerprint.

Cite this