Re: [ojAlgo-user] Quadratic Program fails

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

On 16 jan 2014, at 10:31, Nico Potyka <Nic...@gm...> wrote:

> Thanks for your tips. I tried the debug mode but didn't notice any differences in the output apart from improved accuracy for the expression based model. However, I saw that in the solve-method of the QuadraticSolver class all exceptions (including nullpointer exceptions) are swallowed in the catch-block if you are not in debug mode and the state is just set to FAILED. I'm not sure if this is the way it is meant to be.

It's bad design and will be changed at some point. I've already added validation to the builder to avoid the kind of mistake (transposing C) you made before. When/how was there a NullPointerE?


> I also followed your advice and stepped into the code, but couldn't really follow what was going on (not because of the code, but because I need more time to understand how things work together). I noticed, however, that the call of build() in
> 
> QuadraticSolver qSolver = new QuadraticSolver.Builder(tmpQ, tmpC).equalities(tmpAE, tmpBE).inequalities(tmpAI, tmpBI).build();
> 
> also uses an ExpressionBasedModel of the QuadraticSolver.Builder, but it seems to be used in a different way, because its variable list is empty if I get it right. So maybe the crucial difference is the way I define non-negativity constraints in both implementations. For the expression based model I define non-negativity when defining the variables (via lower(BigMath.ZERO)), whereas I define non-negativity by means of the matrix AI (which is the negative unity matrix in my case) for my matrix implementation. If ojAlgo handles non-negativity constraints in a different way than general inequalities, maybe this is a reasonable explanation? By the way, is there another way to define non-negativity when using the build-method as above? In this case I wouldn't need any inequalities at all.

ExpressionsBasedModel also makes use of that same builder. There's no special way to handle non-negativity, it just an inequality.


> I also tried the NullspaceSolver but it yields wrong results for many examples I tested. These examples need some classes from another library, but if it helps for debugging, I will try to build some stand-alone examples and send them to you soon.

Ok, never mind that then. It'll be some time before I finish it.



> Best regards
> Nico
> 
>  
>  
> 
> Gesendet: Mittwoch, 15. Januar 2014 um 08:46 Uhr
> Von: "Anders Peterson" <an...@op...>
> An: "ojAlgo ojAlgo" <oja...@li...>
> Betreff: Re: [ojAlgo-user] Quadratic Program fails
> There's one more thing that maybe you're interested in trying.
> 
> In the QuadraticSolver.Builder.build(Options) method you may change this
> 
> return new LagrangeSolver(tmpModel, options, this);
> //return new NullspaceSolver(tmpModel, options, this);
> into
> //return new LagrangeSolver(tmpModel, options, this);
> return new NullspaceSolver(tmpModel, options, this);
> 
> That solver is NOT READY! It's a very high level experimental implementation of a different algorithm with better numerical performance. In its current state it uses even more memory and executes about 4 times slower than the default algorithm, but it does handle most of the test cases.
> 
> /Anders
> 
> 
> 
> On 15 jan 2014, at 07:58, Anders Peterson <an...@op...> wrote:
> 
>> I'm surprised your initial trials only worked up to 32 variables - that's not much at all... Must be something "unfortunate" with your numbers.
>> 
>> ExpressionBasedModel obviously did something for you. Debug your code with a breakpoint in the static method QuadraticSolver.make(ExpressionBasedModel). There you should be able to see the actual matrices used in the solver. You can compare that to what you created when you used the solver builder directly.When you've learned what ExpressionBasedModel did maybe you can go back to using the solver/builder and manipulate the input matrices the same way, but more. In your case I'm guessing it's only simple scaling of the problem parameters.
>> 
>> To learn a little about what goes wrong in the solver you can try this: Set this before you solve.
>> 
>> tmpModel.options.debug(QuadraticSolver.class);
>> or
>> tmpSolver.options.debug(QuadraticSolver.class);
>> 
>> Only do that for smaller models. Otherwise there will be too much output.
>> 
>> 
>> /Anders
>> 
>> 
>> On 14 jan 2014, at 12:53, Nico Potyka <Nic...@gm...> wrote:
>> 
>>> I did some experiments now. My original implementation works fine for up to 32 variables (the number of variables doubles necessarily), then I had some numerical problems. Probably because I did not use the library in an optimal way. I changed to the ExpressionBasedModel and it's really quite easy to use and works fine. For 256 variables runtime "exploded" and computing a solution took several minutes (probably because Q can be quite dense) and I stopped experimenting. However, the use of aojalgo is quite elegant and I can compute several interesting examples. So I will keep using it. I'll have a look at the the other unit tests, too, to get a better feeling for the library. Anyway, thanks again for your help and keep on the good work.
>>> 
>>> 
>>> 
>>> 
>>> Gesendet: Freitag, 10. Januar 2014 um 11:54 Uhr
>>> Von: "Nico Potyka" <Nic...@gm...>
>>> An: oja...@li...
>>> Betreff: Re: [ojAlgo-user] Quadratic Program fails
>>> Thanks for your input. Constraints are indeed always restricted to non-negativity and normalization, the problem specific information is encoded in Q. However, existence of a solution is guaranteed for all problem instances. I will let you know what problem size I can handle, after doing some experiments and trying the ExpressionBasedModel.
>>> 
>>> 
>>>> Yes, the solver swallowed the exception, but did output it to the console. You displayed the solver state using System.out.println(); Didn't you see the exception there?
>>> 
>>> For the code below,
>>> 
>>> System.out.println(tmpResult.getState());
>>> 
>>> does not print any information about exceptions on my computer.
>>> 
>>> Best regards
>>> Nico
>>> 
>>> 
>>> 
>>> 
>>> 
>>> Gesendet: Freitag, 10. Januar 2014 um 11:21 Uhr
>>> Von: "Anders Peterson" <an...@op...>
>>> An: "ojAlgo ojAlgo" <oja...@li...>
>>> Betreff: Re: [ojAlgo-user] Quadratic Program fails
>>> After writing that I felt I had to investigate how large problems ojAlgo can handle...
>>> 
>>> Problems structured as in your test case are easy to solve because the inequality constraints doesn't actually affect the solution.
>>> 
>>> dim=2 =>
>>> OPTIMAL in 0.042362s
>>> dim=4 =>
>>> OPTIMAL in 6.18E-4s
>>> dim=8 =>
>>> OPTIMAL in 6.97E-4s
>>> dim=16 =>
>>> OPTIMAL in 0.001164s
>>> dim=32 =>
>>> OPTIMAL in 0.003616s
>>> dim=64 =>
>>> OPTIMAL in 0.021859s
>>> dim=128 =>
>>> OPTIMAL in 0.026166s
>>> dim=256 =>
>>> OPTIMAL in 0.02064s
>>> dim=512 =>
>>> OPTIMAL in 0.073304s
>>> dim=1024 =>
>>> OPTIMAL in 0.508432s
>>> dim=2048 =>
>>> OPTIMAL in 3.590416s
>>> dim=4096 =>
>>> OPTIMAL in 24.111358s
>>> dim=8192 =>
>>> OPTIMAL in 186.600192s
>>> dim=16384 =>
>>> Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
>>> at org.ojalgo.array.PrimitiveArray.<init>(PrimitiveArray.java:326)
>>> 
>>> 
>>> If you start adding inequality constraints that actually affect the solution performance will be very different, and if in fact the inequalities make the problem infeasible the algorithm may not be able to recognize that.
>>> 
>>> /Anders
>>> 
>>> 
>>> On 9 jan 2014, at 22:29, Anders Peterson <an...@op...> wrote:
>>> 
>>>> On 9 jan 2014, at 21:55, Nico Potyka <Nic...@gm...> wrote:
>>>> 
>>>>> Thanks again and sorry for wasting your time. For some reason, there is no exception thrown on my computer and executing the code yields "FAILED". However, after switching to a column vector my general implementation works perfectly fine.
>>>> 
>>>> Yes, the solver swallowed the exception, but did output it to the console. You displayed the solver state using System.out.println(); Didn't you see the exception there?
>>>> 
>>>> 
>>>>> I took your advice, but I need to perform some matrix operations to determine Q in general and therefore prefered the following example from the unit tests. Furthermore, the problems can become quite large. In fact, most interesting problem instances have hundreds of variables and I can easily construct examples with thousands or millions of variables. Therefore I figured that generating a variable object for each optimization variable might not be the best way to go. But I will give it a try.
>>>> 
>>>> ExpressionsBasedModel is "sparse" it only stores the nonzero problem parameters, so it's not as bad as you may think. The solvers are "dense".
>>>> 
>>>> The general advice would be to initially use ExpressionsBasedModel and then maybe switch to a specific solver if necessary and possible.
>>>> 
>>>> ojAlgo's quadratic solver cannot handle millions of variables! 20000 or so would be an absolute limit and I imagine it will struggle with numerical and performance issues long before that. I don't know where the practical limit is - it depends on your specific case. The largest successful cases I know of has hundreds of variables (not thousands). Please let me know how large models you manage to solve.
>>>> 
>>>> /Anders
>>>> 
>>>> 
>>>> 
>>>>> Best regards
>>>>> Nico
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> Gesendet: Donnerstag, 09. Januar 2014 um 21:07 Uhr
>>>>> Von: "Anders Peterson" <an...@op...>
>>>>> An: "ojAlgo ojAlgo" <oja...@li...>
>>>>> Betreff: Re: [ojAlgo-user] Quadratic Program fails
>>>>> When I run that code I get an ArrayIndexOutOfBoundsException, and that's because "C" should be a column vector rather than a row vector.
>>>>> 
>>>>> Had you taken my advice and used ExpressionsBasedModel this wouldn't have happened. That class actually does something for you:
>>>>> 
>>>>> 1) You can model your problems without worrying about specific solver requirements.
>>>>> 2) It knows which solver to use.
>>>>> 3) It knows how to use that solver.
>>>>> 4) It has a presolver that tries to simplify the problem before invoking a solver (sometimes it turns out there is no need to invoke a solver at all).
>>>>> 5) When/if needed it scales problem parameters, before creating solver specific data structures, to minimize numerical problems in the solvers.
>>>>> 6) It's the only way to access the integer solver.
>>>>> 
>>>>> /Anders
>>>>> 
>>>>> 
>>>>> On 9 jan 2014, at 16:53, Nico Potyka <Nic...@gm...> wrote:
>>>>> 
>>>>>> Hi,
>>>>>> 
>>>>>> I tried to use ojAlgo to implement a norm minimization problem, but the solver fails even for very simple instances. The following example is one particular simple instance. Q is the identity matrix, C the zero vector. The constraints express that the solution is a probability function (AE for normalization and AI for non-negativity). Q is positive definite and the solution should be (0.5, 0.5), but qSolver fails.
>>>>>> 
>>>>>> 
>>>>>> PrimitiveDenseStore tmpQ = PrimitiveDenseStore.FACTORY.rows(new double[][]{{1, 0},{0, 1}});
>>>>>> PrimitiveDenseStore tmpC = PrimitiveDenseStore.FACTORY.rows(new double[][]{{0, 0}});
>>>>>> 
>>>>>> PrimitiveDenseStore tmpAE = PrimitiveDenseStore.FACTORY.rows(new double[][]{{1, 1}});
>>>>>> PrimitiveDenseStore tmpBE = PrimitiveDenseStore.FACTORY.rows(new double[][]{{1}});
>>>>>> 
>>>>>> PrimitiveDenseStore tmpAI = PrimitiveDenseStore.FACTORY.rows(new double[][]{{-1, 0}, {0, -1}});
>>>>>> PrimitiveDenseStore tmpBI = PrimitiveDenseStore.FACTORY.rows(new double[][]{{0}, {0}});
>>>>>> 
>>>>>> QuadraticSolver qSolver = new QuadraticSolver.Builder(tmpQ, tmpC).equalities(tmpAE, tmpBE).inequalities(tmpAI, tmpBI).build();
>>>>>> 
>>>>>> Optimisation.Result tmpResult = qSolver.solve();
>>>>>> System.out.println(tmpResult.getState());
>>>>>> 
>>>>>> 
>>>>>> Is there something wrong in my code or is there a problem with the quadratic solver?
>>>>>> 
>>>>>> Thanks
>>>>>> Nico
>>>>>> 
>>>>>> ------------------------------------------------------------------------------
>>>>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>>>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>>>>> Critical Workloads, Development Environments & Everything In Between.
>>>>>> Get a Quote or Start a Free Trial Today.
>>>>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
>>>>>> _______________________________________________
>>>>>> ojAlgo-user mailing list
>>>>>> ojA...@li...
>>>>>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]]][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]]]]
>>>>>> 
>>>>>> 
>>>>> 
>>>>> 
>>>>> ------------------------------------------------------------------------------
>>>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>>>> Critical Workloads, Development Environments & Everything In Between.
>>>>> Get a Quote or Start a Free Trial Today.
>>>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]]][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]]]]
>>>>> _______________________________________________
>>>>> ojAlgo-user mailing list
>>>>> ojA...@li...
>>>>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]]][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]]]]
>>>>> 
>>>>> ------------------------------------------------------------------------------
>>>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>>>> Critical Workloads, Development Environments & Everything In Between.
>>>>> Get a Quote or Start a Free Trial Today.
>>>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]]]
>>>>> _______________________________________________
>>>>> ojAlgo-user mailing list
>>>>> ojA...@li...
>>>>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]]]
>>> 
>>> 
>>> ------------------------------------------------------------------------------
>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>> Critical Workloads, Development Environments & Everything In Between.
>>> Get a Quote or Start a Free Trial Today.
>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]]]
>>> _______________________________________________
>>> ojAlgo-user mailing list
>>> ojA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]]]
>>> 
>>> ------------------------------------------------------------------------------
>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>> Critical Workloads, Development Environments & Everything In Between.
>>> Get a Quote or Start a Free Trial Today.
>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk][http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]]
>>> _______________________________________________
>>> ojAlgo-user mailing list
>>> ojA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user][https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]]
>>> 
>>> ------------------------------------------------------------------------------
>>> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
>>> Learn Why More Businesses Are Choosing CenturyLink Cloud For
>>> Critical Workloads, Development Environments & Everything In Between.
>>> Get a Quote or Start a Free Trial Today.
>>> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]
>>> _______________________________________________
>>> ojAlgo-user mailing list
>>> ojA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]
> 
> 
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today.
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk[http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk]
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user[https://lists.sourceforge.net/lists/listinfo/ojalgo-user]
> 
> ------------------------------------------------------------------------------
> CenturyLink Cloud: The Leader in Enterprise Cloud Services.
> Learn Why More Businesses Are Choosing CenturyLink Cloud For
> Critical Workloads, Development Environments & Everything In Between.
> Get a Quote or Start a Free Trial Today. 
> http://pubads.g.doubleclick.net/gampad/clk?id=119420431&iu=/4140/ostg.clktrk
> _______________________________________________
> ojAlgo-user mailing list
> ojA...@li...
> https://lists.sourceforge.net/lists/listinfo/ojalgo-user