# forum.alglib.net

ALGLIB forum
 It is currently Fri Jun 22, 2018 10:26 pm

 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.

 Page 1 of 1 [ 8 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Simple 4-D QP (SVM) problem fails to produce resultPosted: Mon Feb 05, 2018 10:22 am

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

 Post subject: Re: With non-commercial version quadratic Programming N > 2Posted: Mon Feb 05, 2018 5:01 pm

Joined: Fri May 07, 2010 7:06 am
Posts: 825
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.

Top

 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce resultPosted: Wed Feb 07, 2018 3:01 pm

Joined: Fri May 07, 2010 7:06 am
Posts: 825
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

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

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

 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce resultPosted: Fri Feb 09, 2018 3:36 pm

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

Top

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

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);
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.
//
// 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

 Post subject: Re: Simple 4-D QP (SVM) problem fails to produce resultPosted: Mon Feb 12, 2018 9:03 am

Joined: Fri May 07, 2010 7:06 am
Posts: 825
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

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

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

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 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 forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for: