forum.alglib.net

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)

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.

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.

I'm glad to hear! Can you provide a code snippet demonstrating this successful run? It would be greatly appreciated.

Hi! Can you post your snippet? Maybe I will be able to find out what exactly went wrong.

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

Hi!


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

It works! Thanks a million!