Re: QP solves for zero instead of min?

[Juan Pablo Carbajal]

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.