# 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.
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.
Posted 8 years ago
 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}]]
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}]]
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.
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.
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
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".
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.