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

x

x

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.