On a Family of Relaxed Gradient Descent Methods for Quadratic Minimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911859757547520 |
|---|---|
| author | MacDonald, Liam Murray, Rua Tappenden, Rachael |
| author_facet | MacDonald, Liam Murray, Rua Tappenden, Rachael |
| contents | This paper studies the convergence properties of a family of Relaxed $\ell$-Minimal Gradient Descent methods for quadratic optimization; the family includes the omnipresent Steepest Descent method, as well as the Minimal Gradient method. Simple proofs are provided that show, in an appropriately chosen norm, the gradient and the distance of the iterates from optimality converge linearly, for all members of the family. Moreover, the function values decrease linearly, and iteration complexity results are provided. All theoretical results hold when (fixed) relaxation is employed. It is also shown that, given a fixed overhead and storage budget, every Relaxed $\ell$-Minimal Gradient Descent method can be implemented using exactly one matrix vector product. Numerical experiments are presented that illustrate the benefits of relaxation across the family. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_19255 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On a Family of Relaxed Gradient Descent Methods for Quadratic Minimization MacDonald, Liam Murray, Rua Tappenden, Rachael Optimization and Control This paper studies the convergence properties of a family of Relaxed $\ell$-Minimal Gradient Descent methods for quadratic optimization; the family includes the omnipresent Steepest Descent method, as well as the Minimal Gradient method. Simple proofs are provided that show, in an appropriately chosen norm, the gradient and the distance of the iterates from optimality converge linearly, for all members of the family. Moreover, the function values decrease linearly, and iteration complexity results are provided. All theoretical results hold when (fixed) relaxation is employed. It is also shown that, given a fixed overhead and storage budget, every Relaxed $\ell$-Minimal Gradient Descent method can be implemented using exactly one matrix vector product. Numerical experiments are presented that illustrate the benefits of relaxation across the family. |
| title | On a Family of Relaxed Gradient Descent Methods for Quadratic Minimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2404.19255 |