Content area
Convex programming is a fundamental tool of modern optimization, with applications in areas such as machine learning, combinatorial optimization, and graph theory. Despite their broad utility, general-purpose convex programming solvers such as cutting-plane methods and interior-point methods often struggle to scale efficiently in high-dimensional or large-scale settings. To address these limitations, we develop specialized algorithms that bypass the computational bottlenecks of black-box solvers. Specifically, we give efficient algorithms for solving Ky Fan packing linear programs and for computing approximate Forster transforms — two problems with a plethora of applications — and show that our algorithms significantly improve upon state-of-the-art runtimes based on standard convex optimization techniques.