[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: QP solves for zero instead of min?
From: |
Juan Pablo Carbajal |
Subject: |
Re: QP solves for zero instead of min? |
Date: |
Mon, 4 Aug 2014 12:10:17 +0200 |
On Sun, Aug 3, 2014 at 8:28 PM, Olaf Till <address@hidden> wrote:
> 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
No problem Olaf! Thanks for the answers, you force me to double check.
Is anybody here who knows how QP should handle rank deficient matrices?
I can't find a reference for QP having troubles there...maybe I am not
looking int he right place?
Any help is welcomed, and is rather important, QP is a highly used
algorithm we better have it right.
Here is an example that I do not understand why QP gives the zero if
the cost funtion instead of a minimum. If it is a bug it is triggered
when linear constraints are given.
x = randn(5,10);
H = x.'*x;
q = randn(10,1);
A = randn(1,10);
[a,obj,info] = qp(randn(10,1),H,q,A,0)
Clearly a solves the constraints but it doesn't minimize the cost, it
is just a root. Also the also info == 3 (Maximum number of iterations
reached).
Can it be that QP is incomplete in Octave?
The code of
libinterp/corefcn/__qp__.cc
Says (lines 233 234)
// FIXME: still remain to handle the case of
// non-full rank active set matrix.
- QP solves for zero instead of min?, Juan Pablo Carbajal, 2014/08/02
- Re: QP solves for zero instead of min?, Olaf Till, 2014/08/03
- Re: QP solves for zero instead of min?, Juan Pablo Carbajal, 2014/08/03
- Re: QP solves for zero instead of min?, Olaf Till, 2014/08/03
- Re: QP solves for zero instead of min?, Juan Pablo Carbajal, 2014/08/03
- Re: QP solves for zero instead of min?, Olaf Till, 2014/08/03
- Re: QP solves for zero instead of min?, Juan Pablo Carbajal, 2014/08/03
- Re: QP solves for zero instead of min?, Olaf Till, 2014/08/03
- Re: QP solves for zero instead of min?,
Juan Pablo Carbajal <=