Optimization Online


Cutting Plane Generation Through Sparse Principal Component Analysis

Santanu S. Dey(santanu.dey***at***isye.gatech.edu)
Aleksandr M. Kazachkov(akazachkov***at***ufl.edu)
Andrea Lodi(andrea.lodi***at***polymtl.ca)
Gonzalo Muņoz(gonzalo.munoz***at***uoh.cl)

Abstract: Quadratically-constrained quadratic programs (QCQPs) are optimization models whose remarkable expressiveness has 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 towards 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.

Keywords: QCQPs, non-convex optimization, sparse cutting planes, sparse principal component analysis

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 02/18/2021
Entry Accepted: 02/18/2021
Entry Last Modified: 02/18/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society