Message Boards Message Boards

Performance reduction of FindMinimum in version 10

Posted 8 years ago

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:
POSTED BY: Alexey Popkov
29 Replies

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.

POSTED BY: Daniel Lichtblau

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.

POSTED BY: Matt Latourette

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

POSTED BY: Daniel Lichtblau

I use ParametricIPOPTMinimize whenever possible.

POSTED BY: Frank Kampas

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.

POSTED BY: Matt Latourette

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

POSTED BY: Frank Iannarilli
Posted 8 years ago

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?

POSTED BY: Alexey Popkov

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

POSTED BY: Frank Kampas

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

POSTED BY: Ilian Gachevski

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.

POSTED BY: Frank Kampas
Posted 8 years ago

Hi Frank,

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

POSTED BY: Alexey Popkov

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?

POSTED BY: Frank Kampas
Posted 8 years ago

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}
POSTED BY: Alexey Popkov

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."

POSTED BY: Frank Kampas

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
POSTED BY: Frank Kampas
Posted 8 years ago

(duplicate post is emptied)

POSTED BY: Alexey Popkov
Posted 8 years ago

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.
POSTED BY: Alexey Popkov

@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.

POSTED BY: Ilian Gachevski
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"}}
POSTED BY: Frank Kampas

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.

POSTED BY: Frank Kampas
Posted 8 years ago

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

POSTED BY: Alexey Popkov
Posted 8 years ago

Is your package published?

POSTED BY: Alexey Popkov

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.

POSTED BY: Ilian Gachevski
Posted 8 years ago

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).

POSTED BY: Alexey Popkov

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.

POSTED BY: Frank Kampas

Dear Alexey,

this is what I get on one of my systems:

enter image description here

So that is 27 minutes.

Cheers,

Marco

POSTED BY: Marco Thiel
Posted 8 years ago

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:
POSTED BY: Alexey Popkov

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

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