CVXOPT/Mosek crashes when solving QP

[Martin Cousineau]

Hi,

I was able to solve successfully many QP instances with CVXOPT and CVXOPT/Mosek. However, for one large instance (Q matrix of size 15992x15992), CVXOPT is able to solve this instance but CVXOPT/Mosek crashes when calling cvxopt.solvers.qp().

I would really like to make CVXOPT/Mosek works because it tends to find better solution.

Thank you!

Python 3.4.4

Mosek 7.1

CVXOPT 1.1.8

Windows 7

[Joachim Dahl]

Perhaps MOSEK or CVXOPT runs out of memory and doesn't handle it gracefully.  Can you try the same problem on a machine with more memory?   Ideally such bugs should be fixed, but you still would not be able to solve it with CVXOPT/MOSEK.

--
You received this message because you are subscribed to the Google Groups "CVXOPT" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.
To post to this group, send email to cvx...@googlegroups.com.
Visit this group at https://groups.google.com/group/cvxopt.
For more options, visit https://groups.google.com/d/optout.

[Martin Cousineau]

Hi Joachim,

My machine still got plenty of memory free (about 16GB) when CVXOPT/Mosek crashes. 

Going through the code, I found that the crash happens when executing  

colptr, asub, acof = sparse([G,A]).CCS

in msk.qp(). However, I don't know how to solve the issue.

Thanks!

On Wednesday, August 17, 2016 at 2:32:53 PM UTC-4, Joachim Dahl wrote:

Perhaps MOSEK or CVXOPT runs out of memory and doesn't handle it gracefully.  Can you try the same problem on a machine with more memory?   Ideally such bugs should be fixed, but you still would not be able to solve it with CVXOPT/MOSEK.

On Wed, Aug 17, 2016 at 8:00 PM, Martin Cousineau <marti...@gmail.com> wrote:

Hi,

I was able to solve successfully many QP instances with CVXOPT and CVXOPT/Mosek. However, for one large instance (Q matrix of size 15992x15992), CVXOPT is able to solve this instance but CVXOPT/Mosek crashes when calling cvxopt.solvers.qp().

I would really like to make CVXOPT/Mosek works because it tends to find better solution.

Thank you!

Python 3.4.4

Mosek 7.1

CVXOPT 1.1.8

Windows 7

--
You received this message because you are subscribed to the Google Groups "CVXOPT" group.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+un...@googlegroups.com.

[Martin Cousineau]

Here is my code and data (60MB) to replicate the error in case that it can help you:

http://www.filedropper.com/crashcodeanddata

Thanks again!

[Trish Gillett]

FYI, if you happen to be using 64 bit Windows with 32 bit Python then any Python process will be capped at about 2GB RAM regardless of the amount of free RAM available.  This is not a Python choice but a Windows one - 64 bit Windows caps the amount of RAM which can be used by any 32 bit process.  If this is what your problem is, switching to 64 bit Python is the fix.

Some stackoverflow posts discussing the memory cap for 32 bit:
http://stackoverflow.com/questions/18282867/python-32-bit-memory-limits-on-64bit-windows
http://stackoverflow.com/questions/38628060/is-there-any-way-to-use-more-than-2gb-of-memory-in-32-bit-python-application-in?noredirect=1&lq=1
http://stackoverflow.com/questions/8672622/behavior-of-32-bit-applications-in-64-bit-windows-memory?rq=1
http://stackoverflow.com/questions/18607233/memoryerror-when-read-a-file-larger-than-2g

[Martin Cousineau]

Hi Trish,

I am using 64 bit Python. Hence, this is not the issue.

Thank you.

[Martin Cousineau]

Could it be cvxopt.base that is 32bit?

[Joachim Dahl]

Perhaps you are able to narrow down what fails by manually replication the steps you mentioned:

>>> [G, A]

>>> sparse([G, A])

>>> sparse([G, A]).CCS

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.

[Martin Cousineau]

sparse([G,A]) is the issue

[Joachim Dahl]

I fixed at least one bug related to this problem.  You can either wait for Martin to include it (I have to figure out how to do pull requests first), or install cvxopt from my fork:

https://github.com/joachimdahl/cvxopt

The fork, as well as the latest dev version, includes a revised MOSEK interface for MOSEK 8.0.  The main motivation for revising the interface was to include SDPs, but the interface has not been tested much;  there might be trivial syntax errors as I used search-replace in a bunch of places without having a set of test-scripts to verify all the different interface functions.

It does seem to work on your example, though, but MOSEK claims that Q is not positive definite.  We check convexity by performing a Cholesky factorization of Q, and sometimes that can fail.  In that case you should

rewrite the QP as an SOCP yourself - and starting from MOSEK 8 all QPs are solved internally as SOCPs anyway.

I also suggest you construct G directly as a sparse matrix - your construction via a dense matrix is very inefficient for a problem this size.

Another addition to the MOSEK interface is the ability to generate MOSEK .task files.  If you need support from MOSEK you are encouraged to generate a .task as an attachment for your bug report.  That way we don't have to install lots of packages etc. in order to reproduce the problem.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.

[Martin Cousineau]

Hi Joachim,

I know that my matrix is symmetric PSD because it is a Gaussian RBF kernel matrix. It tends to be declared as non PSD because of numerical error. I have tried writing my problem as a SOCP directly in MOSEK 8  python fusion but it was not as fast as CVXOPT+MOSEK 7.1 (probably because of the preprocessing that CVXOPT does). I was factorizing my matrix using eigendecomposition, then forcing all negative eigenvalues (e.g., -1E-16) to zero before computing Q**0.5 as v*Diag(w**0.5)*v' where w are the eigenvalues and v the eigenvectors. Is there a more efficient way for me to do this?

Is there any gain for me to install this fork if I write my problem as a SOCP? How can I install CVXOPT from this fork? I have previously installed CVXOPT with "pip install".

Is this an "efficient" way to construct a sparse matrix?

>>> G = cvxopt.sparse(cvxopt.matrix(np.r_[np.ones((1,n0)), -np.ones((1,n0)), np.eye(n0), -np.eye(n0)],tc='d'))

Thank you so much!

Thank you!

[Martin Cousineau]

I think I found a much better way to construct G:

        A = cvxopt.spmatrix(1.,[0]*n0,range(n0),tc='d')

        B = cvxopt.spmatrix(1.,range(n0),range(n0),tc='d')

        G = cvxopt.sparse([A,-A,B,-B],tc='d')

=)

[Martin Cousineau]

Hi Joachim,

I don't think I can formulate my problem as a SOCP because the 'mosek' option does not allow equality constraints.

[Martin Cousineau]

By the way, formulating G as a sparse matrix solved my issue!

[Joachim Dahl]

A low-rank factorization as you mention should help MOSEK also.  Tomorrow I can see how I would I specify it in a SOCP form.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.

[Martin Cousineau]

I think I found how to transform the problem but it finds a certificate of infeasibility so my formulation must not be good. I don't know whether my problem is the code or my mathematical formulation.

QP problem (vars = {x}):

minimize x' P x + q' x

S.t. 

G x <= h

SOCP problem (vars = {x,r,s,t}):

minimize t + q' x

S.t. 

G x <= h

2s - t <= -1

|| Hx || <= r

|| [r, s] || <= s + 1

with P = H H'

Is there an issue with using a variable in two different cones?

[Martin Cousineau]

I also tested the following formulation (again with a certificate of dual infeasibility):

SOCP problem (vars = {x,t}):

minimize t

S.t.

G x <= h

|| Hx + a || <= t

with a = 0.5 inv(H) q

[Joachim Dahl]

Can you send a smaller example to sup...@mosek.com?   Then I will try to make an example of how to transform it to SOCP form.

To unsubscribe from this group and stop receiving emails from it, send an email to cvxopt+unsubscribe@googlegroups.com.

[Joachim Dahl]

Also, can you provide explicit code for forming Q?  Very often you can construct Q directly in factored form.

[Martin Cousineau]

Hi Joachim,

I have sent you a smaller test example with explicit code for P and q. I have tried to find how to construct directly Q in factored form but was not able to find an answer.

Thank you,

Martin

[Martin Cousineau]

It seems like Incomplete Cholesky Decomposition can provide me a sparser factorization. Please tell me if you are able to make the SOCP formulation work. If needed, I can upgrade to Mosek 8 and/or new CVXOPT release.

[Martin Cousineau]

The example provided on http://cvxopt.org/userguide/coneprog.html#second-order-cone-programming use the opposite of G as Gq. Is this an error?