The Internal Model Principle of Time-Varying Optimization

Time-varying optimization problems are central to many engineering applications, where performance metrics and system constraints evolve dynamically with time. Several methods have been proposed in the literature to address these problems; a common feature among them is their implicit reliance on prior knowledge of the temporal variability of the optimizers. In this paper, we provide a fundamental characterization of this property: we show that an algorithm can track time-varying optimizers if and only if it incorporates a model of the temporal variability of the optimization. We refer to this concept as theinternal model principle of time-varying optimization.Our analysis relies on showing that the design of optimization algorithms for time-varying problems is fundamentally an output regulation problem from control systems. By leveraging tools from center manifold theory, we derive necessary and sufficient conditions for exact asymptotic tracking and, in turn, establish a foundation for the development of new optimization methods. We validate the proposed approach through numerical experiments on synthetic benchmarks and on the dynamic traffic assignment problem.