How to find location of Minimum in Interpolation function?

Hi, when using an Interpolation object to approximate a function with values known over a few dozen discrete data points, how can I find where the (local) minimum of the function is? (Assuming that the minimum is not actually on one of the discrete data point locations, but somewhere in between two of them.)

Also, each of the commands below seem to produce the exact same thing (a connect-the-dots result with straight line segments between points); am I missing something? Thanks for any info!

plot(interpolate(data,BSpline(Constant())))
plot(interpolate(data,BSpline(Linear())))
plot(interpolate(data, BSpline(Quadratic(Reflect(OnCell())))))
plot(interpolate(data, BSpline(Cubic(Line(OnGrid())))))
(…etc…)

1 Like

What you’re asking is basically an optimization question.

So when we have a discrete set or collection of numbers, ie: [1,2,3,4], we can instruct our computer to find the minimum value or index quite easily(min or argmin).

But when we have a “function”. We need to use numerical optimization methods more often then not. So there’s an awesome Julia package called Optim.jl(https://julianlsolvers.github.io/Optim.jl/stable/). Highly reccommend it!

Here’s an example…

using Interpolations, Optim
t= 1:0.1:2pi
y = sin.(t)
interp_cubic = CubicSplineInterpolation(t, y)
bounds = [1.0, (2pi) - 0.1]
t_interp = first(bounds):0.01:last(bounds) 
scatter([t], [y], label = "raw")
plot!([t_interp], [interp_cubic(t_interp)], label = "Spline")

opt = optimize(x -> interp_cubic(x), first(bounds), last(bounds))
t_min = Optim.minimizer(opt)
scatter!( [t_min], [interp_cubic(t_min)], color = :red,label = "estimated min")

minexample

Hope this helps.

2 Likes

Hi ckneale, thanks a lot for your help & sample code.

I’ve been implementing it, and unfortunately the optimizer’s results are a bit poor & inconsistent.

For example, where y = y(x) is a simple function of x, and trying to minimize the distance z where z^2 = x^2 + y^2, I use cubic interpolation of z to find where z is smallest. x and y are (artificially) sampled as discrete data points.

It finds xMin, and zMin(xMin). Then using the distance formula, y = sqrt(z^2 - x^2), at xMin, I get y = 1.173. BUT, doing a cubic interpolation of the y data points themselves (and using the exact y(x)), yields the value 1.159 at xMin. That’s a pretty big difference!

Also, using Mathematica to find the exact minimum, gets xMin = 0.547 instead of Julia’s xMin = 0.554.

I understand some inexactness, but the inconsistency in y(xMin) is alarming. Is it supposed to be this off, or am I doing something wrong? I’ve included a copy of my sample code below… Thanks again for any feedback!


using Plots, Interpolations, Optim

k = 0.47
xSample = -12.0:1.0:12.0
y = Array{Float64,1}(undef, 25); z = Array{Float64,1}(undef, 25)
for i in 1:25
    y[i] = (1.42-(k*xSample[i]))
    z[i] = sqrt(xSample[i]^2+y[i]^2)
end
y_Interp_cubic = CubicSplineInterpolation(tSample, y)
z_Interp_cubic = CubicSplineInterpolation(tSample, z)
opt = optimize(Stuff -> z_Interp_cubic(Stuff), -12.0, 12.0)
xFORzMin = Optim.minimizer(opt)
yATmin = y_Interp_cubic(xFORzMin)
zMin = z_Interp_cubic(xFORzMin)
println("xFORzMin = ",xFORzMin,"   yATmin = ",yATmin,"   zMin = ",zMin)
InterpDisagreement = zMin-sqrt((xFORzMin^2)+(yATmin^2))
println("InterpDisagreement = ",InterpDisagreement)
yMinValDisagreement = yATmin - sqrt((zMin^2)-(xFORzMin^2))
println("yMinValDisagreement = ",yMinValDisagreement)
#
plot(xSample, abs.(xSample), xlim=(-2,3), ylim=(0,2.5)); plot!(xSample, abs.(y)); plot!(xSample, z)
scatter!(xSample, abs.(xSample)); scatter!(xSample, abs.(y)); scatter!(xSample, z)
xFine = -12.0:0.01:12.0
plot!(xFine,z_Interp_cubic(tFine), linewidth=3); scatter!([xFORzMin], [z_Interp_cubic(xFORzMin)], markersize=7)
scatter(xSample, y); plot!(xFine,y_Interp_cubic(tFine))

You should be able to change the tolerance of the optimization method to get a better approximation. That said your error will depend highly upon your interpolant, and grid spacing. The finer the grid the better your spline will fit. Similarly, you might obtain a closer match with a better interpolant function. For example, there’s no reason to expect your function will follow a cubic spline. Sometimes it’s good enough, but often times interpolation is more cosmetic/approximate than anything. We might want to ask ourselves, “should we be interpolating in the first place?”.

Some of the optimization methods benefit from things like derivatives, hessians, etc. I’d reccomend reading through the docs a bit and trying to see what you can come up with for your problem statement. Might get more lift that way. If your function is analytic, you can analytically determine your minima using calculus :D.

Big picture, we are opening up lots of degrees of freedom for us to get things wrong (add error). Barring that, I think I need more information about what you are trying to do. For some reason I think you will want to use Kriging here… But again, if you could specify your exact needs we can probably help you get where you’re trying to go.