WorksEngineering
Computationally Constrained First-Order Prediction-Correction Approach for Time-Varying Convex Optimization
Abstract
Time-varying optimization methods often predict the locations of time-varying optima, then sample the objective function being minimized, and then compute corrections to those predictions. However, those works typically do not account for settings in which computations are limited. Therefore, in this work we formulate a prediction-correction algorithm that is designed to obey constraints on the total number of iterations it can execute over a given time horizon. We first show that there is a critical threshold for the average number of computations that can be executed between samples of the objective. Then, we show that if the number of allowable computations is above this threshold, then the distance to a time-varying optimum bound decays geometrically. Next, we show that if the number of allowable computations is below that threshold, then the distance to a time-varying optimum still remains bounded. Therefore, it is still possible to track time-varying optima with bounded error even under restrictive limits on the number of computations that can be executed. We also present an algorithm to determine how many prediction and correction steps should be executed for each sample of the objective. Simulation results show that under typical conditions our approach reduces cumulative tracking error by 45.5% compared to a comparable baseline approach.
Introduction
Time-varying optimization problems arise in robotics [1], [2], power systems [3], transportation networks [4], communication systems [5], and distributed systems [6], [7]. A common way to solve such problems is with a prediction-correction method [8], which uses information about the objective sampled at a prior time to predict how the solution will evolve in the future. Then, after resampling the objective, corrections are made to this prediction in order to account for the difference between the predicted and actual movements of the solution.
Such methods often use gradient or Newton steps to correct for those differences [1], [2], [8]. After completing some number of correcting steps, the prediction-correction cycle is repeated again by predicting the subsequent evolution of the solution, then sampling the objective, and then correcting those predictions. This class of method has been shown to track minimizers with error that is acceptable in a wide range of applications [6], [7], [9].
Prior works such as [1], [7]–[9] have used prediction-correction methods in applications such as target tracking, model-predictive control, and various decentralized formulations. All of these works (and many others) use fixed numbers of prediction steps and correction steps between samples of the objective. However, in practice it might not be possible to execute the desired number of computations, e.g., due to constraints on resources such as battery power, which can limit the total number of computations that can be executed over a given time horizon. Such constraints have driven interest in various forms of resource awareness across different settings. For example, existing works in [10]–[17] have investigated resource awareness in multi-agent control, connected and autonomous electric vehicles, and event-triggered control, but to the best of our knowledge there has not been a systematic study of time-varying optimization under computational constraints.
Therefore, in this paper, we develop a computationally constrained prediction-correction algorithm for time-varying optimization. We show that there is a critical threshold for the average number of computations required for each sample of the objective function. Next, we show that if the allowable computations exceed that threshold, then one can still keep the distance to the minimizer bounded, even though it may not decrease at every timestep. Next, we show that if the allowable computations do not exceed that threshold, then one can still decrease the distance to the minimizer over longer periods of time rather than at every timestep. We develop an algorithm for determining how many prediction and correction steps should be completed for each sample of the objective function, and this algorithm is designed to attain the error bounds we derive on the distance to a time-varying optimum.
Summary of Contributions
The contributions of this paper are:
We show that with enough prediction and correction computations, we can guarantee a decrease in the distance to the minimizer at every iteration (Theorem 1).
We show that even when lacking enough prediction and correction computations, the distance to the minimizer still remains bounded, and we derive sufficient conditions for when this is possible (Theorem 2).
We derive rules for how many prediction and correction steps to execute for each sampled objective (Algorithm 1, Theorems 3 and 4).
We show in simulation that our method tracks time-varying optima with 45.5% less cumulative error than a comparable baseline approach (Section V).
All authors were supported by ONR under grant N00014-26-1-2068.
The rest of the paper is organized as follows. Section II provides background and a problem formulation. Section III develops the computationally constrained algorithm, and Section IV computes error bounds. Then, Section V presents simulations, and Section VI concludes.
Notation
We use denote the reals and denote the non-negative reals. We use denote the non-negative integers. We denote the 2-norm of a vector by . We use to denote the identity matrix. For a function , we denote its gradient with respect to its first argument by , and we denote its derivative with respect to its second argument by . We use to denote the Hessian of with respect to its first argument, and is the partial derivative of with respect to ’s second argument.
Preliminaries and Problem Formulation
In this section, we provide background on the prediction-correction approach to time-varying optimization, and then we define the problem of interest.
Time-Varying Optimization
We consider time-varying convex optimization problems of the form
where is a decision variable, the set for a finite time horizon , and is a twice continuously differentiable and strongly convex function that varies in time such that is twice continuously differentiable and strongly convex for all . The objective is only known at past and current times , and future objectives are not known a priori. The goal is to compute the solution trajectory . However, the use of digital computers means continuously sampling the objective is often not possible. Instead of solving the problem continuously, we reformulate (1) in discrete time. We can sample the objective at each time instance , where for a finite time horizon and some sampling interval . This approach allows us to replace (1) with
At each , the current objective and its derivatives are known. We assume the following about .
Assumption 1. The function in (2) is twice continuously differentiable in and there exist constants such that
as well as a constant such that
Assumption 1 ensures that is uniformly strongly convex and smooth, which guarantees that (2) has a unique minimizer at each . The inequalities in (3) provide uniform curvature bounds over time, and the constant bounds the temporal variation of the gradient. The bound in (4) means that the time derivative of is bounded, and Algorithm 1 in Section III uses this fact to predict the movement of future minimizers.
Prediction-Correction Method
With an initial estimate , a prediction-correction algorithm generates approximations of the points along the optimal trajectory associated with the problem in (2). Such methods proceed as follows. For , at iteration the algorithm has some iterate , which it uses to predict the optimizer at the next iteration. This optimizer is , and some number of prediction steps are executed to predict it using . Then, the objective function is sampled, and some number of correction steps are taken to correct the prediction; the mathematical forms of the prediction and correction steps are described in detail in Sections II-B.1 and II-B.2. The final correction step produces the iterate , from which this process of prediction and correction repeats. With each iterate , the predictions and corrections steps correspond to solving for the following iterate .
Definition 1. For the problem in (2), an allocation is a collection of the numbers of prediction and correction steps that are executed for each sample of the objective.
The pair defines the total number of computations needed to compute from . As described in the introduction, there may be a limit on the total number of computations that are executed over the full time horizon of a problem. We formalize such constraints in Section II-C. Next, we describe the prediction and correction update laws that we use, which are based on those in [2].
Prediction
Prediction: Between samples of the objective, some number of prediction steps are executed to predict the minimizer of from , which is the last iterate computed when computing correction steps to minimize . Under a first-order expansion in space and time we have
where , , and . Since it is not always practical to solve for exactly, we impose a relaxed optimality condition as in [2] by seeking a point that satisfies the condition with . This relaxation allows us to use the prediction step
where is the th prediction iterate computed for the th sample of the objective and is the prediction step size. We initialize this step with , where is the last correction iterate computed when minimizing . 2) Correction: After all prediction steps are completed, the objective function is sampled, and then some number of correction steps are computed. We initialize and use the update law
where is the th correction iterate computed for the th sample of the objective, and is the correction step size. After correction steps, we set
and then this process of prediction and correction repeats.
Correction
Problem Formulation
The main focus of this paper is the following problem.
Problem 1. Develop an algorithm that solves (2) while being computationally constrained by a budget on the total number of prediction and correction steps that can be performed across all times.
In addressing the problem, we use to denote the numbers of prediction and correction iterations for minimizing , and we let denote the total number of iterations completed when computing from . Each prediction and correction step is treated as a single computation, and the budget constraint we define is
where is the iteration budget for the entire horizon. Under (7), it is possible that and are not the same for any . To solve Problem 1, we seek an allocation rule in the sense of Definition 1 that obeys (7) and tracks the time-varying optimum in (2) as closely as possible.
Computationally Constrained Prediction-Correction Method
In this section, we develop a computationally constrained allocation strategy for prediction and correction iterations to simultaneously 1) provide a finite-horizon tracking guarantee for solutions and 2) satisfy the budget constraint in (7). We first look at bounding the tracking error before defining and analyzing the two regimes based on the value of from (7). Then, we derive allocations for each regime.
Tracking-Error Bound
We define
where and are from Assumption 1, is the step size from the prediction update law in (5), and is the step size from the correction update law in (6). The terms and represent the contraction factors that quantify how quickly the prediction and correction steps converge, respectively. By Assumption 1, we know that and . We define the tracking error at the sample time as
where is fixed by initialization. We define the cumulative, mean, maximum, and terminal tracking errors as
where the initialization error is excluded from the computations of and since the prediction-correction method cannot change . We have the following tracking error bound.
Proposition 1 (Prediction-Correction Tracking Error Bound). Suppose Assumption 1 holds. Consider Problem 1, and suppose we apply the prediction-correction algorithm from Section II-B to it. Then, the error in tracking the minimizer of is bounded via
where is from (8), , and we define
along with
Proof. See Appendices A and C for case a) in [2].
In Proposition 1, the term quantifies the impact of the prediction-correction algorithm on the distance to the minimizer , and quantifies the impact of the movement of the minimizer on the distance to . Since and , for any allocation in the sense of Definition 1, we have
where , and , , and are from Assumption 1. By recursively unrolling (9), we have
where and . This error bound provides tracking performance on a finite horizon since it accounts for the numbers of prediction and correction steps for each . Now, we look to determining the impact of the budget from (7).
Budget Allocation
The mapping in (10) is decreasing in both and since . From (14) we see that it is desirable to have for all , and therefore we seek to identify the minimum number of total prediction and correction steps needed to ensure . Let
so that for any there exists a pair such that and . Using (15), we see that there exist two regimes based on whether or not the budget from (7) is large enough to allow for for all . The two regimes are
In Regime I it is possible to satisfy for all , but in Regime II it is not possible to do so. Therefore, in Regime II at least one iteration has . The following subsections define the allocations we use for each regime.
Regime I: Sufficient Average Budget
Suppose that , and let us define
where is the largest number of iterations that makes all ’s equal while obeying the budget constraint in (7), and is the remaining budget after using for all . Using any set where , we choose
which satisfies the budget constraint in (7), and holds for all . For each , we choose a pair
where
where is given for each by (18). Since , the set is nonempty.
Regime II: Insufficient Average Budget
Suppose that , where is from (15), is from (7), and is from Section II-A. This condition corresponds to being in Regime II from (16). Pointwise contraction can no longer be guaranteed at every step, in the sense that cannot be guaranteed for all . However, the error recursion in (9) still provides an upper bound on the distance to the minimizer at each time . Although we can no longer guarantee that error decreases for every , an allocation of prediction and correction iterations can still ensure that the error remains bounded over the whole time horizon . We formalize this notion with the following finite-horizon contraction condition.
Finite-horizon contraction certificate
Finite-horizon contraction certificate: For user-specified choices of and , we consider the certificate
such that . This property means that even though pointwise contraction is not enforced at all times, the error can grow by at most a factor of relative to decay at rate , which keeps the tracking error bounded.
To implement this contraction certificate, we seek to quantify the extent to which the error contracts with a rate at each time. Since and for all choices of and , we define
where is from (20). Intuitively, measures the extent to which a given pair ensures contraction with rate at least at iteration . For any , if , then ensures contraction with at least rate , and if , then it does not. We also define
which we use to measure the cumulative non-negativity of and hence the cumulative failure of pairs to ensure contraction with at least rate over time. Then starting with , we set
The term increases if at iteration , decreases if at iteration , and is reset to zero whenever the accumulated sum becomes negative at iteration . We use to prevent the tracking error from becoming too large. The following elementary lemma shows that one can enforce (20) by bounding from (22).
Lemma 1 (Necessary and sufficient condition for (20)). The certificate (20) holds for all satisfying if and only if
Proof. The recursion in (22) gives
Consequently, using (21), we see that having for every is equivalent to having
for every satisfying . Exponentiating proves the equivalence.
Aside from bounding at iteration , we also seek to determine how many total prediction and correction steps should be used at iterations after .
Exact reserve function
Let and . We define the “reserve function” as
which ensures while counting the total prediction and correction iterations used up to a given iteration. We set , and for any time at which the condition cannot be satisfied. The value of is the minimum number of total prediction and correction steps needed to satisfy the constraint for the remaining samples of the objective. The value of also depends on the certificate parameters and from (20) and the term for each , and it is solved offline for all , before the horizon begins.
Computing Allocations
While from (23) ensures that it is still possible to enforce the condition in (20), we still need to choose and for all . Under a specified budget , allocations with for any can be ignored because they are infeasible. Among feasible allocations, the remaining budget at step for is
Then the feasible set for choosing and at iteration is
where the first condition in the set definition enforces (20) for and , and the second condition ensures that we satisfy the budget constraint in (7).
In choosing among feasible allocations, we define
where is from Assumption 1. By strong convexity, using the fact that the solution satisfies , we find that , which implies that in (25) satisfies , where is from (8). Then we can define
which differs from in (11) by using the actual value of the gradient instead of the worst-case gradient bound .
Algorithm 1 Debt-State Computationally Constrained Allocation
Require: Initial iterate , horizon , budget from (7), certificate parameters and from (20), and from (23).
from Assumption 1. Then the values of and can be chosen at iteration using
where is from (25) and is from (26). In (27), we use instead of because the value of is known, and using this exact value more accurately quantifies the impact of the choice of than using the worst-case bound , which leads to greater flexibility in choosing . The complete procedure for the prediction-correction method in Regime II is shown in Algorithm 1.
Tracking Analysis
In this section, we analyze the allocation strategies derived for Regime I in (19) and for Regime II in (27).
Regime I Tracking Guarantees
With the allocation strategy from (19), we now bound the tracking error of a prediction-correction algorithm that uses it when executing prediction steps using (5) and correction steps using (6).
Theorem 1 (Tracking in Regime I). Suppose Assumption 1 holds and , where is from (7) and is from (15). Fix any set such that , where is from (17). Suppose the allocation of prediction and correction steps satisfies (19), and define
Then the budget constraint in (7) is satisfied, and we have
for , where ,
, is from (17), is from (8), and .
Proof. Since every selected allocation satisfies for all , we have
This bound accounts for whether the additional computation at a time is performed as a prediction or correction step since from (18) gives . Using the tracking bound in (14), we can separate out the bound based on whether or to find
Substituting in from (28) and the bound from (29) yields
The result follows from bounding using (13).
Theorem 1 provides insight into the error when tracking minimizers under Regime I. Since this tracking error is in terms of the sampling interval from Section II-A, the error bound can be reduced by sampling the objective more frequently. We now bound the tracking error in Regime II.
Regime II Feasibility and Tracking Guarantees
We first bound the minimum budget necessary for satisfying (20).
Theorem 2 (Exact certificate feasibility). Consider Problem 1, suppose Assumption 1 holds, and let and be given. Then, the certificate in (20) is satisfiable for all such that with total budget if
where is from (23).
Proof. Suppose . We construct a feasible allocation using the minimizers in (23). Since and the values of from (23) are nonnegative integers or , we define with as
which implies . Repeating the same argument at where is from (22) for yields
This construction satisfies the budget constraint in (7) since and implies that the certificate (20) holds by Lemma 1.
Theorem 2 provides a sufficient condition to ensure that the contraction certificate in (20) can be satisfied for a given and under a given budget . Next, we quantify the tracking error under allocations that are generated by Algorithm 1 under Regime II while obeying the budget constraint in (7).
Theorem 3 (Tracking under the exact reserve). Suppose , suppose Assumption 1 holds, and define
For the allocation generated by Algorithm 1, we have
for , where and are from (20), , is from (8), and .
Proof. Using the tracking error recursion in (14) and the contraction certificate in (20) yields
Since from (30), we find
The result follows from bounding using (13).
Theorem 3 provides a bound on the tracking error incurred by allocations produced by Algorithm 1. Since this tracking error bound is in terms of the sampling interval from Section II-A, it can be reduced by sampling the objective more frequently.
A sufficient condition using uniform allocation
Since the function requires a dynamic program to compute its values, we wish to look at sufficient conditions to attain a contraction on the error bound by considering for some and all . This choice will simplify the implementation of Algorithm 1 by eliminating the need to explicitly compute .
Theorem 4 (Closed-form sufficient budget condition). Consider Problem 1, and suppose Assumption 1 holds. Define
where and are from (20). Also define
Consider from (7). If , then the total number of computations for under this uniform allocation satisfies the total budget (7), the contraction certificate (20), and the tracking bound (31). Such a bound allows for admitting allocations generated by Algorithm 1.
Proof. Consider any pair
and consider the constant allocation for . Since , the total budget satisfies .
Moreover, by the definition of , we have . Therefore, for all and such that , we have
where the last inequality follows from and . Hence, the contraction certificate (20) is satisfied for all and such that . Following the same steps from (32) to (33) in the proof of Theorem 3, we find
The results in Theorem 4 show that we can still attain the bound in (31) even while using a uniform allocation of total computations. Since the total number of prediction and correction steps is identical for each , we can reduce the allocation to just solving for the number of correction steps for each .
Consider the bound where is from (10) and is from (34). Fix for all . Then we can solve for the minimum number of correction steps as
where is from (12) and , which implies that
Then the uniform-allocation calculation is reduced to an integer search over prediction counts, without using a dynamic program.
Numerical Experiments
In this section, we compare our adaptive allocation against a uniform allocation under the same total iteration budget .
Problem and Experimental Setup
Consider the unconstrained problem from [2]:
where , is a unit vector, , and the reference traces a closed curve with angular speed
which produces a slow–fast–slow pattern of temporal variation. The objective in (35) satisfies Assumption 1 since is uniformly bounded between and for constants and determined by and , and since gives . The optimizer is computed numerically and is used only to evaluate tracking performance.
We use , , , , , , , and , which gives , , and . We also use , , , , , , , and . Here while , so the experiment lies in Regime II. The uniform baseline uses for all , which is the pair that minimizes while satisfying . Both methods start from .
Adaptive and Uniform Allocation
Adaptive allocation reduces the cumulative tracking error by about 45.5% and the maximum error by 64.7% relative to the uniform baseline, at the cost of a larger terminal error (0.0132 vs. 0.00177). This behavior follows from the online allocation rule in (27): the estimate is large while is far from , so the rule spends most of the budget within the first several intervals, and then it tapers to two iterations per interval once shrinks, while the uniform method uses (2,5) throughout. The adaptive method therefore trades terminal accuracy for faster correction of the initial mismatch.
Sensitivity to Initialization and Budget
We repeat the experiment for ten initial-error magnitudes , , holding the direction of fixed. The reduction in grows with , from about 7.6% at to about 76.1% at , since a larger initial gap raises and lengthens the stretch of near-maximum allocation. The terminal error of each method changes little across this range, so it is a poor indicator of how well either method tracked the trajectory.
We next sweep over , which lies above the reserve and below the Regime I budget , for (Figure 1). The reduction grows with at every budget, from 33.0% to 49.8% at . It peaks near at 35.9–61% and eases to 14.4–47.6% by , since the uniform method improves when from (17) increases from 6 (with (2, 4)) to 7 (with (2, 5)) between and . Over the full grid of and (Figure 2), the reduction ranges from 7.4% (, ) to 76.1% (, ), with an average of 35.4%. The advantage of the adaptive method is largest where the tracking problem is hardest: a small budget paired with a large initial error.

Figure 1. Cumulative error vs. budget , adaptive (solid) against uniform (dashed), at four values of . The drop in the uniform method between and is the increase in from 6 to 7.

Figure 2. Reduction in cumulative tracking error over the joint grid. The adaptive method performs best under a large and a small , and similarly to the uniform method under a small and a large .
Conclusion
This paper presented a computationally constrained version of the prediction-correction method that generates a number of predictions and corrections computed within each time step. We identified the one of two Regimes where there is not enough budget for a uniform allocation of computations. In this Regime, we still show that the we can distribute the number of computations such that the tracking error remains bounded. Simulations support our analysis where our adaptive approach of allocating different amounts of computations based on a budget had better cumulative tracking errors in comparison the the uniform approach. Future work involves extending this approach to other works that have implemented other forms of predictions schemes.
References
References
- [1]A. Simonetto, A. Mokhtari, A. Koppel, G. Leus, and A. Ribeiro, “A class of prediction-correction methods for time-varying convex optimization,” IEEE Transactions on Signal Processing, vol. 64, 2016.DOI
- [2]A. Simonetto and E. Dall’Anese, “Prediction-correction algorithms for time-varying constrained optimization,” in IEEE Transactions on Signal Processing, vol. 65, 2017.DOI
- [3]Z. Lin, J. Hou, and X. Zeng, “Optimal prediction-correction algorithm using sparse linear extrapolation for time-varying optimization,” IEEE Transactions on Signal Processing, vol. 74, pp. 2564–2578, 2026.DOI
- [4]A. Simonetto, E. Dall’Anese, S. Paterniän, G. Leus, and G. B. Giannakis, “Time-varying convex optimization: Time-structured algorithms and applications,” Proceedings of the IEEE, vol. 108, no. 11, pp. 2032–2048, 2020.arxiv.org/abs/2006.08500
- [5]G. Bianchin, J. Cortés, J. I. Poveda, and E. Dall’Anese, “Time-varying optimization of ItI systems via projected primal-dual gradient flows,” IEEE Transactions on Control of Network Systems, vol. 9, no. 1, pp. 474–486, 2022.arxiv.org/abs/2101.01799
- [6]A. Simonetto, “Dual prediction–correction methods for linearly constrained time-varying convex programs,” IEEE Transactions on Automatic Control, vol. 64, no. 8, pp. 3355–3361, 2019.arxiv.org/abs/1709.05850
- [7]A. Simonetto, A. Koppel, A. Mokhtari, G. Leus, and A. Ribeiro, “Decentralized prediction-correction methods for networked time-varying convex optimization,” IEEE Transactions on Automatic Control, vol. 62, no. 11, pp. 5724–5738, 2017.arxiv.org/abs/1602.01716
- [8]——, “Prediction-correction methods for time-varying convex optimization,” in 2015 49th Asilomar Conference on Signals, Systems and Computers, 2015, pp. 666–670.DOI
- [9]S. Paternain, M. Morari, and A. Ribeiro, “A prediction-correction method for model predictive control,” in 2018 Annual American Control Conference (ACC), 2018, pp. 4189–4194.DOI
- [10]P. Sokaert, D. Mayne, and J. Rawlings, “Suboptimal model predictive control (feasibility implies stability),” IEEE Transactions on Automatic Control, vol. 44, no. 3, pp. 648–654, 1999.
- [17]H. Zhang, L. Yuan, and X. Cao, “Event-triggered nonlinear model predictive control for energy-aware way obstacle avoidance,” IEEE Internet of Things Journal, pp. 1–1, 2026.DOI