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.

[DVI] [POSTSCRIPT] [IP PAGE] [SEARCH AGAIN]