A wide neighborhood infeasible-interior-point method with arc-search for linear programming

摘要

In this paper, we propose an arc-search infeasible-interior-point method for linear programming. The proposed algorithm is based on a wide neighborhood of the central path and searches the optimizers along the ellipses that approximate the entire the central path. We also establish polynomial complexity of the proposed algorithm. Finally, numerical experiments showthat the proposed algorithm is efficient and reliable.