Need advice on how to accelerate a problem of 5 variables

[ShuhuaGao]

Hi, I am currently using IntervalOptimisation to find the global minimum (or at least a tight bound) for a nonlinear least-squares problem that includes 5 parameters to be optimized.

The dataset in a CSV file that contains 26 data points can be downloaded here.

Julia code

using CSV, Tables
using IntervalArithmetic, IntervalOptimisation

# read data into a 26×2 Array
const data = CSV.File("data.csv") |> Tables.matrix
const Vt = 0.02638199348809556

function sse_sdm(θ)
    Ir, I0, n, Rs, Rp = θ
    return sum((Ir - I0*1e-6*(exp((V + I*Rs)/(n*Vt)) - 1) - (V + I*Rs)/Rp - I)^2 for (V, I) in eachrow(data))
end

intervals = (0..1)×(0..1)×(1..2)×(0..0.5)×(0..100)
@time minimum, minimisers = minimise(sse_sdm, intervals)

The above code has run more than one and a half hours (still running now). I am wondering whether there are any suggestions that can help accelerate the optimization. I saw in the Julia discourse that the nonrecursive_powers branch may be faster; however, I cannot find it.

[mforets]

nonrecursive_powers branch may be faster; however, I cannot find it.

That branch is from another package (IntervalArithmetic.jl); try ] add IntervalArithmetic#nonrecursive_powers.

[dpsanders]

Unfortunately interval optimisation is often rather slow in higher dimensions.
It should help to use IntervalConstraintPropagation.jl, but this is not hooked up out of the box yet.

[dpsanders]

You can also try using the mean value form from #25. Let me know if you need help with that.

[mforets]

The search space is perhaps too coarse? Picking some sub-intervals on the initial domain,

using IntervalArithmetic

@time sse_sdm((0.9 .. 1.0, 0.9 .. 1.0, 1.8 .. 2.0, 0.4 .. 0.5, 60 .. 62.))
  0.000087 seconds (802 allocations: 33.469 KiB)
[4.00514, 1542.37]

This, at least, gives guaranteed lower/upper bounds very quickly on smaller regions. Note that if you evaluate only once on the full domain (which is generally a bad idea):

@time sse_sdm((0 .. 1.0, 0 .. 1.0, 1 .. 2.0, 0 .. 0.5, 0 .. 100.))
  0.000062 seconds (806 allocations: 40.219 KiB)
[0, ∞]

[ShuhuaGao]

You can also try using the mean value form from #25. Let me know if you need help with that.

Thank you. Now it has run more than 30 hours (still running 😅). I have no idea of the mean value form. Would you kindly make some explanation or give an example?

[ShuhuaGao]

@mforets Thank you for your advice. I need a more tight bound and thus perform optimization. Following your idea, I reduced the domain to a very small one, intervals = IntervalBox(0.7 .. 0.77, 0.3 .. 0.35, 1.45 .. 1.49, 0 .. 0.05, 50 .. 55), which to my knowledge contains the global optimum. Nonetheless, even with such small intervals, the minimise(sse_sdm, intervals) has run more than 4 hours still with no results. I guess the difficulty may be attributed to some inherent property of this nonlinear least-squares problem, e.g., many local minima.

[dpsanders]

I am playing with this problem. The first thing I notice is that just evaluating the function sse_sdm is very slow, but I'm not sure why.

[ShuhuaGao]

Hi, @dpsanders. The evaluation of sse_sdm should be pretty fast. Benchmark results:

@btime sse_sdm($x)

920.000 ns (5 allocations: 224 bytes)

Besides, with intervals = IntervalBox(0.7 .. 0.77, 0.3 .. 0.35, 1.45 .. 1.49, 0 .. 0.05, 50 .. 55), it has taken more than 24 hours without finish. Nonetheless, this behavior was expected according to my experience with another interval analysis based optimizer ibex.

I am also playing with ibex. Overall, ibex has better performance than IntervalOptimisation for this specific problem. ibex can handle the 5-parameter case we are discussing here within 4 hours, while it is stuck with a more complicated 7-parameter case and trapped in a very small region around x*.

If interested, you may refer to the conversation in this issue for more details and possible inspiration.