The Primal-Dual Potential Reduction Algorithm for Positive Semi-Definite Programming

Abstract

In this paper we introduce a primal-dual potential reduction algorithm for positive semi-definite programming. Using the symetric preserving scalings for both primal and dual interior matrices, we can construct an algorithm which is very similar to the primal-dual potential reduction algorithm of Huang and Kortanek [6] for linear programming. The complexity of the algorithm is either $O(n \log(X^0\cdot S^0/\epsilon))$ or $O(\sqrt{n}\log(X^0\cdot S^0/\epsilon))$ depends on the value of $\rho$ in the primal-dual potential function, where $X^0$ and $S^0$ is the initial interior matrices of the positive semi-definite programming.