conic sampling an efficient method for solving linear and quadratic programming by randomly linking constraints within the interior圆锥抽样一个高效的方法求解线性和二次规划通过随机连接的内部约束.pdfVIP

Conic Sampling: An Efficient Method for Solving Linear and Quadratic Programming by Randomly Linking Constraints within the Interior Oliver Serang1,2* 1 Department of Neurobiology, Harvard Medical School, Boston, Massachusetts, United States of America, 2 Department of Pathology, Boston Children’s Hospital, Boston, Massachusetts, United States of America Abstract 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. Citation: Serang O (2012) Conic Sampling: An Efficient Method for Solving Linear and Quadratic Programming by Randomly Linking Constraints within the Interior. PLoS ONE 7(8): e43706. doi:10.1371/journal.pone.0043706 ´ ´ ´ Editor: Jeremie Bourdon, Universite de Nantes, France Received June 12, 2012; Accepted July 25, 2012; Published August 27, 2012 Copyrig