A Class of Prediction-Correction Methods for Time-Varying Convex Optimization

Andrea Simonetto, Aryan Mokhtari, Alec Koppel, Geert Leus, Alejandro Ribeiro

Abstract

This paper introduces a family of prediction-correction algorithms designed to track the optimal solutions of time-varying convex optimization problems. By leveraging the iso-residual dynamics of the optimality conditions, the proposed methods—Gradient Trajectory Tracking (GTT) and Newton Trajectory Tracking (NTT)—achieve significantly higher tracking accuracy than standard running methods. Theoretical analysis and numerical simulations demonstrate that these methods improve tracking error from $O(h)$ to $O(h^2)$ and $O(h^4)$, respectively, where $h$ is the sampling period.

The Challenge of Time-Varying Optimization

In many real-time applications, such as robotics and power grid management, the objective function $f(x; t)$ changes over time. Solving these problems from scratch at each time step is often computationally prohibitive. Existing "running" methods typically apply a single gradient step per sampling interval $h$, resulting in a tracking error that is linearly proportional to the sampling period ($O(h)$). This paper seeks to close this gap by achieving much higher precision without requiring faster hardware or higher sampling frequencies.

The Prediction-Correction Framework

The core contribution is a framework that predicts the optimizer's movement before correcting it. The prediction step uses the "iso-residual dynamics"—the mathematical relationship defining how the optimal solution $x^*(t)$ moves to keep the gradient $ abla_x f(x; t)$ at zero. By analyzing how the gradient changes with respect to both $x$ and $t$, the authors derive a velocity for the optimal solution.

Algorithm for Prediction-Correction Trajectory Tracking

As detailed in the algorithm above, the framework consists of two primary phases:

  1. Prediction: Estimating the next state $x_{k+1|k}$ using a first-order Taylor expansion of the optimality condition.
  2. Correction: Refining the estimate using iterative steps.
  3. GTT (Gradient Trajectory Tracking): Employs gradient descent steps for correction, achieving $O(h^2)$ error.
  4. NTT (Newton Trajectory Tracking): Employs Newton steps, leveraging second-order information to reach $O(h^4)$ error.

Key Results and Theoretical Bounds

The authors prove that by incorporating the time-drift into the prediction step, the tracking error is decoupled from the sampling period's linear drift. This leads to a massive improvement in precision for a similar computational cost.

Worst-case tracking error as a function of the sampling period h

As shown in the figure, the proposed GTT and NTT methods follow the predicted $O(h^2)$ and $O(h^4)$ slopes, respectively. In numerical simulations, the NTT algorithm achieved a tracking error near $10^{-10}$, while the standard Running Gradient (RG) baseline stayed around $10^{-2}$. This represents an eight-order-of-magnitude improvement in precision.

Practical Considerations and Future Work

One of the most practical findings is that users do not need to know the analytical time-derivative of the cost function. The authors propose Approximate versions (AGT/ANT) that use simple finite differences to estimate these changes, proving that high-order accuracy is maintained even with this estimation.

While the current work focuses on unconstrained optimization, the framework's success with Newton-type corrections suggests significant potential for complex real-time autonomous systems. Future research directions include extending these methods to constrained problems using projections or interior-point methods.

Summary updated

Abstract

This paper considers unconstrained convex optimization problems with time-varying objective functions. We propose algorithms with a discrete time-sampling scheme to find and track the solution trajectory based on prediction and correction steps, while sampling the problem data at a constant rate of $1/h$, where $h$ is the length of the sampling interval. The prediction step is derived by analyzing the iso-residual dynamics of the optimality conditions. The correction step adjusts for the distance between the current prediction and the optimizer at each time step, and consists either of one or multiple gradient steps or Newton steps, which respectively correspond to the gradient trajectory tracking (GTT) or Newton trajectory tracking (NTT) algorithms. Under suitable conditions, we establish that the asymptotic error incurred by both proposed methods behaves as $O(h^2)$, and in some cases as $O(h^4)$, which outperforms the state-of-the-art error bound of $O(h)$ for correction-only methods in the gradient-correction step. Moreover, when the characteristics of the objective function variation are not available, we propose approximate gradient and Newton tracking algorithms (AGT and ANT, respectively) that still attain these asymptotical error bounds. Numerical simulations demonstrate the practical utility of the proposed methods and that they improve upon existing techniques by several orders of magnitude.
BibTeX
@article{simonetto2015class,
  author = {Andrea Simonetto and Aryan Mokhtari and Alec Koppel and Geert Leus and Alejandro Ribeiro},
  title = {{A Class of Prediction-Correction Methods for Time-Varying Convex Optimization}},
  journal = {IEEE Trans. Signal Process.},
  year = {2015},
  doi = {10.1109/tsp.2016.2568161},
}
Figure