full
search.png

Search

close.png

Cancel

arrow
Volume 37, Issue 6
A Robust Interior Point Method for Computing the Analytic Center of an Ill-Conditioned Polytope with Errors

Zhouhong Wang, Yuhong Dai & Fengmin Xu

DOI: 10.4208/jcm.1907-m2019-0016

J. Comp. Math., 37 (2019), pp. 843-865.

Published online: 2019-11

Preview Full PDF 2214 27817

Cited by

google scholar semantic scholar
Export citation
  • Abstract

In this paper we propose an efficient and robust method for computing the analytic center of the polyhedral set $P = \{x \in R^n \mid Ax = b, x \ge 0\}$, where the matrix $A \in R^{m\times n}$ is ill-conditioned, and there are errors in $A$ and $b$.  Besides overcoming the difficulties caused by ill-conditioning of the matrix $A$ and errors in $A$ and $b$, our method can also detect the infeasibility and the unboundedness of the polyhedral set $P$ automatically during the computation. Detailed mathematical analyses for our method are presented and the worst case complexity of the algorithm is also given. Finally some numerical results are presented to show the robustness and effectiveness of the new method.

  • Keywords

Analytic center, Ill-conditioning, Unboundedness, Primal-dual interior point algorithm, Convergence, Polynomial complexity.

  • AMS Subject Headings

65K05, 90C51

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

wangzhh@bjtu.edu.cn (Zhouhong Wang)

dyh@lsec.cc.ac.cn (Yuhong Dai)

fengminxu@mail.xjtu.edu.cn (Fengmin Xu)

  • BibTex
  • RIS
  • TXT
@Article{JCM-37-843, author = {Wang , ZhouhongDai , Yuhong and Xu , Fengmin}, title = {A Robust Interior Point Method for Computing the Analytic Center of an Ill-Conditioned Polytope with Errors}, journal = {Journal of Computational Mathematics}, year = {2019}, volume = {37}, number = {6}, pages = {843--865}, abstract = {

In this paper we propose an efficient and robust method for computing the analytic center of the polyhedral set $P = \{x \in R^n \mid Ax = b, x \ge 0\}$, where the matrix $A \in R^{m\times n}$ is ill-conditioned, and there are errors in $A$ and $b$.  Besides overcoming the difficulties caused by ill-conditioning of the matrix $A$ and errors in $A$ and $b$, our method can also detect the infeasibility and the unboundedness of the polyhedral set $P$ automatically during the computation. Detailed mathematical analyses for our method are presented and the worst case complexity of the algorithm is also given. Finally some numerical results are presented to show the robustness and effectiveness of the new method.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1907-m2019-0016}, url = {http://global-sci.org/intro/article_detail/jcm/13378.html} }
TY - JOUR T1 - A Robust Interior Point Method for Computing the Analytic Center of an Ill-Conditioned Polytope with Errors AU - Wang , Zhouhong AU - Dai , Yuhong AU - Xu , Fengmin JO - Journal of Computational Mathematics VL - 6 SP - 843 EP - 865 PY - 2019 DA - 2019/11 SN - 37 DO - http://doi.org/10.4208/jcm.1907-m2019-0016 UR - https://global-sci.org/intro/article_detail/jcm/13378.html KW - Analytic center, Ill-conditioning, Unboundedness, Primal-dual interior point algorithm, Convergence, Polynomial complexity. AB -

In this paper we propose an efficient and robust method for computing the analytic center of the polyhedral set $P = \{x \in R^n \mid Ax = b, x \ge 0\}$, where the matrix $A \in R^{m\times n}$ is ill-conditioned, and there are errors in $A$ and $b$.  Besides overcoming the difficulties caused by ill-conditioning of the matrix $A$ and errors in $A$ and $b$, our method can also detect the infeasibility and the unboundedness of the polyhedral set $P$ automatically during the computation. Detailed mathematical analyses for our method are presented and the worst case complexity of the algorithm is also given. Finally some numerical results are presented to show the robustness and effectiveness of the new method.

Zhouhong Wang, Yuhong Dai & Fengmin Xu. (2019). A Robust Interior Point Method for Computing the Analytic Center of an Ill-Conditioned Polytope with Errors. Journal of Computational Mathematics. 37 (6). 843-865. doi:10.4208/jcm.1907-m2019-0016
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard