A NESTED LANCZOS METHOD FOR THE TRUST-REGION SUBPROBLEM

摘要

The trust-region subproblem (TRS) minimizes a quadratic f(s) = s(T) Hs/2 + s(T)g over the ellipsoidal constraint parallel to s parallel to(M) = Delta 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 K-k(M-1 H, M-1 g) in an efficient way. For an accurate approximation, the dimension k of K-k(M-1 H, M-1 g) 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.