The Generalized Trust Region Subproblem: solution complexity and convex hull results

Understand

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.