{"ID":2876617,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.21335","arxiv_id":"2508.21335","title":"A Fundamental Convergence Rate Bound for Gradient Based Online Optimization Algorithms with Exact Tracking","abstract":"In this paper, we consider algorithms with integral action for solving online optimization problems characterized by quadratic cost functions with a time-varying optimal point described by an $(n-1)$th order polynomial. Using a version of the internal model principle, the optimization algorithms under consideration are required to incorporate a discrete time $n$-th order integrator in order to achieve exact tracking. By using results on an optimal gain margin problem, we obtain a fundamental convergence rate bound for the class of linear gradient based algorithms exactly tracking a time-varying optimal point. This convergence rate bound is given by $ \\left(\\frac{\\sqrtκ - 1 }{\\sqrtκ + 1}\\right)^{\\frac{1}{n}}$, where $κ$ is the condition number for the set of cost functions under consideration. Using our approach, we also construct algorithms which achieve the optimal convergence rate as well as zero steady-state error when tracking a time-varying optimal point.","short_abstract":"In this paper, we consider algorithms with integral action for solving online optimization problems characterized by quadratic cost functions with a time-varying optimal point described by an $(n-1)$th order polynomial. Using a version of the internal model principle, the optimization algorithms under consideration are...","url_abs":"https://arxiv.org/abs/2508.21335","url_pdf":"https://arxiv.org/pdf/2508.21335v2","authors":"[\"Alex Xinting Wu\",\"Ian R. Petersen\",\"Iman Shames\"]","published":"2025-08-29T05:38:06Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"eess.SY\"]","methods":"[]","has_code":false}