Friday, September 30, 2005
1:30 pm Posner Hall 151
Zhaosong Lhu
Dept. of Mathematical Sciences, CMU
Large-Scale Semidefinite Programming via a Saddle Point Mirror-Prox Algorithm
We first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the “dual counterpart” of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of fully defined submatrices of the matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method developed by Nemirovski (2004) with efficiency $O(\epsilon^{-1})$. Implementations and some numerical results for large-scale Lovasz capacity and MAXCUT problems are finally presented.
