2x2 convexifications for convex quadratic optimization with indicator variables
arXiv:2004.07448
Abstract
In this paper, we study the convex quadratic optimization problem with indicator variables. For the bivariate case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the bivariate case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including Shor's SDP relaxation, the optimal perspective relaxation as well as the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems.
References in corpus (9)
- Phase Transitions in Semidefinite Relaxations
- A Second-Order Cone Based Approach for Solving the Trust Region Subproblem and Its Variants
- Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
- Tight MIQP Reformulations for Semi-Continuous Quadratic Programming: Lift-and-Convexification Approach
- Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
- Rank-one Convexification for Sparse Regression
- Sparse and Smooth Signal Estimation: Convexification of L0 Formulations
- A unified approach to mixed-integer optimization problems with logical constraints
- Quadratic Optimization with Switching Variables: The Convex Hull for