betaFeedback

Reading v1View latest version

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 R\mathbb{R} denote the reals and R≥0\mathbb{R}_{\ge0} denote the non-negative reals. We use N\mathbb{N} denote the non-negative integers. 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}_{\ge0}\to\mathbb{R}, we denote its gradient with respect to its first argument by ∇xf\nabla_x f, and we denote its derivative with respect to its second argument by ∇tf\nabla_t f. We use ∇xxf\nabla_{xx}f to denote the Hessian of ff with respect to its first argument, and ∇txf\nabla_{tx}f is the partial derivative of ∇xf\nabla_x f with respect to ff’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

x⋆(t):=arg⁡min⁡x∈Rn f(x,t),t∈T,(1)x^\star(t) := \underset{x\in\mathbb{R}^{n}}{\arg\min}\ f(x,t), \qquad t\in\mathbb{T}, \tag*{(1)}

where x∈Rnx\in\mathbb{R}^{n} is a decision variable, the set T:={t∈R≥0∣0≤t≤Tc}\mathbb{T}:=\{t\in\mathbb{R}_{\ge0}\mid0\le t\le T_c\} for a finite time horizon Tc>0T_c>0, and f:Rn×R≥0→Rf:\mathbb{R}^{n}\times\mathbb{R}_{\ge0}\to\mathbb{R} is a twice continuously differentiable and strongly convex function that varies in time such that f(⋅,t)f(\cdot,t) is twice continuously differentiable and strongly convex for all t∈Tt\in\mathbb{T}. The objective f(⋅,t)f(\cdot,t) is only known at past and current times tt, and future objectives are not known a priori. The goal is to compute the solution trajectory {x⋆(t)}t≥0\{x^\star(t)\}_{t\ge0}. 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 f(⋅,tk)f(\cdot,t_k) at each time instance tk:=kht_k:=kh, where k={0,1,⋯ ,T}k=\{0,1,\cdots,T\} for a finite time horizon T∈NT\in\mathbb{N} and some sampling interval h>0h>0. This approach allows us to replace (1) with

x⋆(tk):=arg⁡min⁡x∈Rn f(x,tk),k=0,1,⋯ ,T.(2)x^\star(t_k):=\underset{x\in\mathbb{R}^{n}}{\arg\min}\ f(x,t_k), \qquad k=0,1,\cdots,T. \tag*{(2)}

At each tkt_k, the current objective f(⋅,tk)f(\cdot,t_k) and its derivatives are known. We assume the following about f(⋅,tk)f(\cdot,t_k).

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

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

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

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

Assumption 1 ensures that f(⋅,tk)f(\cdot,t_k) is uniformly strongly convex and smooth, which guarantees that (2) has a unique minimizer at each tkt_k. The inequalities in (3) provide uniform curvature bounds over time, and the constant Γ\Gamma bounds the temporal variation of the gradient. The bound in (4) means that the time derivative of ∇xf(x,tk)\nabla_x f(x,t_k) 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 x0∈Rnx_0\in\mathbb{R}^{n}, a prediction-correction algorithm generates approximations {xk}k=0T\{x_k\}_{k=0}^{T} of the points along the optimal trajectory {x⋆(tk)}k=0T\{x^\star(t_k)\}_{k=0}^{T} associated with the problem in (2). Such methods proceed as follows. For k∈Nk\in\mathbb{N}, at iteration kk the algorithm has some iterate xkx_k, which it uses to predict the optimizer at the next iteration. This optimizer is arg⁡min⁡x∈Rnf(x,tk+1)\arg\min_{x\in\mathbb{R}^{n}} f(x,t_{k+1}), and some number of prediction steps Pk∈NP_k\in\mathbb{N} are executed to predict it using xkx_k. Then, the objective function f(⋅,tk+1)f(\cdot,t_{k+1}) is sampled, and some number of correction steps Ck∈NC_k\in\mathbb{N} 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 xk+1x_{k+1}, from which this process of prediction and correction repeats. With each iterate xkx_k, the PkP_k predictions and CkC_k corrections steps correspond to solving for the following iterate xk+1x_{k+1}.

Definition 1. For the problem in (2), an allocation is a collection {(Pk,Ck)}k=0T−1\{(P_k,C_k)\}_{k=0}^{T-1} of the numbers of prediction and correction steps that are executed for each sample of the objective.

The pair (Pk,Ck)(P_k,C_k) defines the total number of computations needed to compute xk+1x_{k+1} from xkx_k. 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

  1. Prediction: Between samples of the objective, some number of prediction steps are executed to predict the minimizer of f(⋅,tk+1)f(\cdot,t_{k+1}) from xkx_k, which is the last iterate computed when computing correction steps to minimize f(⋅,tk)f(\cdot,t_k). Under a first-order expansion in space and time we have

∇xf(z,tk+1)≈gk+Hk(z−xk)+hνk,\nabla_x f(z,t_{k+1})\approx g_k+H_k(z-x_k)+h\nu_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 νk:=∇txf(xk,tk)\nu_k:=\nabla_{tx}f(x_k,t_k). Since it is not always practical to solve for ∇xf(z,tk+1)=0\nabla_x f(z,t_{k+1})=0 exactly, we impose a relaxed optimality condition as in [2] by seeking a point zz that satisfies the condition ∇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 allows us to use the prediction step

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

where xkp,ℓx_k^{p,\ell} is the ℓ\ellth prediction iterate computed for the kkth sample of the objective and α>0\alpha>0 is the prediction step size. We initialize this step with xkp,0=xkx_k^{p,0}=x_k, where xkx_k is the last correction iterate computed when minimizing f(⋅,tk)f(\cdot,t_k). 2) Correction: After all PkP_k prediction steps are completed, the objective function f(⋅,tk+1)f(\cdot,t_{k+1}) is sampled, and then some number of correction steps are computed. We initialize xk+1c,0=xk+1p,Pkx_{k+1}^{c,0}=x_{k+1}^{p,P_k} and use the update law

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)}

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\beta>0 is the correction step size. After CkC_k correction steps, we set

xk+1:=xk+1c,Ck,x_{k+1}:=x_{k+1}^{c,C_k},

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 Pk,Ck∈NP_k,C_k\in\mathbb{N} to denote the numbers of prediction and correction iterations for minimizing f(⋅,tk)f(\cdot,t_k), and we let Kk:=Pk+CkK_k:=P_k+C_k denote the total number of iterations completed when computing xk+1x_{k+1} from xkx_k. Each prediction and correction step is treated as a single computation, and the budget constraint we define is

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

where B∈Z≥0B\in\mathbb{Z}_{\ge0} is the iteration budget for the entire horizon. Under (7), it is possible that KkK_k and Kk+1K_{k+1} are not the same for any kk. 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 BB from (7). Then, we derive allocations {(Pk,Ck)}k=0T−1\{(P_k,C_k)\}_{k=0}^{T-1} for each regime.

Tracking-Error Bound

We define

ρ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 from Assumption 1, α∈(0,2L)\alpha\in\left(0,\frac{2}{L}\right) is the step size from the prediction update law in (5), and β∈(0,2L)\beta\in\left(0,\frac{2}{L}\right) is the step size from the correction update law in (6). The terms ρp\rho_p and ρc\rho_c represent the contraction factors that quantify how quickly the prediction and correction steps converge, respectively. By Assumption 1, we know that ρp∈(0,1)\rho_p\in(0,1) and ρc∈(0,1)\rho_c\in(0,1). We define the tracking error at the sample time tkt_k as

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

where e0=∥x0−x⋆(0)∥e_0=\lVert x_0-x^\star(0)\rVert is fixed by initialization. We define the cumulative, mean, maximum, and terminal tracking errors as

ET:=∑k=1Tek,eˉ:=ETT,E_T:=\sum_{k=1}^{T}e_k,\qquad\bar e:=\frac{E_T}{T},
emax⁡:=max⁡1≤k≤Tek,efinal:=eT,e_{\max}:=\max_{1\le k\le T}e_k,\qquad e_{\mathrm{final}}:=e_T,

where the initialization error e0e_0 is excluded from the computations of ETE_T and emax⁡e_{\max} since the prediction-correction method cannot change e0e_0. 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 f(⋅,tk+1)f(\cdot,t_{k+1}) is bounded via

ek+1≤a(Pk,Ck)ek+d(Pk,Ck),(9)e_{k+1}\le a(P_k,C_k)e_k+d(P_k,C_k), \tag*{(9)}

where eke_k is from (8), e0=∥x0−x⋆(0)∥e_0=\lVert x_0-x^\star(0)\rVert, and we define

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

along with

Aγ:=1−γ+2γLm.(12)A_\gamma:=1-\gamma+\frac{2\gamma L}{m}. \tag*{(12)}

Proof. See Appendices A and C for case a) in [2].

In Proposition 1, the term a(Pk,Ck)a(P_k,C_k) quantifies the impact of the prediction-correction algorithm on the distance to the minimizer x⋆(tk)x^\star(t_k), and d(Pk,Ck)d(P_k,C_k) quantifies the impact of the movement of the minimizer on the distance to x⋆(tk)x^\star(t_k). Since ρp∈(0,1)\rho_p\in(0,1) and ρc∈(0,1)\rho_c\in(0,1), for any allocation in the sense of Definition 1, we have

0≤d(Pk,Ck)≤D0hfor all k=0,1,…,T−1,(13)0\le d(P_k,C_k)\le D_0h\quad\text{for all }k=0,1,\ldots,T-1, \tag*{(13)}

where D0:=12Γm(1+Lm)D_0:=\frac{12\Gamma}{m}\left(1+\frac{L}{m}\right), and Γ\Gamma, LL, and mm are from Assumption 1. By recursively unrolling (9), we have

ek≤(∏j=0k−1aj)e0+∑i=0k−1(∏j=i+1k−1aj)di,(14)e_k\le\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, \tag*{(14)}

where aj:=a(Pj,Cj)a_j:=a(P_j,C_j) and di:=d(Pi,Ci)d_i:=d(P_i,C_i). This error bound provides tracking performance on a finite horizon since it accounts for the numbers of prediction and correction steps for each kk. Now, we look to determining the impact of the budget BB from (7).

Budget Allocation

The mapping a(Pk,Ck)a(P_k,C_k) in (10) is decreasing in both PkP_k and CkC_k since ρp,ρc∈(0,1)\rho_p,\rho_c \in(0,1). From (14) we see that it is desirable to have aj<1a_j < 1 for all j∈{0,1,…,k−1}j \in\{0,1,\ldots,k-1\}, and therefore we seek to identify the minimum number of total prediction and correction steps needed to ensure aj<1a_j < 1. Let

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

so that for any K≥Kmin⁡K \geq K_{\min} there exists a pair (Pk,Ck)(P_k,C_k) such that Pk+Ck≤KP_k+C_k \leq K and a(Pk,Ck)<1a(P_k,C_k)<1. Using (15), we see that there exist two regimes based on whether or not the budget BB from (7) is large enough to allow for Pk+Ck≥Kmin⁡P_k+C_k \geq K_{\min} for all k∈{0,1,…,T−1}k \in\{0,1,\ldots,T-1\}. The two regimes are

Regime I: BT≥Kmin⁡andRegime II: BT<Kmin⁡.(16)\text{Regime I: }\frac{B}{T}\geq K_{\min} \quad\text{and}\quad \text{Regime II: }\frac{B}{T}<K_{\min}. \tag*{(16)}

In Regime I it is possible to satisfy Pk+Ck≥Kmin⁡P_k+C_k \geq K_{\min} for all k∈{0,1,…,T−1}k \in\{0,1,\ldots,T-1\}, but in Regime II it is not possible to do so. Therefore, in Regime II at least one iteration kk has a(Pk,Ck)≥1a(P_k,C_k)\geq1. The following subsections define the allocations we use for each regime.

Regime I: Sufficient Average Budget

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

Kbase:=⌊BT⌋andrB:=B−TKbase,(17)K_{\mathrm{base}} := \left\lfloor\frac{B}{T}\right\rfloor \quad\text{and}\quad r_B := B-TK_{\mathrm{base}}, \tag*{(17)}

where KbaseK_{\mathrm{base}} is the largest number of iterations that makes all KkK_k’s equal while obeying the budget constraint in (7), and rBr_B is the remaining budget after using Pk+Ck=KbaseP_k+C_k=K_{\mathrm{base}} for all k∈{0,1,…,T−1}k \in\{0,1,\ldots,T-1\}. Using any set IB⊆{0,1,…,T−1}I_B\subseteq\{0,1,\ldots,T-1\} where ∣IB∣=rB|I_B|=r_B, we choose

Kk={Kbase+1k∈IB,Kbasek∉IB,(18)K_k = \begin{cases} K_{\mathrm{base}}+1 & k\in I_B,\\ K_{\mathrm{base}} & k\notin I_B, \end{cases} \tag*{(18)}

which satisfies the budget constraint in (7), and Kk≥Kmin⁡K_k\geq K_{\min} holds for all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}. For each kk, we choose a pair

(Pk,Ck)∈Ukpc,(19)(P_k,C_k)\in U_k^{pc}, \tag*{(19)}

where

Ukpc:={(P,C)∈Z≥02:P+C=Kk, a(P,C)<1},U_k^{pc}:=\{(P,C)\in\mathbb{Z}_{\geq0}^{2}:P+C=K_k,\ a(P,C)<1\},

where KkK_k is given for each k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\} by (18). Since Kk≥Kmin⁡K_k\geq K_{\min}, the set UkpcU_k^{pc} is nonempty.

Regime II: Insufficient Average Budget

Suppose that B/T<Kmin⁡B/T<K_{\min}, where Kmin⁡K_{\min} is from (15), BB is from (7), and TT 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 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\}. However, the error recursion in (9) still provides an upper bound on the distance to the minimizer at each time tkt_k. Although we can no longer guarantee that error decreases for every kk, an allocation of prediction and correction iterations can still ensure that the error remains bounded over the whole time horizon {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 certificate

∏j=ik−1a(Pj,Cj)≤Mρk−ifor all i∈N,(20)\prod_{j=i}^{k-1}a(P_j,C_j)\leq M\rho^{k-i} \quad\text{for all }i\in\mathbb{N}, \tag*{(20)}

such that 0≤i<k≤T0\leq i<k\leq T. This property means that even though pointwise contraction is not enforced at all times, the error can grow by at most a factor of MM relative to decay at rate ρ\rho, 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 ρ\rho at each time. 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⁡ρ,(21)s(P_k,C_k):=\log a(P_k,C_k)-\log\rho, \tag*{(21)}

where ρ\rho is from (20). Intuitively, s(Pk,Ck)s(P_k,C_k) measures the extent to which a given pair (Pk,Ck)(P_k,C_k) ensures contraction with rate at least ρ\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 (Pk,Ck)(P_k,C_k) ensures contraction with at least rate ρ\rho, and if s(P,C)>0s(P,C)>0, then it does not. 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 cumulative non-negativity of s(Pk,Ck)s(P_k,C_k) and hence the cumulative failure of pairs (Pk,Ck)(P_k,C_k) to ensure contraction with at least rate ρ\rho over time. Then starting with q0=0q_0=0, we set

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

The term qkq_k increases if a(Pk,Ck)>ρa(P_k,C_k)>\rho at iteration kk, decreases 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. We use qkq_k to prevent the tracking error from becoming too large. The following elementary lemma shows that one can enforce (20) by bounding qkq_k from (22).

Lemma 1 (Necessary and sufficient condition for (20)). The certificate (20) holds for all i∈Ni\in\mathbb{N} satisfying 0≤i<k≤T0\leq i<k\leq T if and only if

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

where qkq_k is from (22) and MM is from (20).

Proof. The recursion in (22) gives

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

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

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

for every i∈Ni\in\mathbb{N} satisfying 0≤i<k≤T0\leq i<k\leq T. Exponentiating proves the equivalence. □\square

Aside from bounding qkq_k at iteration kk, we also seek to determine how many total prediction and correction steps should be used at iterations after kk.

Exact reserve function

Let n:=T−kn := T-k and q∈[0,log⁡M]q \in[0,\log M]. We define the “reserve function” as

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

which ensures q+(q;Pn,Cn)≤log⁡Mq^+(q;P_n,C_n)\leq\log M while counting the total prediction and correction iterations used up to a given iteration. We set V0(q):=0V_0(q):=0, and Vn(q):=+∞V_n(q):=+\infty for any time nn at which the condition q+(q;Pn,Cn)≤log⁡Mq^+(q;P_n,C_n)\leq\log M cannot be satisfied. The value of Vn(q)V_n(q) is the minimum number of total prediction and correction steps needed to satisfy the constraint q+(q;Pn,Cn)≤log⁡Mq^+(q;P_n,C_n)\leq\log M for the nn remaining samples of the objective. The value of Vn(q)V_n(q) also depends on the certificate parameters MM and ρ\rho from (20) and the term a(Pn,Cn)a(P_n,C_n) for each nn, and it is solved offline for all nn, before the horizon begins.

Computing Allocations

While VV from (23) ensures that it is still possible to enforce the condition in (20), we still need to choose PkP_k and CkC_k for all kk. Under a specified budget BB, allocations with Pk+Ck>BP_k+C_k>B for any kk can be ignored because they are infeasible. Among feasible allocations, 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}.(24)U_k^{\mathrm{feasible}}:=\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*{(24)}

where the first condition in the set definition enforces (20) for i={0,1,…,T−1}i=\{0,1,\ldots,T-1\} and k={0,1,…,T−1}k=\{0,1,\ldots,T-1\}, and the second condition ensures that we satisfy the budget constraint in (7).

In choosing among feasible allocations, we define

e^k:=∥∇xf(xk,tk)∥m,(25)\widehat e_k:=\frac{\|\nabla_x f(x_k,t_k)\|}{m}, \tag*{(25)}

where mm is from Assumption 1. By strong convexity, using the fact that the solution x⋆(tk)x^\star(t_k) satisfies ∇xf(x⋆(tk),t)=0\nabla_x f(x^\star(t_k),t)=0, we find that ∇xf(xk,tk)⊤(xk−x⋆(t))≥mek2\nabla_x f(x_k,t_k)^\top(x_k-x^\star(t))\geq m e_k^2, which implies that eke_k in (25) satisfies ek≤e^ke_k\leq\widehat e_k, where eke_k is from (8). Then we can define

d^k(P,C):=4h∥∇txf(xk,tk)∥m(1+Lm)ρcp(2ρpP+1),(26)\widehat d_k(P,C):=\frac{4h\|\nabla_t x f(x_k,t_k)\|}{m}\left(1+\frac{L}{m}\right)\rho_c^p(2\rho^pP+1), \tag*{(26)}

which differs from dd in (11) by using the actual value of the gradient ∇txf\nabla_t x f instead of the worst-case gradient bound Γ\Gamma.

Algorithm 1 Debt-State Computationally Constrained Allocation

Require: Initial iterate x0∈Rnx_0\in\mathbb{R}^n, horizon T∈NT\in\mathbb{N}, budget B∈Z≥0B\in\mathbb{Z}_{\geq0} from (7), certificate parameters M≥1M\geq1 and ρ∈(0,1)\rho\in(0,1) from (20), and VT(0)V_T(0) from (23).

  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)∥\|\nabla_t x f(x_k,t_k)\| and e^k\widehat e_k from (25)

  5. Compute d^k\widehat d_k using (26)

  6. Form UkfeasibleU_k^{\mathrm{feasible}} using (24)

  7. Select (Pk,Ck)(P_k,C_k) according to (27)

  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

from Assumption 1. Then the values of PkP_k and CkC_k can be chosen at iteration kk using

(Pk,Ck)∈arg⁡min⁡(P,C)∈Ukfeasible  a(P,C)e^k+d^k(P,C),(27)(P_k,C_k)\in\underset{(P,C)\in U_k^{\mathrm{feasible}}}{\arg\min}\;a(P,C)\widehat e_k+\widehat d_k(P,C), \tag*{(27)}

where e^k\widehat e_k is from (25) and d^k\widehat d_k is from (26). In (27), we use d^k\widehat d_k instead of dkd_k because the value of ∇txf\nabla_{tx}f is known, and using this exact value more accurately quantifies the impact of the choice of (Pk,Ck)(P_k,C_k) than using the worst-case bound Γ\Gamma, which leads to greater flexibility in choosing (Pk,Ck)(P_k,C_k). 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 B/T≥Kmin⁡B/T\geq K_{\min}, where BB is from (7) and Kmin⁡K_{\min} is from (15). Fix any set IB⊆{0,1,…,T−1}\mathcal{I}_B\subseteq\{0,1,\ldots,T-1\} such that ∣IB∣=rB|\mathcal{I}_B|=r_B, where rBr_B is from (17). Suppose the allocation of prediction and correction steps satisfies (19), and define

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

Then the budget constraint in (7) is satisfied, and we have

ek≤ζmax⁡τkaˉke0+D0h[1−(ζmax⁡aˉ)k1−ζmax⁡aˉ+1−aˉk−τk1−aˉ].e_k\leq\zeta_{\max}^{\tau_k}\bar a^k e_0+D_0h\left[\frac{1-(\zeta_{\max}\bar a)^k}{1-\zeta_{\max}\bar a}+\frac{1-\bar a^{k-\tau_k}}{1-\bar a}\right].

for k∈{0,1,…,T}k \in\{0,1,\ldots,T\}, where aˉ<1\bar{a}<1,

ζmax⁡:=max⁡k∈{0,1,…,T−1}{ρc,a(Pk+1,Ck)a(Pk,Ck)}<1,\zeta_{\max}:=\max_{k\in\{0,1,\ldots,T-1\}}\left\{\rho_c,\frac{a(P_k+1,C_k)}{a(P_k,C_k)}\right\}<1,
τk:=∣{0,1,…,k−1}∩IB∣,\tau_k:=\left|\{0,1,\ldots,k-1\}\cap\mathcal{I}_B\right|,

D0:=12Γm(1+Lm)D_0:=\frac{12\Gamma}{m}\left(1+\frac{L}{m}\right), rBr_B is from (17), eke_k is from (8), and e0:=∥x0−x⋆(0)∥e_0:=\lVert x_0-x^\star(0)\rVert.

Proof. Since every selected allocation satisfies (Pk,Ck)∈Ukpc(P_k,C_k)\in\mathcal{U}^{\mathrm{pc}}_k for all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}, we have

a(Pk,Ck)≤{ζmax⁡aˉk∈IBaˉk∉IB.(29)a(P_k,C_k)\le \begin{cases} \zeta_{\max}\bar{a} & k\in\mathcal{I}_B\\ \bar{a} & k\notin\mathcal{I}_B. \end{cases} \tag*{(29)}

This bound accounts for whether the additional computation at a time k∈IBk\in\mathcal{I}_B is performed as a prediction or correction step since k∈IBk\in\mathcal{I}_B from (18) gives Kk=Kbase+1K_k=K_{\mathrm{base}}+1. Using the tracking bound in (14), we can separate out the bound based on whether k∈IBk\in\mathcal{I}_B or k∉IBk\notin\mathcal{I}_B to find

ek≤[∏j∈IBj≤k−1aj⋅∏ℓ∉IBℓ≤k−1aℓ]e0+∑i∈IBi≤k−1(∏j=i+1k−1aj)di+∑i∉IBi≤k−1(∏ℓ=i+1k−1aℓ)di.e_k\le\left[\prod_{\substack{j\in\mathcal{I}_B\\j\le k-1}}a_j\cdot\prod_{\substack{\ell\notin\mathcal{I}_B\\\ell\le k-1}}a_\ell\right]e_0 +\sum_{\substack{i\in\mathcal{I}_B\\i\le k-1}}\left(\prod_{j=i+1}^{k-1}a_j\right)d_i +\sum_{\substack{i\notin\mathcal{I}_B\\i\le k-1}}\left(\prod_{\ell=i+1}^{k-1}a_\ell\right)d_i.

Substituting in di≤dˉd_i\le\bar{d} from (28) and the bound from (29) yields

ek≤[(ζmax⁡aˉ)τk⋅aˉk−τk]e0+dˉ[1−(ζmax⁡aˉ)τk1−ζmax⁡aˉ+1−aˉk−τk1−aˉ]≤ζmax⁡τkaˉke0+dˉ[1−(ζmax⁡aˉ)τk1−ζmax⁡aˉ+1−aˉk−τk1−aˉ].\begin{aligned} e_k\le\left[(\zeta_{\max}\bar{a})^{\tau_k}\cdot\bar{a}^{k-\tau_k}\right]e_0 +\bar{d}\left[\frac{1-(\zeta_{\max}\bar{a})^{\tau_k}}{1-\zeta_{\max}\bar{a}}+\frac{1-\bar{a}^{k-\tau_k}}{1-\bar{a}}\right] \\ &\le\zeta_{\max}^{\tau_k}\bar{a}^k e_0+\bar{d}\left[\frac{1-(\zeta_{\max}\bar{a})^{\tau_k}}{1-\zeta_{\max}\bar{a}}+\frac{1-\bar{a}^{k-\tau_k}}{1-\bar{a}}\right]. \end{aligned}

The result follows from bounding dˉ\bar{d} 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 hh 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 M≥1M\ge1 and ρ∈(0,1)\rho\in(0,1) be given. Then, the certificate in (20) is satisfiable for all i∈Ni\in\mathbb{N} such that 0≤i<k≤T0\le i<k\le T with total budget BB if

B≥VT(0),B\ge V_T(0),

where VTV_T is from (23).

Proof. Suppose VT(0)≤BV_T(0)\le B. We construct a feasible allocation using the minimizers in (23). Since VT(0)≤B<+∞V_T(0)\le B<+\infty and the values of VnV_n from (23) are nonnegative integers or +∞+\infty, we define VT(0)V_T(0) with q1=q+(0;P0,C0)q_1=q^+(0;P_0,C_0) as

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 (22) for k=0,…,T−1k=0,\ldots,T-1 yields

VT(0)=(P0+C0)+VT−1(q1)=⋮=∑k=0T−1(Pk+Ck)+V0(qT)=∑k=0T−1(Pk+Ck).\begin{aligned} V_T(0)&=(P_0+C_0)+V_{T-1}(q_1)\\ &\mathrel{\phantom{=}}\vdots\\ &=\sum_{k=0}^{T-1}(P_k+C_k)+V_0(q_T)=\sum_{k=0}^{T-1}(P_k+C_k). \end{aligned}

This construction satisfies the budget constraint in (7) since ∑k=0T−1(Pk+Ck)=VT(0)≤B\sum_{k=0}^{T-1}(P_k+C_k)=V_T(0)\le B 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 M≥1M\ge1 and ρ∈(0,1)\rho\in(0,1) under a given budget BB. 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 B≥VT(0)B\ge V_T(0), suppose Assumption 1 holds, and define

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

For the allocation generated by Algorithm 1, we have

ek≤Mρke0+MD0h1−ρk1−ρ(31)e_k\le M\rho^k e_0+MD_0h\frac{1-\rho^k}{1-\rho} \tag*{(31)}

for k∈{0,1,…,T}k\in\{0,1,\ldots,T\}, where M≥1M\ge1 and ρ∈(0,1)\rho\in(0,1) are from (20), D0:=12Γm(1+Lm)D_0:=\frac{12\Gamma}{m}\left(1+\frac{L}{m}\right), eke_k is from (8), and e0:=∥x0−x⋆(0)∥e_0:=\lVert x_0-x^\star(0)\rVert.

Proof. Using the tracking error recursion in (14) and the contraction certificate in (20) yields

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

Since di≤dˉd_i\le\bar{d} from (30), we find

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

The result follows from bounding dˉ\bar{d} 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 hh from Section II-A, it can be reduced by sampling the objective more frequently.

A sufficient condition using uniform allocation

Since the function Vn(q)V_n(q) 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 (Pk,Ck)=(P,C)(P_k,C_k)=(P,C) for some (P,C)∈Z≥02(P,C)\in\mathbb{Z}_{\geq0}^2 and all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}. This choice will simplify the implementation of Algorithm 1 by eliminating the need to explicitly compute VnV_n.

Theorem 4 (Closed-form sufficient budget condition). Consider Problem 1, and suppose Assumption 1 holds. Define

θT:=ρM1/T,(34)\theta_T := \rho^{M^{1/T}}, \tag*{(34)}

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

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

Consider BB from (7). If B≥TKunifB\geq T K_{\mathrm{unif}}, then the total number of computations for k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\} under this uniform allocation satisfies the total budget (7), the contraction certificate (20), and the tracking bound (31). Such a bound BB allows for admitting allocations generated by Algorithm 1.

Proof. Consider any pair

(P⋆,C⋆)∈arg min⁡P,C∈Z≥0a(P,C)≤θTP+C,(P^\star,C^\star)\in\operatorname*{arg\,min}_{\substack{P,C\in\mathbb{Z}_{\geq0}\\a(P,C)\leq\theta_T}} P+C,

and consider the constant 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\}. Since P⋆+C⋆=KunifP^\star+C^\star=K_{\mathrm{unif}}, the total budget satisfies ∑k=0T−1(Pk+Ck)=TKunif≤B\sum_{k=0}^{T-1}(P_k+C_k)=T K_{\mathrm{unif}}\leq B.

Moreover, by the definition of KunifK_{\mathrm{unif}}, we have a(P⋆,C⋆)≤θT=ρM1/Ta(P^\star,C^\star)\leq\theta_T=\rho^{M^{1/T}}. Therefore, for all ii and kk such that 0≤i<k≤T0\leq i<k\leq T, we have

∏j=ik−1a(Pj,Cj)=a(P⋆,C⋆)k−i≤(ρM1/T)k−i≤ρM(k−i)/T≤Mρk−i,\begin{aligned} \prod_{j=i}^{k-1}a(P_j,C_j) &=a(P^\star,C^\star)^{k-i} \leq\left(\rho^{M^{1/T}}\right)^{k-i}\\ &\leq\rho^{M(k-i)/T}\\ &\leq M\rho^{k-i}, \end{aligned}

where the last inequality follows from M≥1M\geq1 and (k−i)/T≤1(k-i)/T\leq1. Hence, the contraction certificate (20) is satisfied for all ii and kk such that 0≤i<k≤T0\leq i<k\leq T. Following the same steps from (32) to (33) in the proof of Theorem 3, we find

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

The results in Theorem 4 show that we can still attain the bound in (31) even while using a uniform allocation of TKunifT K_{\mathrm{unif}} total computations. Since the total number of prediction and correction steps is identical for each k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}, we can reduce the allocation to just solving for the number of correction steps for each kk.

Consider the bound a(Pk,Ck)≤θTa(P_k,C_k)\leq\theta_T where a(Pk,Ck)a(P_k,C_k) is from (10) and θT\theta_T is from (34). Fix Pk=PP_k=P for all k∈{0,1,…,T−1}k\in\{0,1,\ldots,T-1\}. Then we can solve for the minimum number of correction steps as

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 (12) and ρc∈(0,1)\rho_c\in(0,1), which implies that

Kunif=min⁡P∈Z≥0a(P,Cmin⁡(P))≤θTP+Cmin⁡(P).K_{\mathrm{unif}}=\min_{\substack{P\in\mathbb{Z}_{\geq0}\\a(P,C_{\min}(P))\leq\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 unconstrained problem from [2]:

min⁡x∈R2f(x,t):=12(x−r(t))⊤Q(x−r(t))+κlog⁡(1+exp⁡(μc⊤x)),(35)\min_{x\in\mathbb{R}^2} f(x,t):=\frac{1}{2}(x-r(t))^\top Q(x-r(t))+\kappa\log(1+\exp(\mu c^\top x)), \tag*{(35)}

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))⊤r(t)=(\cos\phi(t),\sin\phi(t))^\top traces a closed curve with angular speed

ϕ˙(t):=ωs+ωf−ωs2[tanh⁡(t−tsw)−tanh⁡(t−tew)],\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],

which produces a slow–fast–slow pattern of temporal variation. The objective in (35) satisfies Assumption 1 since ∇xxf\nabla_{xx}f is uniformly bounded between mImI and LILI for constants mm and LL determined by QQ and κμ2\kappa\mu^2, and since ∇txf(x,t)=−Qr˙(t)\nabla_{tx}f(x,t)=-Q\dot r(t) gives ∥∇txf(x,t)∥≤∥Q∥2sup⁡t∣ϕ˙(t)∣=:Γ\|\nabla_{tx}f(x,t)\|\leq\|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)⊤/2c=(1,1)^\top/\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. Here Kmin⁡=8K_{\min}=8 while B/T=7B/T=7, so the experiment lies in Regime II. The uniform baseline uses (Pk,Ck)=(2,5)(P_k,C_k)=(2,5) for all kk, which is the pair that minimizes a(Pk,Ck)a(P_k,C_k) while satisfying Kk=7K_k=7. Both methods start from x0=(3,−3)⊤x_0=(3,-3)^\top.

Adaptive and Uniform Allocation

Adaptive allocation reduces the cumulative tracking error ETE_T by about 45.5% and the maximum error emax⁡e_{\max} 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 e^k\hat e_k is large while xkx_k is far from x⋆(tk)x^\star(t_k), so the rule spends most of the budget within the first several intervals, and then it tapers to two iterations per interval once e^k\hat e_k 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 ηj=10−1+2j/9\eta_j=10^{-1+2j/9}, j=0,…,9j=0,\ldots,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.6% at ηj=0.1\eta_j=0.1 to about 76.1% at ηj=10\eta_j=10, since a larger initial gap raises e^0\hat e_0 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 BB over {125,128,⋯ ,155}\{125,128,\cdots,155\}, which lies above the reserve VT(0)=122V_T(0)=122 and below the Regime I budget TKmin⁡=160TK_{\min}=160, for e0∈{0.5,1,2,4}e_0\in\{0.5,1,2,4\} (Figure 1). The reduction grows with e0e_0 at every budget, from 33.0% to 49.8% at B=125B=125. It peaks near B=135B=135 at 35.9–61% and eases to 14.4–47.6% by B=155B=155, since the uniform method improves when KbaseK_{\mathrm{base}} from (17) increases from 6 (with (2, 4)) to 7 (with (2, 5)) between B=135B=135 and B=140B=140. Over the full grid of B∈{125,130,⋯ ,155}B\in\{125,130,\cdots,155\} and ηj\eta_j (Figure 2), the reduction ranges from 7.4% (B=140B=140, e0=0.1e_0=0.1) to 76.1% (B=135B=135, e0=10e_0=10), 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.

Cumulative error versus budget for adaptive and uniform methods

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 the increase in KbaseK_{\mathrm{base}} from 6 to 7.

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 performs best under a large e0e_0 and a small BB, and similarly to the uniform method under a small e0e_0 and a large BB.

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. [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. [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. [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. 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. [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. [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 2015 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 Annual American Control Conference (ACC), 2018, pp. 4189–4194.DOI
  10. [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.
  11. [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

Paper details

vlnc:W_jsp7pdp9
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents