Message Boards Message Boards

Performance reduction of FindMinimum in version 10

GROUPS:

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
Answer
1 year ago

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
Answer
1 year 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
Answer
1 year ago

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
Answer
1 year 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
Answer
1 year ago

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
Answer
1 year ago

Is your package published?

POSTED BY: Alexey Popkov
Answer
1 year 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
Answer
1 year ago

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
Answer
1 year 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
Answer
1 year 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?

POSTED BY: Frank Kampas
Answer
1 year 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
Answer
1 year ago

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
Answer
1 year ago

(duplicate post is emptied)

POSTED BY: Alexey Popkov
Answer
1 year ago

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
Answer
1 year ago

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

POSTED BY: Alexey Popkov
Answer
1 year ago

@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
Answer
1 year ago

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

POSTED BY: Ilian Gachevski
Answer
1 year 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
Answer
1 year ago

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
Answer
1 year ago

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
Answer
1 year ago
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
Answer
1 year ago

enter image description here

POSTED BY: Valeriu Ungureanu
Answer
1 year ago

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

POSTED BY: Frank Kampas
Answer
1 year ago

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
Answer
7 months ago

Group Abstract Group Abstract