COUNTEREXAMPLE TO A CONJECTURE ON AN INFEASIBLE INTERIOR-POINT METHOD.

In [SIAM J. Optim., 16 (2006), pp. 1110-1136], Roos proved that the devised fullstep infeasible algorithm has O(n) worst-case iteration complexity. This complexity bound depends linearly on a parameter Κ̄(&zata;, which is proved to be less than √2n. Based on extensive computational evidence (hundreds of thousands of randomly generated problems), Roos conjectured that Κ̄(ζ) = 1 (Conjecture 5.1 in the above-mentioned paper), which would yield an O(√n) iteration full-Newton step infeasible interior-point algorithm. In this paper we present an example showing that Κ̄(ζ) is in the order of √n, the same order as that proved in Roos's original paper. In other words, the conjecture is false. [ABSTRACT FROM AUTHOR]