We consider an effective new method for solving trust-region and
norm-regularization problems that arise as subproblems in many optimization
applications. We show that the solutions to such subproblems lie on
a manifold of approximately very low rank as a function of their
controlling parameters (trust-region radius or regularization weight).
Based on this, we build a basis for this manifold using an efficient
extended-Krylov-subspace iteration that involves a single matrix
factorization. The problems within the subspace using such a basis
may be solved at very low cost using effective high-order root-finding methods.
This then provides an alternative to common methods using
multiple factorizations or standard Krylov subspaces. We provide numerical
results to illustrate the effectiveness of our TREK/NREK approach.