# forum.alglib.net

ALGLIB forum
 It is currently Wed Feb 21, 2018 10:56 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.

 Page 1 of 1 [ 4 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Trival solvalble quadratic programming problem not solved...Posted: Thu Jan 25, 2018 8:29 am

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

 Post subject: Re: Trival solvalble quadratic programming problem not solvePosted: Thu Jan 25, 2018 8:46 am

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

 Post subject: Re: Trival solvalble quadratic programming problem not solvePosted: Thu Jan 25, 2018 8:48 am

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

 Post subject: Re: Trival solvalble quadratic programming problem not solvePosted: Thu Jan 25, 2018 9:27 am

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

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 4 posts ]

 All times are UTC

#### Who is online

Users browsing this forum: Bing [Bot] and 5 guests

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

Search for: