forum.alglib.net http://forum.alglib.net/ 

Simple 4D QP (SVM) problem fails to produce result http://forum.alglib.net/viewtopic.php?f=2&t=3840 
Page 1 of 1 
Author:  zovnat [ Mon Feb 05, 2018 10:22 am ] 
Post subject:  Simple 4D QP (SVM) problem fails to produce result 
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 Ndimensional 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 3D 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 3D 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 4D 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+X1X2X3 = 0) minqpsetalgobleic() returns with terminationtype 3 (of course with junk Xi values) minqpsetalgodenseaul() returns with terminationtype 2 (with junk Xi values) 
Author:  Sergey.Bochkanov [ Mon Feb 05, 2018 5:01 pm ] 
Post subject:  Re: With noncommercial version quadratic Programming N > 2 
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 100dimensional or 1000dimensional 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 nonconvexity 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. 
Author:  Sergey.Bochkanov [ Wed Feb 07, 2018 3:01 pm ] 
Post subject:  Re: Simple 4D QP (SVM) problem fails to produce result 
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 QPBLEIC and QPDENSEAUL 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 zerofill then yourself. Just for the case it is relevant... 3. By the way, it is much better so specify nonnegativity 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. 
Author:  zovnat [ Thu Feb 08, 2018 6:22 am ] 
Post subject:  Re: Simple 4D QP (SVM) problem fails to produce result 
I'm glad to hear! Can you provide a code snippet demonstrating this successful run? It would be greatly appreciated. 
Author:  Sergey.Bochkanov [ Fri Feb 09, 2018 3:36 pm ] 
Post subject:  Re: Simple 4D QP (SVM) problem fails to produce result 
Hi! Can you post your snippet? Maybe I will be able to find out what exactly went wrong. 
Author:  zovnat [ Sun Feb 11, 2018 6:09 am ] 
Post subject:  Re: Simple 4D QP (SVM) problem fails to produce result 
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 BLEICbased 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.0e9, 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 
Author:  Sergey.Bochkanov [ Mon Feb 12, 2018 9:03 am ] 
Post subject:  Re: Simple 4D QP (SVM) problem fails to produce result 
Hi! Code: minqpcreate(2, state); The problem is here. You created optimizer for 2dimensional 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 QPBLEIC solver). 
Author:  zovnat [ Mon Feb 12, 2018 9:08 am ] 
Post subject:  Re: Simple 4D QP (SVM) problem fails to produce result 
It works! Thanks a million! 
Page 1 of 1  All times are UTC 
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ 