A Quasi-Newton Prediction-Correction Method for Decentralized Dynamic Convex Optimization

Andrea Simonetto, Alec Koppel, Aryan Mokhtari, Geert Leus, Alejandro Ribeiro

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

3 Citations (Scopus)

Abstract

We introduce DeNT, a decentralized Newton-based tracking algorithm that solves and track the solution trajectory of continuously varying networked convex optimization problems. DeNT is derived from the prediction-correction methodology, by which the time-varying optimization problem is sampled at discrete time instances and then a sequence is generated via alternatively executing predictions on how the optimizers are changing and corrections on how they actually have changed. Prediction is based on the sample dynamics of the optimality conditions, while correction is based on a Newton method. After presenting DeNT, we show how it can be implemented in a decentralized way and analyze its convergence. We extend it to cases in which the knowledge on how the optimization programs are changing in time is only approximate, proposing DeANT. We then present an application to a resource allocation problem in a wireless network, demonstrating the proposed method outperforms existing methods by orders of magnitude, and exhibits a trade-off between convergence accuracy, sampling interval, and network communications.
Original languageEnglish
Title of host publicationProceedings 2016 European Control Conference (ECC)
Place of PublicationPiscataway, NJ
PublisherIEEE
Pages1934-1939
Number of pages6
ISBN (Electronic)978-1-5090-2591-6
DOIs
Publication statusPublished - 2016
Event2016 European Control Conference, ECC 2016: 15th annual European Control Conference - Aalborg, Denmark
Duration: 29 Jun 20161 Jul 2016
http://www.ecc16.eu/index.shtml

Conference

Conference2016 European Control Conference, ECC 2016
Abbreviated titleECC'16
CountryDenmark
CityAalborg
Period29/06/161/07/16
Internet address

Keywords

  • Linear programming
  • Optimization
  • Approximation algorithms
  • Prediction algorithms
  • Heuristic algorithms
  • Convex Functions
  • Trajectory

Fingerprint Dive into the research topics of 'A Quasi-Newton Prediction-Correction Method for Decentralized Dynamic Convex Optimization'. Together they form a unique fingerprint.

Cite this