Solving the trust-region subproblem using the Lanczos method. (English) Zbl 1047.90510

Authors’ summary: 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. 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.


90C30 Nonlinear programming
90C20 Quadratic programming
65K05 Numerical mathematical programming methods
65F10 Iterative numerical methods for linear systems
Full Text: DOI