Efficient Solutions for the Large Scale Generalized Trust Region Subproblems

Ting Kei Pong, Heng Ye, Henry Wolkowicz

Department of Combinatorics and Optimization 
University of Waterloo, Canada

Abstract:
The Generalized Trust Region Subproblem (GTRS) is the:
minimization of a quadratic (possibly non-convex) function subject to a
quadratic (possibly non-convex) two sided constraint.
Under a simple Slater type constraint qualification,
this seemingly nonconvex problem is implicitly convex.
We show how to efficiently solve large scale sparse problems using a
parametric eigenvalue algorithm. In addition, we 
use a shift and deflate approach and show that the
so-called hard case is generally actually  a trivial case.