CRPC-TR99795						September 1999

Title: A New Matrix-Free Algorithm for the Large-Scale Trust-Region
Subproblem

Authors: Marielba Rojas, Sandra A. Santos, and Danny C. Sorensen

Submitted November 1999

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 interpolating scheme
than existent 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.

------------------------------------------------------------------------------

Marielba Rojas
mrojas@caam.rice.edu
Department of Computational and Applied Mathematics
Rice University

Sandra A. Santos
sandra@ime.unicamp.br
Department of Mathematics
State University of Campinas

Danny C. Sorensen
sorensen@caam.rice.edu
Department of Computational and Applied Mathematics
Rice University