Minimization with nongrid Interpolation function

I'm trying to minimize a complicated objective functional, which involves unstructured and unsmooth data on the backend of the functional evaluation. The real problem I'm trying to solve is a bit more complicated (and given my attempts to solve it so far will likely need to followup in a different question), but I think this simplified example shows the first part I'm having difficulties with. Consider some random, nongrid coordinate pairs:

SeedRandom[100];
data = RandomReal[{}, {100, 2}];


Mapping these coordinates to some arbitrary function we get some a 3D data set.

zdata = (#[[1]] - .5)^4 + (#[[2]] - .5)^4 & /@ data;
totaldata = Transpose@Join[Transpose@data, {zdata}];


Mathematica can now handle, with the option InterpolationOrder -> 1, unstructured data by default in Interpolation.

fun = Interpolation[totaldata /. {a_, b_, c_} :> {{a, b}, c}, InterpolationOrder -> 1]


One possible visualize of these data is

DensityPlot[fun[x, y], {x, 0, 1}, {y, 0, 1}]


However, this throws a warning from Mathematica regarding extrapolation. This is not necessarily a bad thing, but the real problem doesn't seem to handle extrapolation during the evaluation of NMinimize. I thought of a way of handling this problem, but it is a bit clunky

funexcept =
Interpolation[totaldata /. {a_, b_, c_} :> {{a, b}, c},
InterpolationOrder -> 1,
"ExtrapolationHandler" -> {Indeterminate &,
"WarningMessage" -> False}]
funextrap[x_, y_] :=
If[funexcept[x, y] === Indeterminate, Max@zdata, funexcept[x, y]]


Now the interpolation function appears to be well defined for all values in the bounding domain. Visualizing the differences between these two approaches:

Grid[{{DensityPlot[fun[x, y], {x, 0, 1}, {y, 0, 1}],
DensityPlot[funextrap[x, y], {x, 0, 1}, {y, 0, 1},
PlotRange -> All]}}]


In the real problem the objective functional is significantly more complicated, but here assuming minimizing the interpolation function is the objective:

NMinimize[fun[x, y], {x, y} \[Element] Rectangle[{0, 0}, {1, 1}]]
NMinimize[funexcept[x, y], {x, y} \[Element] Rectangle[{0, 0}, {1, 1}]]


The first NMinimize does return the optimal value, but throws a bunch of warnings (the real problem does not evaluate). The second evaluation throws the same extrapolation warning as the first, and returns unevaluated. Looking at the warning of the second NMinimize, the warning states that a point at {x,y} = {0.8992,0.973579} is not a number, however, calling the interpolation function outside NMinimize does return a value.

funextrap[0.899199876332835, 0.9735786719205788]
(*0.116205*)


So I'm looking for a bit of help on NMinimize use this modified type Interpolation function.

• Try ClearAll[funextrap]; funextrap[x_?NumericQ, y_?NumericQ] :=.... Probably NMinimize examines the function symbolically first, when determining the method. If it does, then the If[...] will evaluate to the False case. (I'm assuming you wanted funextrap  instead of funexcept in the second NMinimize.) Jan 8 '17 at 17:06
• With regard to interpolating the data I think you might find Data interpolation helpful. Jan 8 '17 at 17:40
• Why not MinimalBy[totaldata, Last]? Jan 8 '17 at 19:11
• @MichaelE2 It was silly to forget to force numeric evaluation on modified interpolation function. You are also correct in assuming funextrap instead of funexcept in the NMinimize call. Making that change does appear to yield a minimizable function. MinimalBy works in this case, but the actual problem is not necessarily expected to be optimized at a grid point. @JackLaVigne thanks for the link. For this problem the computational cost of the spline interpolation method is pretty costly, and even in this simplified problem fails to converge to the expected value. Jan 9 '17 at 3:00

Can't you just manually add the corners of the minimization region to the data?

SeedRandom[100];
data = Join[RandomReal[{}, {100, 2}], {{0, 0}, {0, 1}, {1, 0}, {1, 1}}];


Now

DensityPlot[fun[x, y], {x, 0, 1}, {y, 0, 1}]


gives

and

NMinimize[fun[x, y], {x, y} \[Element] Rectangle[{0, 0}, {1, 1}]]


{2.18718*10^-6, {x -> 0.538073, y -> 0.482894}}

without any warnings at all.

• This is a definitely a solution, but the real problem involves concave and isolated regions which would be tedious to manually add points to complete the data field. Thanks for the thought though. Jan 9 '17 at 16:26
• But that has nothing to do with this question though, right? Linear interpolation will miss those regions regardless, unless you provide more points... Jan 9 '17 at 17:23
• I was trying to streamline the implementation of an interpolation object, in this case funextrap, which would simply return some numeric value for inputs not in the function construction domain. So yes, while generally linear interpolation will miss those regions, the interpolation function will be at least defined for those input values. Jan 9 '17 at 19:56