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.
As detailed in the algorithm above, the framework consists of two primary phases:
- Prediction: Estimating the next state $x_{k+1|k}$ using a first-order Taylor expansion of the optimality condition.
- Correction: Refining the estimate using iterative steps.
- GTT (Gradient Trajectory Tracking): Employs gradient descent steps for correction, achieving $O(h^2)$ error.
- 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.
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