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

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

Published online: 2019-11

Preview Full PDF 15 321
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.

65K05, 90C51

wangzhh@bjtu.edu.cn (Zhouhong Wang)

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

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

• References
• Hide All
View All

@Article{JCM-37-843, author = {Wang , Zhouhong and Dai , 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} }
Copy to clipboard
The citation has been copied to your clipboard