We present a nearly-exact method for the large scale trust region subproblem (TRS) based on the properties of the minimal-memory BFGS method. Our study in concentrated in the case where the initial BFGS matrix can be any scaled identity matrix. The proposed method is a variant of the Mor\'{e}-Sorensen method that exploits the eigenstructure of the approximate Hessian $B$, and incorporates both the standard and the hard case. The eigenvalues are expressed analytically, and consequently a direction of negative curvature can be computed immediately by performing a sequence of inner products and vector summations. Thus, the hard case is handled easily while the Cholesky factorization is completely avoided. An extensive numerical study is presented, for covering all the possible cases arising in the TRS with respect to the eigenstructure of $B$. Our numerical experiments confirm that the method is suitable for very large scale problems.
Citation
Optimization Letters http://www.springerlink.com/content/p4t7481772123874 Technical Report No. TR09-01, University of Patras, Department of Mathematics, March 2009.