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 - <p style="text-align: justify;">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$.&nbsp; 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.</p>