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

DOI10.1109/TSP.2016.2568161zbMATH Open1414.94570arXiv1509.05196OpenAlexW2255965710MaRDI QIDQ4620906FDOQ4620906

Authors: Andrea Simonetto, Aryan Mokhtari, Alec Koppel, Alejandro Ribeiro, G. Leus 

Publication date: 8 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1509.05196

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (12)

• Discrete-time Euler-smoothing methods for time-varying convex constrained optimization
• Distributed Nash equilibrium tracking via the alternating direction method of multipliers
• Prediction-Correction Interior-Point Method for Time-Varying Convex Optimization
• Nonlinear optimization filters for stochastic time-varying convex optimization
• General four-step discrete-time zeroing and derivative dynamics applied to time-varying nonlinear optimization
• Distributed dual consensus algorithm for time-varying optimization with coupled equality constraint
• Time-varying distributed optimization problem with inequality constraints
• Distributed fixed‐time optimization for multi‐agent systems with time‐varying objective function
• Stochastic time-varying extremum seeking and its applications
• A continuous-time consensus algorithm using neurodynamic system for distributed time-varying optimization with inequality constraints
• Distributed continuous‐time constrained convex optimization with general time‐varying cost functions
• Distributed continuous-time time-varying optimization for networked Lagrangian systems with quadratic cost functions

This page was built for publication: A Class of Prediction-Correction Methods for Time-Varying Convex Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4620906)