forum.alglib.net

AlgLib's sample - works! - my well-defined solvable problem doesn't - see source code below...
// 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]
//
real_2d_array a = "[[2,0],[0,2]]";
real_1d_array b = "[-6,-4]";
real_1d_array s = "[1,1]";
real_2d_array c = "[[1.0,1.0,2.0]]";
integer_1d_array ct = "[-1]";
real_1d_array x;

My sample - perfectly well defined 'succeeds' with junk result [0.0,0.0] with bleic or denseaul.
Am I doing something wrong?
// minimization of F(x0,x1) = (-5*x0^2 + 16*x0*x1 - 13*x1^2) / 2 + x0 + x1
// subject to linear constraint x0+x1=0 and to x0>=0, x1>=0
//
// Exact solution is [x0,x1] = [1.0,1.0]
//
real_2d_array a = "[[-5,8],[8,-13]]";
real_1d_array b = "[1,1]";
real_1d_array s = "[1,1]";
real_2d_array c = "[[1,0,0],[0,1,0],[1,-1,0]]";
integer_1d_array ct = "[1,1,0]";
real_1d_array x = "[0.85,0.85]";

inneriterationscount 0
ncholesky 0, nmv 0
outeriterationscount 0
terminationtype 4


. . .

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.

/*
AlgLib's sample - works!
real_2d_array a = "[[2,0],[0,2]]";
real_1d_array b = "[-6,-4]";
real_1d_array s = "[1,1]";
real_2d_array c = "[[1.0,1.0,2.0]]";
integer_1d_array ct = "[-1]";
real_1d_array x;
*/

/*
My sample - perfectly well defined, with solution [1.0,1.0]
'succeeds' with junk result [0.0,0.0]
inneriterationscount 0
ncholesky 0, nmv 0
outeriterationscount 0
terminationtype 4
*/

real_2d_array a = "[[-5,8],[8,-13]]";
real_1d_array b = "[1,1]";
real_1d_array s = "[1,1]";
real_2d_array c = "[[1,0,0],[0,1,0],[1,-1,0]]";
integer_1d_array ct = "[1,1,0]";
real_1d_array x = "[0.85,0.85]";

minqpstate state;
minqpreport rep;

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

minqpsetscale(state, s);

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);
for(int i=0; i<N; i++)
printf("x[%u] = %f\n", i, x[i]);
}
}

Hello!



Not actually well defined, and nevertheless - it is solved exactly :))

1. Your QP problem is non-convex (negative eigenvalues in quadratic term), thus it may have multiple local extrema. Convergence to the "true" global solution is not guaranteed. However, solver converged.

2. Your problem statement above tells that constraints are "x0+x1=0 and to x0>=0, x1>=0". However, actual problem specification in program code is "x0=x1 and to x0>=0, x1>=0". You should take it into account.

3. Let's compare function values in the candidate points. ALGLIB: F(x0=0,x1=0)=0. Proposed by you: F(x0=1,x1=1)=1. F_alglib<F_yourchoice. ALGLIB wins :)

I just thought that you may wanted to maximize F instead of minimizing it. In this case, x0=x1=1 is a solution. But you should replace A by -A, b by -b in your problem specification, because ALGLIB QP solver performs only minimization.

Thanks!