Solving the Trust-Region Subproblem using the Lanczos Method

TLDR

Minimizing a quadratic function over an ellipsoidal trust region is a key subproblem in nonlinear programming, and for high‑dimensional problems the standard approach traces conjugate‑gradient iterates until convergence or until the trust‑region boundary is reached. This study explores strategies for continuing the optimization once the trust‑region boundary has been encountered. By exploiting the special structure of the trust‑region problem restricted to the current Krylov subspace, the authors devise an efficient solution method and benchmark it against existing approaches. The resulting implementation is released as the HSL_VF05 package in the Harwell Subroutine Library.

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.