A new matrix-free algorithm for the large-scale trust-region subproblem

We present a new method for the large-scale trust-region subproblem. The me thod is matrix-free in the sense that only matrix-vector products are requi red. We recast the trust-region subproblem as a parameterized eigenvalue pr oblem and compute an optimal value for the parameter. We then nd the soluti on of the trust-region subproblem from the eigenvectors associated with two of the smallest eigenvalues of the parameterized eigenvalue problem corres ponding to the optimal parameter. The new algorithm uses a different interp olating scheme than existing methods and introduces a uni ed 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 computati onal results to illustrate convergence properties and robustness of the met hod.