In classical optimization, we treat the objective function as a static mountain range. The goal is simple: find the lowest valley and stay there. But in real-world deployments—such as tracking trajectories in robotics, managing fluctuating power grids, or training machine learning models on streaming data—the mountain range itself is constantly shifting, warping, and moving. This is the domain of time-varying optimization.
When an optimization landscape evolves over time, we are no longer looking for a single static point $x^*$, but rather an optimal trajectory $x^*(t)$ that minimizes a time-dependent objective function $f(x, t)$.
The naive way to handle a moving target is a "discrete restart" strategy: treat each time step as an independent problem and solve it from scratch. However, as noted by Andrea Simonetto et al. in Prediction-correction methods for time-varying convex optimization, this strategy is computationally prohibitive for real-time systems and completely discards the valuable temporal correlation between consecutive states. To build systems that adapt in real time, we must design algorithms that continuously track the moving optimum with minimal lag.
The Intuition of Prediction-Correction
Why do standard gradient descent or Newton methods fail when the objective function changes over time? If an algorithm only calculates a gradient or Hessian based on the current state, it is correcting for where the optimum was, not where it is going. By the time the algorithm takes a step, the landscape has already changed, resulting in a persistent tracking error.
To overcome this, researchers use prediction-correction methods. The core intuition is to split the algorithm's update into two distinct forces:
- Prediction: Anticipate how the optimum is drifting by evaluating the partial derivative of the objective function with respect to time ($\nabla_{tx}^2 f$). This pushes our estimate in the direction the landscape is moving.
- Correction: Run a standard optimization step (like a Newton or gradient step) to eliminate any residual error and pull the estimate closer to the exact instantaneous optimum.
[Current Estimate]
│
▼ (Prediction Step: Anticipates temporal drift ∇²_tx)
[Predicted Position]
│
▼ (Correction Step: Minimizes spatial error ∇_x)
[New Tracked Optimum]
Andrea Simonetto et al. demonstrated that incorporating this predictive step dramatically reduces tracking errors from $O(h)$ to $O(h^2)$ or better, where $h$ is the time step size. In continuous-time systems, Mahyar Fazlyab et al. showed in Prediction-Correction Interior-Point Method for Time-Varying Convex Optimization that this prediction-correction framework allows a dynamical system to achieve global exponential convergence to the moving optimum, driving the tracking error asymptotically to zero.
Navigating Moving Boundaries
The challenge intensifies when the constraints defining the feasible region are also time-varying ($g(x, t) \le 0$). Imagine trying to keep an autonomous vehicle within a safe zone, but the walls of that zone are constantly expanding, contracting, or shifting.
When the optimal solution lies directly on a moving boundary, maintaining feasibility while minimizing the objective becomes a delicate balancing act. If the algorithm steps too aggressively toward the objective, it risks violating the shifting constraints; if it is too conservative, it falls behind the boundary's motion.
To solve this, Mahyar Fazlyab et al. extended the prediction-correction paradigm to interior-point methods in Interior Point Method for Dynamic Constrained Optimization in Continuous Time. They treated the barrier parameter not as a fixed scalar, but as a continuous, increasing function of time. This allows the optimization path to smoothly glide toward the moving boundary without crossing it.
In discrete-time online settings, where constraints change unpredictably due to external factors like budget fluctuations, the authors of Online Convex Optimization with Perturbed Constraints: Optimal Rates against Stronger Benchmarks and Qingsong Liu et al. in Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints developed primal-dual frameworks. These methods adapt to unknown, perturbed constraints over time, proving that it is possible to simultaneously minimize tracking regret and cumulative constraint violations even when the environment changes adversarially.
The Problem of Stale Data
When we don't have explicit formulas for gradients or time derivatives—such as in black-box Bayesian Optimization (BO) or bandit problems—we must learn the landscape by sampling it. However, non-stationarity introduces a fundamental paradox for learning: old data becomes a liability.
In a static environment, every data point collected increases our certainty. In a time-varying environment, data collected ten minutes ago might describe a landscape that no longer exists. If an algorithm treats all historical data equally, its internal model becomes sluggish and fails to track environmental shifts.
To resolve this, algorithms must systematically forget or discount the past. For instance, Xingyu Zhou et al. proposed two strategies for time-varying Bayesian Optimization in No-Regret Algorithms for Time-Varying Bayesian Optimization:
- Sliding Windows (SW-GP-UCB): The Gaussian Process model only considers data points within a recent temporal window, discarding stale observations entirely.
- Periodic Restarts (R-GP-UCB): The algorithm completely wipes its memory and restarts exploration at fixed intervals to adapt to fresh environmental dynamics.
Alternatively, Antonia Holzapfel et al. utilized an event-triggered approach in Event-triggered safe Bayesian optimization on quadcopters. Instead of blindly clearing memory based on a clock, the system monitors performance deviations. If the system's behavior diverges significantly from the model's predictions, an event is triggered to isolate or reset the data, preventing the accumulation of stale data from corrupting safe exploration.
Sequential Interdependent Decisions
Time-varying optimization also manifests in discrete and combinatorial problems where decisions made today constrain the options available tomorrow. This is evident in control theory and dynamic resource allocation, where current actions have long-term consequences on future states.
For example, Na Li analyzed this in Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis, demonstrating how lookahead windows of future cost predictions allow online controllers to balance immediate performance with the long-term state consequences of their actions.
In the discrete domain, Vanja Doskoč designed greedy variants for submodular maximization under dynamic knapsack constraints in Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings, showing how discrete algorithms can adapt to fluctuating budgets step-by-step without suffering the computational waste of full restarts. By structuring algorithms to maintain stability across time steps, these frameworks bridge the gap between static optimization theory and the fluid reality of dynamic environments.