CVXcanon
Introduction
Convex optimization modeling tools like CVX, CVXPY, and Convex.Jl translate highlevel problem descriptions into lowlevel, canonical forms that are then passed to an backend solver. CVXcanon is a software package that factors out the common operations that all such modeling systems perform into a single library with a simple C++ interface. CVXcanon removes the need to reimplement this canonicalization process in new languages and provides significant performance gains over high level language implemententations.
Usage with CVXPY
To install CVXcanon with CVXPY, simply navigate to /src/python
and run python setup.py install
. CVXcanon will now be installed.
If you're using CVXPY, simply set cvxpy.settings.USE_CVXCANON = True
before constructing a CVXPY problem. For example,
import numpy
from cvxpy import *
settings.USE_CVXCANON = True
m = 30
n = 20
numpy.random.seed(1)
A = numpy.random.randn(m, n)
b = numpy.random.randn(m)
x = Variable(n)
objective = Minimize(norm(A*x  b))
Problem(objective).solve()
The use of CVXPY's Parameters is currently disabled in CVXcanon. One can expect a 2  10x speedup over the original CVXPY implementation on most other problems.
Note: CVXcanon is not currently shipped with the default CVXPY, though there are plans to do this in the near future. We currently have a custom fork of CVXPY available at https://github.com/jacklzhu/cvxpy. To test CVXcanon before this happens, clone the repo and run the included setup.py script before installing CVXcanon.
Integration with other CVX.* solvers
To use CVXcanon with the CVX solver of your choice one must take the following steps:
Represent the problem's objective and constraints each as linear atom trees at some point during the solve process. To convert the linOp trees to a matrix representation, first call the wrapper to convert the high level language linOp tree into a C++ LinOp tree. This involves tree traversal, and some special cases depending on the representation of dense and sparse matrices. You may refer to the
build_lin_op_tree
function in canonInterface.py to see an example of how this is done.Pass your vector of C++ LinOps into CVXcanon's build matrix function. This will return a
ProblemData
structure, containing a sparse matrix representation of the problem data. Currently, final problem data is stored in COO representation usingstd::vector
. You should convert this to a data format accessable to the target language. For Python, this unpacking can be done efficiently using CVXcanon's get{V/I/J} functions, which converts the representation to NUMPY arrays. For future languages, some work may be needed to do this efficiently.With these two steps implemented, you have essentially recreated canonInterface.py in the language of your choice. You now should be able to execute code of the form
V, I, J, b = canonInterface.get_problem_matrix(lin_expr_tree, var_offset_map)
where V, I, J
is a COO representation of the problem matrix A
. Matrix V, I, J
and vector b
can then be passed to your solver as needed.
Code Organization

/src/ contains the source code for CVXcanon

CVXcanon.(c/h)pp implements the matrix building algorithm. This file also provides the main access point into CVXcanon's functionality, the
build_matrix
function.  LinOp.hpp defines the LinOp class, linear atoms which we traverse during construction of the matrix.
 LinOpOperations.(c/h)pp defines functions to get coefficients corresponding to each of the LinOps. This includes 18 special cases, one for each LinOp.

ProblemData.hpp defines the structure returned by
build_matrix
, which includes a sparse representation of the problem matrix and the dense constant vector.

CVXcanon.(c/h)pp implements the matrix building algorithm. This file also provides the main access point into CVXcanon's functionality, the

/src/python contains code specific to our integration of CVXcanon with CVXPY.

canonInterface.py implements code which calls our SWIG binding of CVXcanon, including the function
get_problem_matrix
. It also defines a function to create a C++ LinOp tree from a Python LinOp tree, handling a variety of special cases related to data representation. CVXcanon.py the Python binding autmatically generated by SWIG.
CVXcanon.i exposes functions and data types to SWIG, which automatically generate bindings for CVXcanon in a variety of common programming languages.

canonInterface.py implements code which calls our SWIG binding of CVXcanon, including the function
/tests/ contains code to test the accuracy and performance of CVXcanon. test_linops.py tests a variety of problems to ensure that our basic LinOp construction and representation is correct. huge_testman.py benchmarks CVXcanon on a variety of EE364A problems.
Contact
If you have comments or concerns, please do not hesitate to contact one of us at {piq93,jackzhu,millerjp}@stanford.edu.