« search calendars« CRM/DIMACS Workshop on Mixed-Integer Nonlinear Programming

« Sparse Cutting Planes For Quadratically-Constrained Quadratic Programs

Sparse Cutting Planes For Quadratically-Constrained Quadratic Programs

October 07, 2019, 3:30 PM - 4:00 PM


Auditorium (Amphitheatre Banque Nationale)

HEC Montreal

Cote-Sainte-Catherine Building

Click here for map.

Aleksandr Kazachkov, Polytechnique Montréal

Quadratically-constrained quadratic programs (QCQPs) are an active and challenging research topic in optimization. Their remarkable expressiveness has made these problems a cornerstone in the development of theoretical and practical improvements in non-convex optimization. While modern computational methods, especially those associated to semidefinite programming (SDP), are able to provide strong bounds, they typically rely on computationally-expensive computations hindering their applicability in medium-to-large-scale problems. In this work, we develop a computationally-efficient method that emulates the SDP-based approximations of nonconvex QCQPs via a cutting plane algorithm. These cuts are required to be sparse, in order to ensure attractive numerical properties, and efficiently computable. We present a novel connection between such sparse cut generation and the sparse principal component analysis (PCA) problem in statistics, which allows us to achieve these two goals. We show extensive computational results advocating for the use of our approach.

(Based on joint work with Santanu S. Dey, Andrea Lodi, and Gonzalo Muñoz)