# NMaximize with Nelder-Mead method fails to convergence when tolerance set too high

Recently I have been working on a optimization problem for which I use NMaximize with Nelder-Mead method.

In general, I have to check a lot of systems which are built automatically. I want to skip those for which the maximum cannot be found under given constraints. Therefore, I check if the warning NMaximize::nosat occurs, and when it does, I continue my algorithm with different system. I do it this way because I want to check which constraints are good and which are not (the values returned by NMaximize are not important). So instead of solving each system, I use NMaximize because it is faster.

What I have found and do not quite understand is that sometimes NMaximize, instead of giving me the message NMaximize::nosat, gives an message complaining about failure of convergence.

NMaximize::cvmit: Failed to converge to the requested accuracy or precision within 100 iterations.

I tired to overcome this problem by changing the default number of iterations, but without any success (it works for a really high number of iterations). Finally, I solved it by playing with the value of tolerance. What I found surprising is that the problem was solved for by setting a very small value for tolerance and not by setting a value higher than the default.

Could somebody explain to me how changing the tolerance affected the convergence for functions, which under the given constraints, normally should not be optimized? More importantly, why I do observe convergence for a smaller tolerance value when I rather expect to see it for a higher one.

Here is the demo code:

system = {x, -(1/2) + x + omega1^2 (1 - Cos[theta]) +
Cos[theta] <= -(1/100000),
1/2 + x + omega1^2 (1 - Cos[theta]) + Cos[theta] >=
1/100000, -(1/2) +
y + omega1 omega2 (1 -
Cos[theta]) + omega3 Sin[theta] <= -(1/100000),
1/2 + y + omega1 omega2 (1 -
Cos[theta]) + omega3 Sin[theta] >=
1/100000, -(1/2) +
z + omega1 omega3 (1 -
Cos[theta]) - omega2 Sin[theta] >= 1/100000,
1/2 + z + omega1 omega3 (1 -
Cos[theta]) - omega2 Sin[theta] >= 1/100000,
1/100000 <= theta <= -(1/100000) + \[Pi]/
4, {omega1, omega2, omega3} \[Element]
Sphere[{0, 0, 0}, 1],
1/100000 <= omega1 <= omega2 <= omega3 <=
99999/100000, -(49999/100000) <= x <=
49999/100000, -(49999/100000) <= y <=
49999/100000, -(49999/100000) <= z <= 49999/100000};

NMaximize[system, {theta, omega1, omega2, omega3, x, y,
z}, Reals, Method -> {"NelderMead","Tolerance" -> 1/100000}]

• One thing you did not make clear to me is exactly what NMaximize option you are calling 'tolerance'. Could you give the actual Mathematica name for the option. Jun 12, 2015 at 11:02
• Indeed, relative or absolute tolerance? Jun 12, 2015 at 11:41
• "Tolerance" in Nelder-Mead is "tolerance for accepting constraint violations" reference.wolfram.com/language/tutorial/… Jun 12, 2015 at 11:43
• Tolerance works by adding in a penalty function at the constraint boundary. If that function is more sharply defined by specifying a smaller tolerance then there is a smaller incursion into the prohibited range thus fewer iterations for a given step change of parameter values between iterations needed to converge on the constraint boundary.
– Carl
Apr 15, 2022 at 11:53

According to the documentation, for the Nelder-Mead method,

"Tolerance" is the tolerance for accepting constraint violations

I think you actually meant to use either PrecisionGoal or AccuracyGoal, as per the documentation under NMaximize, depending on whether you want relative or absolute convergence criteria. Indeed, if you set AccuracyGoal to a smaller number, the cvmit error goes away:

NMaximize[system, {theta, omega1, omega2, omega3, x, y, z}, Reals,
Method -> {"NelderMead"}, AccuracyGoal -> 1]

• That is not surpassing, but not what I meant. Interesting is why change of "Tolerance" also fixed the problem. Maybe I did not make myself clear in my question. Jun 12, 2015 at 14:27