5
$\begingroup$

I discovered the following behaviour when using FindMinimum for constrained optimization:

Clear@f
f[x_?NumericQ] := (Print@Precision@x; x^2)
FindMinimum[{f[x], x < 1}, {x, 1}, WorkingPrecision -> 500]
(*MachinePrecision*)
(*...*)
(*31.25*)
(*...*)
(*62.5*)
(*...*)

Note that this bevaviour changes when removing either the constraint or the NumericQ. I'm guessing Mathematica increases the WorkingPrecision in order to sample the region of the constraints. This is all fine if f returns a value no matter the WorkingPrecision, but not if it returns Indeterminate or something similar. It seems that FindMinimum internally sets $MaxPrecision in order to set the precision.

Is there a way around this?

$\endgroup$
5
$\begingroup$

This interesting behavior seems to be a characteristic of the interior point method, which is the only one available in FindMinimum that is applicable to constrained problems. That it is due to the method and not the existence of constraints can be seen by removing the constraints and specifying the method explicitly.

Ramping the precision from MachinePrecision to WorkingPrecision as the minimization proceeds is probably meant as a performance optimization, but clearly it could cause incorrect behavior in some cases. It is hard-coded in the definition of Optimization`NonlinearInteriorPointDump`IPSolveInternal (the interior point method seems to be one FindMinimum method that is not actually implemented in C, so we can see how it works) and, as such, a workaround is the only option available.

Fortunately, NMinimize can deal with constrainted problems using any method, because it preprocesses the problem so that unconstrained methods can be used. The Nelder-Mead method is a fairly efficient quasi-local minimization algorithm, which should be a reasonable alternative to FindMinimum. Particularly given that the interior point method is also implemented in top-level code and is so inefficient to begin with, we do not have very much to lose, perhaps even for expensive objective functions.

We can try:

Clear[f, evals];
evals = 0;
f[x_?NumericQ] := (
   Print["evaluation ", evals++, ", precision = ", Precision@x];
   x^2
  );
NMinimize[{f[x], x < 1}, x,
 WorkingPrecision -> 500, MaxIterations -> 500,
 Method -> {"NelderMead", "InitialPoints" -> {{1}, {1/2}}}
]

It takes 849 objective function evaluations, as compared to 907 for the interior point method, so its efficiency is comparable. (Obviously, this also depends on the problem and the choice of initial points.) But more importantly, every evaluation is at the requested WorkingPrecision, except for some evaluations actually done at infinite precision (I don't know why this happens). However, it may be worth noting that, for different objective functions, the evaluation precision can slip slightly below the WorkingPrecision. For Sinc[x], for example, the evaluation precision can go as low as 499.526. This is unlikely to be problematic in most cases, but it is something to be aware of in case you expect an evaluation precision of always exactly 500.

$\endgroup$
  • $\begingroup$ Great. Thanks for the additional info! $\endgroup$ – sebhofer Mar 8 '15 at 17:17

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.