Efficient Solutions for the Large Scale Trust Region Subproblem
     Heng Ye and Henry Wolkowicz
    University of Waterloo, 
    Department of Combinatorics and Optimization, 
    Waterloo, Ontario, Canada, N2L 3G1.

Abstract:
The \emph{Trust Region Subproblem} (TRS) is the:
minimization of a 
quadratic (possibly non-convex) function over a sphere. 
It is the main step of the trust region method for unconstrained
optimization, and is a basic tool behind regularization.
The TRS has interesting theoretical properties as it is an implicit
convex problem.  
Many efficient algorithms have been proposed and implemented.
In particular, current algorithms can exploit sparsity for large scale problems;
and, they can also handle degeneracy, i.e., the so-called \emph{hard case}.
In this paper we show that a \emph{shift and deflate} approach changes
the hard case into a trivial case. 
Thus the TRS is one instance of a class of problems where one can take
advantage of degeneracy once the structure is well understood.
We add the above approach to several additional
techniques and derive an efficient algorithm for solving large scale
instances of TRS.