Why is EvaluationMonitor not always run when the objective function is called?

Question

A simple demonstration:

f[x_?NumericQ] := (Print["f[x]"]; x^4 - 3 x^2 - x)
NMinimize[f[x], x, EvaluationMonitor :> Print["EvaluationMonitor"], MaxIterations -> 1]

I would except that the output is a repetition of

f[x]
EvaluationMonitor
f[x]
EvaluationMonitor
...

but if I look at the later stages of the output, this shows that the EvaluationMonitor is not always called when f[x] is called, and the output looks more like this:

f[x]
f[x]
f[x]
f[x]
f[x]
...
EvaluationMonitor
f[x]
f[x]
...

I get the same behavior for other functions such as FindMinimum. The example function is not linear, so I guess this is not the same issue as in this post?

This mainly bothers my because sometimes I have much more complex (non-linear) functions, sometimes with external program calls, and I want to use this method to gracefully terminate the optimization after a number of iterations - and if EvaluationMonitor is not executed every time the function is called, this gets complicated...

EDIT:

Another demonstration, also showing the values of the variable x when f[x] is called (+ low settings for the various Precision options):

f[x_?NumericQ]:=(Print["f["<>ToString[x//FullForm]<>"]"];x^4-3 x^2-x)
NMinimize[f[x],x,EvaluationMonitor:>Print["EvaluationMonitor"],MaxIterations->1,AccuracyGoal->2,PrecisionGoal->2,WorkingPrecision->4]

If you look at the output, you can see that some (all?) of the calls of f[x] that happen without running the EvaluationMonitor were already run before with the identical x. For example:

...
f[1.3414060135376415805`4.]
EvaluationMonitor
f[1.3414060135376415805`4.]
f[1.4842631563947844377`4.]
f[1.6271202992519272948`4.]
f[1.1985488706804987234`3.907144839865827]
f[1.0556917278233558663`3.8121174553460224]
EvaluationMonitor
f[1.3414060135376415805`4.]
f[1.4842631563947844377`4.]
f[1.6271202992519272948`4.]
f[1.1985488706804987234`3.907144839865827]
f[1.0556917278233558663`3.8121174553460224]
EvaluationMonitor
f[1.354820073673017999`4.]
...

This seems relatively unnecessary to me, and for the cases where one call of f[x] takes a relatively long time, these calls increase the time to find an optimum dramatically. Sometimes I only need a rough estimate - but as you can see, adjusting the Precision options does not help with this issue.

Answer 1

EvaluationMonitor keeps track of the evaluations caused by NMinimize directly; the "extra" evaluations come from the post-processing done by the low-level optimization routines called by NMinimize.

In fact, you can prevent the extra evaluations of f by turning the post-processing off:

Clear[f]
f[x_?NumericQ] := (Print["f[x]"]; x^4 - 3 x^2 - x)

NMinimize[
 f[x], x,
 EvaluationMonitor :> Print[Style["eval", Blue]],
 MaxIterations -> 3, Method -> {"NelderMead", "PostProcess" -> False}
]

More in general, you can still let the NMinimize heuristics choose the method automatically, but turn off the post-processing, using Method -> {Automatic, "PostProcess" -> False}.

See the various options here: Numerical Algorithms for Constrained Global Optimization - Tutorial