A polynomial-time weighted path-following interior-point algorithm for linear optimization.

In this paper, a weighted short-step primal-dual path-following interior-point algorithm for solving linear optimization (LO) is presented. The algorithm uses at each interior-point iteration a full-Newton step, thus no need to use line search, and the strategy of the central-path to obtain an 𝜖 -approximated solution of LO. We show that the algorithm yields the iteration bound, namely, 𝒪 (n log n 𝜖). This bound is currently the best iteration bound for LO. Finally, some numerical results are reported in order to analyze the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]