How trustworthy is NMaximize?

Question

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.

Answer 1

As was pointed out above, this is a good summary of Mathematica's constrained optimization methods. Read through this if you want to know a lot more. A quick answer is below:

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.

The more local minima your function has, the worse off you are. Global, constrained optimization is actually a large field and cannot be explained in a single post. They key is to realize that for most situations where you have a non-convex function, it is difficult to strictly guarantee that you have found the minimum. If you can guarantee some properties about how curvy your function can be, you can sample your space sufficiently densely that you can guarantee you have not missed a potential minimum.

You should be more precise about defining the accuracy of your result as well. Accuracy can be defined in terms of the precision of the objective function your are optimizing, or in terms of the precision of the coordinates which optimize the objective function. For example, very slowly varying functions can cause a halt in some optimizations, as the computer cannot detect changes in the function with further changes in the coordinates. Mathematica is generally smart about this though, and you get to set the precision goal of the objective function when you call NMinimize.

I am sorry for the fuzzy answer, but the answer is just highly dependent on the input function.