A NESTED LANCZOS METHOD FOR THE TRUST-REGION SUBPROBLEM.

The trust-region subproblem (TRS) minimizes a quadratic f(s) = sTHs=2 + sTg over the ellipsoidal constraint ||s||M ≤ Δ for a symmetric and positive definite matrix M. For a large scale TRS, a Lanczos-type approach, namely, the generalized Lanczos trust-region (GLTR) method was introduced by Gould, Lucidi, Roma, and Toint [SIAM J. Optim., 9 (1999), pp. 504{525], and extends nicely the classical Lanczos method for the eigenvalue problem to TRS. Basically, GLTR attempts to obtain a feasible approximation in the Krylov subspace Kk(M-1H,M-1g) is usually modest for a well-conditioned TRS, but can be large for ill-conditioned problems. This causes numerical difficulties in the computational costs, memory requirements, and numerical stability. This paper introduces an efficient nested restarting strategy for GLTR and resolves these numerical troubles. Convergence analysis and numerical testings are carried out to support our improvements upon GLTR. [ABSTRACT FROM AUTHOR]