Solving trust region subproblems using Riemannian optimization
The Trust Region Subproblem is a fundamental optimization problem that takes a pivotal role in Trust Region Methods. However, the problem, and variants of it, also arise in quite a few other applications. In this article, we present a family of iterative Riemannian optimization algorithms for a vari...
| Main Authors: | , , |
|---|---|
| 格式: | Journal article |
| 语言: | English |
| 出版: |
Springer Nature
2023
|
| _version_ | 1826313289841246208 |
|---|---|
| author | Mor, U Shustin, B Avron, H |
| author_facet | Mor, U Shustin, B Avron, H |
| author_sort | Mor, U |
| collection | OXFORD |
| description | The Trust Region Subproblem is a fundamental optimization problem that takes a pivotal role in Trust Region Methods. However, the problem, and variants of it, also arise in quite a few other applications. In this article, we present a family of iterative Riemannian optimization algorithms for a variant of the Trust Region Subproblem that replaces the inequality constraint with an equality constraint, and converge to a global optimum. Our approach uses either a trivial or a non-trivial Riemannian geometry of the search-space, and requires only minimal spectral information about the quadratic component of the objective function. We further show how the theory of Riemannian optimization promotes a deeper understanding of the Trust Region Subproblem and its difficulties, e.g., a deep connection between the Trust Region Subproblem and the problem of finding affine eigenvectors, and a new examination of the so-called hard case in light of the condition number of the Riemannian Hessian operator at a global optimum. Finally, we propose to incorporate preconditioning via a careful selection of a variable Riemannian metric, and establish bounds on the asymptotic convergence rate in terms of how well the preconditioner approximates the input matrix. |
| first_indexed | 2024-03-07T08:09:46Z |
| format | Journal article |
| id | oxford-uuid:8865d18c-1cb9-4b84-aa09-41f9d10e5adb |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:10:43Z |
| publishDate | 2023 |
| publisher | Springer Nature |
| record_format | dspace |
| spelling | oxford-uuid:8865d18c-1cb9-4b84-aa09-41f9d10e5adb2024-06-24T12:53:57ZSolving trust region subproblems using Riemannian optimizationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8865d18c-1cb9-4b84-aa09-41f9d10e5adbEnglishSymplectic ElementsSpringer Nature2023Mor, UShustin, BAvron, HThe Trust Region Subproblem is a fundamental optimization problem that takes a pivotal role in Trust Region Methods. However, the problem, and variants of it, also arise in quite a few other applications. In this article, we present a family of iterative Riemannian optimization algorithms for a variant of the Trust Region Subproblem that replaces the inequality constraint with an equality constraint, and converge to a global optimum. Our approach uses either a trivial or a non-trivial Riemannian geometry of the search-space, and requires only minimal spectral information about the quadratic component of the objective function. We further show how the theory of Riemannian optimization promotes a deeper understanding of the Trust Region Subproblem and its difficulties, e.g., a deep connection between the Trust Region Subproblem and the problem of finding affine eigenvectors, and a new examination of the so-called hard case in light of the condition number of the Riemannian Hessian operator at a global optimum. Finally, we propose to incorporate preconditioning via a careful selection of a variable Riemannian metric, and establish bounds on the asymptotic convergence rate in terms of how well the preconditioner approximates the input matrix. |
| spellingShingle | Mor, U Shustin, B Avron, H Solving trust region subproblems using Riemannian optimization |
| title | Solving trust region subproblems using Riemannian optimization |
| title_full | Solving trust region subproblems using Riemannian optimization |
| title_fullStr | Solving trust region subproblems using Riemannian optimization |
| title_full_unstemmed | Solving trust region subproblems using Riemannian optimization |
| title_short | Solving trust region subproblems using Riemannian optimization |
| title_sort | solving trust region subproblems using riemannian optimization |
| work_keys_str_mv | AT moru solvingtrustregionsubproblemsusingriemannianoptimization AT shustinb solvingtrustregionsubproblemsusingriemannianoptimization AT avronh solvingtrustregionsubproblemsusingriemannianoptimization |