# Complexity of Minimization Functions

Posted 8 years ago
2086 Views
|
0 Replies
|
1 Total Likes
|
 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.