{"action":"created","issue":{"url":"https://api.github.com/repos/albertosantini/node-quadprog/issues/4","labels_url":"https://api.github.com/repos/albertosantini/node-quadprog/issues/4/labels{/name}","comments_url":"https://api.github.com/repos/albertosantini/node-quadprog/issues/4/comments","events_url":"https://api.github.com/repos/albertosantini/node-quadprog/issues/4/events","html_url":"https://github.com/albertosantini/node-quadprog/issues/4","id":120990615,"number":4,"title":"Solver founds no solution though it should","user":{"login":"castek","id":15982110,"avatar_url":"https://avatars.githubusercontent.com/u/15982110?v=3","gravatar_id":"","url":"https://api.github.com/users/castek","html_url":"https://github.com/castek","followers_url":"https://api.github.com/users/castek/followers","following_url":"https://api.github.com/users/castek/following{/other_user}","gists_url":"https://api.github.com/users/castek/gists{/gist_id}","starred_url":"https://api.github.com/users/castek/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/castek/subscriptions","organizations_url":"https://api.github.com/users/castek/orgs","repos_url":"https://api.github.com/users/castek/repos","events_url":"https://api.github.com/users/castek/events{/privacy}","received_events_url":"https://api.github.com/users/castek/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":4,"created_at":"2015-12-08T11:44:32Z","updated_at":"2015-12-10T09:22:25Z","closed_at":null,"body":"Hello,\r\nI'm using your QP. I have a set of solvable inputs. With the solver I get around 20% failure when output.Solution contains NaN. How can I tune (some threshold) the accuracy of the solver, so that I can get solution in 100% of solvable inputs?\r\n\r\nMy inputs are in format of \r\nminimize 1/2 * x^T D x + d^T x\r\nwhere A x >= b\r\n\r\nI'm calling:\r\nvar output = solveQP(Dmat, dvec, Amat, bvec, meq, factorized);\r\n\r\nOne example of solvable input that returns NaN:\r\nJSON.stringify(Dmat)\r\n\"[[],[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]]\"\r\nJSON.stringify(dvec)\r\n\"[0,-10,-10,-30,-20,-30,-20]\"\r\nJSON.stringify(Amat)\r\n\"[[],[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]]\"\r\nJSON.stringify(bvec)\r\n\"[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]\"\r\nJSON.stringify(meq)\r\n\"0\"\r\nJSON.stringify(factorized)\r\n\"[0,0]\"\r\nThis returns:\r\nfactorized = [0, 0]\r\noutput = {\"solution\":[,NaN,NaN,NaN,NaN,NaN,NaN],\"Lagrangian\":[,NaN,0,NaN,0,NaN,0,0,0,0,0,0,0,0,NaN,0],\"value\":[,NaN],\"unconstrained_solution\":[0,-4.999999999999999,-4.999999999999999,-14.999999999999996,-9.999999999999998,-14.999999999999996,-9.999999999999998],\"iterations\":[,6,1],\"iact\":[,3,5,1,14,0,0,0,0,0,0,0,0,0,0,0],\"message\":\"\"}\r\n\r\nIf there is more than one possible solution with equal minimum value, it's enough to get any solution.\r\n\r\nThe constraints are of three types:\r\n1) x2 + x3 + x4 = 5,\r\nthis returned NaNs for many inputs, so I substituted it with two inequalities:\r\nx2 + x3 + x4 >= 4.999 and\r\nx2 + x3 + x4 <= 5.001\r\nThis substitution helped a lot.\r\n2) sum of some variables <= some positive integer (eg. 7 as in bvec[7])\r\nthis I substituted with:\r\nsum of some variables <= some positive integer + epsilon\r\neg.\r\nsum of some variables <= 7.001\r\n3) each variable >= 0\r\nthat I substituted with:\r\neach variable >= -epsilon\r\neg.\r\neach variable >= -0.001\r\n\r\nThe best I would like to get only integers in solution but I'm noticed you wrote the solver that returns reals."},"comment":{"url":"https://api.github.com/repos/albertosantini/node-quadprog/issues/comments/163542692","html_url":"https://github.com/albertosantini/node-quadprog/issues/4#issuecomment-163542692","issue_url":"https://api.github.com/repos/albertosantini/node-quadprog/issues/4","id":163542692,"user":{"login":"castek","id":15982110,"avatar_url":"https://avatars.githubusercontent.com/u/15982110?v=3","gravatar_id":"","url":"https://api.github.com/users/castek","html_url":"https://github.com/castek","followers_url":"https://api.github.com/users/castek/followers","following_url":"https://api.github.com/users/castek/following{/other_user}","gists_url":"https://api.github.com/users/castek/gists{/gist_id}","starred_url":"https://api.github.com/users/castek/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/castek/subscriptions","organizations_url":"https://api.github.com/users/castek/orgs","repos_url":"https://api.github.com/users/castek/repos","events_url":"https://api.github.com/users/castek/events{/privacy}","received_events_url":"https://api.github.com/users/castek/received_events","type":"User","site_admin":false},"created_at":"2015-12-10T09:22:25Z","updated_at":"2015-12-10T09:22:25Z","body":"In fact I would like to solve this \"analytic\" task (Dmat and dvec are the same as above):\r\n```\r\nAmat <- 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)\r\nbvec <- c(4,5,1,-7,-1,-2,0,0,0,0,0,0)\r\nsolve.QP(Dmat,dvec,Amat,bvec,3)\r\n```\r\n\r\n```javascript\r\nvar 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]]\");\r\nvar bvec = JSON.parse(\"[0,4,5,1,-7,-1,-2,0,0,0,0,0,0]\");\r\n\r\nvar out = solveQP(dmat, dvec, amat, bvec,3);\r\n```\r\nR is not able to solve it (R says 'constraints are inconsistent, no solution!').\r\nSo I had to change the \"analytical\" task to \"numerical\":\r\n```\r\nAmat <- 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)\r\nbvec <- c(4,5,1,-7.001,-1.001,-2.001,0,0,0,0,0,0)\r\nsolve.QP(Dmat,dvec,Amat,bvec,3)\r\n```\r\n\r\n```javascript\r\nvar 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]]\");\r\nvar bvec = JSON.parse(\"[0,4,5,1,-7.001,-1.001,-2.001,0,0,0,0,0,0]\");\r\n\r\nvar out = solveQP(dmat, dvec, amat, bvec,3);\r\n```\r\nR solves this correctly, javascript not.\r\n\r\nSo I modified it finally with other two steps:\r\n1) equalities are replaced by pairs of inequalities with 2*epsilon tolerance\r\n2) x(i) >= 0 are replaced by x(i) >= -epsilon\r\nFor 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.\r\n"}}