LFD Book Forum quadrat prog CVXOPT Python
 User Name Remember Me? Password
 FAQ Calendar Mark Forums Read

 Thread Tools Display Modes
#1
08-26-2012, 03:21 PM
 Andrs Member Join Date: Jul 2012 Posts: 47
quadrat prog CVXOPT Python

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....
#2
08-26-2012, 04:01 PM
 tzs29970 Invited Guest Join Date: Apr 2012 Posts: 52
Re: quadrat prog CVXOPT Python

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.
#3
08-26-2012, 04:10 PM
 Andrs Member Join Date: Jul 2012 Posts: 47
Re: quadrat prog CVXOPT Python

Thanks!
Code:
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?...
#4
08-26-2012, 05:21 PM
 tzs29970 Invited Guest Join Date: Apr 2012 Posts: 52
Re: quadrat prog CVXOPT Python

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 .
#5
08-27-2012, 04:24 AM
 kdresser Junior Member Join Date: Aug 2012 Posts: 6
Re: quadrat prog CVXOPT Python

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://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.
#6
08-27-2012, 12:12 PM
 jiunjiunma@gmail.com Junior Member Join Date: Jul 2012 Posts: 8
Re: quadrat prog CVXOPT Python

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.
#7
08-27-2012, 12:47 PM
 Andrs Member Join Date: Jul 2012 Posts: 47
Re: quadrat prog CVXOPT Python

Quote:
 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?
#8
08-27-2012, 04:37 PM
 jiunjiunma@gmail.com Junior Member Join Date: Jul 2012 Posts: 8
Re: quadrat prog CVXOPT Python

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.

 Tags cvxopt, python, quadratic programming

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home General     General Discussion of Machine Learning     Free Additional Material         Dynamic e-Chapters         Dynamic e-Appendices Course Discussions     Online LFD course         General comments on the course         Homework 1         Homework 2         Homework 3         Homework 4         Homework 5         Homework 6         Homework 7         Homework 8         The Final         Create New Homework Problems Book Feedback - Learning From Data     General comments on the book     Chapter 1 - The Learning Problem     Chapter 2 - Training versus Testing     Chapter 3 - The Linear Model     Chapter 4 - Overfitting     Chapter 5 - Three Learning Principles     e-Chapter 6 - Similarity Based Methods     e-Chapter 7 - Neural Networks     e-Chapter 8 - Support Vector Machines     e-Chapter 9 - Learning Aides     Appendix and Notation     e-Appendices

All times are GMT -7. The time now is 09:17 AM.

 Contact Us - LFD Book - Top