Blocked Cholesky factorization updates of the Riccati recursion using hyperbolic Householder transformations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910884290363392 |
|---|---|
| author | Pas, Pieter Patrinos, Panagiotis |
| author_facet | Pas, Pieter Patrinos, Panagiotis |
| contents | Newton systems in quadratic programming (QP) methods are often solved using direct Cholesky or LDL factorizations. When the linear systems in successive iterations differ by a low-rank modification (as is common in active set and augmented Lagrangian methods), updating the existing factorization can offer significant performance improvements over recomputing a full Cholesky factorization. We review the hyperbolic Householder transformation, and demonstrate its usefulness in describing low-rank Cholesky factorization updates. By applying this hyperbolic Householder-based framework to the well-known Riccati recursion for solving saddle-point problems with optimal control structure, we develop a novel algorithm for updating the factorizations used in optimization solvers for optimal control. Specifically, the proposed method can be used to efficiently solve the semismooth Newton systems that are at the core of the augmented Lagrangian-based QPALM-OCP solver. An optimized open-source implementation of the proposed factorization update routines is provided as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_15372 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Blocked Cholesky factorization updates of the Riccati recursion using hyperbolic Householder transformations Pas, Pieter Patrinos, Panagiotis Optimization and Control Systems and Control 49M15, 65F05 Newton systems in quadratic programming (QP) methods are often solved using direct Cholesky or LDL factorizations. When the linear systems in successive iterations differ by a low-rank modification (as is common in active set and augmented Lagrangian methods), updating the existing factorization can offer significant performance improvements over recomputing a full Cholesky factorization. We review the hyperbolic Householder transformation, and demonstrate its usefulness in describing low-rank Cholesky factorization updates. By applying this hyperbolic Householder-based framework to the well-known Riccati recursion for solving saddle-point problems with optimal control structure, we develop a novel algorithm for updating the factorizations used in optimization solvers for optimal control. Specifically, the proposed method can be used to efficiently solve the semismooth Newton systems that are at the core of the augmented Lagrangian-based QPALM-OCP solver. An optimized open-source implementation of the proposed factorization update routines is provided as well. |
| title | Blocked Cholesky factorization updates of the Riccati recursion using hyperbolic Householder transformations |
| topic | Optimization and Control Systems and Control 49M15, 65F05 |
| url | https://arxiv.org/abs/2503.15372 |