# Convergence of FindMinimum

Posted 8 years ago
4921 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.  Answer
10 Replies
Sort By:
Posted 8 years ago
 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. Answer
Posted 8 years ago
 Here's the code:n = 10^4; SeedRandom; 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}]] Answer
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;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; 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; 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}]]  Answer
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. Answer
Posted 8 years ago
 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. Answer
Posted 8 years ago
 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 setFindArgMin[{Sin[x y], x^2 + y^2 == 1}, Thread[{{x, y} , #}],    Method -> {"InteriorPoint",      "StepControl" -> "TrustRegion"}] & /@ rs  Answer
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". Answer
Posted 8 years ago
 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. Answer
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... Answer
Posted 8 years ago
 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. Answer