Downloads provided by UsageCounts
doi: 10.1137/080729505
Summary: In [the second author, SIAM J. Optim. 16, No.~4, 1110--1136 (2006; Zbl 1131.90029)], Roos proved that the devised full-step infeasible algorithm has \(O(n)\) worst-case iteration complexity. This complexity bound depends linearly on a parameter \(\bar{\kappa}(\zeta)\), which is proved to be less than \(\sqrt{2n}\). Based on extensive computational evidence (hundreds of thousands of randomly generated problems), Roos conjectured that \(\bar{\kappa}(\zeta)=1\) (Conjecture 5.1 in [loc. cit.]), 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 proved in [loc. cit.]. In other words, the conjecture is false.
conjecture, Linear programming, Interior-point methods, linear optimization, full-step infeasible interior-point algorithm
conjecture, Linear programming, Interior-point methods, linear optimization, full-step infeasible interior-point algorithm
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
| views | 10 | |
| downloads | 15 |

Views provided by UsageCounts
Downloads provided by UsageCounts