ResQPASS: an algorithm for bounded variable linear least squares with asymptotic Krylov convergence
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916882771083264 |
|---|---|
| author | Symoens, Bas Vanroose, Wim |
| author_facet | Symoens, Bas Vanroose, Wim |
| contents | We present the Residual Quadratic Programming Active-Set Subspace (ResQPASS) method that solves large-scale linear least-squares problems with bound constraints on the variables. The problem is solved by creating a series of small problems of increasing size by projecting onto the basis of residuals. Each projected problem is solved by the active-set method for convex quadratic programming, warm-started with a working set and solution from the previous problem. The method coincides with conjugate gradients (CG) or, equivalently, LSQR when none of the constraints is active. When only a few constraints are active the method converges, after a few initial iterations, like CG and LSQR. An analysis links the convergence to an asymptotic Krylov subspace. We also present an efficient implementation where QR factorizations of the projected problems are updated over the inner iterations and Cholesky or Gram-Schmidt over the outer iterations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_13616 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | ResQPASS: an algorithm for bounded variable linear least squares with asymptotic Krylov convergence Symoens, Bas Vanroose, Wim Numerical Analysis Optimization and Control 49N45, 65K05, 65F10, 90C20 We present the Residual Quadratic Programming Active-Set Subspace (ResQPASS) method that solves large-scale linear least-squares problems with bound constraints on the variables. The problem is solved by creating a series of small problems of increasing size by projecting onto the basis of residuals. Each projected problem is solved by the active-set method for convex quadratic programming, warm-started with a working set and solution from the previous problem. The method coincides with conjugate gradients (CG) or, equivalently, LSQR when none of the constraints is active. When only a few constraints are active the method converges, after a few initial iterations, like CG and LSQR. An analysis links the convergence to an asymptotic Krylov subspace. We also present an efficient implementation where QR factorizations of the projected problems are updated over the inner iterations and Cholesky or Gram-Schmidt over the outer iterations. |
| title | ResQPASS: an algorithm for bounded variable linear least squares with asymptotic Krylov convergence |
| topic | Numerical Analysis Optimization and Control 49N45, 65K05, 65F10, 90C20 |
| url | https://arxiv.org/abs/2302.13616 |