TY - JOUR
T1 - The Primal-Dual Potential Reduction Algorithm for Positive Semi-Definite Programming
AU - Huang , Si-Ming
JO - Journal of Computational Mathematics
VL - 3
SP - 339
EP - 346
PY - 2003
DA - 2003/06
SN - 21
DO - http://doi.org/
UR - https://global-sci.org/intro/article_detail/jcm/10262.html
KW - Positive semi-definite programming, Potential reduction algorithms, Complexity.
AB - <p style="text-align: justify;">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.</p>