help on solvers.cp()

[xiwe...@gmail.com]

Dear Joachim, Lieven, and others,
I try to use solvers.cp to minimize a function. Please see below for
the detail function.
P is a matrix, mu is a number.
G, h are built to have all x's >= 0, and sum(x) <=1. A and b are None.
Note that, inside the matrix, elements of u will change depending on
x's (This might be the reason it can not get the results? I tried to
set u = mu - P*x, and it works!!).

For small P matrix, like 4X5, it will give the answer.

But for big ones, such as 200X200, it will terminated after 99:
95: -4.0718e+006 5.6339e+006 4e+001 5e-001 5e-001
96: -4.0591e+006 5.5153e+006 4e+001 5e-001 5e-001
97: -4.0589e+006 5.5138e+006 4e+001 5e-001 5e-001
98: -4.0522e+006 5.4612e+006 4e+001 5e-001 5e-001
99: -4.0509e+006 5.4517e+006 4e+001 5e-001 5e-001
None

Is my function correct?
Is there any way to let it run more than 99 cycles to try to get the
answers? Can we set initial x's?

def func_min(P, mu, G=None, h=None, A=None, b=None):
m, n = P.size
def F(x=None, z=None):
if x is None: return 0, matrix(1.0, (n,1))
u = matrix([max((mu - xx),0.0) for xx in P*x], (m,1))
f = u.T * u
Df = (-2*P.T*u).T
if z is None: return f, Df
H = 2*z[0]*P.T*P
return f, Df, H
return solvers.cp(F, G=G, h=h,A=A,b=b)['x']

The func_min() is trying to do the same as below:
__________ matlab ____

function [f df] = lower(x,P,mu)
g = max(mu-P*x,0);
f = g'*g;
df = -2*P'*g;

fmincon(@lower,x0,A,b,Aeq,beq,lb,ub,[],option,P,riskThresh)

[Joachim Dahl]

Dear Xiwen,

It's easier for us to help, if you specify the problem you're trying to solve. I don't know
Matlab's fmincon is supposed to do...

[Xiwen Wang]

Dear Joachim,

Thanks for the quick reply.

I am trying to minimize a function, f. 

f is defined as:

u = matrix([max((mu - xx),0.0) for xx in P*x], (m,1))

f = u.T * u

P is mXn matrix, mu is a real number. I write the func_min as shown in my last post.

Here is the sample run: func_min(P,mu, G,h, A,b)

For small matrix P, it works well:

P=

[-3.69e-004 -3.69e-004  1.99e-004 -7.22e-003 -1.24e-002]

[ 2.56e-004  2.56e-004 -4.26e-004 -4.09e-003 -6.73e-003]

[-3.69e-004 -3.69e-004  1.99e-004  1.03e-002  1.76e-002]

[ 2.56e-004  2.56e-004 -4.26e-004  5.91e-003  9.52e-003]

[ 2.56e-004  2.56e-004  1.99e-004  3.41e-003  3.27e-003]

[ 2.56e-004  2.56e-004  1.99e-004  2.78e-003  1.42e-004]

G=

[-1.00e+000  0.00e+000  0.00e+000  0.00e+000  0.00e+000]

[ 0.00e+000 -1.00e+000  0.00e+000  0.00e+000  0.00e+000]

[ 0.00e+000  0.00e+000 -1.00e+000  0.00e+000  0.00e+000]

[ 0.00e+000  0.00e+000  0.00e+000 -1.00e+000  0.00e+000]

[ 0.00e+000  0.00e+000  0.00e+000  0.00e+000 -1.00e+000]

h=

[ 0.00e+000]

[ 0.00e+000]

[ 0.00e+000]

[ 0.00e+000]

[ 0.00e+000]

A=

[ 1.00e+000  1.00e+000  1.00e+000  1.00e+000  1.00e+000]

b=

[ 1.00e+000]

     pcost       dcost       gap    pres   dres

 0:  0.0000e+000  4.8863e+001  6e+000 1e+000 1e+000

 1:  5.3576e+001  5.3168e+001  8e-001 7e-003 7e-003

 2:  5.3956e+001  5.3924e+001  4e-002 2e-004 2e-004

 3:  5.3946e+001  5.3932e+001  2e-002 6e-005 6e-005

 4:  5.3934e+001  5.3930e+001  3e-003 1e-006 2e-016

 5:  5.3932e+001  5.3932e+001  3e-004 1e-007 1e-016

 6:  5.3932e+001  5.3932e+001  2e-005 1e-008 2e-016

[ 4.60e-005]

[ 4.60e-005]

[ 4.45e-005]

[ 3.25e-003]

[ 9.97e-001]

For big matrix, it will give None. 

My question is, is my func_min correct? Why  the solver gives None? 

Again, thanks very much. Please let me know if you need any other information.

Regards,

[Joachim Dahl]

Is your problem equivalent to the following?

min.  || t ||^2
s.t.   mu - Px <= t
        t >= 0
        Ax = b
        Gx <= h

If so, you should solve it in that form using the buildin quadratic programming solver.

Best regards
joachim

[Xiwen Wang]

Dear Joachim,

You should be right. Would you please take minutes to write your Function for me? I can test and compare with my previous one and tell the difference. 

Thanks very much,

Best Regards,

xiwen

[Joachim Dahl]

You should use the buildin solvers.qp() routine.   The script below is what I had in mind;
the data are randomly generated,  so you probably need to run a few examples to get a feasible
instance.



from cvxopt.base import matrix, normal, spmatrix, setseed
from cvxopt import solvers

# Solve the QP
#
# minimize    t'*t
# subject to  mu - P*x <= t
#             t >= 0
#             A*x = b
#             G*x <= h

setseed(0)

m, n, p = 4, 3, 2
P = normal(n, n); P = P*P.T
G = normal(m, n); h = normal(m, 1)
A = normal(p, n); b = normal(p, 1)
mu = 1

P_ = spmatrix(n*[0.0] + n*[1.0], range(2*n), range(2*n))
q_ = matrix(0.0, (2*n, 1))

In = spmatrix(1.0, range(n), range(n));

G_ = matrix( [ [G, -P, matrix(0.0, (n,n))],
               [matrix(0.0, (m, n)), -In, -In] ] )
h_ = matrix( [ h, -mu*matrix(1.0, (n, 1)), matrix(0.0, (n,1)) ] )
A_ = matrix( [ [A], [matrix(0.0, (p,n))] ] )
b_ = b

sol = solvers.qp(P_, q_, G_, h_, A_, b_)

[Xiwen Wang]

Dear Joachim,

Thanks very much. It works but sometime it fails to find the solution: matrix singularity.

I now try to install cvxopt on LINUX, everything seems fine during the installation, but when I do: import cvxopt, I got this error: 

Traceback (most recent call last):

  File "<stdin>", line 1, in <module>

  File "/home/wangx/lib/python/cvxopt/__init__.py", line 5, in <module>

    import base, printing

ImportError: /home/wangx/lib/python/cvxopt/base.so: undefined symbol: s_wsfe

Do you have any idea why and how to fix it? thanks very much,

Regards,

xiwen

PS: python 2.5.2, atlas3.8.2, lapack3.1.1, blas

[Joachim Dahl]

You most likely need to include 'gfortran' to the list of
libraries for building base, see
http://groups.google.com/group/cvxopt/browse_thread/thread/462b7410d80fccbc

The script I provided generates the data randomly, so often the problem will
be infeasible which for the QP solver results in the singular KKT matrix error message.

If you are solving a problem you know to be feasible, and still encounter
this error,  you can try to increase the tolerances in the algorithms as
described here:
http://abel.ee.ucla.edu/cvxopt/documentation/users-guide/node52.html

[Xiwen Wang]

[Xiwen Wang]

Dear Loachim,

I tried base = Extension('base', libraries = ['gfortran', 'm','lapack','blas'] 

but when I do: python setup.py install --home=~

I get this error: 

building 'base' extension

gcc -pthread -shared build/temp.linux-i686-2.5/C/base.o build/temp.linux-i686-2.5/C/dense.o build/temp.linux-i686-2.5/C/sparse.o -L/home/wangx/lib -lgfortran -lm -llapack -lblas -o build/lib.linux-i686-2.5/cvxopt/base.so

/usr/bin/ld: cannot find -lgfortran

collect2: ld returned 1 exit status

error: command 'gcc' failed with exit status 1

Do I miss something? Thanks

xiwen

[Joachim Dahl]

BLAS/LAPACK or ATLAS often cause difficulties...

If you have either BLAS/LAPACK or ATLAS properly installed,  then
I don't have a good idea of what the problem is...   Note, that CVXOPT
is not setup to use ATLAS;  it uses standard BLAS/LAPACK.

Many Linux platforms there are precompiled binaries for CVXOPT,
which might be easier to install.

Joachim

[Xiwen Wang]

Dear Joachim,

I appreciate your kind help. 

I use atlas first since the install.txt recommends it. Anyway, I think I need tune up lapack/blas to see if i can get cvxopt works. Thanks again,

xiwen

[Joachim Dahl]

you can also try to link against 'g2c' instead of 'gfortran'.

[Xiwen Wang]

Dear Joachim,

Yes, I figured out a moment ago, and want to tell you about. 

Here is another issue. I made glpk, dsdp and modify the setup.py accordingly. During the python setup.py install, I noticed these two are built. Everything seems fine.

But when I use solver='glpk', it tells me:

invalid option (solver='glpk'): cvxopt.glpk is not installed

Do you know why? 

Thanks,

xiwen

[Joachim Dahl]

can you provide a Python script for reproducing the error?

[Xiwen Wang]

Dear Joachim,

Based on /example/doc/chap8/lp

#!/usr/bin/python

# The small LP of section 8.3.  

from cvxopt.base import matrix  

from cvxopt import solvers  

c = matrix([-4., -5.])  

G = matrix([[2., 1., -1., 0.], [1., 2., 0., -1.]])  

h = matrix([3., 3., 0., 0.])  

sol = solvers.lp(c, G, h, solver='glpk')  

print "\nx = \n\n", sol['x']  

when I run it, the error:

Traceback (most recent call last):

  File "lp", line 10, in <module>

    sol = solvers.lp(c, G, h, solver='glpk')  

  File "/home/wangx/lib/python/cvxopt/coneprog.py", line 2164, in lp

    except ImportError: raise ValueError, "invalid option "\

ValueError: invalid option (solver='glpk'): cvxopt.glpk is not installed

In python:

>>> from cvxopt import glpk

Traceback (most recent call last):

  File "<stdin>", line 1, in <module>

ImportError: libglpk.so.0: cannot open shared object file: No such file or directory

Here is the part in setup.py. And the file libglpk.so.0 is at: /home/wangx/lib

BUILD_GLPK = 1

GLPK_LIB_DIR = '/home/wangx/lib'

GLPK_INC_DIR = '/home/wangx/include'

Thanks

xiwen

[Joachim Dahl]

This looks like general problem with your Linux configuration (and
not a problem with CVXOPT).

Most likely you forgot to setup LD_LIBRARY_PATH. If you use a BASH
shell you can write
$ export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/home/xiwen/lib

What platform are you using?  On most Linux platforms there are
binary versions of CVXOPT readily available...

[Xiwen Wang]

Dear Joachim,

You are right, now it works. Thanks very much.

Where can I find the binary versions of CVXOPT? I only see Windows version on: http://abel.ee.ucla.edu/cvxopt/download

I am using Linux version 2.6.5-7.282_lustre.1.4.8bigsmp (geeko@buildhost) (gcc version 3.3.3 (SuSE Linux)) #1 SMP Mon Dec 18 19:58:47 MST 2006

Xiwen

[Joachim Dahl]

We do not provide the binaries.

CVXOPT is included in Debian and Ubuntu and macports,  and searching on
google for python-cvxopt shows that there are several orther flavours of
binary versions available.

Joachim