In this paper, ellipse is used to approximate the central path of the linear programming. An interior-point algorithm is devised to search the optimizers along the ellipse. The algorithm is proved to be polynomial with the complexity bound $O(n^{\frac{1}{2}}\log(1/\epsilon))$. Numerical test is conducted for problems in Netlib. For most tested Netlib problems, the result shows that the new algorithm uses less iteration to converge than the Matlab optimization toolbox {\tt linprog} which implements the state-of-art Mehrotra's predictor-corrector algorithm. For all the tested problems, the number of total iterations using the new algorithm is about 20$\%$ fewer than the one using {\tt linprog}.
Article
View A Polynomial Arc-Search Interior-Point Algorithm for Linear Programming