Convexification of Quadratic Sets

This project was part of Asteroide's thesis and have been done in collaboration with his academic adviser Prof. Santanu S. Dey. It's mainly about studying convex hulls of sets commonly appearing in non-convex optimization problems.

They are particularly interested in Quadratically Constrainted Quadratic Programs (QCQPs) because it finds a large number of applications in a variety of combinatoric problems such as chemical process engineering, waste water management, signal processing and optimal power flow. Even a general polynomial optimization problem can be reformulated as a QCQP with the addition of a suitable number of variables.

In general, a QCQP is a non-convex problem which can be represented as follows:

where Q^k for k in {0, ..., m} are n x n matrices, and a^k for k in {0, ..., m} and b^k for k in {1, ..., m} are vectors of appropriate dimensions.

Because they are non-convex, QCQPs may contain multiple local optimal solutions that are not necessarily a global optimal. Local optimal solutions are computed efficiently for most applications. Identifying a global optimal solution, although very desirable in many applications, is generally a hard task that relies on our ability of deriving strong convex relaxations.

In one of Asteroide's paper, it's proved that the convex hull of a bipartite bilinear constraint (which is a special case of a quadratic constraint) intersected with a box constraint is second order cone representable (SOCP). The proof yields a procedure to compute this convex hull and successful computational results are reported. An SOCP relaxation for bipartite bilinear programs is also proposed which is shown to be stronger than the standard SDP relaxation intersected with the boolean quadratic polytope!

More recently, Asteroide and Prof. Dey were able to generalize the result mentioned above significantly. Specifically, they have shown that the convex hull of a general quadratic equation intersected with a bounded polyhedron is SOCP. Details can be found in the paper here. They are now studying applications and the computational implications of this result.