ICCOPT 2013 Talk, Room 1.6, Wednesday, July 31, 16:30-18:00

 Speaker: Hongbo Dong, University of Wisconsin-Madison, USA
 Title: Relaxations for convex quadratic programming with binary indicator variables
 Co-authors: Jeff Linderoth

 Abstract:
Scientific Program

We consider convex relaxations for quadratic programming with continuous variables and their binary indicators, which has applications in sparse linear regression, sparse principal component analysis, digital filter design, etc. Based on a decomposition that splits a positive semidefinite (PSD) matrix into two PSD matrices, where one of them has a chosen sparsity pattern, we construct several convex relaxations. Some of them can be solved by second order cone programming, and others can be written as semidefinite programming over a sparse PSD cone (with a fixed sparsity pattern). Further we add linear inequalities that come from exploiting low dimensional convex hulls of quadratic forms including the indicator variables. We test on various problems to illustrate the trade-off between the speed of computing the relaxations and the strength of lower bounds.


 Talk in: Organized Session Wed.C.16 Copositive and quadratic optimization
 Cluster: Global optimization and mixed-integer programming


 Go to: Wed.C
 Go to: unframed Scientific Program

 Go to: ICCOPT 2013 Main Webpage