Aleksandr Kazachkov, Polytechnique Montréal

Abstract

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)