Black-Box Acceleration of Monotone Convex Program Solvers

Palma London (), Shai Vardi (), Reza Eghbali () and Adam Wierman ()
Additional contact information
Palma London: California Institute of Technology, Pasadena, California 91125
Shai Vardi: Purdue University, West Lafayette, Indiana 47907
Reza Eghbali: University of California, Berkeley, California 94720
Adam Wierman: California Institute of Technology, Pasadena, California 91125

Operations Research, 2024, vol. 72, issue 2, 796-815

Abstract: This paper presents a black-box framework for accelerating packing optimization solvers. Our method applies to packing linear programming problems and a family of convex programming problems with linear constraints. The framework is designed for high-dimensional problems, for which the number of variables n is much larger than the number of measurements m . Given an ( m × n ) problem, we construct a smaller ( m × ϵ n ) problem, whose solution we use to find an approximation to the optimal solution. Our framework can accelerate both exact and approximate solvers. If the solver being accelerated produces an α -approximation, then we produce a ( 1 − ϵ ) / α 2 -approximation of the optimal solution to the original problem. We present worst-case guarantees on run time and empirically demonstrate speedups of two orders of magnitude.

Keywords: Optimization; linear programming; convex optimization; dimension reduction (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2352 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:2:p:796-815

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().