Title: Strong Convex Relaxations for Quadratically Constrained Quadratic Programs
Advisors: Dr. Santanu Dey

Committee Members:
Dr. George Nemhauser
Dr. Andy Sun
Dr. Natashia Boland
Dr. Yang Wang (School of Civil and Environmental Engineering & School of Electrical and  Computer Engineering)

Date and Time: Thursday, March 7th, 12:00 pm
Location: Groseclose 226A

Abstract: In the first chapter of the thesis, we study cut generating functions for conic sets. Our first main result shows that if the conic set is bounded, then cut generating functions for integer linear programs can easily be adapted to give the integer hull of the conic integer program. We then introduce a new class of cut generating functions which are non-decreasing with respect to the second-order cone. We show that, under some minor technical conditions, these functions together with integer linear programming-based functions are sufficient to yield the integer hull of intersections of conic sections in the two-dimensional space.

In the remaining three chapters of the thesis, we study convexification of sets related to the quadratically constrained quadratic program (QCQP). This is an optimization problem in which the objective function is a quadratic function and the feasible region is defined by quadratic constraints. Solving non-convex quadratically constrained quadratic program to global optimality is a well-known NP-hard problem and a traditional approach is to use convex relaxations and branch-and-bound algorithms. In this thesis, we make several contributions in this direction.

In the second Chapter, we present our first set convexification study which focuses on bipartite bilinear programs (BBP). A bipartite bilinear program is a special case of the quadratically constrained quadratic program where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second-order cone (SOCP) representable relaxation for bipartite bilinear programs, which we show is stronger than the standard semidefinite programming (SDP) relaxation intersected with the boolean quadric polytope. We then propose a new branching rule inspired by the construction of the second-order cone relaxation. In addition, we describe a new application of bipartite bilinear program called the finite element model updating problem, which is a fundamental problem in structural engineering. Our computational experiments on this problem class show that the new branching rule together with a polyhedral outer approximation of the second-order cone relaxation outperforms a state-of-the-art commercial global solver in obtaining dual bounds.

In the third Chapter, we generalize the convexification results of the second Chapter. Specifically, we show 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 of this result.

In the fourth Chapter, we study sets defined as the intersection of a rank-1 constraint with different choices of linear side constraints and show how these sets relate to commonly occurring substructures of the quadratically constrained quadratic program. 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. In all these cases, we also show that a linear objective can be optimized in polynomial time over these sets. Towards the application side, to illustrate the benefit of studying quadratically constrained quadratic programs from a rank-1 perspective, we propose new rank-1 formulations for the generalized pooling problem and use our results to obtain new convex relaxations for the pooling problem. Finally, we run a 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.