Semidefinite programming in data science: strict complementarity and storage optimal algorithms

Time: 3:00-4:00pm

Location: Mathx 1100 (Math Annex) 

Live presentation only

Semidefinite programming (SDP) forms a class of convex optimization problems with remarkable modeling power. Apart from its classical applications in combinatorics and control, it also enjoys a range of applications in data science. This talk first discusses various concrete SDPs in data science and the challenges in solving them. In particular, we show that even though Slater's constraint qualification, a common regularity in convex optimization, may fail, these SDPs still satisfy the strict complementarity. This important regularity ensures the convergence of many existing algorithms.  In the second part of the talk, based on the strict complementarity and computational structure shared by these problems, we design time- and space-efficient algorithms to solve these SDPs.