Abstract:

We propose a fully sparse path-following primal-dual algorithm for semidefinite programming. Interior-point methods for semidefinite programming (SDP) blossomed starting in the mid-1990s because it was found that, first, many applications including interesting combinatorial optimization problems could be reduced to SDP and, second, much of the theory of interior point methods developed for linear programming extended to SDP. One drawback with SDP, however, is that even if the input data is sparse, dense matrices must be used throughout the solution procedure.

Several approaches have been proposed to alleviate the need for carrying dense matrices, most notably Fukuda et al.'s method for storing only a partial primal matrix and extending it when needed. This technique removes the need for some dense matrix computation. We show how to remove the remaining dense matrix computation by using iterative solvers in tandem with automatic differentiation. Our proposed method never stores dense matrices and is faster than Fukuda et al.'s for very large problems.

This talk represents joint work with Gun Srijuntongsiri of Cornell.