Show simple item record

dc.contributor.authorSerang, Oliver R.
dc.date.accessioned2013-03-29T20:02:34Z
dc.date.issued2012
dc.identifier.citationSerang, 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.en_US
dc.identifier.issn1932-6203en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:10482576
dc.description.abstractLinear 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.en_US
dc.language.isoen_USen_US
dc.publisherPublic Library of Scienceen_US
dc.relation.isversionofdoi:10.1371/journal.pone.0043706en_US
dc.relation.hasversionhttp://www.ncbi.nlm.nih.gov/pmc/articles/PMC3428371/pdf/en_US
dash.licenseLAA
dc.subjectComputer Scienceen_US
dc.subjectAlgorithmsen_US
dc.subjectMathematicsen_US
dc.subjectApplied Mathematicsen_US
dc.subjectMathematical Computingen_US
dc.subjectSocial and Behavioral Sciencesen_US
dc.subjectEconomicsen_US
dc.subjectOperations Researchen_US
dc.subjectMathematical Optimizationen_US
dc.titleConic Sampling: An Efficient Method for Solving Linear and Quadratic Programming by Randomly Linking Constraints within the Interioren_US
dc.typeJournal Articleen_US
dc.description.versionVersion of Recorden_US
dc.relation.journalPLoS ONEen_US
dash.depositing.authorSerang, Oliver R.
dc.date.available2013-03-29T20:02:34Z
dc.identifier.doi10.1371/journal.pone.0043706*
dash.contributor.affiliatedSerang, Oliver R.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record