##
Homogeneous Interior--Point Algorithms
for Semidefinite Programming

###
Florian A. Potra and Rongqin Sheng

A simple homogeneous primal-dual feasibility model is proposed for
semidefinite programming (SDP) problems. Two
infeasible-interior-point algorithms are applied to the homogeneous
formulation. The algorithms do not need big M initialization. If the
original SDP problem has a solution, then both algorithms find an
$\eps$-approximate solution (i.e., a solution with residual error less
than or equal to $\eps$) in at most
$O(\sqrt{n}\ln(\rho^*\eps_0/\eps))$ steps, where $\rho^*$ is the trace
norm of a solution and $\eps_0$ is the residual error at the
(normalized) starting point. A simple way of monitoring possible
infeasibility of the original SDP problem is provided such that in at
most $O(\sqrt{n}\ln(\rho\eps_0/\eps))$ steps either an
$\eps$-approximate solution is obtained, or it is determined that
there is no solution with trace norm less than or equal to a given
number $\rho>0$.
Reports On Computational Mathematics, No. 82/1995,
Department Of Mathematics, The University Of Iowa.