Cutting Plane Generation through Sparse Principal Component Analysis
针对非凸二次约束二次规划（QCQP）难以求解的问题，提出一种计算高效的线性切割平面算法，通过稀疏主成分分析生成稀疏切割平面，替代内存密集的半定规划松弛，实验表明该方法有效。
Quadratically constrained quadratic programs (QCQPs) are optimization models whose remarkable expressiveness have made them a cornerstone of methodological research for nonconvex optimization problems. However, modern methods to solve a general QCQP fail to scale, encountering computational challenges even with just a few hundred variables. Specifically, a semidefinite programming (SDP) relaxation is typically employed, which provides strong dual bounds for QCQPs but relies on memory-intensive algorithms. An appealing alternative is to replace the SDP with an easier-to-solve linear programming relaxation while still achieving strong bounds. In this work, we make advances toward achieving this goal by developing a computationally efficient linear cutting plane algorithm that emulates the SDP-based approximations of nonconvex QCQPs. The cutting planes are required to be sparse, in order to ensure a numerically attractive approximation, and efficiently computable. We present a novel connection between such sparse cut generation and the sparse principal component analysis problem in statistics, which allows us to achieve these two goals. We show extensive computational results advocating for the use of our approach.