# How trustworthy is NMaximize?

Suppose I solve a constrained optimisation problem using NMaximize. How confident can I be of the accuracy of the result?

For concreteness, suppose that F,G are (exactly known) functions (say, polynomials with rational coefficients for concreteness), and in answer to NMaximize[ {F[x,y,z], G[x,y,z] > 0}, {x,y,z}] Mathematica produces something like { .453, {x->.787, y->.342, z-> .235} }, with no errors or warnings.

Levels of confidence I have in mind are:

1. The result is provably correct, in the sense that one could in principle use it in a pure mathematics paper (up to some controllable error term, naturally).

2. The result is certainly correct, in the sense that for it to be false would require a lot of very improbable coincidences, and hence it would be very unlikely to happen (but still it might be false, in principle).

3. The result might or might not be correct, depending on a number of factors beyond our control, which may conceivably go wrong (e.g. if F has a very sharp maximum somewhere, the domain is highly non-convex, etc.).

Edit: By "correct" answer I mean a global maximum, found with reasonable accuracy. Hence, if the answer is a local maximum (or worse still, not a maximum at all), then I would consider this answer to be wrong. If the answer is roughly correct but has slightly worse precision than claimed, I am not particularly worried about this.

• What do you mean by "correct" precisely? It can be incorrect as in: 1. the result isn't even a maximum 2. the result is a local, but not global maximum 3. the result is a global maximum but the precision is bad, e.g. it gives 0.215 and claims 3 digits but the real answer is 0.217. – Szabolcs Feb 22 '15 at 16:54
• For what it's worth: Neither the code, nor the machine it is running on can be proven correct, at least not within reasonable time/budget/manpower boundaries. – Jinxed Feb 22 '15 at 17:05
• In any case, the classical methods of verifications could be applied: Check the result. Check small deviations from it. Check the function's behavior near that point using derivatives, make a plot, perform some analytical analysis, ... – Jinxed Feb 22 '15 at 17:07
• You'll find a detailed description of the available methods here (look for numerical global optimization). Most methods have no guarantees about finding the true global maximum. The first (and more relevant) question is how do these methods perform on different problems, and the second how good Mathematica's implementations of the methods are. – Szabolcs Feb 22 '15 at 17:30
• For NMaximize I'd go with door #3. Maximize should give a guaranteed result though. – Daniel Lichtblau Feb 23 '15 at 4:08

The answer to your question is strongly dependent on the function you want to maximize. Convex functions can be maximized quite easily, with the error controlled by the PrecisionGoal and WorkingPrecision that you set in the options.
However, for non-convex functions, you generally need to be very careful about checking your answers. Generally, most global optimization algorithms involve a combination of random initialization and recombination and local gradient descent. The methods of Mathematica's NMinimize are no exception. I find that DifferentialEvolution tends to give good results, but its outputs are fundamentally stochastic; it's based off of a generalization of a genetic algorithm.