betaFeedback

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, existing methods typically do not account for settings in which the number of computations is limited. Therefore, in this work we formulate a prediction-correction algorithm that is designed to obey a budget constraint on the total number of iterations it can execute over a given time horizon. We first identify a threshold on the average number of computations between samples of the objective, above which a bound from prior work certifies contraction of iterates toward a minimizer. Below this threshold, we introduce a finite-horizon contraction certificate, which we use to give budget conditions under which the tracking error admits an explicit bound that decays at a prescribed rate. We also present an algorithm to determine how many prediction and correction steps should be executed for each sample of the objective, while obeying a given budget on the allowable number of computations. Empirically, we show in a simulation that our approach reduces cumulative tracking error by 45.5 % relative 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 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 to account for differences 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 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, 2, 3], [6]–[10] have used prediction-correction methods in applications including 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 [11]–[18] 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. Computation constraints are encoded as an upper bound on the total number of prediction and correction steps that can be executed over a given time horizon, which we call the “budget” for a problem. We consider a first-order prediction-correction algorithm that uses gradient steps for both predictions and corrections.

We first identify a critical threshold on the number of computations that can be executed for each sample of the objective function. Then we show that if the budget permits at least that many computations to be executed for each sample of the objective, then we can certify that the iterates of the first-order algorithm contract toward a minimizer.

In contrast, if the threshold we derive cannot be met for some samples of the objective, the aforementioned contraction guarantee no longer applies. However, we show that one can still allocate prediction and correction steps so that the distance to the minimizer admits a different form of explicit bound that decreases at a prescribed rate. Then, 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 identify a critical threshold on the average number of computations per sample of the objective. Above this threshold, we guarantee that a bound on the distance to the minimizer converges geometrically to a neighbor-

Chuy and Hale were supported by the Office of Naval Research under grant N00014-26-1-2068, and Musavi and Ornik were supported by the Office of Naval Research under grant N00014-25-1-2519 and N00014-25-1-2369. hood whose size is proportional to the time that elapses between taking samples of the objective (Corollary 1).

  • Below this threshold, we introduce a finite-horizon contraction certificate that encodes a desired rate of decay in the distance from iterates to a minimum. Then we derive budget conditions under which this certificate can be satisfied and thus ensure that the distance to a minimizer decreases at a user-specified rate (Theorems 1 and 2).

  • We develop an algorithm that determines how many prediction and correction steps to execute for each sample of the objective while obeying a total computation budget constraint (Algorithm 1, Theorems 2 and 3).

  • We show in simulation that our method tracks time-varying optima with 45.5% less cumulative error than a comparable baseline approach § 5.

The rest of this 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, § 5 presents simulations, and Section VI concludes the paper.

Notation

We use R\mathbb{R} to denote the reals and R≥0\mathbb{R}_{\geq0} to denote the nonnegative reals. For an integer kk, we use Z≥k\mathbb{Z}_{\geq k} to denote the set of integers greater than or equal to kk. We denote the 2-norm of a vector x∈Rnx \in\mathbb{R}^{n} by ∥x∥\lVert x \rVert. We use II to denote the identity matrix. For a function f:Rn×R≥0→Rf : \mathbb{R}^{n} \times\mathbb{R}_{\geq0} \to\mathbb{R} that takes arguments (x,t)(x,t), we denote its gradient with respect to xx by ∇xf\nabla_x f, and we denote its derivative with respect to tt by ∇tf\nabla_t f. We use ∇xxf\nabla_{xx} f to denote the Hessian of ff with respect to xx, and ∇txf\nabla_{tx} f is the time derivative of ∇xf\nabla_x f.

Preliminaries and Problem Formulation

In this section, we first define the time-varying optimization problem in Section II-A. Then in Section II-B, we describe the prediction–correction method. Finally, in Section II-C, we formulate the problem that we address in this paper.

Time-Varying Optimization

Let f:Rn×R≥0→Rf : \mathbb{R}^{n} \times\mathbb{R}_{\geq0} \to\mathbb{R} be a time-varying function, and let Tc>0T_c > 0 be a finite time horizon. We make the following assumption on ff.

Assumption 1. The function ff is twice continuously differentiable in (x,t)(x,t) and there exist constants 0<m≤L0 < m \leq L such that

mI⪯∇xxf(x,t)⪯LIfor all x∈Rn, t∈[0,Tc],(1)mI \preceq\nabla_{xx}f(x,t) \preceq LI \quad\text{for all } x \in\mathbb{R}^{n},\ t \in[0,T_c], \tag*{(1)}

as well as a constant Γ>0\Gamma> 0 such that

∥∇txf(x,t)∥≤Γfor all x∈Rn, t∈[0,Tc].(2)\lVert\nabla_{tx}f(x,t) \rVert\leq\Gamma\quad\text{for all } x \in\mathbb{R}^{n},\ t \in[0,T_c]. \tag*{(2)}

Assumption 1 ensures that f(⋅,t)f(\cdot,t) is uniformly strongly convex and smooth, which guarantees that it has a unique minimizer for each t∈[0,Tc]t \in[0,T_c]. The inequalities in (1) provide uniform curvature bounds over time, and the constant Γ\Gamma bounds the temporal variation of the gradient. The bound in (2) means that the time derivative of ∇xf(x,t)\nabla_x f(x,t) is bounded.

Under Assumption 1, consider time-varying convex optimization problems of the form

x∗(t):=arg min⁡x∈Rn f(x,t),t∈[0,Tc],(3)x^*(t) := \underset{x \in\mathbb{R}^{n}}{\operatorname{arg\,min}}\, f(x,t), \qquad t \in[0,T_c], \tag*{(3)}

where x∈Rnx \in\mathbb{R}^{n} is a decision variable. The objective f(⋅,t)f(\cdot,t) is only known at past and current times tt, and future objectives are not known a prioria\ priori.

Suppose that the objective can only be accessed at discrete time instances. Then, the problem (3) can be considered in discrete time. Following [19, 20], the objective is sampled at the time instances tk:=kht_k := kh, where h>0h > 0 is a constant sampling interval and k∈{0,1,…,T}k \in\{0,1,\ldots,T\} for a finite time horizon T∈Z≥1T \in\mathbb{Z}_{\geq1} such that Th≤TcTh \leq T_c. This yields the sequence of problems

x∗(tk):=arg min⁡x∈Rn f(x,tk),k=0,1,…,T,(4)x^*(t_k) := \underset{x \in\mathbb{R}^{n}}{\operatorname{arg\,min}}\, f(x,t_k), \qquad k = 0,1,\ldots,T, \tag*{(4)}

which is the problem considered in the remainder of this paper. At each tkt_k, the current objective f(⋅,tk)f(\cdot,t_k) and its derivatives at tkt_k, including ∇xxf(⋅,tk)\nabla_{xx}f(\cdot,t_k) and ∇txf(⋅,tk)\nabla_{tx}f(\cdot,t_k), are known.

Prediction-Correction Method

In this section we describe the prediction–correction method of [2], which proceeds as follows. Starting with an initial estimate x0∈Rnx_0 \in\mathbb{R}^{n}, the method generates estimates {xk}k=1T\{x_k\}_{k=1}^{T} of the optimal trajectory {x∗(tk)}k=1T\{x^*(t_k)\}_{k=1}^{T} in (4). For k∈{0,1,…,T−1}k \in\{0,1,\ldots,T-1\}, the method uses the estimate xkx_k of x∗(tk)x^*(t_k) to predict x∗(tk+1)x^*(t_{k+1}) by executing PkP_k prediction steps. Then, the objective f(⋅,tk+1)f(\cdot,t_{k+1}) is sampled, and CkC_k correction steps are executed to correct the prediction. The final correction step produces xk+1x_{k+1}, from which this process repeats. The prediction and correction steps are described in Sections II-B.1 and II-B.2. In [2], the numbers of prediction and correction steps are the same for every kk; here, they may vary with kk.

Prediction

  1. Prediction: Between two sampling times tkt_k and tk+1t_{k+1}, PkP_k prediction steps are executed to predict x∗(tk+1)x^*(t_{k+1}) from xkx_k. A first-order expansion in space and time gives

∇xf(z,tk+1)≈gk+Hk(z−xk)+hvk,\nabla_x f(z,t_{k+1}) \approx g_k + H_k(z-x_k) + h v_k,

where gk:=∇xf(xk,tk)g_k := \nabla_x f(x_k,t_k), Hk:=∇xxf(xk,tk)H_k := \nabla_{xx}f(x_k,t_k), and vk:=∇txf(xk,tk)v_k := \nabla_{tx}f(x_k,t_k). Since f(⋅,tk+1)f(\cdot,t_{k+1}) is not known before it is sampled, solving ∇xf(z,tk+1)=0\nabla_x f(z,t_{k+1}) = 0 exactly may not be practical. Instead, as in [2], a relaxed optimality condition is imposed by seeking a point zz that satisfies ∇xf(z,tk+1)=(1−γ)gk\nabla_x f(z,t_{k+1}) = (1-\gamma)g_k with γ∈[0,1]\gamma\in[0,1]. This relaxation leads to the prediction step

xkp,ℓ+1=xkp,ℓ−α[Hk(xkp,ℓ−xk)+hvk+γgk](5)x_k^{p,\ell+1} = x_k^{p,\ell} - \alpha\left[ H_k\left(x_k^{p,\ell}-x_k\right) + h v_k + \gamma g_k \right] \tag*{(5)}

for ℓ∈{0,…,Pk−1}\ell\in\{0,\ldots,P_k-1\}, where xkp,ℓx_k^{p,\ell} is the ℓ\ellth prediction iterate computed for the kkth sample of the objective, xkp,0=xkx_k^{p,0}=x_k, and α∈(0,2L)\alpha\in\left(0,\frac{2}{L}\right) is the prediction step size.

Correction

After all PkP_k prediction steps are completed, the objective function f(⋅,tk+1)f(\cdot,t_{k+1}) is sampled, and CkC_k correction steps are executed. Initialized at xk+1c,0=xkp,Pkx_{k+1}^{c,0}=x_k^{p,P_k}, the correction step is

xk+1c,ℓ+1=xk+1c,ℓ−β∇xf(xk+1c,ℓ,tk+1)(6)x_{k+1}^{c,\ell+1}=x_{k+1}^{c,\ell}-\beta\nabla_x f(x_{k+1}^{c,\ell},t_{k+1}) \tag*{(6)}

for ℓ∈{0,…,Ck−1}\ell\in\{0,\ldots,C_k-1\}, where xk+1c,ℓx_{k+1}^{c,\ell} is the ℓ\ellth correction iterate computed for the (k+1)(k+1)th sample of the objective, and β∈(0,2L)\beta\in\left(0,\frac{2}{L}\right) is the correction step size. After CkC_k correction steps, xk+1:=xk+1c,Ckx_{k+1}:=x_{k+1}^{c,C_k}, and then this process of prediction and correction repeats.

Problem Formulation

Definition 1. An allocation is a collection {(Pk,Ck)}k=0T−1\{(P_k,C_k)\}_{k=0}^{T-1}, with Pk,Ck∈Z≥0P_k,C_k\in\mathbb{Z}_{\geq0}, of the numbers of prediction and correction steps (5)–(6) executed between consecutive sampling times tkt_k and tk+1t_{k+1}.

The sum Kk:=Pk+CkK_k:=P_k+C_k is the number of iterations used to compute xk+1x_{k+1} from xkx_k. For a given allocation {(Pk,Ck)}k=0T−1\{(P_k,C_k)\}_{k=0}^{T-1}, let {xk}k=0T\{x_k\}_{k=0}^{T} denote the iterates generated by (5)–(6) from an initial estimate x0x_0. We define the tracking error of this allocation as

ek:=∥xk−x⋆(tk)∥,k=0,…,T.(7)e_k:=\lVert x_k-x^\star(t_k)\rVert,\qquad k=0,\ldots,T. \tag*{(7)}

We consider a total iteration budget B∈Z≥1B\in\mathbb{Z}_{\geq1} over the TT sampling intervals. Each prediction iteration (5) and each correction iteration (6) incurs one unit of cost, while sampling the objective and evaluating gkg_k, HkH_k, and vkv_k do not count toward the budget. Our goal is to solve the following problem.

Problem 1. Given an iteration budget BB, determine an allocation {(Pk,Ck)}k=0T−1\{(P_k,C_k)\}_{k=0}^{T-1} with bounded tracking errors eke_k for all k∈{1,…,T}k\in\{1,\ldots,T\} such that

∑k=0T−1(Pk+Ck)≤B.(8)\sum_{k=0}^{T-1}(P_k+C_k)\leq B. \tag*{(8)}

The budget constraint permits the per-sample totals Kk:=Pk+CkK_k:=P_k+C_k to vary across sampling intervals. To address Problem 1, we first characterize how the allocation affects the tracking error. We then use this characterization to develop allocation rules that meets the total iteration budget and admit a finite-horizon tracking bounds.

Computationally Constrained Prediction-Correction Method

In this section, we develop a computationally constrained allocation strategy for prediction and correction iterations that 1) provides a finite-horizon tracking guarantee and 2) satisfies the budget constraint in (8). We first present tracking error bounds for a general allocation {(Pk,Ck)}k=0T−1\{(P_k,C_k)\}_{k=0}^{T-1}. Then, given a budget BB, we derive allocations under two different regimes.

Tracking-Error Bound and Budget Regimes

Let

ρp:=max⁡{∣1−αm∣,∣1−αL∣},\rho_p:=\max\{|1-\alpha m|,|1-\alpha L|\},
ρc:=max⁡{∣1−βm∣,∣1−βL∣},\rho_c:=\max\{|1-\beta m|,|1-\beta L|\},

where mm and LL are the curvature bounds from Assumption 1, and α\alpha and β\beta are the step sizes of the prediction and correction steps in (5) and (6), respectively. The terms ρp\rho_p and ρc\rho_c are the contraction factors of the prediction and correction steps. Since α,β∈(0,2L)\alpha,\beta\in\left(0,\frac{2}{L}\right), it follows from Assumption 1 that ρp,ρc∈(0,1)\rho_p,\rho_c\in(0,1) [2]. For a general allocation, the following proposition describes how the tracking error evolves from one sampling time to the next.

Proposition 1 (Prediction-Correction Tracking Error Bound [2]). Suppose Assumption 1 holds, let {(Pk,Ck)}k=0T−1\{(P_k,C_k)\}_{k=0}^{T-1} be any allocation, and let the iterates {xk}k=0T\{x_k\}_{k=0}^{T} be generated by the prediction and correction steps in (5)–(6). Then, the following inequality holds:

ek+1≤a(Pk,Ck)ek+d(Pk,Ck),∀k∈{0,1,…,T−1},(9)e_{k+1}\leq a(P_k,C_k)e_k+d(P_k,C_k),\qquad\forall k\in\{0,1,\ldots,T-1\}, \tag*{(9)}

where

a(Pk,Ck):=ρcCk[ρpPk+(ρpPk+1)Aγ],a(P_k,C_k):=\rho_c^{C_k}\left[\rho_p^{P_k}+\left(\rho_p^{P_k}+1\right)A_\gamma\right],
d(Pk,Ck):=4hΓm(1+Lm)ρcCk(2ρpPk+1),(10)d(P_k,C_k):=\frac{4h\Gamma}{m}\left(1+\frac{L}{m}\right)\rho_c^{C_k}\left(2\rho_p^{P_k}+1\right), \tag*{(10)}
Aγ:=1−γ+2γLm.A_\gamma:=1-\gamma+\frac{2\gamma L}{m}.

Proof. This result follows from Appendices A and C for case a) in [2]. There, the bound is stated for a fixed number of prediction and correction steps. Because (9) relates only eke_k and ek+1e_{k+1}, the same argument applies at each kk with (Pk,Ck)(P_k,C_k) in place of the fixed counts.

For ease of notation, let aj:=a(Pj,Cj)a_j:=a(P_j,C_j) and dj:=d(Pj,Cj)d_j:=d(P_j,C_j) for j∈{0,1,…,T−1}j\in\{0,1,\ldots,T-1\}. Recursively unrolling (9) gives

ek≤(∏j=0k−1aj)e0+∑i=0k−1(∏j=i+1k−1aj)di, ∀k∈{0,1,…,T}.(11)e_k\leq\left(\prod_{j=0}^{k-1}a_j\right)e_0+\sum_{i=0}^{k-1}\left(\prod_{j=i+1}^{k-1}a_j\right)d_i,\ \forall k\in\{0,1,\ldots,T\}. \tag*{(11)}

Moreover, since ρp,ρc∈(0,1)\rho_p,\rho_c\in(0,1), it follows from (10) that

0≤dj≤D0h,∀j∈{0,1,…,T−1},(12)0\leq d_j\leq D_0h,\qquad\forall j\in\{0,1,\ldots,T-1\}, \tag*{(12)}

where D0:=12Γm(1+Lm)D_0:=\frac{12\Gamma}{m}\left(1+\frac{L}{m}\right). The bound in (11) holds for any allocation, and shows that both the initial error e0e_0 and each term did_i in the sum are multiplied by products of the factors aja_j. If aj<1a_j<1 for all j∈{0,1,…,T−1}j\in\{0,1,\ldots,T-1\}, then these products decay geometrically in kk. The factor a(P,C)a(P,C) in (10) is nonincreasing in both PP and CC, and therefore ensuring a(P,C)<1a(P,C)<1 requires a sufficient number of iterations per sample. Let us define the minimum such number as

Kmin⁡:=min⁡P,C∈Z≥0a(P,C)<1P+C.(13)K_{\min}:=\min_{\substack{P,C\in\mathbb{Z}_{\geq0}\\a(P,C)<1}}P+C. \tag*{(13)}

The minimum in (13) is attained, since a(0,C)<1a(0,C)<1 for sufficiently large CC and P+C∈Z≥0P+C\in\mathbb{Z}_{\geq0}. Since a(⋅,⋅)a(\cdot,\cdot) is nonincreasing in each argument, any K≥Kmin⁡K\geq K_{\min} also admits a pair (P,C)(P,C) with P+C=KP+C=K and a(P,C)<1a(P,C)<1.

For a given horizon TT and budget BB, we define two regimes based on Kmin⁡K_{\min}:

Regime I: BT≥Kmin⁡\frac{B}{T}\geq K_{\min} and Regime II: BT<Kmin⁡\frac{B}{T}<K_{\min}.

Since the budget BB is shared across all TT samples, the regimes depend on the average budget per sample B/TB/T. In Regime I, the budget allows Pk+Ck≥Kmin⁡P_k+C_k\geq K_{\min} for all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}. In Regime II, it does not, and therefore any allocation satisfying (8) has at least one kk with a(Pk,Ck)≥1a(P_k,C_k)\geq1. The following subsections develop allocations for each regime.

Regime I: Sufficient Average Budget

Suppose that B/T≥Kmin⁡B/T\geq K_{\min}, and define

Kbase:=⌊BT⌋.K_{\mathrm{base}}:=\left\lfloor\frac{B}{T}\right\rfloor.

where KbaseK_{\mathrm{base}} is the largest number of iterations that makes all KkK_k’s equal while obeying the budget constraint in (8). Since Kmin⁡K_{\min} is an integer and B/T≥Kmin⁡B/T\geq K_{\min}, we have Kbase≥Kmin⁡K_{\mathrm{base}}\geq K_{\min}. Define Upc:={(P,C)∈Z≥02:P+C=Kbase,a(P,C)<1}\mathcal{U}^{pc}:=\{(P,C)\in\mathbb{Z}_{\geq0}^{2}:P+C=K_{\mathrm{base}},a(P,C)<1\}. We choose a pair

(Pˉ,Cˉ)∈Upc,(14)(\bar{P},\bar{C})\in\mathcal{U}^{pc}, \tag*{(14)}

and we set (Pk,Ck)=(Pˉ,Cˉ)(P_k,C_k)=(\bar{P},\bar{C}) for all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}. Since Kbase≥Kmin⁡K_{\mathrm{base}}\geq K_{\min}, the set Upc\mathcal{U}^{pc} is nonempty. This uniform allocation uses TKbase≤BTK_{\mathrm{base}}\leq B total iterations over the full time horizon, and therefore it satisfies (8).

Regime II: Insufficient Average Budget

If B/T<Kmin⁡B/T<K_{\min}, then a(Pk,Ck)<1a(P_k,C_k)<1 cannot be guaranteed for all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}. If the budget is sufficiently large, an allocation can still ensure that the products of the factors a(Pj,Cj)a(P_j,C_j) in (11) decay at a prescribed rate, which yields an explicit tracking bound over {0,1,…,T}\{0,1,\ldots,T\}. We formalize this notion with the following finite-horizon contraction condition.

Finite-horizon contraction certificate

Finite-horizon contraction certificate: For user-specified choices of M≥1M\geq1 and ρ∈(0,1)\rho\in(0,1), we consider the condition

∏j=ik−1a(Pj,Cj)≤Mρk−i,(15)\prod_{j=i}^{k-1}a(P_j,C_j)\leq M\rho^{k-i}, \tag*{(15)}

for all i,k∈Z≥0i,k\in\mathbb{Z}_{\geq0} with 0≤i<k≤T0\leq i<k\leq T. We call (15) a certificate because, when it holds, the tracking error can be shown to be bounded. This bound is derived in Section IV.

To enforce (15) while choosing (Pk,Ck)(P_k,C_k) one iteration at a time, we quantify the extent to which a(Pk,Ck)a(P_k,C_k) exceeds ρ\rho at each iteration. Since ρ∈(0,1)\rho\in(0,1) and a(P,C)>0a(P,C)>0 for all choices of P∈Z≥0P\in\mathbb{Z}_{\geq0} and C∈Z≥0C\in\mathbb{Z}_{\geq0}, we define

s(Pk,Ck):=log⁡a(Pk,Ck)−log⁡ρ.(16)s(P_k,C_k):=\log a(P_k,C_k)-\log\rho. \tag*{(16)}

Intuitively, s(Pk,Ck)s(P_k,C_k) measures the extent to which a given pair (Pk,Ck)(P_k,C_k) ensures a(Pk,Ck)≤ρa(P_k,C_k)\leq\rho at iteration kk. For any k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}, if s(Pk,Ck)≤0s(P_k,C_k)\leq0, then a(Pk,Ck)≤ρa(P_k,C_k)\leq\rho, and if s(Pk,Ck)>0s(P_k,C_k)>0, then a(Pk,Ck)>ρa(P_k,C_k)>\rho. We also define

q+(q;Pk,Ck):=max⁡{0,q+s(Pk,Ck)},q^{+}(q;P_k,C_k):=\max\{0,q+s(P_k,C_k)\},

which we use to measure the accumulated positive values of s(Pk,Ck)s(P_k,C_k) and hence the cumulative failure of pairs (Pk,Ck)(P_k,C_k) to ensure a(Pk,Ck)≤ρa(P_k,C_k)\leq\rho over time. Starting with q0=0q_0=0, we set

qk+1=q+(qk;Pk,Ck).(17)q_{k+1}=q^{+}(q_k;P_k,C_k). \tag*{(17)}

The term qkq_k increases if a(Pk,Ck)>ρa(P_k,C_k)>\rho at iteration kk, decreases or remains at zero if a(Pk,Ck)<ρa(P_k,C_k)<\rho at iteration kk, and is reset to zero whenever the accumulated sum q+s(Pk,Ck)q+s(P_k,C_k) becomes negative at iteration kk. The following lemma shows that one can enforce (15) by bounding qkq_k from (17).

Lemma 1 (Necessary and sufficient condition for (15)). Let qkq_k be as defined in (17). Then the certificate (15) holds for all i,k∈Z≥0i,k\in\mathbb{Z}_{\geq0} satisfying 0≤i<k≤T0\leq i<k\leq T if and only if

qk≤log⁡Mfor all k∈{0,1,…,T}.q_k\leq\log M\quad\text{for all }k\in\{0,1,\ldots,T\}.

Proof. See Appendix A.

Lemma 1 provides a necessary and sufficient condition for the certificate (15) to hold. Since the budget BB is shared across iterations, maintaining this condition requires reserving enough iterations for the remaining samples, which we quantify next through the reserve function.

Reserve function

Reserve function: Let n∈{0,1,…,T−1}n\in\{0,1,\ldots,T-1\} denote the number of remaining samples of the objective function, and consider q∈[0,log⁡M]q\in[0,\log M]. We define the reserve function as

Vn+1(q):=min⁡(P,C)∈Z≥02q+(q;P,C)≤log⁡M(P+C+Vn(q+(q;P,C))).(18)V_{n+1}(q):= \min_{\substack{(P,C)\in\mathbb{Z}_{\geq0}^{2}\\q^{+}(q;P,C)\leq\log M}} \left(P+C+V_n\left(q^{+}(q;P,C)\right)\right). \tag*{(18)}

where the constraint keeps q+(q;P,C)≤log⁡Mq^{+}(q;P,C)\leq\log M, and Vn+1(q)V_{n+1}(q) counts the minimum total number of prediction and correction iterations needed over the remaining n+1n+1 samples. We set V0(q):=0V_0(q):=0, since no iterations are needed when no samples remain, and Vn+1(q):=+∞V_{n+1}(q):=+\infty if no pair (P,C)(P,C) satisfies the constraint in (18). The value of Vn(q)V_n(q) also depends on the certificate parameters MM and ρ\rho from (15) and the function a(P,C)a(P,C) from (10), and it is solved offline for all nn, before the horizon begins. In practice, we compute VnV_n on a grid of possible values of q∈[0,log⁡M]q\in[0,\log M], rounding each transition q+q^{+} up to the next grid point, which can only increase VnV_n and therefore preserves the guarantees.

Computing Allocations

Computing Allocations: The reserve function determines how many iterations must be saved for future samples so that (15) can still be satisfied. It remains to choose PkP_k and CkC_k at each kk. The remaining budget at step kk for k∈{0,1,…,T}k\in\{0,1,\ldots,T\} is

Rk:=B−∑j=0k−1(Pj+Cj).R_k:=B-\sum_{j=0}^{k-1}(P_j+C_j).

Then the feasible set for choosing PkP_k and CkC_k at iteration kk is

Ukfeasible:={(Pk,Ck)∈Z≥02:q+(qk;Pk,Ck)≤log⁡M,Pk+Ck+VT−k−1(q+(qk;Pk,Ck))≤Rk}.(19)\mathcal{U}^{\mathrm{feasible}}_k := \left\{(P_k,C_k) \in\mathbb{Z}_{\geq0}^2 : q^+(q_k;P_k,C_k) \leq\log M,\quad P_k+C_k+V_{T-k-1}\left(q^+(q_k;P_k,C_k)\right) \leq R_k\right\}. \tag*{(19)}

where the first condition ensures qk+1≤log⁡Mq_{k+1} \leq\log M, so that, by Lemma 1, the certificate (15) continues to hold after iteration kk, and the second condition ensures that the budget constraint in (8) is satisfied.

To choose among feasible pairs, we estimate the two terms in (9) using information available at (xk,tk)(x_k,t_k). Since eke_k cannot be evaluated online, we estimate it with

e^k:=∥∇xf(xk,tk)∥m.(20)\widehat{e}_k := \frac{\left\|\nabla_x f(x_k,t_k)\right\|}{m}. \tag*{(20)}

By strong convexity of f(⋅,tk)f(\cdot,t_k), using the fact that the solution x⋆(tk)x^\star(t_k) satisfies ∇xf(x⋆(tk),tk)=0\nabla_x f(x^\star(t_k),t_k)=0, we find that ∇xf(xk,tk)⊤(xk−x⋆(tk))≥mek2\nabla_x f(x_k,t_k)^\top(x_k-x^\star(t_k)) \geq me_k^2. Combined with the Cauchy–Schwarz inequality, this gives ek≤e^ke_k \leq\widehat{e}_k. To estimate d(P,C)d(P,C) in (10), we define

d^k(P,C):=4h∥∇txf(xk,tk)∥m(1+Lm)ρcC(2ρpP+1),(21)\widehat{d}_k(P,C) := \frac{4h\left\|\nabla_{tx}f(x_k,t_k)\right\|}{m}\left(1+\frac{L}{m}\right)\rho_c^C(2\rho_p^P+1), \tag*{(21)}

which differs from dd in (10) by using the value of ∇txf\nabla_{tx}f at (xk,tk)(x_k,t_k) instead of the worst-case bound Γ\Gamma from Assumption 1.

At iteration kk, we then choose PkP_k and CkC_k using

(Pk,Ck)∈arg⁡min⁡(P,C)∈Ukfeasible a(P,C)e^k+d^k(P,C).(22)(P_k,C_k) \in\underset{(P,C)\in\mathcal{U}^{\mathrm{feasible}}_k}{\arg\min}\ a(P,C)\widehat{e}_k+\widehat{d}_k(P,C). \tag*{(22)}

The objective in (22) is a heuristic score that mimics the right-hand side of (9) using information available at tkt_k. The procedure for allocating the budget in Regime II is summarized in Algorithm 1.

Tracking Analysis

In this section, we analyze the allocation strategies derived for Regime I in (14) and for Regime II in (22).

Regime I Tracking Guarantees

With the allocation strategy from (14), the tracking error of the prediction-correction algorithm that executes prediction steps using (5) and correction steps using (6) follows directly from Proposition 1.

Corollary 1 (Tracking in Regime I). Suppose Assumption 1 holds and B/T≥Kmin⁡B/T \geq K_{\min}, where BB is from (8) and Kmin⁡K_{\min} is from (13). Consider the allocation of prediction and correction steps (Pˉ,Cˉ)(\bar{P},\bar{C}) from (14), and define aˉ:=a(Pˉ,Cˉ)\bar{a}:=a(\bar{P},\bar{C}). Then the budget constraint in (8) is satisfied, aˉ<1\bar{a}<1, and we have

ek≤aˉke0+D0h1−aˉk1−aˉe_k \leq\bar{a}^k e_0+D_0h\frac{1-\bar{a}^k}{1-\bar{a}}

for k∈{0,1,…,T}k\in\{0,1,\ldots,T\}, where D0D_0 is from (12).

Algorithm 1 Computationally Constrained Allocation
Require: Initial iterate x0∈Rnx_0\in\mathbb{R}^n, horizon T∈Z≥1T\in\mathbb{Z}_{\geq1}, budget B∈Z≥1B\in\mathbb{Z}_{\geq1} from (8), certificate parameters M≥1M\geq1 and ρ∈(0,1)\rho\in(0,1) from (15), and {Vn}n=0T\{V_n\}_{n=0}^T from (18), computed offline
1: Verify B≥VT(0)B\geq V_T(0)
2: q0←0q_0\leftarrow0, R0←BR_0\leftarrow B
3: for k=0,…,T−1k=0,\ldots,T-1 do
4: Compute ∣∇txf(xk,tk)∣\left|\nabla_{tx}f(x_k,t_k)\right| and e^k\widehat{e}_k from (20)
5: Compute d^k\widehat{d}_k using (21)
6: Form Ukfeasible\mathcal{U}^{\mathrm{feasible}}_k using (19)
7: Select (Pk,Ck)(P_k,C_k) according to (22)
8: Perform PkP_k prediction iterations from (5) using the objective f(⋅,tk)f(\cdot,t_k)
9: Sample the objective f(⋅,tk+1)f(\cdot,t_{k+1})
10: Perform CkC_k correction iterations from (6) using the objective f(⋅,tk+1)f(\cdot,t_{k+1}) to obtain xk+1x_{k+1}
11: qk+1←q+(qk;Pk,Ck)q_{k+1}\leftarrow q^+(q_k;P_k,C_k)
12: Rk+1←Rk−Pk−CkR_{k+1}\leftarrow R_k-P_k-C_k
13: end for

Table 1.

Proof. The budget constraint holds by Section III-B, and aˉ<1\bar{a}<1 because (Pˉ,Cˉ)∈Upc(\bar{P},\bar{C})\in\mathcal{U}^{\mathrm{pc}}. Since the allocation is constant, aj=aˉa_j=\bar{a} for all jj, and from (12), di≤D0hd_i\leq D_0h for all ii. Thus, the result follows from (11). □\square

Corollary 1 shows that under Regime I a uniform allocation suffices: the tracking error bound converges geometrically to a neighborhood of size D0h/(1−aˉ)D_0h/(1-\bar{a}). This neighborhood size depends on the sampling interval hh from Section II-A, which can be changed by a user. We now bound the tracking error in Regime II.

Regime II Feasibility and Tracking Guarantees

We first provide a sufficient condition under which (15) can be satisfied.

Theorem 1 (Certificate feasibility). Suppose Assumption 1 holds, and let M≥1M\geq1 and ρ∈(0,1)\rho\in(0,1) be given. If B≥VT(0)B\geq V_T(0), where VTV_T is from (18), then there exists an allocation that satisfies both the budget constraint (8) and the certificate (15).

Proof. See Appendix B. □\square

Under the condition of Theorem 1, Algorithm 1 generates such an allocation, and its tracking error is bounded as follows.

Theorem 2 (Tracking in Regime II). Suppose Assumption 1 holds, we define

dˉ:=max⁡0≤j≤T−1d(Pj,Cj).(23)\bar{d}:=\max_{0\leq j\leq T-1}d(P_j,C_j). \tag*{(23)}

and B≥VT(0)B\geq V_T(0) holds. Then, Ukfeasible\mathcal{U}^{\mathrm{feasible}}_k is nonempty for all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}. Moreover, the allocation generated by Algorithm 1 satisfies the budget constraint in (8), and

ek≤Mρke0+MD0h1−ρk1−ρ,∀k∈{0,1,…,T}.(24)e_k\leq M\rho^k e_0+MD_0h\frac{1-\rho^k}{1-\rho},\qquad\forall k\in\{0,1,\ldots,T\}. \tag*{(24)}

where MM and ρ\rho are from (15) and D0D_0 is from (12).

Proof. See Appendix C.

Theorem 2 provides a bound on the tracking error incurred by allocations produced by Algorithm 1. As in Regime I, the bound converges geometrically to a neighborhood whose size is proportional to the sampling interval hh.

A simpler condition using uniform allocation

Checking the condition B≥VT(0)B \ge V_T(0) in Theorem 1 requires solving the dynamic program (18). A simpler sufficient condition is obtained by restricting to uniform allocations (Pk,Ck)=(P,C)(P_k,C_k)=(P,C) for all k∈{0,1,…,T−1}k \in\{0,1,\ldots,T-1\}, which yields a budget condition, and an allocation that satisfies it, without computing VnV_n.

Theorem 3 (Uniform-allocation budget condition). Suppose Assumption 1 holds. Define

θT:=ρM1/T,\theta_T := \rho M^{1/T},

where M≥1M \ge1 and ρ∈(0,1)\rho\in(0,1) are from (15). Also define

Kunif:=min⁡P,C∈Z≥0a(P,C)≤θTP+C,K_{\mathrm{unif}} := \min_{\substack{P,C\in\mathbb{Z}_{\ge0}\\a(P,C)\le\theta_T}} P+C,

and let (P⋆,C⋆)(P^\star,C^\star) be any pair such that P⋆+C⋆=KunifP^\star+C^\star=K_{\mathrm{unif}}. If B≥TKunifB \ge T K_{\mathrm{unif}}, then the uniform allocation (Pk,Ck)≡(P⋆,C⋆)(P_k,C_k)\equiv(P^\star,C^\star) for k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\} satisfies the budget constraint in (8), the certificate in (15), and the bound in (24). Moreover, VT(0)≤BV_T(0)\le B, and therefore Algorithm 1 can be used.

Proof. See Appendix § 7.4.

Since VT(0)≤TKunifV_T(0)\le T K_{\mathrm{unif}}, the condition in Theorem 3 is more conservative than that in Theorem 1, but it does not require computing VnV_n. The results in Theorem 3 show that we can still attain the bound in (24) even while using a uniform allocation of TKunifT K_{\mathrm{unif}} total iterations.

Moreover, since the allocation is the same for every k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}, computing KunifK_{\mathrm{unif}} reduces to finding, for each number of prediction steps PP, the minimum number of correction steps that satisfies a(P,C)≤θTa(P,C)\le\theta_T. Since ρc∈(0,1)\rho_c\in(0,1), solving this inequality for CC gives

Cmin⁡(P):=max⁡{0,⌈log⁡(θT/[Aγ+(1+Aγ)ρpP])log⁡ρc⌉},C_{\min}(P):=\max\left\{0,\left\lceil\frac{\log\left(\theta_T/[A_\gamma+(1+A_\gamma)\rho_p^P]\right)}{\log\rho_c}\right\rceil\right\},

where AγA_\gamma is from (10), which implies that

Kunif=min⁡P∈Z≥0a(P,Cmin⁡(P))≤θTP+Cmin⁡(P).K_{\mathrm{unif}}=\min_{\substack{P\in\mathbb{Z}_{\ge0}\\a(P,C_{\min}(P))\le\theta_T}}P+C_{\min}(P).

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 BB.

Problem and Experimental Setup

Consider the following unconstrained problem, adapted from [2], in which the minimizer follows a moving reference whose speed changes over the horizon:

min⁡x∈R2f(x,t):=12(x−r(t))TQ(x−r(t))+κlog⁡(1+exp⁡(μcTx))(25)\min_{x\in\mathbb{R}^{2}} f(x,t):=\frac{1}{2}(x-r(t))^{\mathsf{T}}Q(x-r(t))+\kappa\log\left(1+\exp(\mu c^{\mathsf{T}}x)\right) \tag*{(25)}

where Q≻0Q\succ0, c∈R2c\in\mathbb{R}^{2} is a unit vector, κ,μ>0\kappa,\mu>0, and the reference r(t)=(cos⁡ϕ(t),sin⁡ϕ(t))Tr(t)=(\cos\phi(t),\sin\phi(t))^{\mathsf{T}} traces a closed curve with angular speed

ϕ˙(t):=ωs+ωf−ωs2[tanh⁡(t−tsw)−tanh⁡(t−tew)],(26)\dot{\phi}(t):=\omega_s+\frac{\omega_f-\omega_s}{2}\left[\tanh\left(\frac{t-t_s}{w}\right)-\tanh\left(\frac{t-t_e}{w}\right)\right], \tag*{(26)}

which produces a slow–fast–slow pattern of temporal variation. The objective in (25) satisfies Assumption 1 since ∇xxf\nabla_{xx}f is uniformly bounded between mImI and LILI with m=λmin⁡(Q)m=\lambda_{\min}(Q) and L=λmax⁡(Q)+κμ2/4L=\lambda_{\max}(Q)+\kappa\mu^2/4, and since ∇t∇xf(x,t)=−Q˙r(t)\nabla_t\nabla_x f(x,t)=-\dot{Q}r(t) gives ∥∇t∇xf(x,t)∥≤∥Q∥2sup⁡t∣ϕ˙(t)∣=Γ\|\nabla_t\nabla_x f(x,t)\|\le\|Q\|_2\sup_t|\dot{\phi}(t)|=\Gamma. The optimizer x⋆(tk)x^\star(t_k) is computed numerically and is used only to evaluate tracking performance.

We use Q=[1002]Q=\begin{bmatrix}1&0\\0&2\end{bmatrix}, c=(1,1)T/2c=(1,1)^{\mathsf{T}}/\sqrt{2}, κ=μ=1\kappa=\mu=1, ωs=0.05\omega_s=0.05, ωf=1\omega_f=1, ts=3.6t_s=3.6, te=9.6t_e=9.6, and w=0.5w=0.5, which gives m=1m=1, L=2.25L=2.25, and Γ=2\Gamma=2. We also use T=20T=20, h=1.2h=1.2, α=2/(m+L)\alpha=2/(m+L), β=0.2\beta=0.2, γ=0.5\gamma=0.5, B=140B=140, M=1000M=1000, and ρ=0.95\rho=0.95. The step size α=2/(m+L)\alpha=2/(m+L) minimizes ρp\rho_p, and the remaining parameters are chosen so that the fast phase of (26) occurs within the horizon and the experiment lies in Regime II. Here Kmin⁡=8K_{\min}=8 while B/T=7B/T=7, and therefore the experiment lies in Regime II. For the adaptive allocation, we compute the reserve function in (18) on a uniform grid of qq values with spacing 0.030.03. The uniform baseline uses (Pk,Ck)=(2,5)(P_k,C_k)=(2,5) for all kk. Both methods use x0=(3,−3)Tx_0=(3,-3)^{\mathsf{T}}, which gives e0≈3.69e_0\approx3.69, and we set ϕ(0)=0\phi(0)=0. To compare the two methods, we use the cumulative tracking errors

ET:=∑k=1Tekandemax⁡:=max⁡1≤k≤Tek,E_T:=\sum_{k=1}^{T}e_k \qquad\text{and}\qquad e_{\max}:=\max_{1\le k\le T}e_k,

where eke_k is from (7), and we refer to eTe_T as the terminal error. The initialization error e0e_0 is excluded from ETE_T and emax⁡e_{\max} because the prediction-correction method cannot change it.

Adaptive and Uniform Allocation

Under the above conditions, adaptive allocation reduces the cumulative tracking error ETE_T by about 45.5%45.5\% and the maximum error emax⁡e_{\max} by about $64.7% relative to the uniform baseline, at the cost of a larger terminal error (0.01320.0132 for the adaptive allocation vs. 0.001770.00177 for the uniform baseline). This behavior follows from the online allocation rule in (22). Since a(P,C)a(P,C) and k˙(P,C)\dot{k}(P,C) are nondecreasing in PP and CC, the rule spends as many iterations as UkfeasibleU_k^{\mathrm{feasible}} allows. As a result, the adaptive allocation front-loads the budget: it uses 10 iterations per interval during the first seven intervals, while reserving enough budget to satisfy the certificate, and it then tapers to two prediction steps per interval over the final five intervals. Spending more iterations early reduces the large initial error quickly, which lowers ETE_T and emax⁡e_{\max}, while the small allocation at the end leads to the larger terminal error. The uniform allocation uses (2,5)(2, 5) throughout.

Sensitivity to Initialization and Budget

This subsection examines whether the advantage of the adaptive allocation persists across initial errors and budgets. We first repeat the preceding experiment with B=140B = 140 for ten initial-error magnitudes ηj=10−1+2j/9\eta_j = 10^{-1+2j/9}, j=0,⋯ ,9j = 0, \cdots, 9, holding the direction of x0−x(0)x_0-x^{(0)} fixed. The reduction in ETE_T grows with ηj\eta_j, from about 7.4% at η0=0.1\eta_0 = 0.1 to about 67.7% at η9=10\eta_9 = 10. The terminal error of each method is the same across this range (0.013 for the adaptive allocation and 0.002 for the uniform baseline), and therefore terminal error alone does not reflect how well either method tracked the trajectory.

Next, we examine the cumulative error between the uniform baseline and the adaptive allocation with the budget BB ranging over {125,128,…,155}\{125, 128, \ldots, 155\}. These values all lie above the value VT(0)=122V_T(0) = 122 and below the Regime I budget TKmin⁡=160TK_{\min} = 160. We consider the initial error values e0∈{0.5,1,2,4}e_0 \in\{0.5, 1, 2, 4\}, which are shown in Figure 1. The adaptive allocation achieves a lower cumulative tracking error for all budgets and initial errors considered.

Cumulative error versus budget for adaptive and uniform allocations

Figure 1. Cumulative error vs. budget BB, adaptive (solid) against uniform (dashed), at four values of e0e_0. The drop in the uniform method between B=137B = 137 and B=140B = 140 is due to the increase in ⌊B/T⌋\lfloor B/T \rfloor from 6 to 7. The adaptive allocation outperforms the uniform allocation for all budgets and initial errors considered.

Finally, we examine the error reduction between the adaptive allocation and the uniform baseline with a budget BB ranging over {125,130,…,155}\{125, 130, \ldots, 155\} and values of the initial error ranging over e0∈{η0,η1,…,η9}e_0 \in\{\eta_0, \eta_1, \ldots, \eta_9\}. We find that the error reduction ranges from 7.4% (B=140B = 140, e0=η0e_0 = \eta_0) to 76.1% (B=135B = 135, e0=η9e_0 = \eta_9), with an average of 35.4%, which is shown in Figure 2. The decrease in this reduction that occurs between a budget of 135 and 140 corresponds to the improvement in the cumulative tracking error of the uniform baseline due to the increase in ⌊B/T⌋\lfloor B/T \rfloor from 6 (with an allocation of (2,4)(2, 4) to 7 (with an allocation of (2,5)(2, 5)) iterations. The advantage of the adaptive method is largest for large initial errors and for budgets below B=140B = 140 where the uniform baseline is limited to six iterations per sample, and the adaptive method produces a decrease in error across all values of the budget and initial error.

Reduction in cumulative tracking error over the joint budget and initial-error grid

Figure 2. Reduction in cumulative tracking error over the joint (B,e0)(B, e_0) grid. The adaptive method provides the largest decreases in error for large e0e_0 and for budgets below B=140B = 140, and it decreases the error for all values of these parameters considered.

Conclusion

This paper presented a method of adaptive allocation for the number of prediction and correction steps in a prediction-correction algorithm that is subject to computational constraints. We showed that when the average computational budget per sample exceeds a certain threshold, a uniform allocation suffices for a decaying tracking error bound. When it does not, we introduced a finite-horizon contraction certificate that yields budget conditions and an allocation algorithm that enforce explicit tracking error bounds. Simulations show that the adaptive allocation reduces cumulative tracking error compared with a uniform allocation across all problems considered. Future work includes extending this approach to other prediction schemes.

Appendix

Proof of Lemma 1

The recursion in (17) gives

qk=max⁡{0,max⁡0≤i<k∑j=ik−1s(Pj,Cj)}.q_k=\max\left\{0,\max_{0\le i<k}\sum_{j=i}^{k-1}s(P_j,C_j)\right\}.

Consequently, using (16), we see that having qk≤log⁡Mq_k\le\log M for every kk in {0,1,…,T}\{0,1,\ldots,T\} is equivalent to having

∑j=ik−1(log⁡a(Pj,Cj)−log⁡ρ)≤log⁡M\sum_{j=i}^{k-1}\left(\log a(P_j,C_j)-\log\rho\right)\le\log M

for every i∈Z≥0i\in\mathbb{Z}_{\geq0} satisfying 0≤i<k≤T0\le i<k\le T. Exponentiating proves the equivalence.

Proof of Theorem 1

Suppose VT(0)≤BV_T(0)\le B. We construct a feasible allocation using the minimizers in (18). Since VT(0)≤B<+∞V_T(0)\le B<+\infty and the values of VnV_n from (18) are nonnegative integers or +∞+\infty, the minimum defining VT(0)V_T(0) is attained. Let (P0,C0)(P_0,C_0) be a minimizer and q1=q+(P0,C0)q_1=q^+(P_0,C_0), so that

VT(0)=(P0+C0)+VT−1(q1).V_T(0)=(P_0+C_0)+V_{T-1}(q_1).

which implies VT−1(q1)<+∞V_{T-1}(q_1)<+\infty. Repeating the same argument at q1,q2,…q_1,q_2,\ldots, where qk+1=q+(qk;Pk,Ck)q_{k+1}=q^+(q_k;P_k,C_k) is from (17) for k=0,…,T−1k=0,\ldots,T-1, yields

VT(0)=∑k=0T−1(Pk+Ck)+V0(qT)=∑k=0T−1(Pk+Ck).V_T(0)=\sum_{k=0}^{T-1}(P_k+C_k)+V_0(q_T)=\sum_{k=0}^{T-1}(P_k+C_k).

This allocation satisfies the budget constraint in (8) since ∑k=0T−1(Pk+Ck)=VT(0)≤B\sum_{k=0}^{T-1}(P_k+C_k)=V_T(0)\le B. Moreover, each minimizer satisfies the constraint qk+1≤log⁡Mq_{k+1}\le\log M in (18), so the certificate (15) holds by Lemma 1.

Proof of Theorem 2

We show by induction that Rk≥VT−k(qk)R_k\ge V_{T-k}(q_k) and Ukfeasible≠∅U_k^{\mathrm{feasible}}\ne\varnothing for all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}. For k=0k=0, we have R0=B≥VT(0)=VT(q0)R_0=B\ge V_T(0)=V_T(q_0). Suppose Rk≥VT−k(qk)R_k\ge V_{T-k}(q_k). Then VT−k(qk)<+∞V_{T-k}(q_k)<+\infty, and the minimum in (18) defining VT−k(qk)V_{T-k}(q_k) is attained by some pair (Pˉ,Cˉ)(\bar P,\bar C). This pair satisfies q+(qk;Pˉ,Cˉ)≤log⁡Mq^+(q_k;\bar P,\bar C)\le\log M and

Pˉ+Cˉ+VT−k−1(q+(qk;Pˉ,Cˉ))=VT−k(qk)≤Rk.\bar P+\bar C+V_{T-k-1}\left(q^+(q_k;\bar P,\bar C)\right)=V_{T-k}(q_k)\le R_k.

Then (Pˉ,Cˉ)∈Ukfeasible(\bar P,\bar C)\in U_k^{\mathrm{feasible}}. For the selected (Pk,Ck)∈Ukfeasible(P_k,C_k)\in U_k^{\mathrm{feasible}}, the second condition in (19) gives Rk+1=Rk−Pk−Ck≥VT−k−1(qk+1)R_{k+1}=R_k-P_k-C_k\ge V_{T-k-1}(q_{k+1}), which completes the induction.

Since V0≡0V_0\equiv0, we have RT≥0R_T\ge0, and (8) holds. The first condition in (19) gives qk≤log⁡Mq_k\le\log M for all k∈{0,1,…,T}k\in\{0,1,\ldots,T\}, and the certificate in (15) holds by Lemma 1. Using the tracking error recursion in (11) and the certificate in (15), where an empty product equals 1≤M1\le M, we find

ek≤Mρke0+M∑i=0k−1ρk−i−1di.(27)e_k\le M\rho^k e_0+M\sum_{i=0}^{k-1}\rho^{k-i-1}d_i. \tag*{(27)}

Since di≤dˉd_i\le\bar d from (23), we find

ek≤Mρke0+Mdˉ∑i=0k−1ρk−i−1=Mρke0+Mdˉ1−ρk1−ρ.(28)e_k\le M\rho^k e_0+M\bar d\sum_{i=0}^{k-1}\rho^{k-i-1} =M\rho^k e_0+M\bar d\frac{1-\rho^k}{1-\rho}. \tag*{(28)}

The result follows from bounding dˉ≤D0h\bar d\le D_0h using (12).

Proof of Theorem 3

Consider the uniform allocation (Pk,Ck)≡(P∗,C∗)(P_k,C_k)\equiv(P^*,C^*) for k∈{0,…,T−1}k\in\{0,\ldots,T-1\}. Since P∗=KunifP^*=K_{\mathrm{unif}}, the total budget satisfies ∑k=0T−1(Pk+Ck)=TKunif≤B\sum_{k=0}^{T-1}(P_k+C_k)=TK_{\mathrm{unif}}\le B. Moreover, by the definition of KunifK_{\mathrm{unif}}, we have a(P∗,C∗)≤θT=ρM1/Ta(P^*,C^*)\le\theta_T=\rho M^{1/T}. Therefore, for all integers ii and kk such that 0≤i<k≤T0\le i<k\le T, we have

∏j=ik−1a(Pj,Cj)=a(P∗,C∗)k−i≤ρk−iM(k−i)/T≤Mρk−i,\prod_{j=i}^{k-1}a(P_j,C_j)=a(P^*,C^*)^{k-i}\le\rho^{k-i}M^{(k-i)/T}\le M\rho^{k-i},

where the last inequality follows from M≥1M\ge1 and (k−i)/T≤1(k-i)/T\le1. Hence, the certificate in (15) is satisfied. Following the same steps from (27) to (28) in the proof of Theorem 2, we find

ek≤Mρke0+MD0h1−ρk1−ρ.e_k\le M\rho^k e_0+MD_0h\frac{1-\rho^k}{1-\rho}.

Finally, by Lemma 1, the uniform allocation keeps qk≤log⁡Mq_k\le\log M for all kk, and therefore it is feasible in (18) at every stage. Hence VT(0)≤TKunif≤B.V_T(0)\le TK_{\mathrm{unif}}\le B.$

References

  1. [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, no. 17, pp. 4576–4591, 2016.DOI
  2. [2]A. Simonetto and E. Dall’Anese, “Prediction-correction algorithms for time-varying constrained optimization,” IEEE Transactions on Signal Processing, vol. 65, no. 20, pp. 5481–5494, 2017.DOI
  3. [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. [4]A. Simonetto, E. Dall’Anese, S. Paterlain, 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. [5]G. Bianchin, J. Cortés, J. I. Poveda, and E. Dall’Anese, “Time-varying optimization of LTI 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. [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. [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. [8]——, “Prediction-correction methods for time-varying convex optimization,” in 49th Asilomar Conference on Signals, Systems and Computers, 2015, pp. 666–670.DOI
  9. [9]S. Paternain, M. Morari, and A. Ribeiro, “A prediction-correction method for model predictive control,” in 2018 American Control Conference (ACC), 2018, pp. 4189–4194.DOI
  10. [10]N. Bastianello, R. Carli, and A. Simonetto, “Extrapolation-based prediction-correction methods for time-varying convex optimization,” Signal Processing, vol. 210, 2023, art. no. 109089.DOI
  11. [11]P. O. M. Skaf, D. Q. Mayne, and J. B. Rawlings, “Suboptimal model predictive control (feasibility implies stability),” IEEE Transactions on Automatic Control, vol. 44, no. 3, pp. 648–654, 1999.
  12. [18]H. Zhang, L. Yuan, and X. Cao, “Event-triggered nonlinear model predictive control for energy-aware UAV obstacle avoidance,” IEEE Internet of Things Journal, 2026, early access, doi: 10.1109/JIOT.2026.3728027.DOI
  13. [19]Y. Nesterov, Lectures on Convex Optimization, 2nd ed. Cham, Switzerland: Springer, 2018.DOI
  14. [20]S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge, UK: Cambridge University Press, 2004.

Paper details

vlnc:W_jsp7pdp9
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents