Winner
Alex L. Wang (Computer Science, Carnegie Mellon University) for the paper titled “On the tightness of SDP relaxations of QCQPs" (jointly authored with Fatma Kilinc-Karzan)
Citation
This paper examines semidefinite programming (SDP) relaxations of general quadratically constrained quadratic programs (QCQPs). Although each QCQP can be relaxed into a semidefinite program immediately and there has been much work on understanding the approximation quality of SDP relaxations for specific QCQP classes (e.g., MaxCut), much less is known about the quality of SDP relaxations in terms of more abstract properties. Furthermore, not much is known about when the SDP relaxation of a given QCQP is exact beyond simple settings (e.g., the case where the QCQP has a single constraint). This paper makes significant progress towards identifying the properties of nonconvex QCQPs that ensure that their SDP relaxations are “good.” To this end, the paper defines and examines two notions of SDP exactness: (i) objective value exactness—the condition that the optimal value of the QCQP and the optimal value of its SDP relaxation coincide; and (ii) convex hull exactness—the condition that the convex hull of the QCQP epigraph coincides with the (projected) SDP epigraph. This paper show that the exactness conditions hold whenever the QCQP satisfies two abstract properties: (i) its set of convex Lagrange multipliers is polyhedral; and (ii) a natural symmetry parameter of the QCQP, the quadratic eigenvalue multiplicity, is sufficiently large. Variants of the paper's results hold for a number of interesting practical problems (e.g., applying variants of the main result show that robust least squares with nonconvex uncertainty regions or certain sphere packing problems can be solved exactly using SDPs).
This paper is of very high quality and timely. The constructions developed in this paper are essentially novel and highly nontrivial, witnessing very good creativeness and technical skills, and the overall framework has been exceptionally instrumental in establishing results on SDP exactness. Given the vast use of SDP relaxations and their surprisingly good performance in practical applications, the theoretical justifications for this phenomena offered in this paper are foundational.
Honorable Mention: Shixuan Zhang (Industrial and Systems Engineering, Georgia Institute of Technology) for the paper "Stochastic Dual Dynamic Programming for Multistage Stochastic Mixed-Integer Nonlinear Optimization" (jointly authored with Andy Sun)
Prize committee
Ruth Misener (chair), Paul Grigas, Robert Hildebrand, Weijun Xie