ConvexSolver didn't found correct solution

[miropich-sf]

Hi, I recently run to this issue with Convex solver so I would like to report it.

The next code will demonstrate the problem:

@Test
public void testConvexSolverIssue() {
        Primitive64Store Q = Primitive64Store.FACTORY.rows(new double[][] {
                { 2.0, 0.0, 0.0, 0.0, 0.0 },
                { 0.0, 0.0000000002, 0.0, 0.0, 0.0 },
                { 0.0, 0.0, 0.0000000002, 0.0, 0.0 },
                { 0.0, 0.0, 0.0, 0.0000000002, 0.0 },
                { 0.0, 0.0, 0.0, 0.0, 7.0 }
        });
        Primitive64Store C = Primitive64Store.FACTORY.column(
                56.0,
                5.6E-9,
                5.6E-9,
                5.6E-9,
                196.0
        );
        Primitive64Store C_issue = Primitive64Store.FACTORY.column(
                56.0,
                5.6000000000000005E-9,
                5.6000000000000005E-9,
                5.6000000000000005E-9,
                196.0
        );
        Primitive64Store AI = Primitive64Store.FACTORY.rows(new double[][] {
                { 1.0, 0.0, 0.0, 0.0, 1.0 },
                { 0.0, 1.0, 0.0, 0.0, 1.0 },
                { 0.0, 0.0, 1.0, 0.0, 1.0 },
                { 0.0, 0.0, 0.0, 1.0, 1.0 },
                { -1.0, -0.0, -0.0, -0.0, -0.0 },
                { -0.0, -1.0, -0.0, -0.0, -0.0 },
                { -0.0, -0.0, -1.0, -0.0, -0.0 },
                { -0.0, -0.0, -0.0, -1.0, -0.0 },
                { -0.0, -0.0, -0.0, -0.0, -1.0 }
        });
        Primitive64Store BI = Primitive64Store.FACTORY.column(28.0, 25.0, 25.0, 25.0, 0.0, 0.0, 0.0, 0.0, 0.0);

        ConvexSolver solverOk = ConvexSolver.newBuilder().objective(Q, C).inequalities(AI, BI).build();
        Result resultOk = solverOk.solve();

        ConvexSolver solverNOk = ConvexSolver.newBuilder().objective(Q, C_issue).inequalities(AI, BI).build();
        Result resultNOk = solverNOk.solve();

        System.out.println("Result OK: " + resultOk);
        System.out.println("Result NOK: " + resultNOk);
    }

As can be seen from the code the small change in input vector (C) for objective function is causing issue in the Convex solver. It will not converge to correct solution:

Result OK: OPTIMAL -2918.222222273241 @ { 6.22222222387408, 3.2222233327795915, 3.2222222238740756, 3.2222222238740756, 21.777777776125927 }
Result NOK: OPTIMAL -2712.5 @ { -0.0, -0.0, -0.0, -0.0, 25.0 }

The second result is obviously not optimal.

Version used for test: 53.3.0

[apete]

Yes, the expected behaviour here would be to get the same (very similar) solution in both cases. (And if there's some problem, don't report the solution as optimal.)

Problem seems to be with the accuracy of the iterative Lagrange multiplier solver. This is configurable to help with situations like this. Try changing it with:

    Optimisation.Options options = new Optimisation.Options();
    options.convex().iterative(NumberContext.of(8));
    builder..build(options);

or use the extended precision solver:

    options.convex().extendedPrecision(true);

With that the reported solution is: { 6.222222222222222, -6.0000000000000005E-31, -6.0000000000000005E-31, -6.0000000000000005E-31, 21.77777777777778 }

Not the same as either of the solutions you got before.

Regardless of the solver's behaviour here you really should avoid generating models with parameters like 5.6000000000000005E-9. I mean, exactly which problem is it you want to solve? I recommend using ExpressionsBasedModel and setting the individual model parameters as BigDecimal with clearly defined precision and scale.

[apete]

Short term I won't do anything about this. (Don't know what to do.) The issue can be handled by tweaking the iterative solver precision (as described above) but changing the defaults cause other tests to fail.

It is (always) recommended to use ExpressionsBasedModel. If you do that you get the correct solution even when you input parameters like 5.6000000000000005E-9. It has presolve and rescaling functionality that help avoid many problems like this.

I'm keeping this test case and hope to solve the issue sometime.

[miropich-sf]

Hi,
Thank you for the recommendations how to solve the problem. It looks like it works with the options.convex().extendedPrecision(true);, however I will look to ExpressionsBasedModel.

Regarding parameters like 5.6000000000000005E-9. In this case it was result of other computation. Small fraction is probably the result of Double rounding error in computation. However I experienced not ideal results from solver also for nicely rounded input. Input I reported here is just the first I ran into as the problematic one.

Thank you one more time for your time and help.