title:
Robust search directions for large sparse semidefinite programming (SDP)

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.
-----------------------------------------
Part II: (added after abstract submission)
title: 
Strengthened Existence and Uniqueness Conditions for
Search Directions in Semidefinite Programming

Primal-dual interior-point (p-d i-p) methods for Semidefinite 
Programming (SDP) are generally based on solving a system of matrix
equations for a Newton type
search direction for a symmetrization of the optimality conditions.
These search directions  followed
the derivation of similar p-d i-p methods for linear programming (LP).
Among these, a computationally interesting
search direction is the AHO direction.
However, in contrast to the LP case, existence and uniqueness of the
AHO search direction is not guaranteed under the standard nondegeneracy
assumptions.
Two different sufficient conditions are known that guarantee
the existence and
uniqueness independent of the specific linear constraints. The first
is given by Shida-Shindoh-Kojima and is based on the semidefiniteness
of the symmetrization of the product $SX$ at the current iterate.
The second is a centrality condition given first
by Monteiro-Zanj{\'a}como and then improved by Monteiro-Todd.

In this paper, we revisit and strengthen both of the above mentioned
sufficient conditions. 
We include characterizations for existence and
uniqueness in the matrix equations arising from the linearization of
the optimality conditions.
As well, we present new results on the relationship between the
Kronecker product and the {\em symmetric Kronecker product} that arise
from these matrix equations.  We conclude with a proof that
the existence and uniqueness of the AHO direction is a generic
property for every SDP problem and extend the results to the
general Monteiro-Zhang family of search directions.