Message Boards Message Boards

GROUPS:

Performance reduction of FindMinimum in version 10

Posted 3 years ago
4578 Views
|
29 Replies
|
7 Total Likes
|

When working on this question dedicated to what I believe is a significant limitation/defect of the current implementation of the "LevenbergMarquardt" algorithm in FindMinimum, I found that the same code evaluates 15 - 25 times slower in version 10.4.1 as compared to version 8.0.4 on the same machine!

At the bottom of this post a Notebook containing the complete setup reproducing the issue is attached.

The following is a comparison of absolute timings of the same FindMinimum code evaluated with the two versions along with the number of steps taken by FindMinimum, achieved minimum and obtained new values of parameters of the model. The setup can be found in the attached Notebook.

With version 8.0.4 on Windows 7 x64 I get the following:

findMinimum[init, MaxIterations -> 500, WorkingPrecision -> 20, PrecisionGoal -> 3, 
 StepMonitor :> ++steps, Method -> {"LevenbergMarquardt", "Residual" -> residualVect}]
{"00:06:35", 220, 0.00405321003823167,
{ν0[1]->406.18, Γ[1]->346.16, ζ[2]->0.22879, ν0[2]->666.41, Γ[2]->239.54, ζ[3]->0.20278}}

The output means that the evaluation has taken 6 min 35 sec and finished in 220 steps, obtained minimum is 0.00405321003823167, the obtained new values of the parameters follow.

And this is what I get with version 10.4.1 installed on the same machine:

findMinimum[init, MaxIterations -> 500, WorkingPrecision -> 20, PrecisionGoal -> 3, 
 StepMonitor :> ++steps, Method -> {"LevenbergMarquardt", "Residual" -> residualVect}]
{"02:37:07", 220, 0.00405321003823167,
{ν0[1]->406.18, Γ[1]->346.16, ζ[2]->0.22879, ν0[2]->666.41, Γ[2]->239.54, ζ[3]->0.20278}}

As you see, the only difference is that now the evaluation has taken 2 hours 37 min 7 sec! It is more than 23 times slower than with version 8.0.4!


Do you experience the same problem? Is it possible to get FindMinimum of version 10.4.1 working as fast as FindMinimum of version 8.0.4?

Attachments:
29 Replies

It would be useful to know if the same degradation in speed has occurred for other FindMinimum methods, such as the QuasiNewton method.

Hi Frank,

I have compared the timings of the "QuasiNewton" method of versions 8.0.4 and 10.4.1 using the setup from the original post (at the bottom you can find updated Notebook with new tests and their results). Apparently the default behavior of the algorithm is improved in version 10.4.1 as compared to version 8.0.4. But with explicit setting "StepMemory" -> 50 the algorithm converges even faster than by default in the both versions. With this setting they produce comparable results and hence an explicit timings comparison can be made.

Here is what I get with version 8.0.4:

steps = 0;
AbsoluteTiming[
 FindMinimum[Total[residualVect^2], init, MaxIterations -> 500, WorkingPrecision -> 20, 
  PrecisionGoal -> 3, StepMonitor :> ++steps, 
  Method -> {"QuasiNewton", "StepMemory" -> 50}]]
steps
{77.2794201, {0.0040532100382316668330, {ν0[1] -> 406.17642254420099564, Γ[1] -> 346.16361654338725225, 
    ζ[2] -> 0.22878779542210714314, ν0[2] -> 666.41208186332494022, Γ[2] -> 239.54267192029381286, 
    ζ[3] -> 0.20278392706935620149}}}

104

And here is the output produced by version 10.4.1 installed on the same system:

{2711.84, {0.0040532100382316668330, {ν0[1] -> 406.17642254104854240, Γ[1] -> 346.16361649727125909, 
    ζ[2] -> 0.22878779542329246759, ν0[2] -> 666.41208186274857108, Γ[2] -> 239.54267192096217456, 
    ζ[3] -> 0.20278392707024245288}}}

146

As seen from the above, the algorithm of version 10.4.1 converges slower but this doesn't explain the 35 times difference in the timings. On the average one step of version 10.4.1 takes 25 times more time than of version 8.0.4!

P.S. I would be pleased if you share your timings. I understand that they strongly depend on hardware but when the performance difference between versions is 20 times or more we should take into account that all usual PCs and laptops (at least no more than 8 years old) have lesser difference in the performance! So your absolute timings even for one version can confirm (or disprove) that the described difference in speed isn't specific for my system.

Attachments:

Dear Alexey,

this is what I get on one of my systems:

enter image description here

So that is 27 minutes.

Cheers,

Marco

Thanks Marco,

It indeed confirms that the problem isn't specific to my system where FindMinimum of version 8.0.4 achieves the same in 6 min 35 sec (I recorded my timings on a 8 years old Lenovo R500 laptop).

I have to admit I almost never use FindMinimum. I've written a LibraryLink interface to the open-source local optimizer, Ipopt.

https://projects.coin-or.org/Ipopt

For problems with more than a few variables, it runs many times faster than FindMinimum, takes bounds on variables as inputs and returns constraint violations and associated Lagrange multipliers. I don't understand why Wolfram Research doesn't do something like that.

Is your package published?

Found: with version 10.4.1 we have it built-in:

Needs["IPOPTLink`"]

?IPOPTMinimize
IPOPTMinimize[fx, gx, gbounds, xvars, xbounds, x0, opts]
finds a local solution for the optimization problem
   min     f(x)
x in R^n
s.t.       g_L <= g(x) <= g_U
            x_L <=  x  <= x_U
and returns a result in the form of IPOPTMinimization[id]
which can be queried using the functions IPOPTMinimizationMinimalPoint, IPOPTMinimizationObjectiveValue, etc.

I got a simple problem to run with IPOPTMinimization

In[9]:= Needs["IPOPTLink`"]

In[15]:= res = 
 IPOPTMinimize[
  x + y, {x^2 + y^2}, {{1, 1}}, {x, y}, {{-2, 2}, {-2, 2}}, {0, 0}]

Out[15]= IPOPTMinimization[4]

In[16]:= IPOPTMinimizationMinimalPoint[res]

Out[16]= {-0.707107, -0.707107}

In[17]:= IPOPTMinimizationObjectiveValue[res]

Out[17]= -1.41421

Thanks. It is interesting that if I add the constraint 0 <= Abs[x] + Abs[y] <= 2, it returns wrong result without an error message:

Needs["IPOPTLink`"]

res = IPOPTMinimize[
   x + y, {x^2 + y^2, Abs[x] + Abs[y]}, {{1, 1}, {0, 2}}, {x, 
    y}, {{-2, 2}, {-2, 2}}, {0, 0}];
IPOPTMinimizationMinimalPoint[res]
{0.707107, 0.707107}

But with constraint 0 <= Abs[x] + Abs[y] <= 4 the result is correct:

res = IPOPTMinimize[
   x + y, {x^2 + y^2, Abs[x] + Abs[y]}, {{1, 1}, {0, 4}}, {x, 
    y}, {{-2, 2}, {-2, 2}}, {0, 0}];
IPOPTMinimizationMinimalPoint[res]
{-0.707107, -0.707107}

When working on this question dedicated to what I believe is a significant limitation/defect of the current implementation of the "LevenbergMarquardt" algorithm in FindMinimum, I found that the same code evaluates 15 - 25 times slower in version 10.4.1 as compared to version 8.0.4 on the same machine!

At the bottom of this post a Notebook containing the complete setup reproducing the issue is attached.

The following is a comparison of absolute timings of the same FindMinimum code evaluated with the two versions along with the number of steps taken by FindMinimum, achieved minimum and obtained new values of parameters of the model. The setup can be found in the attached Notebook.

With version 8.0.4 on Windows 7 x64 I get the following:

findMinimum[init, MaxIterations -> 500, WorkingPrecision -> 20, PrecisionGoal -> 3, 
 StepMonitor :> ++steps, Method -> {"LevenbergMarquardt", "Residual" -> residualVect}]
{"00:06:35", 220, 0.00405321003823167,
{ν0[1]->406.18, Γ[1]->346.16, ζ[2]->0.22879, ν0[2]->666.41, Γ[2]->239.54, ζ[3]->0.20278}}

The output means that the evaluation has taken 6 min 35 sec and finished in 220 steps, obtained minimum is 0.00405321003823167, the obtained new values of the parameters follow.

And this is what I get with version 10.4.1 installed on the same machine:

findMinimum[init, MaxIterations -> 500, WorkingPrecision -> 20, PrecisionGoal -> 3, 
 StepMonitor :> ++steps, Method -> {"LevenbergMarquardt", "Residual" -> residualVect}]
{"02:37:07", 220, 0.00405321003823167,
{ν0[1]->406.18, Γ[1]->346.16, ζ[2]->0.22879, ν0[2]->666.41, Γ[2]->239.54, ζ[3]->0.20278}}

As you see, the only difference is that now the evaluation has taken 2 hours 37 min 7 sec! It is more than 23 times slower than with version 8.0.4!


Do you experience the same problem? Is it possible to get FindMinimum of version 10.4.1 working as fast as FindMinimum of version 8.0.4?

Hi Frank,

Have you read your last post? It seems you have faced a bug of this forum's engine...

I'll try again.

Ipopt uses the first and second derivative of the objective function and constraints. That may be why a constraint containing Abs doesn't always work, since the first derivative is discontinuous.

(duplicate post is emptied)

I don't understand why Wolfram Research doesn't do something like that.

IPOPT is already used by FindMinimum for constrained problems in 10.4, some documentation will be coming in the next release.

Can you confirm the described slowdown of FinMinimum in version 10? Is it a known problem?

@Alexey I do see the slowdown, which happened somewhere between version 8 and 9. Will investigate further, thank you very much for pointing it out.

@Alexey Popkov The slowdown should be addressed in version 11.0.

Thank you, the performance issue seems to be solved with version 11.0.0.

BTW, have you noticed this post of mine which raises much more subtle and interesting issue, and which (as I hope) can help to improve the "LevenbergMarquardt" algorithm in FindMinimum?

Would have been nice if you had told us that. Also, why doesn't FindMinimum take lower bounds and upper bounds on variables and give the constraint values and constraint and bound Lagrange multipliers the way Ipopt does?

Tooting my own horn, my code to call Ipopt can take multiple starting points as input in one run.

The IPOPT link enables you to create a parametric function object for varying the parameters in the objective function, constraints and variable and constraint bounds but does not enable you to run multiple starting points. That would have been very useful for improving NMinimize.

ParametricIPOPTMinimize::usage = "ParametricIPOPTMinimize[fx, gx, gbounds, xvars, xbounds, x0, params, opts] finds a local solution for the optimization problem min f(x, p) x in R^n s.t. gL(p) <= g(x, p) <= gU(p) xL(p) <= x <= xU(p) and returns a ParametricFunction object. For given parameter values the parametric function gives a \ solution object IPOPTMinimization[id], \ which can be queried using the functions IPOPTMinimizationMinimalPoint, IPOPTMinimizationObjectiveValue, etc."

In[1]:= Needs["IpOptInterface`Int`"]

In[2]:= callIpOpt[
 Sin[x y], {x^2 + y^2 == 1}, {{x, -2, {-1, 1}, 2}, {y, -2, {1, -1}, 
   2}}]

Out[2]= {{-0.479426, {x -> -0.707107, y -> 0.707107}, 
  "cons values" -> {1.}, 
  "var lb \[Lambda]s" -> {1.93821*10^-9, 9.25676*10^-10}, 
  "var ub \[Lambda]s" -> {9.25676*10^-10, 1.93821*10^-9}, 
  "cons \[Lambda]s" -> {0.438791}, 
  "Solve_Succeeded"}, {-0.479426, {x -> 0.707107, y -> -0.707107}, 
  "cons values" -> {1.}, 
  "var lb \[Lambda]s" -> {9.25676*10^-10, 1.93821*10^-9}, 
  "var ub \[Lambda]s" -> {1.93821*10^-9, 9.25676*10^-10}, 
  "cons \[Lambda]s" -> {0.438791}, "Solve_Succeeded"}}

FindMinimum in Version 11 has an option to use Ipopt, which I suspect is the default for constrained problems.

Yes, but it's a shame the Documentation Center still doesn't advertise this, to wit, the FindMinimum doc page still does not mention IPOPT as a Method option.
There is however a doc page for IPOPTLink: IPOPTLink/tutorial/OptimizingWithIPOPT

FindMinimum's performance is still very poor (I'm using version 11.3) because of the algorithm's failure to increase the step size when it ought to.

This would be more useful if accompanied by a specific example.

Daniel,

The code is too large to post on the forum and it would not be appropriate for me to share it publicly since the model that I'm developing is part of a larger research effort which is unpublished. However, I'd be happy to share the specific application privately with Wolfram Research.

Okay, that's fine. Can contact Technical Support via link below (feel free to note I requested it).

https://www.wolfram.com/support/contact/email/?topic=Technical

I suspect my own contact info is out there in cyberspace, so you could send to me directly if you prefer.

In any case, the more you can winnow to a direct example, the better.

I use ParametricIPOPTMinimize whenever possible.

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