Internal Model-Based Online Optimization

In this paper we propose a model-based approach to the design of online optimization algorithms, with the goal of improving the tracking of the solution trajectory (trajectories) w.r.t. state-of-the-art methods. We focus first on quadratic problems with a time-varying linear term, and use digital control tools to propose a novel online algorithm that can achieve zero tracking error by modeling the cost with a dynamical system. We prove the convergence of the algorithm for both strongly convex and convex problems. We further discuss the sensitivity of the proposed method to model uncertainties and quantify its performance. As part of our discussion, we also proposed a compensated online gradient that achieves our goal for problems with a linear dependence on time. We discuss how these algorithms can be applied to general (non-quadratic) problems using an approximate model of the cost. We present numerical results that showcase the superior performance of the proposed algorithms over previous methods for both quadratic and non-quadratic problems