Re: [ojAlgo-user] Probably User Error, but...

[Anders P. <an...@op...>]

The short answer and quick solution for you is to model your problems using ExpressionsBasedModel rather than using the ConvexSolver directly. It brings many advantages - among other things it would automagically switch to the LinearSolver for that  one degenerate case.


The ConvexSolver assumes there is a Q-matrix and that it is symmetric and (semi) positive definite. A Q-matrix with all zeros does theoretically meet those requirements, and It seems reasonable to assume that a convex solver can handle a linear problem. That said I’m not surprised it fails - it’s not designed to handle that case. I will, however, have a look your test code and investigate what (if anything) I can do handle the linear case.


/Anders



> On 9 aug 2015, at 02:40, Greg Sterijevski <gs...@ho...> wrote:
> 
> Hi, 
> 
> I have a very simple quadratic programming problem. In one degenerate case, the Q matrix is composed of zeroes. In other words, the problem is a linear programming problem with Equality and Inequality constraints. It seems like ConvexSolver should be able to solve the problem but it fails in somewhat interesting ways. I am not sure what I am doing wrong. 
> 
> I am minimizing the expression 
> 
> x' Q x' - c' x
> 
> where c = { 0.12, -0.05, 0.08, 0.07 }
> 
> I would expect that without an constraints, the solver should fail as it attempts to take x[0],x[2],x[3] to +infinity and x[1] to -infinity. I next set liberal constraints of +/- 99999 for all the factors.. I would expect the solver to take the x vector to the bounds and terminate gracefully. In either case, the results are hard to understand. 
> 
> In the case where I use the zero matrix for Q, I get an infeasibility failure. Failure State = INVALID
> 
> 
> In the case where I use an identity matrix (which is PSD and nice) , I get the result as:
> x[0] = 0.12
> x[1] = -0.05
> x[2] = 0.08
> x[3] = 0.07
> 
> In the case of zero matrix and constraints I get:
> 
> x[0] = 0.25
> x[1] = 0.25
> x[2] = 0.25
> x[3] = 0.25
> 
> The for the case of an identity matrix and constraints I get
> 
> Identity Q matrix and  constraints -------------------------!
> Initial solution: [0.12, -0.05, 0.08, 0.07]
> Initial I-included-slack: []
> Initial I-excluded-slack: [99999.12, 99998.95, 99999.08, 99999.07, 99998.88, 99999.05, 99998.92, 99998.93]
> 
> PerformIteration
> Last Incl/Excl: -1/-1 => [] / [0, 1, 2, 3, 4, 5, 6, 7]
> X/L: true X=[0.0, 0.0, 0..0, 0.0] L=[]
> Current: [0.12, -0.05, 0.08, 0.07]
> Step: [0.0, 0.0, 0.0, 0.0]
> java.lang.NullPointerException
> 
> 
> Any thoughts would be appreciated. Thank you to the creators of OjAlgo. It looks like a complete package!
> 
> 
> -Greg
> 
> 
> Test code below. 
> 
> public static void attempt5(boolean identity, boolean addDummyConstraints) {
>         if (!identity && !addDummyConstraints) {
>             System.out.println("Zero Q matrix and no constraints -------------------------!");
>         } else if (!identity) {
>             System.out.println("Zero Q matrix and constraints -------------------------!");
>         } else if (!addDummyConstraints) {
>             System.out.println("Identity Q matrix and no constraints -------------------------!");
>         } else {
>             System.out.println("Identity Q matrix and  constraints -------------------------!");
>         }
> 
>         double[] C = new double[]{0.12, -0.05, 0.08, 0.07};
>         final RawStore cov = new RawStore(4, 4);
>         if (identity) {
>             for (int i = 0; i < 4; i++) {
>                 cov.set(i, i, 1.0);
>             }
>         }
>         final RawStore linPart = new RawStore(C, 4);
>         ConvexSolver.Builder builder = ConvexSolver.getBuilder(
>                 cov,
>                 linPart);
> 
>         if (addDummyConstraints) {
>             RawStore ineq = RawStore.FACTORY.rows(
>                     new double[][]{{-1.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.0, 0.0, -1.0},
>                     {1.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.0, 0.0, 1.0}});
> 
>             RawStore coeff = RawStore.FACTORY.columns(new double[][]{{99999, 99999, 99999, 99999, 99999, 99999, 99999, 99999}});
> 
>             builder = builder.inequalities(ineq, coeff);
>         }
>         final Optimisation.Options opts = new Optimisation.Options();
>         opts.iterations_abort = 10000;
>         opts.iterations_suffice = 100;
>         opts.debug(ConvexSolver.class);
>         final ConvexSolver cs = builder.build(opts);
> 
>         try {
>             final Optimisation.Result solution = cs.solve();
>             if (solution.getState() == Optimisation.State.DISTINCT
>                     || solution.getState() == Optimisation.State.APPROXIMATE
>                     || solution.getState() == Optimisation.State.OPTIMAL) {
>                 double[] pt = new double[4];
>                 for (int i = 0; i < pt.length; i++) {
>                     pt[i] = solution.doubleValue(i);
>                 }
> 
>                 System.out.println("Objective " + solution.getValue());
>                 for (int ii = 0; ii < 4; ii++) {
>                     System.out.println("x[" + ii + "] = " + solution.doubleValue(ii));
>                 }
>             } else {
>                 System.out.println("Failure State = " + solution.getState().name());
> 
>             }
> 
>         } catch (Exception e) {
>             System..out.println(e);
>         }
>     }
> ------------------------------------------------------------------------------
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user