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

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.