论文标题
单纯形方法平滑复杂性的上限和下限
Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
论文作者
论文摘要
线性编程的单纯形方法在实践中非常有效，从理论角度了解其表现是一个积极的研究主题。为此目的，Spielman和Teng（JACM '04）首先引入的平滑分析框架定义了求解具有$ d $变量的线性程序的平滑复杂性，而$ n $约束则是预期的运行时间，当时高斯差异$σ^2^2^2^2^2 $添加到LP数据中。我们证明，单纯形方法的平滑复杂性为$ O（σ^{ - 3/2} d^{13/4} \ log^{7/4} n）$，提高了对$ 1/σ$的依赖性，而先前的限制$ o（σ^{-2} d^{-2} d^2^2^2 \ sqrt log n}）$。我们通过对\ emph {shadow绑定}的新分析来实现这一目标，这也是早期分析的关键。说明了我们的新方法的功能，我们使用我们的方法证明了几乎紧密的上部结合了二维多边形的平滑复杂性。 我们还建立了单纯形方法平滑复杂性的第一个非平凡的下限，证明\ emph {shadow certex sissyx方法}需要至少$ω\ big（\ min \ big \ big（σ^{ - 1/2} d { - 1/2} d^{ - 1/2} { - 1/2}} \ log^\ log^^{ - 1/4} d，$ piv big）我们分析的关键部分是针对常规$ 2^k $ -gon的扩展配方的新变体。我们以一个数值实验结尾，表明该分析可以进一步改善。
The simplex method for linear programming is known to be highly efficient in practice, and understanding its performance from a theoretical perspective is an active research topic. The framework of smoothed analysis, first introduced by Spielman and Teng (JACM '04) for this purpose, defines the smoothed complexity of solving a linear program with $d$ variables and $n$ constraints as the expected running time when Gaussian noise of variance $σ^2$ is added to the LP data. We prove that the smoothed complexity of the simplex method is $O(σ^{-3/2} d^{13/4}\log^{7/4} n)$, improving the dependence on $1/σ$ compared to the previous bound of $O(σ^{-2} d^2\sqrt{\log n})$. We accomplish this through a new analysis of the \emph{shadow bound}, key to earlier analyses as well. Illustrating the power of our new method, we use our method to prove a nearly tight upper bound on the smoothed complexity of two-dimensional polygons. We also establish the first non-trivial lower bound on the smoothed complexity of the simplex method, proving that the \emph{shadow vertex simplex method} requires at least $Ω\Big(\min \big(σ^{-1/2} d^{-1/2}\log^{-1/4} d,2^d \big) \Big)$ pivot steps with high probability. A key part of our analysis is a new variation on the extended formulation for the regular $2^k$-gon. We end with a numerical experiment that suggests this analysis could be further improved.
