Solving trust region subproblems using Riemannian optimization

DOI10.1007/S00211-023-01360-0MaRDI QIDQ6109916zbMATH OpenOpenAlexFDO

Authors Uria Mor, Boris Shustin, Haim Avron

Publication date 4 July 2023

Published in Numerische Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2010.07547

Mathematics Subject Classification ID

Acceleration of convergence in numerical analysis (65B99) Numerical linear algebra (65F99) Mathematical programming (90C99)

Abstract: 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.

Cites work

• A constrained eigenvalue problem
• A Riemannian Optimization Approach for Computing Low-Rank Solutions of Lyapunov Equations
• An Introduction to Optimization on Smooth Manifolds
• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• Computing a Trust Region Step
• Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs
• Globally solving the trust region subproblem using simple first-order methods
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• Local Minimizers of Quadratic Functions on Euclidean Balls and Spheres
• Minimizing a quadratic over a sphere
• On Some Properties of Quadratic Programs with a Convex Quadratic Constraint
• Optimization techniques for semi-supervised support vector machines
• Practical methods of optimization.
• Practical sketching algorithms for low-rank matrix approximation
• Provably robust estimation of modulo 1 samples of a smooth function with applications to phase unwrapping
• Quadratically constrained least squares and quadratic problems
• Riemannian preconditioning
• Solving the trust-region subproblem by a generalized eigenvalue problem
• Solving the Trust-Region Subproblem using the Lanczos Method
• The Geometry of Algorithms with Orthogonality Constraints

Cited in

(3)

• A Subspace Minimization Method for the Trust-Region Step
• A Riemannian subspace limited-memory SR1 trust region method
• On solving trust-region and other regularised subproblems in optimization

This page was built for publication: Solving trust region subproblems using Riemannian optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6109916)