forum.alglib.net

ALGLIB forum
It is currently Mon Sep 24, 2018 10:24 am

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 8 posts ] 
Author Message
 Post subject: Simple 4-D QP (SVM) problem fails to produce result
PostPosted: Mon Feb 05, 2018 10:22 am 
Offline

Joined: Thu Jan 25, 2018 7:38 am
Posts: 11
I was unsuccessful solving linearly separable SVM problems having dimension > 2 (and succeeded with dimension = 2).
I created various synthetic SVM problems of higher dimensions - in which for the first dimension of N-dimensional points - the values are clearly separated - and the other dimensions have random values or all set equal to one.
In all cases when the dimensionality exceeds 2 neither minqsetalgobleic nor minqpsetalgodensaul converge (basically return with code 2 and junk values).

Here is a sample problem:

Consider a trivial SVM problem in 3-D space with four training points pi, i=0..3
and the first 2 belong to class 1 and the other two to class -1:

P0 = (x=2, y=2, z=3), Y0=1
P1 = (x=2, y=3, z=3), Y1=1
P2 = (x=2, y=2, z=1), Y2=-1
P3 = (x=2, y=3, z=1), Y3=-1

The plane z=2 separates the training points {p0, p1} from {p2, p3}.

I would imagine that this represents a solvable QP problem (but I've been wrong before...).

The Dual form of the linearly separable SVM problem is:

Maximize in Xi, sigma(Xi, i=0..3) - 0.5 * sigma(Xi*Xj*Yi*Yj*<Pi.Pj>, i=0..3, j=0..3)
where <pi.pj> is the 3-D inner product between the vectors Pi & Pj
and Xi >= 0, i=0..3
and sigma(Xi*Yi, i=0..3) = 0

In order to use Alglib 'bleic' or 'denseaul' the problem becomes:

Maximize in Xi, sigma(-Xi, i=0..3) + 0.5 * sigma(Xi*Xj*Yi*Yj*<Pi.Pj>, i=0..3, j=0..3)
where Xi >= 0, i=0..3
sigma(Xi*Yi, i=0..3) = 0

f(X) = 0.5*X'*A*X + B'*X ==> minimum
subject to:
Xi >= 0, i=0..3
sigma(Xi*Yi, i=0..3) = 0

The 4 x 4 quadratic matrix 'A' becomes:
0 1 2 3
---------------------------------------
0 17.00 19.00 -11.00 -13.00
1 19.00 22.00 -13.00 -16.00
2 -11.00 -13.00 9.00 11.00
3 -13.00 -16.00 11.00 14.00

The 4-D linear vector 'B' becomes:
0 1 2 3
---------------------------------------
-1 -1 -1 -1

The constraint matrix 'c' & constraint type 'ct' are:
0 1 2 3 b type
------------------------------------------ ---
0 1 0 0 0 0 1 (X0 >= 0)
1 0 1 0 0 0 1 (X1 >= 0)
2 0 0 1 0 0 1 (X2 >= 0)
3 0 0 0 1 0 1 (X3 >= 0)
4 1 1 -1 -1 0 0 (X0+X1-X2-X3 = 0)

minqpsetalgobleic() returns with terminationtype -3 (of course with junk Xi values)
minqpsetalgodenseaul() returns with terminationtype 2 (with junk Xi values)


Last edited by zovnat on Wed Feb 07, 2018 10:17 am, edited 2 times in total.

Top
 Profile  
 
 Post subject: Re: With non-commercial version quadratic Programming N > 2
PostPosted: Mon Feb 05, 2018 5:01 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 826
Hi!

1. ALGLIB QP solvers definitely support dimensions larger than 2. Any QP solver must support dimensions larger than 2. Why would anyone need QP solver which can not handle 100-dimensional or 1000-dimensional problem????????

2. The most likely reason behind such "errors" is that you got something wrong. Say, you solved maximization problem and forgot to convert it to minimization one before passing data to ALGLIB. Or did not account for non-convexity of your QP problem. Or something else.

If you want, you may write more about your QP problem. It is hard to debug it without having more information.


Top
 Profile  
 
 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce result
PostPosted: Wed Feb 07, 2018 3:01 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 826
Hi!

1. Would you like to leave previous posts unchanged, and reply with completely new ones? You edited your previous post instead of producing new one, so this conversation become a bit fragmented.

2. I just tried your example, with all the data provided by you, and got (X0,X1,X2,X3)=(1/4, 1/4, 1/4, 1/4) with both QP-BLEIC and QP-DENSE-AUL solvers. According to formulae by wikipedia, it results in completely expected weight vector (0, 0, 1) which perfectly separates dataset.

My conclusion: something is wrong with your code which uses ALGLIB, not with ALGLIB itself. Did you initialize matrices correctly?

Note: in C++ they are not initialized by zero defaults, you have to zero-fill then yourself. Just for the case it is relevant...

3. By the way, it is much better so specify non-negativity constraints by means of minqpsetbc() call - it results in much faster solves and better stability. However, when I tried your data, I used minqpsetlc() in order to reproduce your setup - and still it worked.


Top
 Profile  
 
 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce result
PostPosted: Thu Feb 08, 2018 6:22 am 
Offline

Joined: Thu Jan 25, 2018 7:38 am
Posts: 11
I'm glad to hear! Can you provide a code snippet demonstrating this successful run? It would be greatly appreciated.


Top
 Profile  
 
 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce result
PostPosted: Fri Feb 09, 2018 3:36 pm 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 826
Hi! Can you post your snippet? Maybe I will be able to find out what exactly went wrong.


Top
 Profile  
 
 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce result
PostPosted: Sun Feb 11, 2018 6:09 am 
Offline

Joined: Thu Jan 25, 2018 7:38 am
Posts: 11
Here it is; I didn't provide the fuction ir_svn(&pa, &pb, &pc, &pct, &ps, &px) - but the output - below - shows what input to QP was provided...
-------------------------------------------------------------------------------------------
// AlgLib.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <windows.h>
#include "src\optimization.h"

extern int ir_svn(double **pa, double **pb, double **pc, int **pct, double **ps, double **px);
extern void TestSolution(double *x, double *pa, double *pb);

using namespace alglib;

int _tmain(int argc, _TCHAR* argv[])
{
try
{
//
// This example demonstrates minimization of F(x0,x1) = x0^2 + x1^2 -6*x0 - 4*x1
// subject to linear constraint x0+x1<=2
//
// Exact solution is [x0,x1] = [1.5,0.5]
//
// IMPORTANT: this solver minimizes following function:
// f(x) = 0.5*x'*A*x + b'*x.
// Note that quadratic term has 0.5 before it. So if you want to minimize
// quadratic function, you should rewrite it in such way that quadratic term
// is multiplied by 0.5 too.
// For example, our function is f(x)=x0^2+x1^2+..., but we rewrite it as
// f(x) = 0.5*(2*x0^2+2*x1^2) + ....
// and pass diag(2,2) as quadratic term - NOT diag(1,1)!
//
double *pa, *pb, *pc, *ps, *px;
int *pct;

int N = ir_svn(&pa, &pb, &pc, &pct, &ps, &px);

real_2d_array a;
a.setcontent(N, N, pa);

real_1d_array b;
b.setcontent(N, pb);

real_1d_array s;
s.setcontent(N, ps);

real_2d_array c;
c.setcontent(N + 1, N + 1, pc);

integer_1d_array ct;
ct.setcontent(N + 1, pct);

real_1d_array x;
x.setcontent(N, px);

if(N <= 4)
{
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
printf("\ta[%u][%u] = %f", i, j, a[i][j]);
}
printf("\tb[%u] = %f\n", i, b[i]);
}
for(int i=0; i<N+1; i++)
{
for(int j=0; j<N+1; j++)
{
printf("\tc[%u][%u] = %f", i, j, c[i][j]);
}
printf("\tct[%u] = %u\n", i, ct[i]);
}
}

minqpstate state;
minqpreport rep;

// create solver, set quadratic/linear terms
minqpcreate(2, state);
minqpsetquadraticterm(state, a);
minqpsetlinearterm(state, b);
minqpsetlc(state, c, ct);

// Set scale of the parameters.
// It is strongly recommended that you set scale of your variables.
// Knowing their scales is essential for evaluation of stopping criteria
// and for preconditioning of the algorithm steps.
// You can find more information on scaling at http://www.alglib.net/optimization/scaling.php
//
// NOTE: for convex problems you may try using minqpsetscaleautodiag()
// which automatically determines variable scales.
minqpsetscale(state, s);

//
// Solve problem with BLEIC-based QP solver.
//
// This solver is intended for problems with moderate (up to 50) number
// of general linear constraints and unlimited number of box constraints.
//
// Default stopping criteria are used.
//

minqpsetalgobleic(state, 0.0, 0.0, 0.0, 0);
//minqpsetalgodenseaul(state, 1.0e-9, 1.0e+4, 5);

minqpoptimize(state);
minqpresults(state, x, rep);
printf("inneriterationscount %u\n"
"ncholesky %u, nmv %u\n"
"outeriterationscount %u\n"
"terminationtype %d\n"
, rep.inneriterationscount, rep.ncholesky, rep.nmv, rep.outeriterationscount, rep.terminationtype);
if(rep.terminationtype >= 0 && rep.terminationtype <= 4)
{
for(int i=0; i<N; i++)
printf("x[%u] = %f\n", i, x[i]);
}

getchar();
}
catch(ap_error)
{
printf("Exception!\n");
getchar();
}
return 0;
}

Output: -----------------------------------------------------------------------

a[0][0] = 17.000000 a[0][1] = 19.000000 a[0][2] = -11.000000 a[0][3] = -13.000000 b[0] = -1.000000
a[1][0] = 19.000000 a[1][1] = 22.000000 a[1][2] = -13.000000 a[1][3] = -16.000000 b[1] = -1.000000
a[2][0] = -11.000000 a[2][1] = -13.000000 a[2][2] = 9.000000 a[2][3] = 11.000000 b[2] = -1.000000
a[3][0] = -13.000000 a[3][1] = -16.000000 a[3][2] = 11.000000 a[3][3] = 14.000000 b[3] = -1.000000
c[0][0] = 1.000000 c[0][1] = 0.000000 c[0][2] = 0.000000 c[0][3] = 0.000000 c[0][4] = 0.000000 ct[0] = 1
c[1][0] = 0.000000 c[1][1] = 1.000000 c[1][2] = 0.000000 c[1][3] = 0.000000 c[1][4] = 0.000000 ct[1] = 1
c[2][0] = 0.000000 c[2][1] = 0.000000 c[2][2] = 1.000000 c[2][3] = 0.000000 c[2][4] = 0.000000 ct[2] = 1
c[3][0] = 0.000000 c[3][1] = 0.000000 c[3][2] = 0.000000 c[3][3] = 1.000000 c[3][4] = 0.000000 ct[3] = 1
c[4][0] = 1.000000 c[4][1] = 1.000000 c[4][2] = -1.000000 c[4][3] = -1.000000 c[4][4] = 0.000000 ct[4] = 0
x[0] = 0.750000 x[1] = 0.750000 x[2] = 0.750000 x[3] = 0.750000
inneriterationscount 0
ncholesky 0, nmv 0
outeriterationscount 0
terminationtype -3


Top
 Profile  
 
 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce result
PostPosted: Mon Feb 12, 2018 9:03 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 826
Hi!

Code:
minqpcreate(2, state);

The problem is here. You created optimizer for 2-dimensional problems, so it silently truncates everything beyond two dimensions. In particular, your constraints become "1*x0 + 0*x1 = 0; 0*x0 + 1*x1 = 0; 0*x0 + 0*x1 = 1", which is clearly infeasible (hence -3 is returned by QP-BLEIC solver).


Top
 Profile  
 
 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce result
PostPosted: Mon Feb 12, 2018 9:08 am 
Offline

Joined: Thu Jan 25, 2018 7:38 am
Posts: 11
It works! Thanks a million!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group