Computing the local minimizers of a large and sparse trust-region subproblem

We present new algorithms for computing local minimizers of the trust-region subproblem (TRS). This problem consists in minimizing a quadratic function subject to a ball constraint. In particular, this problem appears as a subproblem in trust-region methods for constrained and unconstrained optimization. First, by modeling the TRS with a new semidefinite program, different than the standard semidefinite relaxation, we derive an algorithm, similar in structure to the Rendl-Wolkowicz Algorithm, which implicitly solves the semidefinite program by maximizing a single variable concave function over a closed interval. Second, we extend the theory needed for this algorithm and the Rendl-Wolkowicz Algorithm to derive two algorithms for computing a local-nonglobal minimizer of the TRS. These algorithms are based upon finding a root of a single variable convex function with the secant method. In all our algorithms, we compute at most the two smallest eigenvalues of a parameterized matrix. This can be done using an ARPACK subroutine which only requires matrix-vector multiplications. Hence, we are able to exploit the possible sparsity of the Hessian matrix of the quadratic objective, making the algorithms suitable for large problems. Computationally, the algorithms for finding a local-nonglobal minimizer are more competitive than the previous approach based on computing a matrix factorization at each iteration