A lowlevel library to perform the matrix building step in cvxpy, a convex optimization modeling software.
Project description
[![Build Status](https://travisci.org/cvxgrp/CVXcanon.svg?branch=master)](https://travisci.org/cvxgrp/CVXcanon)
# 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
If you're using CVXPY update to it 0.3.0 or higher.
One can expect a 3  10x speedup over the original CVXPY implementation on most other problems.
## Installation
CVXcanon supports both Python 2 and Python 3.
1. Install ``numpy`` with ``pip`` from the commandline.
```
pip install numpy
```
2. Install ``CVXcanon`` with ``pip`` from the commandline.
```
pip install CVXcanon
```
Note: If you're installing CVXcanon on Windows, a nonstandard system, or wish to build CVXcanon directly from source, you need to install ```swig.``` We are currently working to remove this dependency.
On Linux,
```
sudo aptget install swig
```
On Mac OSX, using homebrew,
```
brew install swig
```
## Integration with other CVX.* solvers
To use CVXcanon with the CVX solver of your choice one must take the following steps:
1. 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.
2. 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 using ```std::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.
3. 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
```python
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.
 **/CVXCannon** 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.
 **/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.
# 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
If you're using CVXPY update to it 0.3.0 or higher.
One can expect a 3  10x speedup over the original CVXPY implementation on most other problems.
## Installation
CVXcanon supports both Python 2 and Python 3.
1. Install ``numpy`` with ``pip`` from the commandline.
```
pip install numpy
```
2. Install ``CVXcanon`` with ``pip`` from the commandline.
```
pip install CVXcanon
```
Note: If you're installing CVXcanon on Windows, a nonstandard system, or wish to build CVXcanon directly from source, you need to install ```swig.``` We are currently working to remove this dependency.
On Linux,
```
sudo aptget install swig
```
On Mac OSX, using homebrew,
```
brew install swig
```
## Integration with other CVX.* solvers
To use CVXcanon with the CVX solver of your choice one must take the following steps:
1. 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.
2. 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 using ```std::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.
3. 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
```python
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.
 **/CVXCannon** 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.
 **/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.
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size CVXcanon0.0.21cp27nonemacosx_10_10_intel.whl (740.9 kB)  File type Wheel  Python version 2.7  Upload date  Hashes View 
Filename, size CVXcanon0.0.21cp33cp33mmacosx_10_6_x86_64.whl (831.0 kB)  File type Wheel  Python version 3.3  Upload date  Hashes View 
Filename, size CVXcanon0.0.21.tar.gz (689.5 kB)  File type Source  Python version None  Upload date  Hashes View 
Close
Hashes for CVXcanon0.0.21cp27nonemacosx_10_10_intel.whl
Algorithm  Hash digest  

SHA256  f009686673f7134a137d954dcc1d0172cf9d8382b37a05ea9b89d38f8d8fae6d 

MD5  1660b3ef1268c300374955d5b37b009c 

BLAKE2256  a547fcc3c206854b26a70b99cacf29edf23b3c3e58b0703ebce2751d30efa8da 
Close
Hashes for CVXcanon0.0.21cp33cp33mmacosx_10_6_x86_64.whl
Algorithm  Hash digest  

SHA256  ad9fe71456b617b2d68f5351bc02caeeffe9b4f306127edaac3bddd781cbdad3 

MD5  4cafde544a1b661903485edd35f10d47 

BLAKE2256  4a36d5a4ae2276b1b74549cd01bcef1839ace6b36d14ceab00527e3163c1c479 