full
search.png

Search

close.png

Cancel

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

Si-Ming Huang

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

Published online: 2003-06

Preview Full PDF 1791 19453

Cited by

google scholar semantic scholar
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.

  • Keywords

Positive semi-definite programming, Potential reduction algorithms, Complexity.

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • 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
BibteX RIS TXT
The citation has been copied to your clipboard