Black-Box Acceleration of Monotone Convex Program Solvers

• 成果类型: Article
• 署名作者: London, Palma; Vardi, Shai; Eghbali, Reza; Wierman, Adam
• 署名单位: California Institute of Technology; Purdue University System; Purdue University; University of California System; University of California Berkeley
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2352
• 发表日期: 2024
• 关键词: approximation algorithms; Column Generation; optimization; EQUATIONS; FRAMEWORK; packing

摘要

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 x n) problem, we construct a smaller (m x epsilon 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 a-approximation, then we produce a (1 - epsilon)/alpha(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.