A Rewriting System for Convex Optimization Problems

By Akshay Agrawal, Robin Verschueren, Steven Diamond, Stephen P. Boyd. Journal of Control and Decision, 2017

838 citations recorded by the source corpus.

We describe a modular rewriting system for translating optimization problems written in a domain-specific language 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 domain-specific language 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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/a6a1fb4df010e8dde0a90f8b0f0e958ba4ef9624

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Beyond the Return: Off-policy Function Estimation under User-specified Error-measuring Distributions (2022, methodology): “Solver We solve the linear system using CVXPY with optimizer SCS [DB16; AVDB18].”
Learning Binary Trees via Sparse Relaxation (2020, methodology): “We compare its solving time with the time needed by the popular convex optimization framework Cvxpy (Diamond & Boyd, 2016; Agrawal et al., 2018) to solve Problem 3 with OSQP solver (Stellato et al., 2020) 4 .”
Differentiable Convex Optimization Layers (2019, methodology): “…targets convex cone programs, implementing a function s : DCP-based DSLs for convex optimization can canonicalize disciplined convex programs to equivalent cone programs, producing the problem data A, b , c , and K [3]; ( A, b, c ) depend on the parameter θ and the canonicalization procedure.”
Implicit Regularization in Deep Matrix Factorization (2019, methodology): “Our implementation is based on Python, with PyTorch ([40]) for realizing deep matrix factorizations and CVXPY ([13, 2]) for ﬁnding minimum nuclear norm solutions.”