The Primal-Dual Potential Reduction Algorithm for Positive Semi-Definite Programming (Journal of Computational Mathematics, 2003)
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.
Keywords: Positive semi-definite programming; Potential reduction algorithms; Complexity.