Efficient use of semidefinite programming for selection of rotamers in protein conformations and other applications

-
Henry Wolkowicz, University of Waterloo
Fine Hall 214

In this paper we study a semidefinite programming relaxation of the (NP-hard) side chain positioning problem. We show that the Slater constraint qualification (strict feasibility) fails for the SDP relaxation. We then show the advantages of using facial reduction to regularize the SDP. In fact, after applying facial reduction, we have a smaller problem that is more stable both in theory and in practice. We include a discussion of the background of SDP relaxations and exploiting pecial structure in various applications such as sensor network localization, SNL.  Work with: Forbes Burkowski (University of Waterloo) Yuen-Lam Cheung Voronin (University of Colorado, Boulder)