Solving the trust-region subproblem using the Lanczos method

The approximate minimization of a quadratic function within an ellipsoidal trust region is an important subproblem for many nonlinear programming meth ods. When the number of variables is large, the most widely used strategy i s 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 genera ted Krylov subspace has a very special structure which enables it to be sol ved very efficiently. We compare the new strategy with existing methods. Th e resulting software package is available as HSL-VF05 within the Harwell Su broutine Library.