Re: [ojAlgo-user] Quadratic Program fails

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

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]]]
>>>
>>>
>>
>>
>> ------------------------------------------------------------------------------
>> 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][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]

Re: [ojAlgo-user] Quadratic Program fails

Mathematics, linear algebra and optimisation

Re: [ojAlgo-user] Quadratic Program fails