A decentralized prediction-correction method for networked time-varying convex optimization

We study networked unconstrained convex optimization problems where the objective function changes continuously in time. We propose a decentralized algorithm (DePCoT) with a discrete time-sampling scheme to find and track the solution trajectory based on prediction and gradient-based correction steps, while sampling the problem data at a constant sampling period h. Under suitable conditions and for limited sampling periods, we establish that the asymptotic error bound behaves as O(h²), which outperforms the state of the art existing error bound of O(h) for correction-only methods. The key contributions are the prediction step and a decentralized method to approximate the inverse of the Hessian of the cost function in a decentralized way, which yields quantifiable trade-offs between communication and accuracy.