Counter Example to A Conjecture on Infeasible Interior-Point Methods

Based on extensive computational evidence (hundreds of thousands of randomly generated problems) the second author conjectured that $\bar{\kappa}(\zeta)=1$, which is a factor of $\sqrt{2n}$ better than that has been proved, and which would yield an $O(\sqrt{n})$ iteration full-Newton step infeasible interior-point algorithm. In this paper we present an example showing that $\bar{\kappa}(\zeta)$ is in the order of $\sqrt{n}$, the same order as that has been proved. In other words, the current best iteration bound for infeasible interior-point algorithms cannot be improved.

Citation

July/2008

Article

Download

View Counter Example to A Conjecture on Infeasible Interior-Point Methods