forum.alglib.net

ALGLIB forum
It is currently Mon May 21, 2018 6:45 pm

All times are UTC


Forum rules


1. This forum can be used for discussion of both ALGLIB-related and general numerical analysis questions
2. This forum is English-only - postings in other languages will be removed.



Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Trival solvalble quadratic programming problem not solved...
PostPosted: Thu Jan 25, 2018 8:29 am 
Offline

Joined: Thu Jan 25, 2018 7:38 am
Posts: 11
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]);
}
}


Top
 Profile  
 
 Post subject: Re: Trival solvalble quadratic programming problem not solve
PostPosted: Thu Jan 25, 2018 8:46 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 822
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 :)


Top
 Profile  
 
 Post subject: Re: Trival solvalble quadratic programming problem not solve
PostPosted: Thu Jan 25, 2018 8:48 am 
Offline
Site Admin

Joined: Fri May 07, 2010 7:06 am
Posts: 822
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.


Top
 Profile  
 
 Post subject: Re: Trival solvalble quadratic programming problem not solve
PostPosted: Thu Jan 25, 2018 9:27 am 
Offline

Joined: Thu Jan 25, 2018 7:38 am
Posts: 11
Thanks!


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group