title:
Robust algorithms for large sparse semidefinite programming (SDP)
abstract
Current paradigms for search directions
for primal-dual interior-point methods for SDP use: (i) symmetrize
the linearization of the optimality conditions at the current estimate;
(ii) form and solve the Schur complement equation for the dual
variable dy; (iii) back solve to complete the search direction.
These steps result in loss of sparsity and ill-conditioning/instability, in
particular when one takes long steps and gets close to the boundary
of the positive semidefinite cone. This has resulted in the exclusive
use of direct, rather than iterative methods, for the linear system.
We look at alternative paradigms based on least squares, an inexact
Gauss-Newton approach, and a matrix-free preconditioned conjugate
gradient method. This avoids the ill-conditioning in the nondegenerate
case. We emphasize exploiting structure in large sparse problems.
In particular, we look at LP and SDP relaxations of the: Max-Cut; Quadratic
Assignment; Theta function; and Nearest Correlation Matrix problems.