Re: QP solves for zero instead of min?

[Olaf Till]

On Sun, Aug 03, 2014 at 06:51:47PM +0200, Juan Pablo Carbajal wrote:
> On Sun, Aug 3, 2014 at 6:10 PM, Olaf Till <address@hidden> wrote:
> > On Sun, Aug 03, 2014 at 05:40:07PM +0200, Juan Pablo Carbajal wrote:
> >> <snip>
> >> So far QP gives
> >> the zero of the cost function and not the solution.
> >
> > Why do you think it is not the solution?
> >
> > Olaf
> >
> > --
> > public key id EAFE0591, e.g. on x-hkp://pool.sks-keyservers.net
> 
> If the problem is convex, ther eis one minimum. QP is gving a zero and
> sqp finds a lower point.

I didn't see first that sqp gets lower, now I see it. Sorry.

The quadratic problem in your example, due to rank deficiency, has no
single solution, but probably a 3-dimensional solution space (solution
here means `a' together with `lambda'). I silently concluded in my
answer that this corresponds to some space of solutions for the actual
minimum of the problem (for any fixed `lambda'), but this was probably
theoretically wrong (I have no time at the moment to update my
knowledge). Sorry again.

Looking closer, it seems that `qp', apart from not getting to the
minimum, not even correctly solves the quadratic problem (with
a=[0;0;0;0;0]), so indeed there seems to be something wrong. But I
don't know how qp-algorithms are supposed to handle rank-deficient
problems. In sqp-algorithms, the qp-subalgorithms seem to be mostly
called with full-rank matrices.

Again, let me please apologize for talking a while without quite
seeing the point.

Olaf

> It seems sqp gives the solution while QP is
> stuck in a zero of the cost function. I am getting this often.
> It might be that I do not understand why QP can fail (if it does) or
> why would there be more than one solution to a convex problem.
> 
> I am testing the primal form of SVM and sometimes I do not get the
> right solution
> http://en.wikipedia.org/wiki/Support_vector_machine#Primal_form
> 
> Here an example that works
> 
> N = 6;
> x = [0 0.2 0.5 0.3 0.7 0.8; -0.2 -0.5 -0.1 0.3 0.4 0.1];
> y = [ones(1,3) -ones(1,3)];
> 
> scatter (x(1,:),x(2,:),[],y)
> axis tight
> 
> X = x.'*x;
> Y = y.'*y;
> H = Y.*X;
> Q = -ones(N,1);
> a = qp (rand(N,1),H,Q,y,0,zeros(N,1),inf(N,1));
> sv = find(a>0); #support vectors
> 
> w = (y.*x)*a; #normal to the classification line
> b = mean(w.'*x(:,sv) -y(sv));
> 
> # needs geometry
> drawLine (createLine([0,b/w(2)],[-w(2),w(1)]))
> 
> If you change for random points N ~10 then sometimes it fails.

-- 
public key id EAFE0591, e.g. on x-hkp://pool.sks-keyservers.net

signature.asc
Description: Digital signature