Message Boards Message Boards

GROUPS:

Convergence of FindMinimum

Posted 8 years ago
4920 Views
|
10 Replies
|
5 Total Likes
|
I wondered if FindMinimum always converges to the nearest minimum, so I minimized sin(x) cos(y)  with random starting points with x and y between -6 and 6 and colored the points by the location of the minimum.

10 Replies
I get basically the same plot for the constrained problem if I use a LibraryLink interface to Ipopt ( https://projects.coin-or.org/Ipopt )
but in 1/4 the time.
Posted 8 years ago
Frank,
Yes, unfortunately the absence of an error message does not necessarily mean that the option is available. Only presence of an error message should be considered as a prove that the option is not supported, but even for this rule may be rare exceptions. The official politics of the WRI is that only documented behavior is supported. At the same time, the Documentation is very sparse and it sometimes takes hours even for an experienced user to find an "obvious" option hidden deeply in the Documentation. This thread is an illustration: how much time you would spend finding all that information having only the Documentation? I am certain that a newbie has no chance! Note also how simple and obvious looks the answer: it is hard to believe that such "obvious" things are really deeply hidden and in practice are unavailable even for experienced users...
Alexey,
I didn't get an error message when I added the option, so I assumed it was a valid option.
Perhaps the absence of an error message does not mean the option is available.
Posted 8 years ago
Frank,
I cannot find in the Documentation any mention of the "StepControl" suboption for the "InteriorPoint" method. Please provide a link if you have.
Brief search give me only this: The Method Options of "InteriorPoint".
StepControl -> TrustRegion doesn't seem to make any difference for constrained problems solved using the InteriorPoint method.  I get the same result with and without that option set
FindArgMin[{Sin[x y], x^2 + y^2 == 1}, Thread[{{x, y} , #}],
   Method -> {"InteriorPoint",
     "StepControl" -> "TrustRegion"}] & /@ rs
Thanks for pointing that out Alexey.  I have looked at the Unconstrained Optimization tutorial, but didn't go to the one on Newton's method.  Personally, I think that the Options function in Mathematica should be made more powerful so you can somehow see Options on Options.  Perhaps some sort of tree structure.
Posted 8 years ago
Thanks for the code, it is interesting to compare different methods. For example, if one changes the default  "StepControl" -> "LineSearch" to "StepControl" -> "TrustRegion", the plot becomes well-ordered:
n = 10^4; SeedRandom[0];
rs = RandomReal[{-6, 6}, {n, 2}];
Off[FindArgMin::lstol];
resn = FindArgMin[Sin[x] Cos[y], Thread[{{x, y}, #}],
     Method -> {"Newton", "StepControl" -> "TrustRegion"}] & /@ rs;
c[{x_, y_}] = RGBColor[(x + 6)/12, (y + 6)/12, 0]; Show[
Graphics@Table[{c[resn[[i]]], Point[rs[[i]]]}, {i, n}]]


From the other side, setting bigger value of "StartingScaledStepSize" suboption gives lesser ordered result as expected:
 n = 10^4; SeedRandom[0];
 rs = RandomReal[{-6, 6}, {n, 2}];
 Off[FindArgMin::lstol];
 resn = FindArgMin[Sin[x] Cos[y], Thread[{{x, y}, #}],
      Method -> {"Newton",
        "StepControl" -> {"TrustRegion",
          "StartingScaledStepSize" -> 10}}] & /@ rs;
 c[{x_, y_}] = RGBColor[(x + 6)/12, (y + 6)/12, 0]; Show[
 Graphics@Table[{c[resn[[i]]], Point[rs[[i]]]}, {i, n}]]


There also are other suboptions of the "TrustRegion" method one can play with.

And playing with the "StepControl" -> "LineSearch" suboptions allows to get well-ordered result too:
 n = 10^4; SeedRandom[0];
 rs = RandomReal[{-6, 6}, {n, 2}];
 Off[FindArgMin::lstol];
 resn = FindArgMin[Sin[x] Cos[y], Thread[{{x, y}, #}],
      Method -> {"Newton",
        "StepControl" -> {"LineSearch",
          "MaxRelativeStepSize" -> .1}}] & /@ rs;
 c[{x_, y_}] = RGBColor[(x + 6)/12, (y + 6)/12, 0]; Show[
 Graphics@Table[{c[resn[[i]]], Point[rs[[i]]]}, {i, n}]]
Here's the code:
n = 10^4; SeedRandom[0]; rs = RandomReal[{-6, 6}, {n, 2}]; Off[
FindArgMin::lstol]; resn =
FindArgMin[Sin[x] Cos[y], Thread[{{x, y} , #}],
    Method -> "Newton"] & /@ rs;
c[{x_, y_}] = RGBColor[(x + 6)/12, (y + 6)/12, 0]; Show[
Graphics @ Table[{c[resn[[i]]], Point[rs[[i]]]}, {i, n}]]
This is kinda similar to what you see with Newton Fractals
The answer is no. It won't always converge to the nearest root. For example, plotting the basins of attraction for newton's method produces pretty fractals. 
Posted 8 years ago
The behavior of FindMinimum depends on the Method and on values of its sub-options.
Please post the code you used to produce the graphics.
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