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

Si-ming Huang

DOI:

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

Published online: 2003-06

Preview Full PDF 158 1602
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 primaldual 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 ppositive 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 = {Si-ming Huang}, 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 primaldual 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 ppositive 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 - Si-ming Huang 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 KW - Potential reduction algorithms KW - 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 primaldual 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 ppositive 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