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

Henry Wolkowicz, Univ. of Waterloo
Apr 20 2015 - 4:30pm
Event type: 
PACM Colloquium
Fine 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 special 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)