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

Abstract

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.

16 pages, 8 figures

References in corpus (2)

• Interior Point Method for Dynamic Constrained Optimization in Continuous Time
• A Parametric Non-Convex Decomposition Algorithm for Real-Time and Distributed NMPC

Cited by in corpus (30)

• Prediction-Correction Algorithms for Time-Varying Constrained Optimization
• Second-order Online Nonconvex Optimization
• Time-Varying Convex Optimization via Time-Varying Averaged Operators
• Can Primal Methods Outperform Primal-dual Methods in Decentralized Dynamic Optimization?
• Distributed Constrained Online Learning
• Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit
• Internal Model-Based Online Optimization
• Suboptimal Safety-Critical Control for Continuous Systems Using Prediction-Correction Online Optimization
• Local Strong Convexity of Source Localization and Error Bound for Target Tracking under Time-of-Arrival Measurements
• Extrapolation-based Prediction-Correction Methods for Time-varying Convex Optimization
• On-line Non-Convex Constrained Optimization
• Time-Varying Convex Optimization: A Contraction and Equilibrium Tracking Approach
• tvopt: A Python Framework for Time-Varying Optimization
• Prediction-Correction Splittings for Nonsmooth Time-Varying Optimization
• Nonstationary Nonparametric Online Learning: Balancing Dynamic Regret and Model Parsimony
• Interior Point Method for Dynamic Constrained Optimization in Continuous Time
• A Prediction-Correction Algorithm for Real-Time Model Predictive Control
• Technical Report: A Totally Asynchronous Algorithm for Tracking Solutions to Time-Varying Convex Optimization Problems
• Escaping spurious local minimum trajectories in online time-varying nonconvex optimization
• A Control Theoretical Approach to Online Constrained Optimization
• Adiabatic quantum computing with parameterized quantum circuits
• Prediction techniques for dynamic imaging with online primal-dual methods
• Prediction-Correction for Nonsmooth Time-Varying Optimization via Forward-Backward Envelopes
• Predictive resource allocation for flexible loads with local QoS
• Tracking Moving Agents via Inexact Online Gradient Descent Algorithm
• Online Proximal-ADMM For Time-varying Constrained Convex Optimization
• Moving Horizon Estimation for Quadrotors: An ${\mathcal{L}}_1$ Adaptive Optimizer Approach
• Dynamic Distribution State Estimation Using Synchrophasor Data
• Time-Varying Optimization: Algorithms and Engineering Applications
• Consistent Sensor, Relay, and Link Selection in Wireless Sensor Networks