Re: NMinimize eats all memory b/c of unnecessary symbolic work
- To: mathgroup at smc.vnet.net
- Subject: [mg120739] Re: NMinimize eats all memory b/c of unnecessary symbolic work
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Mon, 8 Aug 2011 04:20:34 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
----- Original Message -----
> From: "Daniel Jensen" <jensend at iname.com>
> To: mathgroup at smc.vnet.net
> Sent: Sunday, August 7, 2011 5:15:37 AM
> Subject: NMinimize eats all memory b/c of unnecessary symbolic work
> The following code is a fairly naive way to find the least number
> whose
> square has n divisors (the minimum should be its log and the x_i the
> powers in its prime factorization). If I look at the case n00 and use
> ten variables instead of twenty, this uses somewhere around 600MB of
> memory. With the value of n I'm actually trying to find the answer
> for,
> I need around 20 variables to be sure of not missing the actual
> solution, and it quickly uses up all available memory and then
> thrashes
> swap.
>
> n=8*10^6;
> a = Table[N[Log[Prime[i]]], {i, 20}];
> b = Table[Subscript[x, i], {i, 20}];
> cond = Fold[And, Product[2 Subscript[x, i] + 1, {i, 20}] > n,
> Table[Subscript[x, i] >= 0, {i, 20}]] && b \[Element] Integers;
> NMinimize[{a.b, cond}, b, MaxIterations -> 1000]
>
> It turns out that the problem isn't related to integer programming etc
> at all (removing the restriction to the integers doesn't help).
>
> My best guess is that the problem is that Mathematica is wasting all
> that memory expanding Product[2 Subscript[x, i] + 1, {i, 20}]. If I
> replace the product with just Product[Subscript[x, i],{i,20}] and
> change
> the constraints to be >= 1 rather than 0 I get results without a
> hassle
> and without the kernel using more than 50MB of memory. (Though that
> preserves the inequality constraint and doesn't change the task of
> minimizing the objective function, it does mess up the integrality
> requirement- I get even results, which correspond to half-integers in
> the actual problem.)
>
> Searching the Web, I found one person who had a somewhat similar
> problem; in their case, they had an objective function which was
> getting
> evaluated symbolically at a huge cost. They were able to remedy it by
> making the function only accept numeric input. I don't seem to be able
> to do that with the constraint.
>
> Any thoughts on how to fix this?
This seems to "work". Except
(1) It does not give the global optimum with the settings provided, and
(2) It seems sometimes to crash the kernel.
n = 8*10^6;
nvars = 20;
a = Table[N[Log[Prime[i]]], {i, nvars}];
b = Table[Subscript[x, i], {i, nvars}];
c1[xx : {_?NumericQ ..}] := Times @@ (2 xx + 1);
c2 = Map[# >= 0 &, b];
c3 = b \[Element] Integers;
cond = Join[{c1[b] > n}, c2, {c3}];
In[10]:= Timing[NMinimize[{a.b, cond}, b, MaxIterations -> 1000]]
During evaluation of In[10]:= NMinimize::cvmit: Failed to converge to the requested accuracy or precision within 1000 iterations. >>
Out[10]= {103.679, {36.77416664719056, {Subscript[x, 1] -> 3,
Subscript[x, 2] -> 3, Subscript[x, 3] -> 2, Subscript[x, 4] -> 2,
Subscript[x, 5] -> 1, Subscript[x, 6] -> 1, Subscript[x, 7] -> 1,
Subscript[x, 8] -> 1, Subscript[x, 9] -> 1, Subscript[x, 10] -> 1,
Subscript[x, 11] -> 1, Subscript[x, 12] -> 1,
Subscript[x, 13] -> 0, Subscript[x, 14] -> 0,
Subscript[x, 15] -> 0, Subscript[x, 16] -> 0,
Subscript[x, 17] -> 0, Subscript[x, 18] -> 0,
Subscript[x, 19] -> 0, Subscript[x, 20] -> 0}}}
I'll look into item (2) when I get a chance.
Daniel Lichtblau
Wolfram Research