Department of Neurobiology, Harvard Medical School, Boston, Massachusetts, United States of America.
PLoS One. 2012;7(8):e43706. doi: 10.1371/journal.pone.0043706. Epub 2012 Aug 27.
Linear programming (LP) problems are commonly used in analysis and resource allocation, frequently surfacing as approximations to more difficult problems. Existing approaches to LP have been dominated by a small group of methods, and randomized algorithms have not enjoyed popularity in practice. This paper introduces a novel randomized method of solving LP problems by moving along the facets and within the interior of the polytope along rays randomly sampled from the polyhedral cones defined by the bounding constraints. This conic sampling method is then applied to randomly sampled LPs, and its runtime performance is shown to compare favorably to the simplex and primal affine-scaling algorithms, especially on polytopes with certain characteristics. The conic sampling method is then adapted and applied to solve a certain quadratic program, which compute a projection onto a polytope; the proposed method is shown to outperform the proprietary software Mathematica on large, sparse QP problems constructed from mass spectometry-based proteomics.
线性规划 (LP) 问题在分析和资源分配中被广泛应用，通常作为更困难问题的近似方法出现。现有的 LP 方法主要由一小部分方法主导，随机算法在实践中并没有得到广泛应用。本文提出了一种新的随机方法，通过沿着多面体的棱和面以及在由边界约束定义的多面锥体内沿着从多面锥抽样的射线移动来解决 LP 问题。然后将这种共形抽样方法应用于随机抽样的 LP，并显示其运行时性能优于单纯形和原始仿射缩放算法，特别是在具有某些特征的多面体上。然后，对共形抽样方法进行了修改并应用于解决二次规划问题，该问题计算多面体上的投影；所提出的方法在基于质谱的蛋白质组学构建的大型稀疏 QP 问题上优于专有的 Mathematica 软件。
