Wednesday, June 10, 2015
at GERAD Colloquium
University of Montreal Campus, Andre-Aisenstadt Building, 2920, Chemin de la Tour, 4th floor, room 4457
Abstract
In this talk we study SDP relaxations of the
(NP-hard) QIP problem: a quadratic objective with linear and integer
constraints. We discuss how adding redundant constraints helps
strengthen the relaxation.
We show that the Slater constraint qualification (strict feasibility)
fails for the SDP relaxation. We then show the advantages of using facial
reduction, a minimal representation, to regularize the SDP.
In fact, after applying facial reduction, we have a smaller equivalent
problem that is more stable both in theory and in practice.
Thus we have the seemingly contradictory strategy: adding redundant
constraints and a maximal representation before the relaxation while
removing redundancy and obtaining a minimal representation after the
relaxation.
We illustrate the strategy with applications including an application
to the side chain positioning problem in protein conformations.
Work with: Forbes Burkowski (University of Waterloo); Yuen-Lam Cheung Voronin (University of Colorado, Boulder)