# 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. – m_goldberg Jun 12 '15 at 11:02
• Indeed, relative or absolute tolerance? – dr.blochwave Jun 12 '15 at 11:41
• "Tolerance" in Nelder-Mead is "tolerance for accepting constraint violations" reference.wolfram.com/language/tutorial/… – dr.blochwave Jun 12 '15 at 11:43

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. – marekszpak Jun 12 '15 at 14:27