Minimization of Large Scale Quadratic Function Subject to an Ellipsoidal Constraint
An important problem in linear algebra and optimization is the Trust Region Problem: Minimize a quadratic function subject to an ellipsoidal constraint. This basic problem has several important large scale applications including seismic inversion and forcing convergence in optimization methods. Existing methods to solve the trust region problem require matrix factorizations that are not feasible in the large scale setting. This paper presents an algorithm for solving the large scale trust region problem that requires a fixed size limited storage proportional to order of the quadratic and that relies only on matrix-vector products. The algorithm recasts the trust region problem in terms of parameterized eigenvalue problem and adjusts the parameter with a superlinearly convergent iteration to find the optimal solution from the eigenvector of the parameterized problem. Only the smallest eigenvalue and corresponding eigenvector of the parameterized problem needs to be computed.
Citable link to this pagehttps://hdl.handle.net/1911/101839
MetadataShow full item record
- CAAM Technical Reports