10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Szabolcs Feb 22 '15 at 16:54
  • $\begingroup$ 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. $\endgroup$ – Jinxed Feb 22 '15 at 17:05
  • $\begingroup$ 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, ... $\endgroup$ – Jinxed Feb 22 '15 at 17:07
  • 2
    $\begingroup$ 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. $\endgroup$ – Szabolcs Feb 22 '15 at 17:30
  • 1
    $\begingroup$ For NMaximize I'd go with door #3. Maximize should give a guaranteed result though. $\endgroup$ – Daniel Lichtblau Feb 23 '15 at 4:08
14
$\begingroup$

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 densel 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.