  We consider the Generalized Trust Region Subproblem (GTRS) of minimizing a
nonconvex quadratic objective over a nonconvex quadratic constraint. A lifting
of this problem recasts the GTRS as minimizing a linear objective subject to
two nonconvex quadratic constraints. Our first main contribution is structural:
we give an explicit description of the convex hull of this nonconvex set in
terms of the generalized eigenvalues of an associated matrix pencil. This
result may be of interest in building relaxations for nonconvex quadratic
programs. Moreover, this result allows us to reformulate the GTRS as the
minimization of two convex quadratic functions in the original space. Our next
set of contributions is algorithmic: we present an algorithm for solving the
GTRS up to an epsilon additive error based on this reformulation. We carefully
handle numerical issues that arise from inexact generalized eigenvalue and
eigenvector computations and establish explicit running time guarantees for
these algorithms. Notably, our algorithms run in linear (in the size of the
input) time. Furthermore, our algorithm for computing an epsilon-optimal
solution has a slightly-improved running time dependence on epsilon over the
state-of-the-art algorithm. Our analysis shows that the dominant cost in
solving the GTRS lies in solving a generalized eigenvalue problem --
establishing a natural connection between these problems. Finally,
generalizations of our convex hull results allow us to apply our algorithms and
their theoretical guarantees directly to equality-, interval-, and hollow-
constrained variants of the GTRS. This gives the first linear-time algorithm in
the literature for these variants of the GTRS.
