Strong convex relaxations for quadratically constrained quadratic programs

In Chapter 2 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 $\mathbb{R}^2$. In the next 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 Chapter 3, we present our first set convexification study which focuses on bipartite bilinear programs. The bipartite bilinear program (BBP) 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 these sets results in a linear program. We propose a new second-order cone (SOCP) representable relaxation for the bipartite bilinear program. We show that this relaxation 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 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 Chapter 4, we generalize the convexification results of Chapter 3. 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 Chapter 5, 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 this class of problems. 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.Ph.D