LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 7

Reply
 
Thread Tools Display Modes
  #1  
Old 08-26-2012, 03:21 PM
Andrs Andrs is offline
Member
 
Join Date: Jul 2012
Posts: 47
Default 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....
Reply With Quote
  #2  
Old 08-26-2012, 04:01 PM
tzs29970 tzs29970 is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 52
Default 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 \alpha's might sometimes be negative despite the constraint so you need to include some fuzziness in how you interpret the results.
Reply With Quote
  #3  
Old 08-26-2012, 04:10 PM
Andrs Andrs is offline
Member
 
Join Date: Jul 2012
Posts: 47
Default 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?...
Reply With Quote
  #4  
Old 08-26-2012, 05:21 PM
tzs29970 tzs29970 is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 52
Default Re: quadrat prog CVXOPT Python

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

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 \alpha's from a few runs, and eyeballed them to get an idea of what a good \epsilon 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 \epsilon.
Reply With Quote
  #5  
Old 08-27-2012, 04:24 AM
kdresser kdresser is offline
Junior Member
 
Join Date: Aug 2012
Posts: 6
Default 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://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.
Reply With Quote
  #6  
Old 08-27-2012, 12:12 PM
jiunjiunma@gmail.com jiunjiunma@gmail.com is offline
Junior Member
 
Join Date: Jul 2012
Posts: 8
Default 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.
Reply With Quote
  #7  
Old 08-27-2012, 12:47 PM
Andrs Andrs is offline
Member
 
Join Date: Jul 2012
Posts: 47
Default Re: quadrat prog CVXOPT Python

Quote:
Originally Posted by jiunjiunma@gmail.com View Post
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?
Reply With Quote
  #8  
Old 08-27-2012, 04:37 PM
jiunjiunma@gmail.com jiunjiunma@gmail.com is offline
Junior Member
 
Join Date: Jul 2012
Posts: 8
Default 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.
Reply With Quote
Reply

Tags
cvxopt, python, quadratic programming

Thread Tools
Display Modes

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 Jump


All times are GMT -7. The time now is 10:34 AM.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.