Primal-Dual Prediction-Correction Method with Tunable Memory for Linearly Constrained Time-Varying Convex Optimization

This paper presents a primal-dual prediction-correction (PD-PC) method for solving linearly constrained time-varying convex optimization problems, which frequently arise in control, signal processing, and online learning applications. The proposed method establishes a novel integration of primal-dual gradient dynamics with a discrete-time prediction-correction structure, specifically designed for problems with time-dependent linear constraints. A tunable memory parameter is introduced in the prediction phase to perform linear extrapolation using past iterates, enabling a flexible trade-off between the amount of historical information stored and the computational cost of correction. In the correction phase, primal and dual variables are updated via gradient descent-ascent iterations, thus maintaining the computational efficiency of a first-order method without requiring Hessian or high-order derivative computations. Theoretical analysis shows that the method achieves O(h2) asymptotic tracking accuracy for both primal and dual variables, matching the state-of-the-art performance among first-order methods even in unconstrained settings. Numerical experiments on problems with both time-invariant and time-varying constraints validate the theoretical findings and demonstrate the method’s effectiveness.