Message Boards Message Boards

1
|
2178 Views
|
0 Replies
|
1 Total Likes
View groups...
Share
Share this post:
GROUPS:

Complexity of Minimization Functions

Occasionally users try to symbolically solve problems with 10 or more variables and find that takes a long time. As an experiment, I looked at the time to minimize a multi-dimensional extension of the Rosenbrock function.

The first test used Minimize:

In[14]:= rosemin[n_] := 
 Minimize[Sum[(1 - x[i])^2 + 100 (x[i + 1] - x[i]^2)^2, {i, n - 1}], 
  Array[x, n]]

In[21]:= Table[AbsoluteTiming @ rosemin[n], {n, 2, 5}]

Out[21]= {{0.0035214, {0, {x[1] -> 1, 
    x[2] -> 1}}}, {0.011846, {0, {x[1] -> 1, x[2] -> 1, 
    x[3] -> 1}}}, {0.0653159, {0, {x[1] -> 1, x[2] -> 1, x[3] -> 1, 
    x[4] -> 1}}}, {53.9166, {0, {x[1] -> 1, x[2] -> 1, x[3] -> 1, 
    x[4] -> 1, x[5] -> 1}}}}

I was startled by the large change going from n = 4 to n = 5 and decided to try FindMinimum next.

In[17]:= roseminfm[n_] := 
 FindMinimum[
  Sum[(1 - x[i])^2 + 100 (x[i + 1] - x[i]^2)^2, {i, n - 1}], 
  Thread[{Array[x, n], 0}]]

In[22]:= Table[AbsoluteTiming @ roseminfm[n], {n, 2, 5}]

Out[22]= {{0.138229, {0., {x[1] -> 1., 
    x[2] -> 1.}}}, {0.00161892, {8.34935*10^-27, {x[1] -> 1., 
    x[2] -> 1., 
    x[3] -> 1.}}}, {0.00175626, {4.00495*10^-27, {x[1] -> 1., 
    x[2] -> 1., x[3] -> 1., 
    x[4] -> 1.}}}, {0.00185059, {0., {x[1] -> 1., x[2] -> 1., 
    x[3] -> 1., x[4] -> 1., x[5] -> 1.}}}}

For FindMinimum, n = 2 was the slowest, possibly due to internal caching of problem. I next went to NMinimize, using the Differential Evolution method, as the default method (probably Nelder-Mead) gave an incorrect result for n = 4.

In[25]:= roseminnmd[n_] := 
 NMinimize[Sum[(1 - x[i])^2 + 100 (x[i + 1] - x[i]^2)^2, {i, n - 1}], 
  Array[x, n], Method -> "DifferentialEvolution"]

In[26]:= Table[AbsoluteTiming @ roseminnmd[n], {n, 2, 5}]

Out[26]= {{0.155879, {0., {x[1] -> 1., 
    x[2] -> 1.}}}, {0.220144, {0., {x[1] -> 1., x[2] -> 1., 
    x[3] -> 1.}}}, {0.317786, {0., {x[1] -> 1., x[2] -> 1., 
    x[3] -> 1., 
    x[4] -> 1.}}}, {0.273166, {3.24173*10^-30, {x[1] -> 1., 
    x[2] -> 1., x[3] -> 1., x[4] -> 1., x[5] -> 1.}}}}

In this case, there was no obvious trend in the time required, for n = 2 to 5.

I think these results illustrate why one should generally not expect symbolic functions to work in reasonable time periods for more than about 4 variables.

POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract