论文标题
内点方法并不比单纯形差
Interior point methods are not worse than Simplex
论文作者
论文摘要
我们为解决线性程序开发了新的“子空间分层”内部点方法（IPM）。以标准形式应用于$ n $可变量的线性程序，我们的IPM的迭代复杂性最大为线性程序的\ emph {直线复杂性}（SLC）的$ O（n^{1.5} \ log n）$ factor factor factor上限。该术语是指任何分段线性曲线的最小段数，该线性曲线穿越了中心路径的\ emph {宽邻域}，这是任何IPM的迭代复杂性的下限，沿着沿着分段线性轨迹的迭代复杂性沿着自我符合障碍物引起的路径。特别是，我们的算法将任何此类IPM的迭代次数匹配到相同的因子$ O（n^{1.5} \ log n）$。作为我们的第二个贡献，我们表明，任何线性程序的SLC都由$ 2^{n + o（1）} $限制，这意味着我们的IPM的迭代复杂性最多是指数的。这与现有的迭代复杂性界限相反，该迭代复杂性范围取决于比重复杂性或条件度量；这些可以在问题维度中无限。我们通过表明中心路径被组合代理良好地ximimed来实现上限，我们称为\ emph {max central路径}，该路径由$ 2N $ shadow shadow dertex simplex路径组成。我们的上限补充了Allamigeon，Benchimol，Gaubert和Joswig（Siaga 2018）和Allamigeon，Gaubert和Vandame（STOC 2022）的下限，后者用指数SLC构建了线性程序。最后，我们表明我们的IPM的每次迭代都可以在强烈的多项式时间内实现。在此过程中，我们开发了一种确定性算法，该算法近似于在强度多项式时间内矩阵的奇异值分解至高精度，这可能具有独立的关注。
We develop a new `subspace layered least squares' interior point method (IPM) for solving linear programs. Applied to an $n$-variable linear program in standard form, the iteration complexity of our IPM is up to an $O(n^{1.5} \log n)$ factor upper bounded by the \emph{straight line complexity} (SLC) of the linear program. This term refers to the minimum number of segments of any piecewise linear curve that traverses the \emph{wide neighborhood} of the central path, a lower bound on the iteration complexity of any IPM that follows a piecewise linear trajectory along a path induced by a self-concordant barrier. In particular, our algorithm matches the number of iterations of any such IPM up to the same factor $O(n^{1.5}\log n)$. As our second contribution, we show that the SLC of any linear program is upper bounded by $2^{n + o(1)}$, which implies that our IPM's iteration complexity is at most exponential. This in contrast to existing iteration complexity bounds that depend on either bit-complexity or condition measures; these can be unbounded in the problem dimension. We achieve our upper bound by showing that the central path is well-approximated by a combinatorial proxy we call the \emph{max central path}, which consists of $2n$ shadow vertex simplex paths. Our upper bound complements the lower bounds of Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018), and Allamigeon, Gaubert, and Vandame (STOC 2022), who constructed linear programs with exponential SLC. Finally, we show that each iteration of our IPM can be implemented in strongly polynomial time. Along the way, we develop a deterministic algorithm that approximates the singular value decomposition of a matrix in strongly polynomial time to high accuracy, which may be of independent interest.
