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

C Roos (C.Roosewi.tudelft.nl)

Abstract: 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})$.

Keywords: Linear optimization, infeasible interior-point method,

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

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

Download: [PDF]

Entry Submitted: 06/22/2005
Entry Accepted: 06/22/2005
Entry Last Modified: 06/22/2005

Modify/Update this entry