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

Conference paper (2016)

Authors

A. Simonetto Signal Processing Systems - EEMCS
Alec Koppel University of Pennsylvania
Aryan Mokhtari University of Pennsylvania
G.J.T. Leus Signal Processing Systems - EEMCS
Alejandro Ribeiro University of Pennsylvania
Research Group
Signal Processing Systems (EEMCS) (TU Delft)
Optimization Linear programming Approximation algorithms Heuristic algorithms Trajectory Prediction algorithms Convex Functions
More Info
expand_more

Published Date

2016

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Microelectronics

Research Group

Signal Processing Systems

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.