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.19cp27nonemacosx_10_10_intel.whl (739.2 kB)  File type Wheel  Python version 2.7  Upload date  Hashes View 
Filename, size CVXcanon0.0.19cp33cp33mmacosx_10_6_x86_64.whl (831.0 kB)  File type Wheel  Python version 3.3  Upload date  Hashes View 
Filename, size CVXcanon0.0.19.tar.gz (619.8 kB)  File type Source  Python version None  Upload date  Hashes View 
Close
Hashes for CVXcanon0.0.19cp27nonemacosx_10_10_intel.whl
Algorithm  Hash digest  

SHA256  e85e52885004b4d3f2a3085d010ddeadc315e79504d5366b87226310d8df9ceb 

MD5  b170c918477e05cbba50286f98db8452 

BLAKE2256  3f99483e0cfe757603e5a8c1f3d6f47b7e72749a04d816bcbde3d1fcbb652ad8 
Close
Hashes for CVXcanon0.0.19cp33cp33mmacosx_10_6_x86_64.whl
Algorithm  Hash digest  

SHA256  f94553089871bf0a87e665535bb03f1e075ffe5ee604c333e1e14924814df181 

MD5  f8bf3e85327e1f7cf8cfca41260069e0 

BLAKE2256  c93105b9e3ee5b81bb110fbc7594b5cb5116fab3ae342916f82ad382f738addf 