Solving Linear Programs with Õ ( √ rank ) Linear System Solves
Solving Linear Programs with Õ ( √ rank ) Linear System Solves
复制标题
使用 Õ ( √ 秩 ) 线性系统求解线性规划
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Y. Lee
中科院分区：
文献类型：
--
作者：
Y. Lee
我们提出一种算法，对于具有\(n\)个变量、\(m\)个约束以及约束矩阵\(A\)的线性规划问题，该算法能以高概率在\(\tilde{O}(\sqrt{\text{rank}(A)}\log(1 / \epsilon))\)次迭代中计算出一个\(\epsilon\)-近似解。我们方法的每次迭代包括求解\(\tilde{O}(1)\)个线性系统以及额外的近线性时间计算，相较于Renegar（1988）[51]提出的具有此迭代成本的先前最快方法，速度提高了\(\tilde{\Omega}((m / \text{rank}(A)))\)倍。此外，我们为多面体提供了一个确定性的多项式时间可计算的\(\tilde{O}(\text{rank}(A))\)-自和谐障碍函数，解决了Nesterov和Nemirovski（1994）[47]关于内点法“通用障碍”理论的一个开放性问题。将我们的技术应用于最大流的线性规划公式，得到了一个\(\tilde{O}(|E|\sqrt{|V|}\log(U))\)时间的算法，用于解决具有\(|E|\)条边、\(|V|\)个顶点且整数容量最大为\(U\)的有向图的最大流问题。这比Goldberg和Rao（1998）[18]所达到的先前最快的多项式运行时间\(O(|E|\min\{|E|, |V|\}\log(|V| / |E|)\log(U))\)有所改进。在解决稠密有向单位容量图的特殊情况下，我们的算法比Even和Tarjan（1975）[16]以及Karzanov（1973）[22]所达到的先前最快运行时间\(O(|E|\min\{|E|, |V|\})\)以及Mądry（2013）[39]最近达到的\(\tilde{O}(|E|)\)都有所改进。本文是论文“线性规划的路径寻找方法：在\(\tilde{O}(\sqrt{\text{rank}})\)次迭代中求解线性规划以及最大流的更快算法”[34]以及arXiv投稿[32, 33]的期刊版本。本文包含了这些先前投稿之外的几个新结果。本文首次证明了对于所有多面体\(\{x\in\mathbb{R}:Ax\geq b\}\)（其中\(r = \text{rank}(A)\)）存在一个\(\tilde{O}(r)\)-自和谐障碍，且该障碍是多项式时间可计算的（与[47]中通用障碍的伪多项式时间可计算性相对）。此外，本文提供了一个概念上比我们先前工作更简单的权重函数，并通过在算法、障碍和\(\ell_p\)刘易斯权重[37, 9, 8]之间建立新的联系进行了统一分析。[34, 32, 33]的几个部分未包含在本期刊版本中。利用本文精确求解线性规划的技术推迟到[32]，分析近似线性系统求解所引入误差的技术推迟到[33]。这些技术相当标准和通用，为简洁起见本文省略。此外，[32]中降低线性系统成本的技术也未包含，并且在一系列近期工作[35, 8, 2]中得到了改进，解决广义最小费用流（与本文所考虑的更受限的最小费用流问题相对）的技术推迟到[33]。arXiv:1910.08033v1 [cs.DS] 2019年10月17日
We present an algorithm that given a linear program with n variables, m constraints, and constraint matrix A, computes an -approximate solution in Õ( √ rank(A) log(1/ )) iterations with high probability. Each iteration of our method consists of solving Õ(1) linear systems and additional nearly linear time computation, improving by a factor of Ω̃((m/ rank(A))) over the previous fastest method with this iteration cost due to Renegar (1988) [51].1 Further, we provide a deterministic polynomial time computable Õ(rank(A))-self-concordant barrier function for the polytope, resolving an open question of Nesterov and Nemirovski (1994) [47] on the theory of “universal barriers” for interior point methods. Applying our techniques to the linear program formulation of maximum flow yields an Õ(|E| √ |V | log(U)) time algorithm for solving the maximum flow problem on directed graphs with |E| edges, |V | vertices, and integer capacities of size at most U . This improves upon the previous fastest polynomial running time of O(|E|min{|E|, |V |} log(|V |/|E|) log(U)) achieved by Goldberg and Rao (1998) [18]. In the special case of solving dense directed unit capacity graphs our algorithm improves upon the previous fastest running times ofO(|E|min{|E|, |V |}) achieved by Even and Tarjan (1975) [16] and Karzanov (1973) [22] and of Õ(|E|) achieved more recently by Mądry (2013) [39]. This paper is a journal version of the paper, “Path-Finding Methods for Linear Programming : Solving Linear Programs in Õ( √ rank) Iterations and Faster Algorithms for Maximum Flow” [34] and arXiv submissions [32, 33]. This paper contains several new results beyond these prior submissions. This paper provides the first proof of a Õ(r)-self-concordant barrier for all polytopes {x ∈ R : Ax ≥ b} with r = rank(A) that is polynomial time computable (as opposed to the pseudo-polynomial time computability of the universal barrier of [47]). Further, this paper provides a conceptually simpler weight function than that in our prior works and a unified analysis by establishing new connections between the algorithm, the barrier, and `p Lewis weights [37, 9, 8]. Several components of [34, 32, 33] were not included in this journal version. Techniques, for leveraging this paper to solve linear programs exactly are deferred to [32] and techniques for analyzing the error induced by approximate linear system solves are deferred to [33]. These techniques are fairly standard and general and omitted from this paper for brevity. Further, techniques for reducing the cost of the linear systems found in [32] are also not included and have been improved in a sequence of recent work [35, 8, 2] and techniques solving generalized minimum cost flow as opposed to more restricted minimum cost flow problem considered in this paper are deferred to [33]. ar X iv :1 91 0. 08 03 3v 1 [ cs .D S] 1 7 O ct 2 01 9