cvxgrp / cvxcanon Goto Github PK

View Code? Open in Web Editor NEW

42.0 42.0 25.0 8.22 MB

License: Apache License 2.0

C++ 94.25% CMake 0.17% C 2.42% Python 2.76% Jupyter Notebook 0.34% Shell 0.01% SWIG 0.05%

cvxcanon's People

Contributors

Stargazers

Watchers

cvxcanon's Issues

Segmentation fault after adding linear constraint in cvxpy

Hey,

I encountered a segfault after adding a specific type of linear constraint in cvxpy. While the backtrace (see here) points to one of Eigen's template methods, I figured it was most likely an issue in CVXcanon/cvxopt/cvxpy given the maturity of Eigen. Of course, that's just a guess and the issue could be caused elsewhere. Always hard to tell when it comes to segfaults.

A minimal working example can be found here. Here's what python/cvx* versions I'm using:

[numberwang ⚡ ~] » python -V
Python 3.5.1
[numberwang ⚡ ~] » pip list | grep -i cvx
CVXcanon (0.0.23.4)
cvxopt (1.1.8)
cvxpy (0.4.0)

Some background on the problem: I'm trying to solve the basis pursuit problem on complex data with the additional constraint that the solution by conjugate symmetric so that its inverse Fourier transform be real-valued.

Regards

Easy way to get the matrix representation of a linear function

There should be a simple function that returns the matrix representation of a linear function, i.e., the matrix representing an index operation or negation or vstack, etc. The argument could be a LinOp tree or just a LinOp type with additional info. The function should return a V, I, J tuple.

When a linear function takes multiple argument, I want to get the matrix representation of the action on each argument separately. So vstack(x,y,z) should return 3 matrices/tuples.

I need this functionality to compute gradients in CVXPY. Here is my current stand in code. The function we add to CVXcanon should return more or less the same thing.

        # TODO should be a simple function in CVXcanon for this.
        # Make a fake lin op tree for the function.
        fake_args = []
        var_offsets = {}
        offset = 0
        for idx, arg in enumerate(self.args):
            fake_args += [lu.create_var(arg.size, idx)]
            var_offsets[idx] = offset
            offset += arg.size[0]*arg.size[1]
        fake_expr, _ = self.graph_implementation(fake_args, self.size,
                                              self.get_data())
        # Get the matrix representation of the function.
        V, I, J, _ = canonInterface.get_problem_matrix(
            [lu.create_eq(fake_expr)],
            var_offsets,
            None
        )
        shape = (offset, self.size[0]*self.size[1])
        stacked_grad = sp.coo_matrix((V, (J, I)), shape=shape).tocsc()
        # Break up into per argument matrices.
        grad_list = []
        start = 0
        for idx, arg in enumerate(self.args):
            stop = start + arg.size[0]*arg.size[1]
            grad_list += [stacked_grad[start:stop,:]]
            start = stop
        return grad_list

swig dependency

Before this makes it into the cvxpy on pip, I'd like to simplify the swig dependency. The easiest approach is to compile CVXstoch for different platforms and put the distributions on pypi. That way people will only need swig if they're installing on non-standard platforms.

how to install CVXcanon on windows?

...

uninstalled VCForPython27.msi
installed VCForPython27.msi

then

pip install "setuptools>=6.0"
pip install CVXcanon

results in

    ....
  creating build\temp.win-amd64-2.7\Release\src\python
  cl.exe /c /nologo /Ox /MD /W3 /GS- /DNDEBUG -Isrc/ -Isrc/python/ -Iinclude/Eigen -IC:\Anaconda\lib\site-packages\numpy
\core\include -IC:\Anaconda\include -IC:\Anaconda\PC /Tpsrc/CVXcanon.cpp /Fobuild\temp.win-amd64-2.7\Release\src/CVXcano
n.obj
  error: command 'cl.exe' failed: No such file or directory

Please also see cvxopt/cvxopt#67 and pystruct/pystruct#190

Thanks

build failure on os x with g++ 7.2 and case preserving filesystem

CVXcanon doesn't build from the pip package on OS X using g++ 7.2 (from homebrew) in the case where the filesystem is configured to be case preserving rather than case sensitive.

The problem is that the compiler confuses Eigen/Array for the array header in the STL, leading to errors:

  /usr/local/bin/gcc-7 -Wno-unused-result -Wsign-compare -Wunreachable-code -fno-common -dynamic -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -Isrc/ -Isrc/python/ -Iinclude/Eigen -I/usr/local/lib/python3.6/site-packages/numpy/core/include -I/usr/local/include -I/usr/local/opt/openssl/include -I/usr/local/opt/sqlite/include -I/usr/local/Cellar/python3/3.6.3/Frameworks/Python.framework/Versions/3.6/include/python3.6m -c src/CVXcanon.cpp -o build/temp.macosx-10.13-x86_64-3.6/src/CVXcanon.o
  cc1plus: warning: command line option '-Wstrict-prototypes' is valid for C/ObjC but not for C++
  In file included from /usr/local/Cellar/gcc/7.2.0/include/c++/7.2.0/tuple:39:0,
                   from /usr/local/Cellar/gcc/7.2.0/include/c++/7.2.0/functional:54,
                   from src/../include/Eigen/Core:153,
                   from src/../include/Eigen/SparseCore:4,
                   from src/../include/Eigen/Sparse:19,
                   from src/Utils.hpp:18,
                   from src/LinOp.hpp:22,
                   from src/CVXcanon.hpp:20,
                   from src/CVXcanon.cpp:16:
  include/Eigen/array:8:4: error: #error The Eigen/Array header does no longer exist in Eigen3. All that functionality has moved to Eigen/Core.
     #error The Eigen/Array header does no longer exist in Eigen3. All that functionality has moved to Eigen/Core.
      ^~~~~

It looks to me like the Eigen/Array header is not used at all in the project - if you remove this header then the build proceeds without error.

Can you please delete the Array header and repackage the library on pip?

Does CVXcanon support c++?

I will use CVXcanon in c++, which will be deployed in SoC. Does it support it? Otherwise, which CVX support it? Thank you very much.

ImportError: No module named '_version__' under CVXcanon 0.0.23.1.

Using 64-bit Python 3.4.3 on Windows 10, I get ImportError: No module named '_version__' when importing CVXcanon 0.0.23.1. I didn't have this problem with 0.0.23.

C:\Python34>pip3.4 install cvxcanon
Collecting cvxcanon
  Using cached CVXcanon-0.0.23.1.tar.gz
Requirement already satisfied (use --upgrade to upgrade): numpy in c:\python34\lib\site-packages (from cvxcanon)
Requirement already satisfied (use --upgrade to upgrade): scipy in c:\python34\lib\site-packages (from cvxcanon)
Installing collected packages: cvxcanon
  Running setup.py install for cvxcanon
Successfully installed cvxcanon-0.0.23.1

C:\Python34>ipython
Python 3.4.3 (v3.4.3:9b73f1c3e601, Feb 24 2015, 22:44:40) [MSC v.1600 64 bit (AMD64)]
Type "copyright", "credits" or "license" for more information.

IPython 4.0.0 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]: import CVXcanon
---------------------------------------------------------------------------
ImportError                               Traceback (most recent call last)
<ipython-input-1-4f15d2aaacbb> in <module>()
----> 1 import CVXcanon

C:\Python34\lib\site-packages\CVXcanon.py in <module>()
      5 # the SWIG interface file instead.
      6
----> 7 from _version__ import __version__
      8
      9

ImportError: No module named '_version__'

Make version number accessible

Could you add a CVXcanon.__version__ field (or cvxcanon.__version__), so that people can check what version of CVXcanon they have in Python?

Circular dependency

From __init__.py:

from cvxpy.lin_ops.lin_op import *

If the intention of this library is to offer "cvx-independent" capability, then it needs to be possible to build and test it without cvxpy. If the module depends critically on cvxpy functionality, then that functionality either needs to be moved to CVXcanon, or this module should just be included within cvxpy itself until such time as the separation makes more sense.

version 0.0.22 is missing from github

Please tag and push the versions to allow notifications/tracking.

Transfer this repo to cvxgrp

Could we transfer this repo to cvxgrp? That's where we have all the projects related to cvxpy, convex.jl, etc. I've invited all of you to join the group.

It's ok if you prefer not to transfer it, but it's easier to have a cvxpy dependency like this in the group.

Here's info about transferring a repo:
https://help.github.com/articles/transferring-a-repository/

Interesting matrix-free optimization

Someone suggested an interesting optimization to CVXcanon. Right now CVXcanon takes an expression tree where each parent node represents a linear function and converts it to a map of variable to matrix coefficient (then to a single matrix). The algorithm essentially replaces each parent node with an explicit sparse matrix and then collapses the tree by multiplying out the matrices.

But there's no need to form the matrices at each parent node. You can just have the parent node evaluate it's function on the input coefficients. For example, if a node's function is to extract index i, it would extract row i of each of its input coefficient matrices. Does this make sense? It's not super clear how much better this would be, but at least you would avoid forming a lot of matrices.

tests fail

Does travis run any of the CVXcanon tests? I tried running python tests/python/test_linops.py and I got a segfault on test_index.

Clarify license and copyright

I wonder if you could clarify the copyright and license for CVXcanon. It would be great if you could put a copyright notice somewhere (does the copyright belong to Stanford? To the three authors?) and a copy of GPLv3 into the root directory.

I'd like to use newer versions of CVXPY in Google, but I can't until this is done. Thank you very much!

Make division work with vectors

Could you modify the division operator so it works with vectors and matrices, i.e., elementwise division?

Need new Windows conda package

We need a conda package on Windows for CVXcanon 0.23.4. Right now there's one for 0.23.3, but 0.23.4 has a small bug fix for an issue in the cvxpy tests:
https://ci.appveyor.com/project/StevenDiamond/cvxpy

Installation of cvxcanon

Hi,

I have some problems with installing the package
I try to install via pip directly from your git rep (you may want to create releases here, e.g. tags)

In my requirements.txt I use
git+https://github.com/cvxgrp/CVXcanon.git#egg=cvxcanon

The error message I get refers to an egg problem:

Could not find .egg-info directory in install record for cvxcanon from git+http://github.com/cvxgrp/CVXcanon.git#egg=cvxcanon

I am running Ubuntu 64bit.
Any hints are very appreciated. This is a part of the bigger attempt to install cvxpy.

Thanks

thomas

Cut a new pip release

The current version that's on PyPI is missing the fix in this merged PR #27

Constraint offsets

Could you add an optional field constr_offsets to canonInterface.get_problem_matrix that takes a list of constraint offsets? In other words, if the argument to constr_offsets is [3,5,7] then constraint 0 starts at row 3, constraint 1 starts at row 5, and constraint 2 starts at row 7.

You might want to check that the offsets make sense, but it's also ok if you don't and just throw an error at some point. Another option would be for constr_offsets to expect a map of constraint id to offset. Either way is fine with me. The default behavior should be to assume all the constraints are stacked with no gaps, as in the current implementation.

This feature will make it much easier to handle parameters.

Tests you might find useful

Here are the tests for matrix stuffing from cvxpy. I'm removing them as part of switching to CVXcanon, but you might find them useful.

    def test_get_coefficients(self):
        """Test the get_coefficients function.
        """
        size = (5, 4)
        # Eye
        x = create_var(size)
        coeffs = get_coefficients(x)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(id_, x.data)
        self.assertItemsAlmostEqual(mat.todense(), sp.eye(20).todense())
        # Eye with scalar mult.
        x = create_var(size)
        A = create_const(5, (1, 1))
        coeffs = get_coefficients(mul_expr(A, x, size))
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertItemsAlmostEqual(mat.todense(), 5*sp.eye(20).todense())
        # Promoted
        x = create_var((1, 1))
        coeffs = get_coefficients(promote(x, size))
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (20, 1))
        self.assertItemsAlmostEqual(mat, np.ones((20, 1)))
        # Normal
        size = (5, 5)
        x = create_var((5, 1))
        A = create_const(np.ones(size), size)
        coeffs = get_coefficients(mul_expr(A, x, (5, 1)))
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (5, 5))
        self.assertItemsAlmostEqual(mat.todense(), A.data)
        # Blocks
        size = (5, 5)
        x = create_var(size)
        A = create_const(np.ones(size), size)
        coeffs = get_coefficients(mul_expr(A, x, size))
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (25, 25))
        self.assertItemsAlmostEqual(mat.todense(),
         sp.block_diag(5*[np.ones(size)]).todense())
        # Scalar constant
        size = (1, 1)
        A = create_const(5, size)
        coeffs = get_coefficients(A)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(intf.size(mat), (1, 1))
        self.assertEqual(mat, 5)
        # Dense constant
        size = (5, 4)
        A = create_const(np.ones(size), size)
        coeffs = get_coefficients(A)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (size[0]*size[1], 1))
        self.assertItemsAlmostEqual(mat, np.ones(size))
        # Sparse constant
        size = (5, 5)
        A = create_const(sp.eye(5), size)
        coeffs = get_coefficients(A)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (size[0]*size[1], 1))
        self.assertItemsAlmostEqual(mat, sp.eye(5).todense())
        # Parameter
        size = (5, 4)
        param = Parameter(*size)
        param.value = np.ones(size)
        A = create_param(param, size)
        coeffs = get_coefficients(A)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (size[0]*size[1], 1))
        self.assertItemsAlmostEqual(mat, param.value)

    def test_transpose(self):
        """Test transpose op and coefficients.
        """
        size = (5, 4)
        x = create_var(size)
        expr = transpose(x)
        self.assertEqual(expr.size, (4, 5))
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        test_mat = np.mat(range(20)).T
        self.assertItemsAlmostEqual((mat*test_mat).reshape((4, 5), order='F'),
            test_mat.reshape(size, order='F').T)

    def test_index(self):
        """Test the get_coefficients function for index.
        """
        size = (5, 4)
        # Eye
        key = (slice(0,2,None), slice(0,2,None))
        x = create_var(size)
        expr = index(x, (2, 2), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(id_, x.data)
        self.assertEqual(mat.shape, (4, 20))
        test_mat = np.mat(range(20)).T
        self.assertItemsAlmostEqual((mat*test_mat).reshape((2, 2), order='F'),
            test_mat.reshape(size, order='F')[key])
        # Eye with scalar mult.
        key = (slice(0,2,None), slice(0,2,None))
        x = create_var(size)
        A = create_const(5, (1, 1))
        expr = mul_expr(A, x, size)
        expr = index(expr, (2, 2), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        test_mat = np.mat(range(20)).T
        self.assertItemsAlmostEqual((mat*test_mat).reshape((2, 2), order='F'),
            5*test_mat.reshape(size, order='F')[key])
        # Promoted
        key = (slice(0,2,None), slice(0,2,None))
        x = create_var((1, 1))
        value = np.array(range(20)).reshape(size)
        A = create_const(value, size)
        prom_x = promote(x, (size[1], 1))
        expr = mul_expr(A, diag_vec(prom_x), size)
        expr = index(expr, (2, 2), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (4, 1))
        self.assertItemsAlmostEqual(mat, value[key])
        # Normal
        size = (5, 5)
        key = (slice(0,2,None), slice(0,1,None))
        x = create_var((5, 1))
        A = create_const(np.ones(size), size)
        expr = mul_expr(A, x, (5, 1))
        expr = index(expr, (2, 1), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (2, 5))
        self.assertItemsAlmostEqual(mat.todense(), A.data[slice(0,2,None)])
        # Blocks
        size = (5, 5)
        key = (slice(0,2,None), slice(0,2,None))
        x = create_var(size)
        value = np.array(range(25)).reshape(size)
        A = create_const(value, size)
        expr = mul_expr(A, x, size)
        expr = index(expr, (2, 2), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (4, 25))
        test_mat = np.mat(range(25)).T
        self.assertItemsAlmostEqual((mat*test_mat).reshape((2, 2), order='F'),
            (A.data*test_mat.reshape(size, order='F'))[key])
        # Scalar constant
        size = (1, 1)
        A = create_const(5, size)
        key = (slice(0,1,None), slice(0,1,None))
        expr = index(A, (1, 1), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(intf.size(mat), (1, 1))
        self.assertEqual(mat, 5)
        # Dense constant
        size = (5, 4)
        key = (slice(0,2,None), slice(0,1,None))
        value = np.array(range(20)).reshape(size)
        A = create_const(value, size)
        expr = index(A, (2, 1), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (2, 1))
        self.assertItemsAlmostEqual(mat, value[key])
        # Sparse constant
        size = (5, 5)
        key = (slice(0,2,None), slice(0,1,None))
        A = create_const(sp.eye(5), size)
        expr = index(A, (2, 1), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (2, 1))
        self.assertItemsAlmostEqual(mat, sp.eye(5).todense()[key])
        # Parameter
        size = (5, 4)
        key = (slice(0,2,None), slice(0,1,None))
        param = Parameter(*size)
        value = np.array(range(20)).reshape(size)
        param.value = value
        A = create_param(param, size)
        expr = index(A, (2, 1), key)
        coeffs = get_coefficients(expr)
        assert len(coeffs) == 1
        id_, mat = coeffs[0]
        self.assertEqual(mat.shape, (2, 1))
        self.assertItemsAlmostEqual(mat, param.value[key])

Sum coefficients for the same variable

Instead of keeping a vector of matrices for each variable id, you should sum them all and keep a single matrix. Someone recently posted on the CVXPY google group about canonicalization using a ton of memory. This should help with that.

pip install fails

pip install isn't working for me.

(develop)➜  dev_cvxpy git:(develop) ✗ pip install CVXcanon
Collecting CVXcanon
  Downloading CVXcanon-0.0.1.dev1.tar.gz
Requirement already satisfied (use --upgrade to upgrade): numpy in /Users/stevend2/anaconda/envs/develop/lib/python2.7/site-packages (from CVXcanon)
Installing collected packages: CVXcanon
  Running setup.py install for CVXcanon
    Complete output from command /Users/stevend2/anaconda/envs/develop/bin/python -c "import setuptools, tokenize;__file__='/private/var/folders/gb/15j5cwts2lscjq9301sc9hx80000gn/T/pip-build-6iJDFS/CVXcanon/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /var/folders/gb/15j5cwts2lscjq9301sc9hx80000gn/T/pip-_MkYbs-record/install-record.txt --single-version-externally-managed --compile:
    running install
    running build
    running build_py
    creating build
    creating build/lib.macosx-10.5-x86_64-2.7
    copying canonInterface.py -> build/lib.macosx-10.5-x86_64-2.7
    copying CVXcanon.py -> build/lib.macosx-10.5-x86_64-2.7
    running build_ext
    building '_CVXcanon' extension
    swigging CVXcanon.i to CVXcanon_wrap.cpp
    swig -python -c++ -I../ -outcurrentdir -o CVXcanon_wrap.cpp CVXcanon.i
    CVXcanon.i:8: Error: Unable to find 'numpy.i'
    CVXcanon.i:25: Error: Unable to find 'LinOp.hpp'
    CVXcanon.i:30: Error: Unable to find 'ProblemData.hpp'
    error: command 'swig' failed with exit status 1

osx Mojave compilation error

I was trying to install using sudo -H pip install CVXcanon on mac osx Mojave with XCode10.1 and running into compiler issues such as:

    warning: include path for stdlibc++ headers not found; pass '-std=libc++' on the command line to use the libc++ standard library instead [-Wstdlibcxx-not-found]
    In file included from src/CVXcanon.cpp:16:
    src/CVXcanon.hpp:19:10: fatal error: 'vector' file not found
    #include <vector>

In the end I downloaded your source code and added:

    extra_link_args=["-stdlib=libc++",],
    extra_compile_args=["-mmacosx-version-min=10.9",]

to the Extensions of setup.py and was able to successfully compile using:

sudo -H pip install -e /Users/$USER/Downloads/CVXcanon-0.1.1/

I feel this solution is not generic enough to warrant a PR, but I thought I would let you know.

cvxpy memory usage

I'm using cvxpy version 0.4.0 on python 3.4.3 and have been seeing excessive memory usage when calling a function that solves a matrix optimization problem using cvxpy in a for loop. It sounded similar to this issue which was apparently resolved, but when I ran the same code snippet from the resolved issue on my computer I noticed that memory usage (monitored through >> top) still seems to be increasing with the loop. For prob.solve() with arguments CVXOPT, ECOS, SCS, or no argument, memory usage increased from about 40 kB at the start to about 300 kB after the last loop. While 300 kB isn't a huge deal for this test case of 10000 loops, it turns into tens of GB after billions of loops.

I posted this issue to the cvxpy Google Groups and was told that it might be an issue with CVXcanon, so I'm reposting the question here.

Module name should be lowercase

Per PEP8:

Modules should have short, all-lowercase names. Underscores can be used in the module name if it improves readability. Python packages should also have short, all-lowercase names, although the use of underscores is discouraged.

Please consider changing the name of the Python package to 'cvxcanon'.

cvxgrp / cvxcanon Goto Github PK

cvxcanon's People

Contributors

Stargazers

Watchers

Forkers

cvxcanon's Issues

Recommend Projects

Recommend Topics

Recommend Org