Solving the Trust-Region Subproblem using the Lanczos Method
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 9 (2), 504-525
- https://doi.org/10.1137/s1052623497322735
Abstract
The approximate minimization of a quadratic function within an ellipsoidal trust region is an important subproblem for many nonlinear programming methods. When the number of variables is large, the most widely used strategy is to trace the path of conjugate gradient iterates either to convergence or until it reaches the trust-region boundary. In this paper, we investigate ways of continuing the process once the boundary has been encountered. The key is to observe that the trust-region problem within the currently generated Krylov subspace has a very special structure which enables it to be solved very efficiently. We compare the new strategy with existing methods. The resulting software package is available as HSL_VF05 within the Harwell Subroutine Library.Keywords
This publication has 14 references indexed in Scilit:
- Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical ConstraintSIAM Journal on Optimization, 1997
- CUTEACM Transactions on Mathematical Software, 1995
- Max-min eigenvalue problems, primal-dual Interior point algorithms, and Trust region subproblemstOptimization Methods and Software, 1995
- A New Modified Cholesky FactorizationSIAM Journal on Scientific and Statistical Computing, 1990
- Newton-Type Minimization via the Lanczos MethodSIAM Journal on Numerical Analysis, 1984
- Computing a Trust Region StepSIAM Journal on Scientific and Statistical Computing, 1983
- Computing Optimal Locally Constrained StepsSIAM Journal on Scientific and Statistical Computing, 1981
- Tracking the Progress of the Lanczos Algorithm for Large Symmetric EigenproblemsIMA Journal of Numerical Analysis, 1981
- Two new unconstrained optimization algorithms which use function and gradient valuesJournal of Optimization Theory and Applications, 1979
- Maximization by Quadratic Hill-ClimbingEconometrica, 1966