PaperlayerView exact revision on arXiv

Source-linked AI summary

A Class of Prediction-Correction Methods for Time-Varying Convex Optimization

Andrea Simonetto, Aryan Mokhtari, Alec Koppel, Geert Leus, Alejandro Ribeiro

arXiv:1509.05196v2cs.ITmath.OC

TL;DR

The paper addresses how to track optimizers of continuously time-varying unconstrained convex objectives without repeatedly solving each sampled problem. It proposes prediction-correction algorithms based on optimality-condition dynamics, with gradient and Newton corrections and approximate variants when time variation is unknown. Under suitable conditions, the methods achieve O(h^2) asymptotic error and sometimes O(h^4), while numerical studies support their practical utility and identify latency trade-offs.

  • Problem

    Repeatedly solving sampled time-varying optimization problems is often impractical for real-time applications, motivating methods that track the solution trajectory as objectives change.

  • Method

    The paper uses discrete-time prediction-correction algorithms: predictors follow iso-residual optimality dynamics, while gradient or Newton corrections refine each prediction; AGT and ANT estimate unknown time variation.

  • Results

    O(h^2) asymptotic error, and in some cases O(h^4), is established for the proposed methods, improving on the O(h) bound of correction-only methods.

  • Takeaways & Limitations

    The methods provide sampling-controlled neighborhoods of the optimal trajectory, with second-order methods offering high accuracy when their computational latency can be afforded.

  • Takeaways & Limitations

    Higher-accuracy second-order methods can have too much computational latency for closed-loop control, and the analysis relies on strong convexity and smoothness assumptions.

Abstract

from arXiv · show

This paper considers unconstrained convex optimization problems with time-varying objective functions. We propose algorithms with a discrete time-sampling scheme to find and track the solution trajectory based on prediction and correction steps, while sampling the problem data at a constant rate of $1/h$, where $h$ is the length of the sampling interval. The prediction step is derived by analyzing the iso-residual dynamics of the optimality conditions. The correction step adjusts for the distance between the current prediction and the optimizer at each time step, and consists either of one or multiple gradient steps or Newton steps, which respectively correspond to the gradient trajectory tracking (GTT) or Newton trajectory tracking (NTT) algorithms. Under suitable conditions, we establish that the asymptotic error incurred by both proposed methods behaves as $O(h^2)$, and in some cases as $O(h^4)$, which outperforms the state-of-the-art error bound of $O(h)$ for correction-only methods in the gradient-correction step. Moreover, when the characteristics of the objective function variation are not available, we propose approximate gradient and Newton tracking algorithms (AGT and ANT, respectively) that still attain these asymptotical error bounds. Numerical simulations demonstrate the practical utility of the proposed methods and that they improve upon existing techniques by several orders of magnitude.

I. INTRODUCTION

The paper develops prediction-correction algorithms for tracking the solution trajectory of continuously time-varying, strongly convex objectives from arbitrary initial points. Sampling-based prediction and correction avoid repeatedly solving each sampled optimization problem while achieving error bounds that improve on correction-only methods.

  • Problem: Time-varying optimization seeks the solution trajectory x*(t) of unconstrained objectives whose functions vary continuously in time.The objectives are smooth and strongly convex, ensuring a unique optimizer at each time.
  • Motivation: Repeatedly solving every sampled problem is often too slow for real-time applications, and static-objective iterative methods do not generally extend easily to changing objectives.The paper identifies computation time and unpredictable solve duration as practical obstacles.
  • Approach: The proposed methods use discrete-time prediction-correction updates initialized at an arbitrary point to track near-optimal variables at successive sampling times.Prediction uses the changing solution dynamics, while correction reduces the distance from the optimizer of the updated objective.
  • Contributions: O(h^2) asymptotic error, and in some cases O(h^4), improves on the O(h) bound of the existing correction-only method.The bounds depend on the sampling period h and are established under suitable assumptions.
  • Approach: The predictor is derived from optimality conditions and iso-residual dynamics, then discretized using prior information available at the current sampling time.The correction step can use gradient or Newton updates.

B. Newton trajectory tracking

Newton trajectory tracking combines the GTT predictor with Newton correction steps, using second-order information throughout. It can require higher per-step cost but fewer iterations, especially for poorly conditioned problems, and approximate time-variation information supports a related ANT method.

  • Newton trajectory tracking: NTT uses second-order information for both prediction and correction, including a partial Hessian inverse.The Hessian-inverse computation has complexity O(n^3).
  • Newton trajectory tracking: NTT uses the same prediction step as GTT but applies τ Newton corrections to the predicted solution.The corrected variable after τ iterations is the NTT decision variable at the next sampling time.
  • Computational trade-off: Newton steps cost O(n^3), whereas gradient steps cost O(n), so fixed sampling periods permit fewer NTT than GTT correction iterations.Newton generally needs fewer iterations to reach comparable accuracy.
  • Computational trade-off: NTT is preferable to GTT for problems with large condition numbers because its convergence-speed advantage becomes substantial.This preference trades more expensive individual steps for fewer correction iterations.
  • Approximate time derivatives: When the objective’s time variation is unavailable, AGT and ANT approximate the mixed partial derivative using a first-order backward finite difference.The approximation uses information from the previous sampling step and has error O(h).
  • Approximate time derivatives: The derivative approximation does not change the asymptotic error orders of the tracking methods, although AGT has a slightly larger bound than GTT.The paper states that AGT and GTT retain identical error orders.

III. CONVERGENCE ANALYSIS

The convergence analysis links sampling error to the smoothness and strong convexity assumptions, establishing bounded prediction error and convergence to a sampling-dependent neighborhood of the optimal trajectory. These assumptions can be weakened when the optimizer remains in a known domain, but then convergence may be only local.

  • Convergence framework: The analysis establishes convergence of the prediction-correction schemes to the continuous-time problem with error determined by the sampling period.Technical smoothness and convexity conditions are imposed for the guarantees.
  • Assumptions: Strong convexity makes each sampled objective have a unique optimizer and keeps its Hessian invertible.The analysis assumes a uniform lower Hessian bound m.
  • Assumptions: Bounded derivatives in x and t provide the regularity needed to construct prediction schemes from how the objective and its derivatives change over time.The stated conditions include bounded second- and third-order derivatives and mixed time-space derivatives.
  • Regularity of the solution trajectory: The assumptions imply that the optimizer mapping is single-valued and locally Lipschitz in time, linking the sampling period h to allowable optimizer variation.The paper emphasizes that this variation condition follows from its smoothness assumptions rather than being separately assumed.
  • Scope boundary: If the optimizer and generated sequence are known to lie in a subset X, the assumptions may hold only on X; projection to a neighborhood yields only local convergence.This weakens the global scope of the standard assumptions.
  • Discretization error: O(h^2) bounds the Euler prediction discretization error, which is then used in convergence proofs for all proposed methods.The prediction error bound is central because it captures error introduced by the prediction step.

A. Gradient trajectory tracking convergence

GTT converges exponentially to a neighborhood of the time-varying optimizer, with accuracy governed by the sampling period, stepsize, and correction-step count. Under a sampling condition, its asymptotic error improves from O(h) to O(h^2), while Newton-based tracking can achieve O(h^4) under additional local conditions.

  • Gradient trajectory tracking: GTT converges exponentially to a bounded neighborhood of x*(t_k) for any sampling period under an admissible gradient stepsize.The stepsize must satisfy 0 < γ < 2/L, ensuring ρ < 1.
  • Gradient trajectory tracking: Increasing the number of gradient corrections τ improves both exponential convergence speed and asymptotic accuracy through the factor ρ^τ.The accuracy improves because the asymptotic bound is proportional to ρ^τ/(1 − ρ^τ).
  • Gradient trajectory tracking: O(h^2) asymptotic accuracy holds when the sampling condition ρ^τσ < 1 is satisfied.Without this condition, the asymptotic accuracy is O(h).
  • Newton trajectory tracking: For quadratic objectives, the Newton locality parameter satisfies C1 = 0, so the stated locality restriction disappears and global convergence is achieved.For nonquadratic objectives, the analysis remains local and backtracking can be used to initialize Newton correction.

C. Convergence of methods with approximated time derivative

AGT and ANT replace the unavailable time derivative of the gradient with an approximation while retaining the same asymptotic dependence on the sampling period. The approximation slightly increases error magnitude, with ANT and NTT retaining fourth-order behavior under their respective conditions.

  • Approximate prediction: AGT and ANT approximate the objective’s time variation without changing the asymptotic error order with respect to h.The approximation affects the bound’s magnitude rather than its functional dependence on h.
  • AGT: AGT converges exponentially to a bounded neighborhood, with asymptotic error of order O(h) or O(h^2) depending on the sampling-period condition.The relevant condition is ρ^τσ < 1 for the higher-order regime.
  • AGT: AGT has the same error orders as GTT, although its error bound is slightly larger because of derivative-approximation error.The first-order approximation contributes an additional error term while preserving the order in h.
  • Practical implication: Approximate derivative information therefore preserves the proposed methods’ error dependence while supporting applications where objective variation is not directly known.The paper identifies robotics and statistical signal processing as examples of such settings.

IV. NUMERICAL EXPERIMENTS

Numerical experiments compare exact and approximate prediction-correction methods on scalar time-varying optimization and trajectory-tracking tasks. The proposed methods substantially reduce tracking error, with NTT or its hybrid strategy generally performing best in the high-condition-number scalar case.

  • Scalar example: The scalar worst-case error-floor plots attain the theoretical O(h), O(h^2), and O(h^4) behaviors shown by the dashed reference lines.These behaviors corroborate the analytical convergence orders in the simulations.
  • Scalar example: 10^-2 is the reported error for running gradient, while GTT achieves approximately 10^-5 in the scalar experiment with h = 0.1.GTT results are reported for τ = 1, 3, and 5; AGT also outperforms running gradient, and NTT with τ = 1 performs better still.
  • Conditioning comparison: Changing to κ = .1 and µ = .5 yields a condition number close to 1, altering the relative performance of GTT and NTT.The experiment uses L = 1.0063 and γ = 1 < 2/L, and evaluates the resulting trajectories and error floors.
  • Scalar example: NTT, or equivalently the hybrid strategy after switching, achieves the minimal worst-case error floor as h varies.The reported ordering is running gradient, AGT, GTT with increasing τ, then NTT or the hybrid strategy.
  • Trajectory tracking: All trajectory-tracking methods follow the optimum effectively, while AGT and ANT track x*(t) closer than running gradient.The comparison is shown using dashed reference trajectories and continuous algorithm trajectories.

B. Target Tracking Experiments

The target-tracking experiments apply the proposed and approximate algorithms to an autonomous robot following a continuously moving object, under limited actuation and computational budgets. AGT and ANT track the optimal trajectory with small errors, with ANT achieving the strongest reported accuracy but higher computational cost.

  • Experimental setup: The experiment models a mobile robot choosing waypoints to follow a continuously moving reference trajectory.The tracking objective also keeps the robot sufficiently close to a base station.
  • Experimental setup: The robot is fully actuated but velocity-limited, so prediction-correction updates are rescaled to respect the allowable speed.The experiments use a maximum velocity of 4 m/s; more complicated actuation models are outside the work’s scope.
  • Tracking performance: RG, AGT, and ANT successfully track the optimal trajectory and consequently the reference path up to a small error.The approximate algorithms are used because the time derivative of the objective is unavailable in this practical setting.
  • Tracking performance: 10, 10^-1, and 10^-5 are the approximate steady-state errors reported for RG, AGT, and ANT, respectively.AGT has comparable error across correction-step counts, while ANT far outperforms the other methods.
  • Sampling-period dependence: RG exhibits approximately O(h), AGT approximately O(h^2), and ANT approximately O(h^4) worst-case error as the sampling interval increases.The optimality gap increases when the problem is sampled less often.
  • Computational considerations: Under fixed computational time, ANT is preferable for larger h, whereas small sampling periods favor lower-latency alternatives.Newton steps require O(n^3) computation versus O(n) for gradient steps, although Newton methods need fewer iterations for comparable accuracy.
  • Practical implications: The conclusion reports that higher-accuracy second-order methods can require too much latency for closed-loop control, but are highly accurate when that latency is affordable.The numerical analysis also empirically supports the established error bounds.
  • Scope and future work: Future work includes constrained and general convex problems and approximate second-order methods that reduce Hessian-inverse computational requirements.

APPENDIX A PROOF OF PROPOSITION 1

The appendix bounds the forward-Euler prediction error for the continuous-time nonlinear dynamics underlying the tracking method. It combines the Euler update, Taylor expansion, chain-rule derivative, and smoothness bounds to establish the proposition.

  • Euler discretization: The forward-Euler prediction is x_k+1|k = x(t_k) + h F(x(t_k), t_k).This update is compared with a Taylor expansion of the exact state at the next sampling time.
  • Euler discretization: The local discretization error is defined as Δ_k = x_k+1|k − x(t_k+1).The proof bounds this difference using the second time derivative term from the Taylor expansion.
  • Derivative bound: The derivative of F along the continuous trajectory is obtained by the chain rule as ∇_tF(x,t) + [∇_xF(x,t)]ẋ.Using ẋ = F(x(t),t) expresses the derivative entirely through the system dynamics and partial derivatives.
  • Derivative bound: The proof bounds the derivative terms with the triangle inequality, Cauchy-Schwarz inequality, and the assumptions on functional smoothness.These bounds yield the claimed upper bound on the prediction discretization error.

APPENDIX B PROOF OF THEOREM 1

The proof of Theorem 1 combines prediction and correction error bounds for strongly convex objectives. It uses Euler discretization, Hessian and time-derivative smoothness, and gradient-contraction properties to obtain asymptotic tracking bounds.

  • Proof strategy: The proof first bounds prediction error through Taylor expansions and then bounds gradient-correction error using convergence of gradient descent on strongly convex functions.Substituting the correction bound into the prediction bound establishes the main result.
  • Prediction bound: The prediction step uses the Hessian inverse and time derivative evaluated at the current iterate, while the optimizer satisfies a null residual condition.The optimizer-side quantities are denoted by ∇_xxf* and ∇_txf*.
  • Smoothness estimates: Hessian inverse perturbation is bounded using strong convexity, with ||[∇_xxf]^-1 − [∇_xxf*]^-1|| ≤ 1/m^2 ||∇_xxf − ∇_xxf*||.Additional derivative bounds control the dependence of the prediction error on the current tracking error.
  • Correction bound: For gradient correction, the contraction factor is ρ = max{|1 − γm|, |1 − γL|}.The condition γ < 2/L ensures ρ < 1 and a finite asymptotic bound.
  • Combined bound: The combined prediction-correction recursion contracts the previous tracking error by ρ^τ and adds a bounded prediction-correction error term.Recursive application gives a bound in terms of the initial error and the convergence-neighborhood term.
  • Prediction bound: The forward-Euler prediction error is bounded by the current tracking error plus a term proportional to h^2.The resulting recursion includes the discretization contribution through constants defined from the smoothness assumptions.

APPENDIX C PROOF OF THEOREM 2

The proof bounds the NTT correction error after prediction and shows that, under sampling-period conditions, induction yields an O(h^4) trajectory-tracking error for all later steps.

  • Proof mechanism: The proof derives the one-step Newton bound by combining prediction-error bounds with inequalities from the Newton correction update.
  • One-step error: The Newton correction error after one step is O(h^(4τ)), improving on the initial O(h^2) error.The proof then establishes conditions ensuring the first corrected error is at most ch^2.
  • Sampling condition: If the sampling-period condition holds, the first corrected error satisfies ||x1 − x˚(t1)|| ≤ ch^2.
  • Induction: Because the sufficient condition does not depend on the optimality gap, induction extends the ch^2 bound to every k ≥ 1.The argument substitutes successive tracking errors into the recurrence and applies induction.

APPENDIX D PROOF OF THEOREM 3

The proof analyzes approximate prediction using a finite-difference mixed-gradient estimate and shows that AGT retains the same asymptotic error orders as GTT.

  • Approximate prediction: The approximate mixed-gradient error is bounded using Taylor expansion and the bounded second time derivative.
  • Asymptotic result: The shared recurrence allows the GTT proof steps to establish the corresponding AGT asymptotic error results.
  • Error recurrence: AGT’s prediction error recurrence matches GTT’s recurrence except for the multiplier of h^2.

APPENDIX E PROOF OF THEOREM 4

The proof transfers the approximate-prediction analysis to ANT and combines it with the NTT correction analysis to obtain the stated ANT error result.

  • Correction step: ANT and NTT share the same correction step, so the NTT correction bounds apply to ANT.
  • Prediction step: AGT and ANT use identical prediction steps, so the AGT prediction-error result also holds for ANT.
  • Final bound: The resulting ANT bound is analogous to the NTT bound, and repeating the NTT proof steps establishes the theorem’s ANT result.
Loading 1509.05196v2…