Group Abstract Group Abstract

Message Boards Message Boards

Performance reduction of FindMinimum in version 10

Alexey Popkov
Posted 10 years ago
Attachments:
POSTED BY: Alexey Popkov
29 Replies
Sort By:

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

This would be more useful if accompanied by a specific example.
POSTED BY: Daniel Lichtblau
POSTED BY: Matt Latourette

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

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

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

POSTED BY: Frank Kampas

enter image description here
POSTED BY: Valeriu Ungureanu
POSTED BY: Frank Kampas

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
Alexey Popkov
Alexey Popkov
Posted 10 years ago

Can you confirm the described slowdown of FinMinimum in version 10? Is it a known problem?
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

@Alexey Popkov The slowdown should be addressed in version 11.0.
POSTED BY: Ilian Gachevski
Alexey Popkov
Alexey Popkov
Posted 10 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

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

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

Is your package published?

POSTED BY: Alexey Popkov
Alexey Popkov
Alexey Popkov
Posted 10 years ago
POSTED BY: Alexey Popkov

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

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
Alexey Popkov
Alexey Popkov
Posted 10 years ago

(duplicate post is emptied)
POSTED BY: Alexey Popkov

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
Alexey Popkov
Alexey Popkov
Posted 10 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
Alexey Popkov
Alexey Popkov
Posted 10 years ago
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.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard