Séminaire conjoint avec la Chaire de recherche du Canada sur l'optimisation non linéaire discrète en ingénierie et le GERAD
Titre : Efficient semidefinite programming relaxations for quadratic integer programming with applications including selection of rotamers in protein conformations
Conférencier : Henry Wolkowicz – University of Waterloo, Canada
Résumé :
In this talk we study Semidefinite Programming (SDP) relaxations of the (NP-hard) Quadratic Integer Programming (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)
Ce séminaire vous permettra d’échanger avec le conférencier et les chercheurs présents autour de boissons et de collations. Nous vous remercions de confirmer votre présence.
Entrée gratuite.
Bienvenue à tous!
