First-Order Projected Algorithms With the Same Linear Convergence Rate Bounds as Their Unconstrained Counterparts
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909979402829824 |
|---|---|
| author | Li, Mengmou Lestas, Ioannis Nagahara, Masaaki |
| author_facet | Li, Mengmou Lestas, Ioannis Nagahara, Masaaki |
| contents | In this paper, we propose a systematic approach for extending first-order optimization algorithms, originally designed for unconstrained strongly convex problems, to handle closed and convex set constraints. We show that the resulting projected algorithms retain the same linear convergence rate bounds, provided that the underlying unconstrained optimization algorithms admit a quadratic Lyapunov function obtained from integral quadratic constraint (IQC) analysis. The projected algorithms are constructed by applying a projection in the norm induced by the Lyapunov matrix, ensuring both constraint satisfaction and optimality at the fixed point. Furthermore, under a linear transformation associated with this matrix, the projection becomes non-expansive in the Euclidean norm, allowing the use of the contraction mapping theorem to establish convergence. Our results indicate that, when analyzing worst-case convergence rates or when synthesizing first-order optimization algorithms with potentially higher-order dynamics, it suffices to focus solely on the unconstrained dynamics, since the same parameters or stepsizes can be employed without retuning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_13965 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | First-Order Projected Algorithms With the Same Linear Convergence Rate Bounds as Their Unconstrained Counterparts Li, Mengmou Lestas, Ioannis Nagahara, Masaaki Optimization and Control In this paper, we propose a systematic approach for extending first-order optimization algorithms, originally designed for unconstrained strongly convex problems, to handle closed and convex set constraints. We show that the resulting projected algorithms retain the same linear convergence rate bounds, provided that the underlying unconstrained optimization algorithms admit a quadratic Lyapunov function obtained from integral quadratic constraint (IQC) analysis. The projected algorithms are constructed by applying a projection in the norm induced by the Lyapunov matrix, ensuring both constraint satisfaction and optimality at the fixed point. Furthermore, under a linear transformation associated with this matrix, the projection becomes non-expansive in the Euclidean norm, allowing the use of the contraction mapping theorem to establish convergence. Our results indicate that, when analyzing worst-case convergence rates or when synthesizing first-order optimization algorithms with potentially higher-order dynamics, it suffices to focus solely on the unconstrained dynamics, since the same parameters or stepsizes can be employed without retuning. |
| title | First-Order Projected Algorithms With the Same Linear Convergence Rate Bounds as Their Unconstrained Counterparts |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2503.13965 |