Mathematics Colloquium: Results on Quadratic Programming with Binary Indicator Variables
4:10 pm - Neill Hall
We study a special class of mixed-binary quadratic optimization problems, where the binary variables are "on/off" switches of other continuous variables. Problems with this structure arise in many applications, including portfolio selection, sparse least-squares, discrete time filter design, etc. We study a fundamental convex hull, comprise of the (vector of) continuous variable x, its quadratic form xx^T, and binary "on/off" switches z. Valid inequalities for this convex hull can be obtained by "lifting" inequalities for a related set without binary variables (QPB), that was recently studied by [Burer and Letchford, 2009]. 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 relaxation 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. Motivated by these theoretical insights, we derive a new computational mechanism using 2-variable lifted-concave-QPB cuts. Preliminary results on portfolio selection problems show this approach is promising.