Santanu Dey, Georgia Institute of Technology

Abstract

An important approach to solving non-convex quadratically constrained quadratic program (QCQP) to global optimality is to use convex relaxations and branch-and-bound algorithms. In our first result, we show that the exact convex hull of the solutions of a general quadratic equation intersected with any polytope is second-order cone representable. The proof is constructive and relies on the discovery of an interesting property of quadratic functions, which may be of independent interest: A set defined by a single quadratic equation is either (1) the boundary of a convex set, or (2) the boundary of union of two convex sets or (3) it has the property that through every point on the surface, there exists a straight line that is entirely contained in the surface. We next study sets defined for matrix variables that satisfy rank-1 constraint together with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-1 set is polyhedral or second-order cone representable. Finally, we present results from comprehensive set of computational experiments and show that our convexification results together with discretization significantly help in improving dual bounds for the generalized pooling problem.

This is joint work with Asteroide Santana and Burak Kocuk.