skip to main content
Ngôn ngữ:
Giới hạn tìm kiếm: Giới hạn tìm kiếm: Dạng tài nguyên Hiển thị kết quả với: Hiển thị kết quả với: Chỉ mục

Conic Sampling: An Efficient Method for Solving Linear and Quadratic Programming by Randomly Linking Constraints within the Interior

Serang, Oliver R.

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. [Tạp chí có phản biện]

ISSN: 1932-6203 ; DOI: 10.1371/journal.pone.0043706

Toàn văn sẵn có

Trích dẫn Trích dẫn bởi
  • Nhan đề:
    Conic Sampling: An Efficient Method for Solving Linear and Quadratic Programming by Randomly Linking Constraints within the Interior
  • Tác giả: Serang, Oliver R.
  • Chủ đề: Computer Science ; Algorithms ; Mathematics ; Applied Mathematics ; Mathematical Computing ; Social And Behavioral Sciences ; Economics ; Operations Research ; Mathematical Optimization
  • Là 1 phần của: 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.
  • Mô tả: 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.
  • Ngôn ngữ: English
  • Số nhận dạng: ISSN: 1932-6203 ; DOI: 10.1371/journal.pone.0043706

Đang tìm Cơ sở dữ liệu bên ngoài...