Volume 21, Issue 3
The Primal-Dual Potential Reduction Algorithm for Positive Semi-Definite Programming

J. Comp. Math., 21 (2003), pp. 339-346.

Published online: 2003-06

Cited by

Export citation
• 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.

• BibTex
• RIS
• TXT
@Article{JCM-21-339, author = {Huang , Si-Ming}, title = {The Primal-Dual Potential Reduction Algorithm for Positive Semi-Definite Programming}, journal = {Journal of Computational Mathematics}, year = {2003}, volume = {21}, number = {3}, pages = {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.

}, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/10262.html} }
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 -

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.

Si-Ming Huang. (1970). The Primal-Dual Potential Reduction Algorithm for Positive Semi-Definite Programming. Journal of Computational Mathematics. 21 (3). 339-346. doi:
Copy to clipboard
The citation has been copied to your clipboard