quadrat prog CVXOPT Python

[Andrs]

I have a question about specifying the upper/lower bounds in CVXOPT/Python.
The A and b matrix specify the condition: yTranspose.alpha = 0 and this is clear.
The bounds for "alpha" are defined as: lower bound = 0, upper bound = infinity.
There is a G matrix that defines inequalities (G.alpha<= h).
Could we use the (negative)G matrix defined as an
Identity matrix to define the lower bound. That is, -G<0 (G.alpha<=0)? If G = I than I.alpha = alpha and it would define a bound for alpha.
How about defining the upper bounds as infinite???
Any comments about the use of CVXOPT are really appreciated. How did you reason about specifying the upper/lower bounds....

[tzs29970]

I used CVXOPT and Python for this homework set. I had never used CVXOPT before this. Here are some observations based on my experience.

• Yes, the negative of the identity matrix works to deal with the fact that cvxopt.solvers.qp wants constraints that go the opposite direction from what we need.
• Make sure all your matrices are floating point. For most of them you'll get an error if they are integer, but I think there was one where it did not give an error but rather just silently gave inaccurate results.
• Keep in mind that the results aren't exact. In particular, the 's might sometimes be negative despite the constraint so you need to include some fuzziness in how you interpret the results.

[Andrs]

Thanks!

Keep in mind that the results aren't exact. In particular, the alphas's might sometimes be negative despite the constraint so you need to include some fuzziness in how you interpret the results.

CVXOPT calls alpha for x. They may show very small values for x (alpha) or even negatives values.....
What do you mean by fuziness? If the alpha is very small (i.e. e-5, e-9), it should be the same as zero? Or...
What about negative values? Should they be treated as zero?...

[tzs29970]

It's similar to floating point in general. If you have some computed number whose exact value should be , the floating point number you actually get is not necessarily exactly but rather is in some interval for some (hopefully) small .

Thus, when you are looking for a 0, you should consider anything close to 0 to be 0. The question then is how close is close enough? To deal with that, I printed out the 's from a few runs, and eyeballed them to get an idea of what a good might be. That was good enough to get all of the problems right.

Alternatively, one of the items in the dictionary gp returns is named 'gap'. I do not understand CVXOPT well enough yet to be quite sure what the gap is, but it seems to be a good candidate for .

[jiunjiunma@gmail.com]

Did you need an upper bound in CVXOPT? I didn't use it but the result was quite strange. Not only it has negative values, it doesn't seem to be right. I am still trying to figure out where I did wrong.

[Andrs]

Originally Posted by jiunjiunma@gmail.com

Did you need an upper bound in CVXOPT? I didn't use it but the result was quite strange. Not only it has negative values, it doesn't seem to be right. I am still trying to figure out where I did wrong.

I was able to specify a lower bound but I am not sure about the upper bound.

http://courses.csail.mit.edu/6.867/w.../Qp-cvxopt.pdf
This document makes a quick reference to upper bounds (first page/last paragraph) but it is not clear how to specify our upper bound (infinite).

When I run my CVXOPT, I am getting quite a few failures with the information: Terminated (singular KKT matrix). I am using all the default parameters....I am not sure about the reason. Are you getting the same problem?

[jiunjiunma@gmail.com]

No, I didn't get the singular KKT matrix error, but the results I got didn't seem to be right. I tried to run the sample svm code suggested by kdresser and found it gave the same error result. Now I am even more confused.

[kdresser]

I'm another newbie to QP solvers, using CVXOPT. Also new to NumPy, whose speed made running many large tests feasible.

These helped:
From a post by kkkkk from the first (Spring 2012) run of this course:
http://ascratchpad.blogspot.com/2010...erivation.html
http://www.mblondel.org/journal/2010...nes-in-python/
And:
http://courses.csail.mit.edu/6.867/w.../Qp-cvxopt.pdf

Ensure that double floats are used everywhere ( cvxopt.matrix(... tc='d')).

The docs state that these tolerances are the defaults (though the options dictionary is initially empty)

cvxopt.solvers.options['abstol'] = 1e-7 # Default?
cvxopt.solvers.options['reltol'] = 1e-6 # Default?
cvxopt.solvers.options['feastol'] = 1e-7 # Default?

Tightening things to

cvxopt.solvers.options['abstol'] = 1e-9 # <<<
cvxopt.solvers.options['reltol'] = 1e-8 # <<<
cvxopt.solvers.options['feastol'] = 1e-9 # <<<

reduced the number of extra SVs and reduced E_in from ~1% to 0 for the 100 sample experiment. Further tightening upset QP, causing a handfull of "Terminated (singular KKT matrix)" messages. Note: this was all thud and blunder experimenting, with no understanding of CVXOPT's internals.

The fiddle invented by elkka (see Spring postings) to improve Octave's QP made no significant difference to my CVXOPT QP runs, other than to reduce the number of extra SVs a little bit more. It also eliminated E_in before the above tolerance changes were made.

CVXOPT's iteration count never ran away (~7 .. ~24 for 10 .. 500 points).

HTH.