A Full-Newton Step (n)$ Infeasible Interior-Point Algorithm for Linear Optimization

We present a full-Newton step infeasible interior-point algorithm. It is shown that at most $O(n)$ (inner) iterations suffice to reduce the duality gap and the residuals by the factor $\frac1{e}$. The bound coincides with the best known bound for infeasible interior-point algorithms. It is conjectured that further investigation will improve the above bound to $O(\sqrt{n})$.

Citation

Manuscript. Delft University of Technology. P.O. Box 5031, 2600 GA Delft, The Netherlands. March 2005

Article

Download

View A Full-Newton Step (n)$ Infeasible Interior-Point Algorithm for Linear Optimization