A New Matrix-Free Algorithm for the Large-Scale Trust-Region Subproblem
Marielba Rojas, Sandra A. Santos, and Danny C. Sorensen
Reports in Informatics No. 175, September 1999, Department of
Informatics, University of Bergen, Norway.
Abstract
We present a matrix-free algorithm for the large-scale trust-region
subproblem. Our algorithm relies on matrix-vector products only and
does not require matrix factorizations. We recast the trust-region
subproblem as a parameterized eigenvalue problem and compute an
optimal value for the parameter. We then find the optimal solution of
the trust-region subproblem from the eigenvectors associated with two
of the smallest eigenvalues of the parameterized eigenvalue problem
corresponding to the optimal parameter. The new algorithm uses a
different interpolation scheme than existing methods and introduces a
unified iteration that naturally includes the so-called hard case. We
show that the new iteration is well defined and convergent at a
superlinear rate. We present computational results to illustrate
convergence properties and robustness of the method.
Download
Back