Year: 2003
Author: Si-Ming Huang
Journal of Computational Mathematics, Vol. 21 (2003), Iss. 3 : pp. 339–346
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.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/2003-JCM-10262
Journal of Computational Mathematics, Vol. 21 (2003), Iss. 3 : pp. 339–346
Published online: 2003-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 8
Keywords: Positive semi-definite programming Potential reduction algorithms Complexity.