##
Symmetric primal-dual path following algorithms for semidefinite programming

###
Jos Sturm and Shuzhong Zhang

In this paper a symmetric primal-dual transformation for positive
semidefinite programming is proposed. For standard SDP problems,
after this symmetric transformation the primal variables and the
dual slacks become identical. In the context of linear
programming, existence of such a primal-dual transformation is a
well known fact. Based on this symmetric primal-dual
transformation we derive Newton search directions for primal-dual
path-following algorithms for semidefinite programming. In
particular, we generalize: (1) the short step path following
algorithm, (2) the predictor-corrector algorithm and (3) the
largest step algorithm to semidefinite programming. It is shown
that these algorithms require at most
${\cal O}(\sqrt{n}\mid \log \epsilon \mid )$ main
iterations for computing an $\epsilon $-optimal solution.
The symmetric primal-dual transformation discussed in this paper can be
interpreted as a specialization of the scaling-point concept introduced
by Nesterov and Todd \cite{NT95} for self-scaled conic problems.
The difference is that we explicitly
use the usual $v$-space notion and the proofs look very similar to
the linear programming case.
Report 9554/A, Econometric Institute, Erasmus University, Rotterdam.