A rewriting system for convex optimization problems

Abstract

We describe a modular rewriting system for translating optimization problems written in a domain-specific language (DSL) to forms compatible with low-level solver interfaces. Translation is facilitated by reductions, which accept a category of problems and transform instances of that category to equivalent instances of another category. Our system proceeds in two key phases: analysis, in which we attempt to find a suitable solver for a supplied problem, and canonicalization, in which we rewrite the problem in the selected solver’s standard form. We implement the described system in version 1.0 of CVXPY, a DSL for mathematical and especially convex optimization. By treating reductions as first-class objects, our method makes it easy to match problems to solvers well-suited for them and to support solvers with a wide variety of standard forms.

Keywords:

• Convex optimization
• domain-specific languages
• rewriting systems
• reductions

Acknowledgements

We extend many thanks to Enzo Busseti, for significant contributions to the quadratic programme canonicalization procedure, and Yifan Lu, for fruitful conversations about the analogy between our rewriting system and software compilers.

Notes

No potential conflict of interest was reported by the authors.