Convex relaxations of non-convex MIQCP
Presenter
November 18, 2008
Keywords:
- Convex relation
MSC:
- 52B55
Abstract
Joint work with Pierre Bonami and Jon Lee.
This talk addresses the problem of generating strong convex
relaxations of Mixed Integer Quadratically Constrained Programming
(MIQCP) problems. MIQCP problems are very difficult because they
combine two kinds of non-convexities: integer variables and
non-convex quadratic constraints. To produce strong relaxations of
MIQCP problems, we use techniques from disjunctive programming and
the lift-and-project methodology. In particular, we propose new methods for
generating valid inequalities by using the equation Y = x xT. We
use the concave constraint $0 \succcurlyeq Y - x xT $ to derive
disjunctions of two types. The first ones are directly derived from
the eigenvectors of the matrix Y - x xT with positive
eigenvalues, the second type of disjunctions are obtained by
combining several eigenvectors in order to minimize the width
of the disjunction. We also use the convex SDP constraint Y - x
xT \succcurlyeq 0 to derive convex quadratic cuts, and we combine
both approaches in a cutting plane algorithm. We present
computational results to illustrate our findings.