Conic Sampling: An Efficient Method for Solving Linear and Quadratic Programming by Randomly Linking Constraints within the Interior
View/ Open
Author
Published Version
https://doi.org/10.1371/journal.pone.0043706Metadata
Show full item recordCitation
Serang, Oliver. 2012. Conic sampling: an efficient method for solving linear and quadratic programming by randomly linking constraints within the interior. PLoS ONE 7(8): e43706.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.Other Sources
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3428371/pdf/Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:10482576
Collections
- HMS Scholarly Articles [17922]
Contact administrator regarding this item (to report mistakes or request changes)