Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2510.27540 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909880531550208 |
|---|---|
| author | van Treek, Kira Peña, Javier F. Vera, Juan C. Zuluaga, Luis F. |
| author_facet | van Treek, Kira Peña, Javier F. Vera, Juan C. Zuluaga, Luis F. |
| contents | Many optimization algorithms$\unicode{x2013}$including gradient descent, proximal methods, and operator splitting techniques$\unicode{x2013}$can be formulated as fixed-point iterations (FPI) of continuous operators. When these operators are averaged, convergence to a fixed point is guaranteed when one exists, but the convergence is generally sublinear. Recent results establish linear convergence of FPI for averaged operators under certain conditions. However, such conditions do not apply to common classes of operators, such as those arising in piecewise linear and quadratic optimization problems. In this work, we prove that a local error-bound condition is both necessary and sufficient for the linear convergence of FPI applied to averaged operators. We provide explicit bounds on the convergence rate and show how these relate to the constants in the error-bound condition. Our main result demonstrates that piecewise linear operators satisfy local error bounds, ensuring linear convergence of the associated optimization algorithms. This leads to a general and practical framework for analyzing convergence behavior in algorithms such as ADMM and Douglas-Rachford in the absence of strong convexity. In particular, we obtain convergence rates that are independent of problem data for linear optimization, and depend only on the condition number of the objective for quadratic optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_27540 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Convergence and Error Bounds for Optimization Without Strong Convexity van Treek, Kira Peña, Javier F. Vera, Juan C. Zuluaga, Luis F. Optimization and Control 90C25, 90C20, 90C05 Many optimization algorithms$\unicode{x2013}$including gradient descent, proximal methods, and operator splitting techniques$\unicode{x2013}$can be formulated as fixed-point iterations (FPI) of continuous operators. When these operators are averaged, convergence to a fixed point is guaranteed when one exists, but the convergence is generally sublinear. Recent results establish linear convergence of FPI for averaged operators under certain conditions. However, such conditions do not apply to common classes of operators, such as those arising in piecewise linear and quadratic optimization problems. In this work, we prove that a local error-bound condition is both necessary and sufficient for the linear convergence of FPI applied to averaged operators. We provide explicit bounds on the convergence rate and show how these relate to the constants in the error-bound condition. Our main result demonstrates that piecewise linear operators satisfy local error bounds, ensuring linear convergence of the associated optimization algorithms. This leads to a general and practical framework for analyzing convergence behavior in algorithms such as ADMM and Douglas-Rachford in the absence of strong convexity. In particular, we obtain convergence rates that are independent of problem data for linear optimization, and depend only on the condition number of the objective for quadratic optimization. |
| title | Linear Convergence and Error Bounds for Optimization Without Strong Convexity |
| topic | Optimization and Control 90C25, 90C20, 90C05 |
| url | https://arxiv.org/abs/2510.27540 |