Solver founds no solution though it should about quadprog

[albertosantini]

Did you notice the arrays are based one-index?
See, for instance, the tests how to setup correctly the inputs.

Hope that helps you.

Otherwise I need the js test you run to reproduce the issue and the R script to compare the results.

Edit - Generally speaking, here there is an issue if the figures of R quadprog and Node.js quadprog are different. Maybe you would expect the message constraints are inconsistent, no solution!.
However check also the dimensions of the inputs (Amat, for instance, is 6x15, I think, otherwise dvec and Amat are incompatible) and you need to insert the values by column in js.

For instance, in R

R version 3.2.2 (2015-08-14) -- "Fire Safety"
Copyright (C) 2015 The R Foundation for Statistical Computing
Platform: x86_64-w64-mingw32/x64 (64-bit)

R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.

  Natural language support but running in an English locale

R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.

Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for an HTML browser interface to help.
Type 'q()' to quit R.

> require(quadprog)
Loading required package: quadprog
> 
> Dmat <- matrix(0,6,6)
> diag(Dmat) <- 2
> dvec <- c(-10,-10,-30,-20,-30,-20)
> Amat <- matrix(c(1,-1,0,0,0,0,-1,0,0,1,0,0,0,0,0,   0,0,1,-1,0,0,-1,0,0,0,1,0,0,0,0,   0,0,1,-1,0,0,0,-1,0,0,0,1,0,0,0,   0,0,1,-1,0,0,0,0,-1,0,0,0,1,0,0,   0,0,0,0,1,-1,0,-1,0,0,0,0,0,1,0,   0,0,0,0,1,-1,0,0,-1,0,0,0,0,0,1), 6,15)
> bvec <- c(3.999,-4.001,4.999,-5.001,0.999,-1.001,-7.001,-1.001,-2.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001)
> 
> solve.QP(Dmat,dvec,Amat,bvec=bvec)
Error in solve.QP(Dmat, dvec, Amat, bvec = bvec) : 
  constraints are inconsistent, no solution!
> Dmat
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    2    0    0    0    0    0
[2,]    0    2    0    0    0    0
[3,]    0    0    2    0    0    0
[4,]    0    0    0    2    0    0
[5,]    0    0    0    0    2    0
[6,]    0    0    0    0    0    2
> dvec
[1] -10 -10 -30 -20 -30 -20
> Amat
     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,]    1   -1    0   -1    0    0    0    0   -1     0     0     0     0     0
[2,]   -1    0    0    0    1    0   -1    0    0     0     0    -1     1     1
[3,]    0    0    0    0    0    1    0    0    0     0     0     0     0    -1
[4,]    0    1    0   -1    0   -1    0    0    0     1     0     0     0     0
[5,]    0    0    0    0    0    0    0    0    0     0     1     0     0     0
[6,]    0    0    1    0    0    0    1    1   -1     0    -1     0     0    -1
     [,15]
[1,]     0
[2,]     0
[3,]     0
[4,]     0
[5,]     0
[6,]     1
> bvec
 [1]  3.999 -4.001  4.999 -5.001  0.999 -1.001 -7.001 -1.001 -2.001 -0.001
[11] -0.001 -0.001 -0.001 -0.001 -0.001
> 

In javascript,

    require("quadprog");

    var dmat = [], dvec = [], amat = [], bvec = [];

    dmat = JSON.parse("[null,[null,2,0,0,0,0,0],[null,0,2,0,0,0,0],[null,0,0,2,0,0,0],[null,0,0,0,2,0,0],[null,0,0,0,0,2,0],[null,0,0,0,0,0,2]]");
    dvec = JSON.parse("[null,-10,-10,-30,-20,-30,-20]");
    amat = JSON.parse("[null,[null,1,-1,0,0,0,0],[null,-1,0,0,1,0],[null,0,0,0,0,0,1],[null,-1,0,0,-1,0,0],[null,0,1,0,0,0,0],[null,0,0,1,-1,0,0],[null,0,-1,0,0,0,1],[null,0,0,0,0,0,1],[null,-1,0,0,0,0,-1],[null,0,0,0,1,0,0],[null,0,0,0,0,1,-1],[null,0,-1,0,0,0,0],[null,0,1,0,0,0,0],[null,0,1,-1,0,0,-1],[null,0,0,0,0,0,1]]");
    bvec = JSON.parse("[null,3.999,-4.001,4.999,-5.001,0.999,-1.001,-7.001,-1.001,-2.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001]");

    qp.solveQP(dmat, dvec, amat, bvec);

The response

[ undefined, 1 ]
{ solution:
   [ ,
     -4.999999999999999,
     -4.999999999999999,
     -14.999999999999996,
     -9.999999999999998,
     -14.999999999999996,
     -9.999999999999998 ],
  Lagrangian: [ , 0, 0, 0, 0, 0, 0 ],
  value: [ , -699.9999999999999 ],
  unconstrained_solution:
   [ null,
     -4.999999999999999,
     -4.999999999999999,
     -14.999999999999996,
     -9.999999999999998,
     -14.999999999999996,
     -9.999999999999998 ],
  iterations: [ , 1, 0 ],
  iact: [ , 0, 0, 0, 0, 0, 0 ],
  message: 'constraints are inconsistent, no solution!' }
 }

Eventually you need always to double check with R.

[castek]

Hello,
I used to compare it with accord, they ported the same fortran code of goldfarb-idnani to c# as you did. I think inputs are well formed (Amat transposition, arrays starting from 1). I tried several thousands of solvable tasks and node-quadprog finds solution only in around 80 % of cases. Accord finds solution in 97 % of my tasks. I need to find solution in 100% of solvable tasks on javascript (I used c# accord only for comparison). Here I attached the same example in javascript as well as in R. Though amat seems to be different, they are equal in both languages, only tranformed.
javascript_R_QP.txt
R script found correct solution. Javascript returned NaNs.

[albertosantini]

Thanks for the details. Nice catch.

I am afraid I need to investigate in depth to find the bug.
I need to compare step by step, iteration by iteration where is the difference.

Edit: I report here the content of that attachment.

-- javascript ----

require("quadprog");

var dmat = JSON.parse("[[],[0,2,0,0,0,0,0],[0,0,2,0,0,0,0],[0,0,0,2,0,0,0],[0,0,0,0,2,0,0],[0,0,0,0,0,2,0],[0,0,0,0,0,0,2]]");
var dvec = JSON.parse("[0,-10,-10,-30,-20,-30,-20]");
var amat = JSON.parse("[[],[0,1,-1,0,0,0,0,-1,0,0,1,0,0,0,0,0],[0,0,0,1,-1,0,0,-1,0,0,0,1,0,0,0,0],[0,0,0,1,-1,0,0,0,-1,0,0,0,1,0,0,0],[0,0,0,1,-1,0,0,0,0,-1,0,0,0,1,0,0],[0,0,0,0,0,1,-1,0,-1,0,0,0,0,0,1,0],[0,0,0,0,0,1,-1,0,0,-1,0,0,0,0,0,1]]");
var bvec = JSON.parse("[0,3.999,-4.001,4.999,-5.001,0.999,-1.001,-7.001,-1.001,-2.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001]");

var out = qp.solveQP(dmat, dvec, amat, bvec);
JSON.stringify(out)
"{"solution":[null,null,null,null,null,null,null],"Lagrangian":[null,null,0,null,0,null,0,0,0,0,0,0,0,0,null,0],"value":[null,null],"unconstrained_solution":[0,-4.999999999999999,-4.999999999999999,-14.999999999999996,-9.999999999999998,-14.999999999999996,-9.999999999999998],"iterations":[null,6,1],"iact":[null,3,5,1,14,0,0,0,0,0,0,0,0,0,0,0],"message":""}"

----- R ----

> Dmat <- matrix(0,6,6)
> dvec <- c(-10,-10,-30,-20,-30,-20)
> diag(Dmat) <- 2
> bvec <- c(3.999,-4.001,4.999,-5.001,0.999,-1.001,-7.001,-1.001,-2.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001)
> Amat <- matrix(c(1,0,0,0,0,0, -1,0,0,0,0,0, 0,1,1,1,0,0, 0,-1,-1,-1,0,0, 0,0,0,0,1,1, 0,0,0,0,-1,-1, -1,-1,0,0,0,0, 0,0,-1,0,-1,0, 0,0,0,-1,0,-1, 1,0,0,0,0,0, 0,1,0,0,0,0, 0,0,1,0,0,0, 0,0,0,1,0,0, 0,0,0,0,1,0, 0,0,0,0,0,1), 6,15)
> solve.QP(Dmat,dvec,Amat,bvec)
$solution
[1] 3.999 3.002 0.747 1.250 0.248 0.751

$value
[1] 167.63

$unconstrained.solution
[1]  -5  -5 -15 -10 -15 -10

$iterations
[1] 8 2

$Lagrangian
 [1] 33.488  0.000 31.494  0.000 30.496  0.000 15.490  0.000  8.994  0.000  0.000  0.000
[13]  0.000  0.000  0.000

$iact
[1] 3 5 1 7 9

[castek]

In fact I would like to solve this "analytic" task (Dmat and dvec are the same as above):

Amat <- matrix(c(1,0,0,0,0,0, 0,1,1,1,0,0, 0,0,0,0,1,1, -1,-1,0,0,0,0, 0,0,-1,0,-1,0, 0,0,0,-1,0,-1, 1,0,0,0,0,0, 0,1,0,0,0,0, 0,0,1,0,0,0, 0,0,0,1,0,0, 0,0,0,0,1,0, 0,0,0,0,0,1), 6,12)
bvec <- c(4,5,1,-7,-1,-2,0,0,0,0,0,0)
solve.QP(Dmat,dvec,Amat,bvec,3)

var amat = JSON.parse("[[],[0,1,0,0,-1,0,0,1,0,0,0,0,0],[0,0,1,0,-1,0,0,0,1,0,0,0,0],[0,0,1,0,0,-1,0,0,0,1,0,0,0],[0,0,1,0,0,0,-1,0,0,0,1,0,0],[0,0,0,1,0,-1,0,0,0,0,0,1,0],[0,0,0,1,0,0,-1,0,0,0,0,0,1]]");
var bvec = JSON.parse("[0,4,5,1,-7,-1,-2,0,0,0,0,0,0]");

var out = solveQP(dmat, dvec, amat, bvec,3);

R is not able to solve it (R says 'constraints are inconsistent, no solution!').
So I had to change the "analytical" task to "numerical":

Amat <- matrix(c(1,0,0,0,0,0, 0,1,1,1,0,0, 0,0,0,0,1,1, -1,-1,0,0,0,0, 0,0,-1,0,-1,0, 0,0,0,-1,0,-1, 1,0,0,0,0,0, 0,1,0,0,0,0, 0,0,1,0,0,0, 0,0,0,1,0,0, 0,0,0,0,1,0, 0,0,0,0,0,1), 6,12)
bvec <- c(4,5,1,-7.001,-1.001,-2.001,0,0,0,0,0,0)
solve.QP(Dmat,dvec,Amat,bvec,3)

var amat = JSON.parse("[[],[0,1,0,0,-1,0,0,1,0,0,0,0,0],[0,0,1,0,-1,0,0,0,1,0,0,0,0],[0,0,1,0,0,-1,0,0,0,1,0,0,0],[0,0,1,0,0,0,-1,0,0,0,1,0,0],[0,0,0,1,0,-1,0,0,0,0,0,1,0],[0,0,0,1,0,0,-1,0,0,0,0,0,1]]");
var bvec = JSON.parse("[0,4,5,1,-7.001,-1.001,-2.001,0,0,0,0,0,0]");

var out = solveQP(dmat, dvec, amat, bvec,3);

R solves this correctly, javascript not.

So I modified it finally with other two steps:

1. equalities are replaced by pairs of inequalities with 2*epsilon tolerance
2. x(i) >= 0 are replaced by x(i) >= -epsilon
   For most tasks this helped to be solved also in javascript, but around 20% of tasks these modifications are not enough. Modified task can be seen two comments above.

[albertosantini]

Please, give a try to the master, it is fixed there.
Javascript and R give the same results.

If it is ok for you, in a few hours I publish a new release.

[albertosantini]

As you saw, fourth and fifth tests reproduce the examples you provided in this issue.
Both tests have the same results as well as in R examples.

Thanks a lot for your feedback.

[castek]

100% of tasks have been solved. It works perfectly! Thanks a lot.

[castek]

third and fifth tests address this issue. fourth seems to be something else.

[albertosantini]

Published 1.4.0.

Thanks a lot for the snippets.