A Fundamental Convergence Rate Bound for Gradient Based Online Optimization Algorithms with Exact Tracking
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918138950451200 |
|---|---|
| author | Wu, Alex Xinting Petersen, Ian R. Shames, Iman |
| author_facet | Wu, Alex Xinting Petersen, Ian R. Shames, Iman |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21335 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Fundamental Convergence Rate Bound for Gradient Based Online Optimization Algorithms with Exact Tracking Wu, Alex Xinting Petersen, Ian R. Shames, Iman Optimization and Control Systems and Control 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. |
| title | A Fundamental Convergence Rate Bound for Gradient Based Online Optimization Algorithms with Exact Tracking |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2508.21335 |