THE CONVEX HULL OF A QUADRATIC CONSTRAINT OVER A POLYTOPE

A quadratically constrained quadratic program (QCQP) is an optimization problem in which the objective function is a quadratic function and the feasible region is defined by quadratic constraints. Solving nonconvex QCQP to global optimality is a well-known NP-hard problem and a traditional approach is to use convex relaxations and branch-and-bound algorithms. This paper makes a contribution in this direction by showing that the exact convex hull of a general quadratic equation intersected with any bounded polyhedron is second-order cone representable. We present a simple constructive proof and some preliminary applications of this result.