LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 7 (http://book.caltech.edu/bookforum/forumdisplay.php?f=136)
-   -   Quadratic programming (http://book.caltech.edu/bookforum/showthread.php?t=1119)

invis 08-23-2012 06:28 AM

Quadratic programming
 
I never used QP in my practice. And I using Octave for solve HWs.
So there is built-in function for quadratic programming in Octave - qp. (example)

But I still dont know what parameters I should use to solve:

\min_{w,b} 0.5w^Tw
s.t.
y_n(w^Tx_n+b)=>1

Looks like H is Y*Y^T .* X*X^T (.* is element by element product)
But what is the other parameters :confused:

invis 08-23-2012 10:09 AM

Re: Quadratic programming
 
And where is ?
http://i1161.photobucket.com/albums/...7/b3472e2a.png

invis 08-23-2012 11:23 AM

Re: Quadratic programming
 
I am absolutly confused :(

Should I use QP to solve this inequality:

\min_{w,b} 0.5w^Tw
s.t.
y_n(w^Tx_n+b)=>1

OR to solve inequality in picture in previous message ?

yaser 08-23-2012 05:22 PM

Re: Quadratic programming
 
Quote:

Originally Posted by invis (Post 4326)
I am absolutly confused :(

Should I use QP to solve this inequality:

\min_{w,b} 0.5w^Tw
s.t.
y_n(w^Tx_n+b)=>1

OR to solve inequality in picture in previous message ?

The version in the picture. It's the dual problem (equivalent) to the version that is in the quote.

invis 08-24-2012 04:40 AM

Re: Quadratic programming
 
Why sometimes it is impossible to find the solution and what to do with that ?
On 200 iterations with random line and random dots (#10) 81 times QP didnt find the solution (I plot the line and dots for this situations and all looks pretty clear).
This is the parameters for QP I use:

H = (Y*Y') .* (X*X');
A = Y';
q=-1*ones(n,1);
b=0;
lb=zeros(n,1); (lower bound)
ub=[]; (upper bound)

min 0.5 x'*H*x + x'*q
subject to

A*x = b
lb <= x <= ub


where x is our \alpha

htlin 08-24-2012 05:30 AM

Re: Quadratic programming
 
Quote:

Originally Posted by invis (Post 4367)
Why sometimes it is impossible to find the solution and what to do with that ?
On 200 iterations with random line and random dots (#10) 81 times QP didnt find the solution (I plot the line and dots for this situations and all looks pretty clear).
This is the parameters for QP I use:

H = (Y*Y') .* (X*X');
A = Y';
q=-1*ones(n,1);
b=0;
lb=zeros(n,1); (lower bound)
ub=[]; (upper bound)

min 0.5 x'*H*x + x'*q
subject to

A*x = b
lb <= x <= ub


where x is our \alpha

Sometimes the numerical condition of the optimization problem makes it hard for the solver to locate a good solution. One possibility is to set ub (upper bound) to a really large value. Hope this helps.

invis 08-24-2012 05:42 AM

Re: Quadratic programming
 
I change ub to:
ub=10^22*ones(n,1);

For 400 iterations 154 without solution :( How to deal with it in context of homework ?
"How often is g_{SVM}
better than g_{PLA} in approximating f?"

jakvas 08-24-2012 06:03 AM

Re: Quadratic programming
 
@invis

for the 100 points problem 400 iterations may be too little (i used 2000 iterations in my matlab code and in ~2% of the cases even that limit was exceeded but that still gives a decent accuracy you could use even more but don't go too far or you will never get results) also for the upper bound I used 10^5 and 10^10 without any significant change in results, 10^22 seems a bit much considering you are probably using single precision numbers:)

invis 08-24-2012 06:10 AM

Re: Quadratic programming
 
400 iterations I use only to show that ~40% of problems QP cant solve even with 10 dots. So how can I compare results with PLA ?

Jakvas you are using matlab, so maybe you can tell me am I miss something in parameters for QP ? Why almost half of problems without solution ?

jakvas 08-24-2012 06:17 AM

Re: Quadratic programming
 
try a smaller upper bound and maybe plot some of the results you do get to see if there is no serious error somewhere.


All times are GMT -7. The time now is 07:39 PM.

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.