On Valid Inequalities for Quadratic Programming with Continuous Variables and Binary Indicators

摘要

In this paper we study valid inequalities for a set that involves a continuous vector variable x ∈ [0, 1]~n, its associated quadratic form xx~T, and binary indicators on whether or not x > 0. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). Valid inequalities for this set can be obtained by lifting inequalities for a related set without binary variables (QPB), that was studied by Burer and Letchford. After closing a theoretical gap about QPB, we characterize the strength of different classes of lifted QPB inequalities. We show that one class, lifted-posdiag-QPB inequalities, capture no new information from the binary indicators. However, we demonstrate the importance of the other class, called lifted-concave-QPB inequalities, in two ways. First, all lifted-concave-QPB inequalities define the relevant convex hull for the case of convex quadratic programming with indicators. Second, we show that all perspective constraints are a special case of lifted-concave-QPB inequalities, and we further show that adding the perspective constraints to a semidefinite programming relaxation of convex quadratic programs with binary indicators results in a problem whose bound is equivalent to the recent optimal diagonal splitting approach of Zheng et al.. Finally, we show the separation problem for lifted-concave-QPB inequalities is tractable if the number of binary variables involved in the inequality is small. Our study points out a direction to generalize perspective cuts to deal with non-separable nonconvex quadratic functions with indicators in global optimization. Several interesting questions arise from our results, which we detail in our concluding section.