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

Trival solvalble quadratic programming problem not solved...
http://forum.alglib.net/viewtopic.php?f=2&t=3830		 Page 1 of 1
Author:  zovnat [ Thu Jan 25, 2018 8:29 am ]
Post subject:  Trival solvalble quadratic programming problem not solved...
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]);
}
}
Author:  Sergey.Bochkanov [ Thu Jan 25, 2018 8:46 am ]
Post subject:  Re: Trival solvalble quadratic programming problem not solve
Hello!

Quote:
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


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 :)
Author:  Sergey.Bochkanov [ Thu Jan 25, 2018 8:48 am ]
Post subject:  Re: Trival solvalble quadratic programming problem not solve
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.
Author:  zovnat [ Thu Jan 25, 2018 9:27 am ]
Post subject:  Re: Trival solvalble quadratic programming problem not solve
Thanks!
Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/