Message Boards Message Boards

0
|
11745 Views
|
8 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Speeding up the FindMinimum function

Hi all,

I am updating some programs that I wrote in Mathematica 7.0 and now when I run them in Mathematica 9.0 they run much much slower. Something that takes about 3.5 minutes in the 7.0 version took about 2.5 hours.

The main culprit seems to be the FindMinimum function which is used a couple/few hundred times during the run.

I was able to speed up the FindMinimum function from about 31 seconds for a single evaluation to about 2.5 seconds per evaluation by addition the "Gradient->"FiniteDifference" option. This means that the whole program still takes about 24.5 minutes instead of 3.5, so I'm hoping that I can reduce this time even further (and maybe even get an explanation for why the new version is so much slower).

I'm attaching a file with the FindMinimum function in it. The function itself is rather complicated and is 6-dimensional.

I would appreciate any advice you could give.

Thanks,

Matty

Attachments:
POSTED BY: Matty Mookerjee
8 Replies

The file you attached is missing definitions (ErrorIndex), so it's not really possible to tell what's going on.

To debug the issue, you can:

  • Count how many times FindMinimum calls your funtion by wrapping it, e.g. i=0; g[x_?NumericQ] := (i++; f[x])

  • Benchmark the function to be minimized on its own (without using FindMinimum).

This will tell you whether the slowdown is due to FindMinimum itself, or hidden somewhere in your function.

POSTED BY: Szabolcs Horvát

Szabolcs,

Sorry that my notebook wasn't formatted correctly. The function was there, but it was at the bottom of the page. I've attached a new notebook which has everything in the correct order and all self-contained within one cell. I hope that helps.

I'm not totally sure what you meaning by benchmarking the function.

In the notebook that I attached you can see that the FindMinimum function takes 28.766584 seconds. I opened that exact same notebook in Mathematica 7 and it took 0.328 seconds. So, it seems like something different is going on with the function, but I can seem to fix it.

Again, any help anyone could provide would be greatly appreciated.

Thanks,

Matty

Attachments:
POSTED BY: Matty Mookerjee

I filed a slowdown report for this.

POSTED BY: Daniel Lichtblau

Thanks Daniel.

Do you think there is any way to make it run faster in the current version. I am running a Short Course on my Strain Analysis program at the Colorado School of Mines on Sunday and it would be nice if I could get the programs to run faster so the participants will have time to actually run through the entire process of strain analysis. I don't know if there are any options for the FindMinimum function that I could employ (in addition to the Gradient->"FiniteDifference" which I've already added) that might help it run more quickly.

Thanks for the help and sending in the report.

Matty

POSTED BY: Matty Mookerjee

Sad to say, I do not know how to speed it. If anyone here suggests something to me I'll pass it along.

Something I've not tried, which might or might not be viable, is to recast as an unconstrained problem with an explicit penalty term for inequality violations. That way at least you have access to method option settings that might help.

POSTED BY: Daniel Lichtblau

Actually I do have a speedup. The constraints state in effect that all three roots of a parametrized cubic are nonnegative. Replace them with the constraints that all three coefficients of said cubic are of appropriate sign (so the constant and quadratic terms will be nonpositive, the linear coefficient nonnegative).

In[42]:= gam2^2 - 2*gam1*gam2*gam3 + gam1^2*lam1 + gam3^2*lam3 - 
   lam1*lam3 + (-1*gam1^2 - 1*gam2^2 - 1*gam3^2 + lam1 + lam3 + 
      lam1*lam3)*#1 + (-1 - 1*lam1 - 1*lam3)*#1^2 + #1^3 &[x]

Out[42]= gam2^2 - 2 gam1 gam2 gam3 + gam1^2 lam1 + gam3^2 lam3 - 
 lam1 lam3 + (-gam1^2 - gam2^2 - gam3^2 + lam1 + lam3 + 
    lam1 lam3) x + (-1 - lam1 - lam3) x^2 + x^3

In[46]:= mycons2 = {(-1 - lam1 - lam3) <= 
    0, (-gam1^2 - gam2^2 - gam3^2 + lam1 + lam3 + lam1 lam3) >= 0, 
   gam2^2 - 2 gam1 gam2 gam3 + gam1^2 lam1 + gam3^2 lam3 - lam1 lam3 <=
     0};

In[47]:= Timing[
 fm1 = FindMinimum[{errindex, 
    mycons2}, {lam1, .01}, {lam3, .11}, {gam1, 0.0}, {gam2, 
    0.0}, {gam3, 0.0}]]

Out[47]= {0.104000, {0.0308505996903, {lam1 -> 1.0254443981, 
   lam3 -> 9.42312324422, gam1 -> -0.182347311039, 
   gam2 -> 1.50192292523, gam3 -> -0.0452412524485}}}
POSTED BY: Daniel Lichtblau

Daniel,

Thank you, thank you, thank you, thank you!

Replacing mycons with what you suggested (as apposed to mycons = N[ Thread[Eigenvalues[GeneralEllipsoid] > 0], 50]; which was how it was defined before) definitely speeds things up. However, it doesn't speed it up consistently, i.e., there are still errorindex functions (which change with each sample run as well as changing slightly during each monte carlo-style iteration during a single run) where Mathematica 7 is still significantly faster than Mathematica 9. So, I think it's still good that you filed the slowdown report.

With your improvement, and the addition of the Gradient->"FiniteDifference" option, I think it is now running about as fast (potentially even faster) than before, although I haven't had time to test a lot of different examples yet.

Thank you again for your help. You have reduce my stress level 10-fold.

Take care,

Matty

POSTED BY: Matty Mookerjee

Matty,

Glad that last post helped.

Here is what I had meant by using a penalty. It might be faster in some cases where the improved constraint setup remains slow. Also I did not try to adjust the method so that could perhaps give further speed gains.

I include my version of "errindex". I obtained it by multiple use of Chop. It might or might not improve the FindMinimum computation speed but at least it makes the code easier to read. I'd be surprised if this in any way lead to a worsened quality of result 9and if it did, that would indicate you're dealing with a numerically unstable computation).

errindex = (0.8988621286229235 - ((-1.*gam3^2 + 1.*lam1)^2)^(-1/
         4))^2 + (0.04410530083035308 + (1.*
         gam3)/((-1.*gam3^2 + 1.*lam1)^2)^(1/
          4))^2 + (1.114681824560056 - (1.*
         lam1)/((-1.*gam3^2 + 1.*lam1)^2)^(1/
          4))^2 + (0.3334610964453241 - 
      1./((-1.*gam1^2 + 1.*lam3)^2)^(1/
          4))^2 + (0.07055833545418581 + (1.*
         gam1)/((-1.*gam1^2 + 1.*lam3)^2)^(1/
          4))^2 + (3.013780286261509 - (1.*
         lam3)/((-1.*gam1^2 + 1.*lam3)^2)^(1/
          4))^2 + (0.4795936666881171 - (1.*
         gam2)/((-1.*gam2^2 + 1.*lam1*lam3)^2)^(1/
          4))^2 + (0.3499718837183906 - (1.*
         lam1)/((-1.*gam2^2 + 1.*lam1*lam3)^2)^(1/
          4))^2 + (3.5145968643500987 - (1.*
         lam3)/((-1.*gam2^2 + 1.*lam1*lam3)^2)^(1/4))^2;

errindex2 = 
  100*(Max[(-1 - lam1 - lam3), 0] - 
      Min[(-gam1^2 - gam2^2 - gam3^2 + lam1 + lam3 + lam1 lam3), 0] +
      Max[(gam2^2 - 2 gam1 gam2 gam3 + gam1^2 lam1 + gam3^2 lam3 - 
         lam1 lam3), 0]) + errindex;

Timing[
 fm1 = FindMinimum[
   errindex2, {lam1, .01}, {lam3, .11}, {gam1, 0.0}, {gam2, 
    0.0}, {gam3, 0.0}]]

During evaluation of In[55]:= FindMinimum::lstol: The line search decreased the step size to within the tolerance specified by AccuracyGoal and PrecisionGoal but was unable to find a sufficient decrease in the function. You may need more than MachinePrecision digits of working precision to meet these tolerances. >>

Out[55]= {0.120000, {0.0308505996903, {lam1 -> 1.02544451853, 
   lam3 -> 9.4231233029, gam1 -> -0.182347320429, 
   gam2 -> 1.50192314333, gam3 -> -0.0452412621552}}}
POSTED BY: Daniel Lichtblau
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