论文标题
没有自我符合的屏障内部方法是强烈的多项式
No self-concordant barrier interior point method is strongly polynomial
论文作者
论文摘要
确定自我符合障碍的理论是否可以在线性编程中具有强烈多项式复杂性。在对数障碍的特殊情况下，它在[Allamigeon，Benchimol，Gaubert和Joswig，Siam J. on Applied代数和几何学上，2018年]中显示出答案是负面的。在本文中，我们表明，没有一个自我符合的屏障内部方法是强烈多项式的。通过确定，在凸优化问题的参数族中，中央路径的对数限制将脱离到分段线性曲线，而与屏障函数的选择无关。我们提供了一个明确的线性程序，该程序与Klee-Minty反例相同的类别，即尺寸$ n $，带有$ 2N $约束，其中迭代次数为$ω（2^n）$。
It is an open question to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the special case of the logarithmic barrier, it was shown in [Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. on Applied Algebra and Geometry, 2018] that the answer is negative. In this paper, we show that none of the self-concordant barrier interior point methods is strongly polynomial. This result is obtained by establishing that, on parametric families of convex optimization problems, the log-limit of the central path degenerates to a piecewise linear curve, independently of the choice of the barrier function. We provide an explicit linear program that falls in the same class as the Klee-Minty counterexample, i.e., in dimension $n$ with $2n$ constraints, in which the number of iterations is $Ω(2^n)$.
