Decentralized Prediction-Correction Methods for Networked Time-Varying Convex Optimization

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

Research output: Contribution to journalArticleScientificpeer-review

24 Citations (Scopus)

Abstract

We develop algorithms that find and track the optimal solution trajectory of time-varying convex optimization problems that consist of local and network-related objectives. The algorithms are derived from the prediction-correction methodology, which corresponds to a strategy where the time-varying problem is sampled at discrete time instances, and then, a sequence is generated via alternatively executing predictions on how the optimizers at the next time sample are changing and corrections on how they actually have changed. Prediction is based on how the optimality conditions evolve in time, while correction is based on a gradient or Newton method, leading to decentralized prediction-correction gradient and decentralized prediction-correction Newton. We extend these methods to cases where the knowledge on how the optimization programs are changing in time is only approximate and propose decentralized approximate prediction-correction gradient and decentralized approximate prediction-correction Newton. Convergence properties of all the proposed methods are studied and empirical performance is shown on an application of a resource allocation problem in a wireless network. We observe that the proposed methods outperform existing running algorithms by orders of magnitude. The numerical results showcase a tradeoff between convergence accuracy, sampling period, and network communications.
Original languageEnglish
Pages (from-to)5724-5738
Number of pages15
JournalIEEE Transactions on Automatic Control
Volume62
Issue number11
DOIs
Publication statusPublished - 2017

Keywords

  • Distributed algorithms
  • optimization methods
  • time-varying optimization

Fingerprint Dive into the research topics of 'Decentralized Prediction-Correction Methods for Networked Time-Varying Convex Optimization'. Together they form a unique fingerprint.

Cite this