A Flexible Algorithmic Framework for Strictly Convex Quadratic Minimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915275773837312 |
|---|---|
| author | MacDonald, Liam Murray, Rua Tappenden, Rachael |
| author_facet | MacDonald, Liam Murray, Rua Tappenden, Rachael |
| contents | This paper presents an algorithmic framework for the minimization of strictly convex quadratic functions. The framework is flexible and generic. At every iteration the search direction is a linear combination of the negative gradient, as well as (possibly) several other `sub-search' directions, where the user determines which, and how many, sub-search directions to include. Then, a step size along each sub-direction is generated in such a way that the gradient is minimized (with respect to a matrix norm), over the hyperplane specified by the user chosen search directions. Theoretical machinery is developed, which shows that any algorithm that fits into the generic framework is guaranteed to converge at a linear rate. Moreover, these theoretical results hold even when relaxation and/or symmetric preconditioning is employed. Several state-of-the-art algorithms fit into this scheme, including steepest descent and conjugate gradients. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04047 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Flexible Algorithmic Framework for Strictly Convex Quadratic Minimization MacDonald, Liam Murray, Rua Tappenden, Rachael Optimization and Control 65K10 (Primary), 49M20 (Secondary), 90C25 This paper presents an algorithmic framework for the minimization of strictly convex quadratic functions. The framework is flexible and generic. At every iteration the search direction is a linear combination of the negative gradient, as well as (possibly) several other `sub-search' directions, where the user determines which, and how many, sub-search directions to include. Then, a step size along each sub-direction is generated in such a way that the gradient is minimized (with respect to a matrix norm), over the hyperplane specified by the user chosen search directions. Theoretical machinery is developed, which shows that any algorithm that fits into the generic framework is guaranteed to converge at a linear rate. Moreover, these theoretical results hold even when relaxation and/or symmetric preconditioning is employed. Several state-of-the-art algorithms fit into this scheme, including steepest descent and conjugate gradients. |
| title | A Flexible Algorithmic Framework for Strictly Convex Quadratic Minimization |
| topic | Optimization and Control 65K10 (Primary), 49M20 (Secondary), 90C25 |
| url | https://arxiv.org/abs/2505.04047 |