Winner
Gonzalo Munoz (Universidad de O'Higgins, Rancagua, Chile)
Felipe Serrano (ZIB, Berlin, Germany)
Citation
In this paper, Dr. Munoz and Dr. Serrano develop foundations for using cutting plane technology in nonconvex, quadratically constrained quadratic optimization problems. Cutting planes are an indispensable tool in algorithms and solvers for mixed-integer linear optimization. The overall idea is to convexify a nonconvex problem and thus reduce to convex optimization. A central idea from this field is that of intersection cuts. This idea was introduced for mixed-integer linear optimization by Balas in the 70s, but in principle can be applied to a general nonconvex optimization problem with “structured” nonconvexity. Nevertheless, this paper by Dr. Munoz and Dr. Serrano is one of the first ones that applies this technique outside the integer optimization setting, in this case for continuous nonconvex quadratic optimization. There are several highly nontrivial conceptual and technical challenges that must be surmounted to make this transfer of ideas work. First, some convex geometry issues are easier to handle in the integer lattice case because of the regular structure of the integer lattice, and fresh new ideas are needed to handle them in the quadratic case. Second, the structure of quadratics “at infinity” requires developing completely new insights for these tools that have no counterpart in the integer lattice case. The constructions by the authors for handling asymptotes in nonlinear sets also hold promise beyond the quadratic setting. Further, the paper itself is written with a textbook-like exposition, presenting the new ideas with clarity and illustrated with well-designed figures. While the paper itself is of a theoretical and foundational nature, its computational viability has been proven convincingly in follow up work by the authors and other collaborators. In conclusion, we feel this paper makes a fundamental and lasting contribution which has the potential to significantly advance algorithms and solvers for general nonconvex QCQPs, and nonconvex optimization more broadly.
Prize committee
Amitabh Basu (chair), Ilya Hicks, Courtney Paquette, Andy Sun