Source-linked AI summary
Time-Varying Convex Optimization: Time-Structured Algorithms and Applications
Andrea Simonetto, Emiliano Dall'Anese, Santiago Paternain, Geert Leus, Georgios B. Giannakis
TL;DR
Dynamic infrastructures and networked systems require optimization methods that handle changing problems and large, heterogeneous data streams. This paper reviews time-varying convex optimization, emphasizing structured algorithms that use models of optimizer evolution alongside applications and analytical results. It concludes that exploiting temporal structure can improve solutions and reduce computational complexity, while identifying unresolved challenges in distributed and feedback settings.
Problem
Changing costs, constraints, and streaming data create a need for optimization methods suited to dynamic environments rather than only batch, time-invariant problems.
Method
The paper surveys convex time-varying optimization models and algorithms, emphasizing structured methods that predict optimizer evolution before corrective optimization steps.
Results
The overview reports that structured algorithms can improve time-varying solutions and reduce computational cost relative to unstructured approaches in illustrated applications.
Takeaways & Limitations
Time-varying optimization provides an engineering framework for systems with evolving data and operating conditions, including power systems, robotics, and networked applications.
Takeaways & Limitations
Distributed time-varying analysis remains largely unexplored when nodes use different evolution models, sampling timescales, or solution accuracies.
Abstract
from arXiv · showhide
Optimization underpins many of the challenges that science and technology face on a daily basis. Recent years have witnessed a major shift from traditional optimization paradigms grounded on batch algorithms for medium-scale problems to challenging dynamic, time-varying, and even huge-size settings. This is driven by technological transformations that converted infrastructural and social platforms into complex and dynamic networked systems with even pervasive sensing and computing capabilities. The present paper reviews a broad class of state-of-the-art algorithms for time-varying optimization, with an eye to both algorithmic development and performance analysis. It offers a comprehensive overview of available tools and methods, and unveils open challenges in application domains of broad interest. The real-world examples presented include smart power systems, robotics, machine learning, and data analytics, highlighting domain-specific issues and solutions. The ultimate goal is to exempify wide engineering relevance of analytical tools and pertinent theoretical foundations.
I. INTRODUCTION
Time-varying optimization addresses dynamic systems whose costs, constraints, and data streams evolve over time. This overview develops structured algorithms that exploit temporal information, contrasts them with unstructured methods, and illustrates their engineering relevance.
- Motivation: Time-varying optimization extends static convex programs to settings where costs and constraints change continuously or across discrete time steps.Online solvers aim to track trajectories of time-varying optimizers, generally up to asymptotic error bounds.
- Algorithmic distinction: Structured algorithms use prior information about optimizer evolution, whereas unstructured algorithms rely only on currently revealed costs and constraints.The paper distinguishes structured methods from interactive online convex optimization algorithms, which belong to the unstructured class.
- Motivation: Streaming system data feed predictors and optimizers that produce decision streams for operational actions, sometimes with feedback to the underlying system.Examples include intermittent renewable generation, changing traffic, and mobile drone-delivery destinations.
- Algorithmic distinction: With equal computational time, structured algorithms can outperform unstructured methods by several orders of magnitude in a robot tracking problem.The comparison uses asymptotic tracking error and includes specified online proximal-gradient and Taylor-model variants.
- Applications: Exploiting temporal structure reduces MPC computational complexity, measured by the number of Hessian inversions required to control the Hicks reactor.The paper presents this as an application-level example of structured versus unstructured solvers.
- Scope and contributions: The overview presents models and algorithms analytically and from an application-oriented perspective, demonstrates structured applications, and links them to unstructured dynamic-optimization methods.Its stated application focus includes robotic and power-system examples, while the broader setting spans engineering and science domains.
II. TIME-VARYING OPTIMIZATION
Time-varying optimization addresses convex programs whose costs and constraints evolve over time, requiring approximate optimizer trajectories under limited computation. The paper distinguishes structured methods that predict temporal evolution from unstructured methods that use only currently revealed problems, and evaluates them using tracking and computational metrics.
- Problem formulation: The paper studies convex optimization problems with time-dependent costs f(x,t) and potentially time-varying convex constraint sets X(t).Under strong convexity and nonempty constraints, each time t has a unique global optimizer and an optimal solution trajectory.
- Motivation: Batch methods can identify the optimal trajectory when changes are slow, but computational and communication bottlenecks limit their timeliness in highly dynamic settings.The motivating example contrasts changes every 10 seconds with a batch convergence time of 5 seconds against changes every 0.5 seconds.
- Structured versus unstructured methods: Structured algorithms predict optimizer evolution using temporal information, whereas unstructured algorithms rely only on optimization problems revealed at each time.Temporal information may include a learned model or prior regularity such as Lipschitz continuity or smoothness.
- Performance metrics: Asymptotic tracking error measures the long-run distance between delivered decisions and optimal decisions; it can be zero for structured methods but not for unstructured methods when the optimum varies.For an asymptotically stationary optimum, asymptotic consistency requires the tracking error to be zero.
- Performance metrics: Time rate compares computation time with allowed time, while convergence rate measures approach speed to the asymptotic tracking error; both expose implementation and responsiveness trade-offs.An online method requires time rate below one, and lower tracking error may require higher convergence rate.
- Performance metrics: Structure gain compares structured and unstructured asymptotic tracking errors at equal computation time, and values greater than one favor the structured method.The metric is intended to guide algorithm choice for a given time-varying optimization task.
A. Discrete-time algorithms
Discrete-time algorithms sample the evolving problem at intervals and generate approximate optimizer sequences using correction-only or predictive updates. Under bounded temporal variation and smoothness assumptions, prediction-correction methods can improve tracking error, while correction-only methods retain an error tied to problem movement and sampling.
- Discrete-time setting: Sampling at times t_k = kh converts the continuous time-varying problem into a sequence of time-indexed optimization problems.The sampling period h controls how frequently the changing problem is processed.
- Assumptions: Structured analyses require bounded optimizer movement and often bounded time variation of the gradient, while strong convexity and smoothness support trajectory regularity.Under these assumptions, the optimizer trajectory is globally Lipschitz in time, with a bound proportional to Δ_0/m.
- Assumptions: The optimal trajectory is globally Lipschitz in time under the stated assumptions, a property typically unnecessary for unstructured algorithms and online convex optimization.Assumption 2 implies the trajectory bound with K = Δ_0 h/m.
- No-predictor algorithms: No-predictor methods apply corrective updates after each new cost function, but generally achieve high asymptotic tracking error.Projected gradient is a representative correction-only method, and multiple gradient steps may be applied per time step.
- No-predictor algorithms: A Q-linearly convergent method applied C times per sample tracks the optimizer trajectory within an error bound proportional to ϱ^C O(K), becoming exact as C approaches infinity.Under Assumption 2, the asymptotic error is proportional to the sampling period h.
- Prediction-correction algorithms: Prediction-correction methods combine a model-based prediction with correction from newly acquired costs, and their guarantees require suitable numbers of prediction and correction steps.The analysis bounds model error and finite prediction error before combining them with correction error.
- Prediction-correction algorithms: With exact prediction, first-order Taylor models yield O(h) error generally and O(h^2) when higher-order derivatives are bounded, while other methods can achieve O(h^4) or lower.Theorem 2 separates approximation error from prediction gain and reports improved local tracking under stronger smoothness conditions.
B. Continuous-time algorithms
Continuous-time algorithms track evolving optimizer trajectories by incorporating temporal variation into dynamical systems, with prediction enabling exact asymptotic tracking in unconstrained settings. Interior-point extensions additionally support asymptotic convergence for constrained problems while maintaining feasibility when initialized feasibly.
- Continuous-time prediction-correction algorithms track minimizers by accounting for their evolution over time, supporting control and robotics applications.
- The controller combines gradient, Hessian, and time-derivative information to steer decisions toward the time-varying optimizer trajectory.Its gain κ controls the decision trajectory, and the resulting non-autonomous dynamical system converges exponentially under the stated hypotheses.
- Exponential convergence to the optimal trajectory yields zero asymptotic tracking error when prediction incorporates the optimal solution’s time variation.Without prediction, tracking is limited to an asymptotic error depending on gradient variation and controller gain.
- Under strong convexity, convex constraints, and Slater’s condition, the barrier-system solution converges asymptotically to the optimizer trajectory.The theorem states lim_{t→∞} ||x(t) − x⋆(t)|| = 0.
- Interior-point dynamics extend continuous-time tracking to constrained optimization while preserving feasibility for all time from a feasible initial solution.The barrier uses an increasing function c(t) and a decaying slack s(t) so constraint satisfaction is promoted as the barrier approaches the indicator function.
III. APPLICATIONS
Time-varying optimization methods address dynamic environments across infrastructure, control, learning, signal processing, and robotics. Applications include changing power networks, transportation conditions, online learning problems, and robot coordination, with structured and unstructured approaches selected according to domain needs.
- Cyber-physical systems require optimization for highly dynamic environments containing massive numbers of interacting entities across power, transportation, and smart-city infrastructures.
- Power-system formulations capture changing loads, renewable availability, and dynamic pricing for demand response, optimal power flow, state estimation, and distributed-resource control.Online updates can use measurements such as voltage violations to relax sensing requirements.
- Transportation applications address time-dependent routing and traffic-light control under changing traffic, pedestrians, accidents, events, and mobility-on-demand requests.
- Machine learning and signal-processing applications include dynamic sparse reconstruction, concept-drift classification, beamforming, and other time-varying estimation tasks.
- Robotics uses time-varying optimization for safe navigation, mobile-robot communication integrity, and robotic-manipulator control.For mobile robots, an unstructured method achieves asymptotic tracking error associated with small constraint violation and sub-optimality.
A. Example in Power Grids
The power-grid example applies prediction-correction optimization to real-time management of distributed energy resources under changing loads and grid conditions. With equal computational time, exploiting temporal structure improves tracking-related performance relative to an unstructured running projected-gradient method.
- The optimization minimizes distributed-resource and network-operator costs subject to device and power-network constraints.The network model relates electrical quantities to controllable outputs and non-controllable-device powers through sensitivity matrices.
- The example controls N = 500 distributed energy resources, with active and reactive power ranges of [−50, 50] kW and [−50, 50] kVAr.The local cost is f_i(x_i; t) = 1/2||x_i||^2, representing an illustrative energy-storage setting.
- The structured method predicts for P steps and corrects for C steps, while P = 0 recovers the unstructured running projected-gradient method.The comparison fixes computational time using (P, C) = (3, 1) for structured prediction-correction and (0, 3) for unstructured updates.
- 1.6, the structured method’s speedup factor, follows from ATE values of approximately 50 W for unstructured and 80 W for structured methods under equal computational time.Both methods enter their ATE balls in approximately 1 minute; the reported tracking-error metric is mean cumulative error over time.
- The structured prediction-correction algorithm offers improved performance by leveraging temporal structure in the power-grid problem.
B. Example in Robotics
The robotics example convexifies collision avoidance through a local obstacle-free workspace and uses continuous-time optimization to estimate a projected goal for robot control. The structured controller, which includes prediction, provides a significant tracking benefit over its unstructured counterpart.
- The navigation problem drives a disk-shaped robot toward a desired configuration while avoiding obstacles in a closed convex workspace.Although obstacles make the original problem nonconvex, the collision-free local workspace around the robot is convexified.
- Figure 6 compares tracking error over time for structured and unstructured algorithms, while its left panel depicts the desired target, projected-goal estimate, and robot trajectories.
- Each obstacle contributes a linear bound, producing a polygonal local free space guaranteed to be obstacle-free.
- The controller estimates the projected goal with a barrier-based continuous-time system and applies control toward that estimate.The robot follows the control law using the estimated projected goal rather than the unconstrained desired configuration.
- The structured algorithm shows a significant tracking benefit over the unstructured algorithm in the robotics simulation.
V. RESEARCH OUTLOOK AND FUTURE CHALLENGES
The outlook identifies broader problem classes, feedback-coupled optimization, and links to interactive learning as important directions for time-varying optimization. Structured methods remain comparatively unexplored for nonconvex settings, while feedback-loop stability and asynchronous analysis remain open challenges.
- Wider classes of problems: Structured time-varying optimization for nonconvex and broader problem classes remains largely unexplored because suitable evolution models have yet to be developed.Unstructured methods already address non-strongly convex and nonconvex costs using dynamic regret, whereas structured approaches rely on additional functional assumptions.
- Asynchrony: Asynchronous updates complicate analysis because computing nodes may use different evolution models, sampling timescales, or solution accuracies.These heterogeneous update conditions hinder standard analytical techniques and remain largely unexplored.
- Error bounds: Time-varying algorithms converge to an error bound, but the bound can become arbitrarily large when convergence is arbitrarily slow.The passage links this behavior to the convergence factor ϱ approaching 1.
- Feedback loop: When decisions feed back into the system, ensuring closed-loop stability and performance is a mostly open challenge.Feedback can make convergence difficult and may render the notion of asymptotic tracking error ill-defined or too hard to establish.
- Interactive and Reinforcement Learning: Online structured and unstructured algorithms are being developed as feedback-controlled dynamical systems, with connections to OCO, bandits, and reinforcement learning.These links are active research directions in applications including network-resource allocation, secure mobile edge computing, and Internet-of-Things management.