Prediction-Correction Dual Ascent for Time-Varying Convex Programs

Abstract

We develop a prediction-correction dual ascent algorithm that tracks the optimal primal-dual pair of linearly constrained time-varying convex programs. This is especially useful, e.g., for time-varying distributed optimization problems. We prove that our discrete time algorithm has better asymptotical error bound than state-of-the-art methods, which only correct their approximate primal-dual pair without predicting how this changes with time. In numerical simulations, we show that the improvement in accuracy still holds even when computational considerations are taken into account, in almost all cases.