QP

[castek]

Hello,
I'm using accord's goldfarb idnani QP. I have a set of solvable inputs. With accord I get around 2% failure with "NoPossibleSolution" result. How can I tune (some threshold) the accuracy of the solver, so that I can get solution in 100% of solvable inputs?

My inputs are in format of
minimize 1/2 * x^T Q x + d^T x
where A x >= b

I'm calling:
var solver = new GoldfarbIdnani(Q, d,
A, b, Equalities);
solver.Minimize();

One example of solvable input that returns NoPossibleSolution:
{"Q":[2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2],"d":[3132,6264,15660,18792,21924,6264,18792,21924,9396,3132,12528,6264,9396,18792,21924,9396,3132,3132,6264,15660,18792],"A":[1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],"b":[703.999,-704.001,1267.999,-1268.001,1565.999,-1566.001,471.999,-472.001,1425.999,-1426.001,-107.001,-1164.001,-57.001,-311.001,-1433.001,-0.001,-0.001,-788.001,-472.001,-850.001,-273.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001,-0.001],"Equalities":0}

If there is more than one possible solution with equal minimum value, it's enough to get any solution.

The constraints are of three types:

1. x1 + x2 + x3 + x4 = 704,
   it returned NoPossibleSolution for many inputs, so I substituted it with two inequalities:
   x1 + x2 + x3 + x4 >= 703.999 and
   x1 + x2 + x3 + x4 <= 704.001
   This substitution helped a lot.
2. sum of some variables <= some positive integer (eg. 107 as in b[10])
   this I substituted with:
   sum of some variables <= some positive integer + epsilon
   eg.
   sum of some variables <= 107.001
3. each variable >= 0
   that I substituted with:
   each variable >= -epsilon
   eg.
   each variable >= -0.001

[cesarsouza]

Hello there,

Have you tried specifying different values for the ConstraintTolerances property of GoldfarbIdnani? It should achieve the same effect as manually introducing an epsilon. If you are creating LinearConstraint objects, you can also adjust their Tolerance property just before passing them to GoldfarbIdnani's constructor.

I will try to reproduce the issue and check whether the framework couldn't handle this case automatically by using a small constant for equality constraints by default.

Thanks for reporting the issue!

Regards,
Cesar

[cesarsouza]

Please, could you also post the expected solution for this optimization problem?

[castek]

The example above suddenly works, I don't know why, because I don't remember that I have made any change. But there are plenty of other examples that don't work. Using ConstraintTolerances helped slightly, but not in all cases. I'm attaching another example, I'm comparing it with Berwin Turlach's R code and Alberto Santini's node-quadprog's (javascript) code: both give correct results for this example, but accord says NoFeasibleSolution. I've found two differences between your code and R code: <= instead of < on lines 889 and 913 of GolfarbIdnani.cs, but only a little improvement has been reached. I will continue to debug your code comparing it with node-quadprog (I don't have R debugger).

[castek]

New GoldfarbIdnaniMinimizeWithEqualityTest2(), that fails without change commited in 873ddbe:
NewGoldfarbIdnaniTest.cs.zip

An old test GoldfarbIdnaniLargeSampleTest2() was failing before the change has been made.

[cesarsouza]

Hi Castek,

I have just commited a new version of the Goldfarb Idnani solver. Can you please check if it solves that issue? I have added your example in the unit tests as well.

Sorry for the inconvenience. A few indices were off, mostly due the index differences between Fortran (1-based) and C# (zero-based).

If you have more examples that fail, please let me know!

Regards,
Cesar

[castek]

Hello,
your new version works 100% on other 5000 tasks. Please add test from #issuecomment-178005878 above too. You can close the issue. Thanks

[cesarsouza]

Fixed in release 3.2.