forum.alglib.nethttp://forum.alglib.net/ Simple 4-D QP (SVM) problem fails to produce resulthttp://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 4-D 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 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..3and the first 2 belong to class 1 and the other two to class -1:P0 = (x=2, y=2, z=3), Y0=1P1 = (x=2, y=3, z=3), Y1=1P2 = (x=2, y=2, z=1), Y2=-1P3 = (x=2, y=3, z=1), Y3=-1The 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*, i=0..3, j=0..3) where is the 3-D inner product between the vectors Pi & Pj and Xi >= 0, i=0..3 and sigma(Xi*Yi, i=0..3) = 0In 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*, i=0..3, j=0..3)where Xi >= 0, i=0..3sigma(Xi*Yi, i=0..3) = 0f(X) = 0.5*X'*A*X + B'*X ==> minimumsubject to: Xi >= 0, i=0..3 sigma(Xi*Yi, i=0..3) = 0The 4 x 4 quadratic matrix 'A' becomes: 0 1 2 3---------------------------------------0 17.00 19.00 -11.00 -13.001 19.00 22.00 -13.00 -16.002 -11.00 -13.00 9.00 11.003 -13.00 -16.00 11.00 14.00The 4-D linear vector 'B' becomes: 0 1 2 3--------------------------------------- -1 -1 -1 -1The 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)

 Author: Sergey.Bochkanov [ Mon Feb 05, 2018 5:01 pm ] Post subject: Re: With non-commercial 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 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.

 Author: Sergey.Bochkanov [ Wed Feb 07, 2018 3:01 pm ] Post subject: Re: Simple 4-D 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 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.

 Author: zovnat [ Thu Feb 08, 2018 6:22 am ] Post subject: Re: Simple 4-D 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 4-D 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 4-D 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 #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= 0 && rep.terminationtype <= 4) { for(int i=0; i

 Author: Sergey.Bochkanov [ Mon Feb 12, 2018 9:03 am ] Post subject: Re: Simple 4-D QP (SVM) problem fails to produce result 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).

 Author: zovnat [ Mon Feb 12, 2018 9:08 am ] Post subject: Re: Simple 4-D 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 Grouphttp://www.phpbb.com/