# Latest recommendations for global optimization

**URL:** <https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718>\
**Category:** Optimization (Mathematical)\
**Tags:** package\
**Created:** [November 19, 2018, 3:51pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718 "2018-11-19T15:51:05Z")\
**Posts on this page:** 20\
**Page:** 4

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [December 18, 2019, 11:49am UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/61 "2019-12-18T11:49:04Z")

</div>

What’s the run length measured in? Function evaluations or wall clock time?

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [December 18, 2019, 12:13pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/62 "2019-12-18T12:13:41Z")

</div>

Number of function evaluations. In the original benchmark they go up to 1e7, but this takes already took like 20 minutes to run.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 18, 2019, 2:03pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/63 "2019-12-18T14:03:59Z")

</div>

That’s very interesting. Could you please share the benchmarking code?

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 18, 2019, 2:04pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/64 "2019-12-18T14:04:50Z")

</div>

Did you use the fastpowers branch of IntervalArithmetic.jl? That should give a huge speedup.

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [December 18, 2019, 2:42pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/65 "2019-12-18T14:42:13Z")

</div>

My script is [here](https://github.com/jonathanBieler/BlackBoxOptimizationBenchmarking.jl/blob/master/scripts/benchmark_interval_optim.jl) (need master, my PR of IntervalOptimisation and a couple of other packages, like BlackBoxOptim.jl).

I just tried the fastpowers branch but I’m getting this :

```julia
julia> minf, minx = minimise( x->sum(abs2.(x)), IntervalBox(-5.5..5.5, 3) )
ERROR: MethodError: no method matching +(::Interval{Float64}, ::RoundingMode{:Down})
Closest candidates are:
  +(::Any, ::Any, ::Any, ::Any...) at operators.jl:502
  +(::PyObject, ::Any) at /Users/jbieler/.julia/packages/PyCall/ttONZ/src/pyoperators.jl:13
  +(::Interval) at /Users/jbieler/.julia/packages/IntervalArithmetic/19YeJ/src/intervals/arithmetic.jl:65
  ...
Stacktrace:
 [1] +(::Interval{Float64}, ::Interval{Float64}, ::RoundingMode{:Down}) at ./operators.jl:502
 [2] +(::Interval{Interval{Float64}}, ::Interval{Interval{Float64}}) at /Users/jbieler/.julia/packages/IntervalArithmetic/19YeJ/src/intervals/arithmetic.jl:85
 [3] macro expansion at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:103 [inlined]
 [4] _mapreduce at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:95 [inlined]
 [5] _reduce at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:204 [inlined] (repeats 2 times)
 [6] #sum#275 at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:229 [inlined]
 [7] sum(::StaticArrays.SArray{Tuple{3},Interval{Interval{Float64}},1,3}) at /Users/jbieler/.julia/packages/StaticArrays/1g9bq/src/mapreduce.jl:229
 [8] (::getfield(Main, Symbol("##21#22")))(::StaticArrays.SArray{Tuple{3},Interval{Float64},1,3}) at ./REPL[9]:1
 [9] #minimise#1(::Type, ::Float64, ::Float64, ::Function, ::getfield(Main, Symbol("##21#22")), ::IntervalBox{3,Float64}) at /Users/jbieler/.julia/dev/IntervalOptimisation/src/optimise.jl:41
 [10] minimise(::Function, ::IntervalBox{3,Float64}) at /Users/jbieler/.julia/dev/IntervalOptimisation/src/optimise.jl:22
 [11] top-level scope at none:0

```

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 18, 2019, 3:04pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/66 "2019-12-18T15:04:59Z")

</div>

> [@jonathanBieler](#):
>
> minf, minx = minimise( x-\>sum(abs2.(x)), IntervalBox(-5.5…5.5, 3) )

Sorry, make that the `nonrecursive_powers` branch then.

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [December 19, 2019, 10:00am UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/67 "2019-12-19T10:00:40Z")

</div>

That branch is almost 10x faster indeed. I went a bit further with the number of iterations and IntervalOptimisation does very well.

![mean_succ_3](https://global.discourse-cdn.com/julialang/original/3X/d/b/dbce4a7f21c7261a3b808ca723ebc66f746b387e.png)  
 ![mean_succ_6](https://global.discourse-cdn.com/julialang/original/3X/7/a/7a1bb1120b93764575c2876d295c33b6e51ea186.png)

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [December 19, 2019, 10:56am UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/68 "2019-12-19T10:56:06Z")

</div>

Wall-clock time would arguably be more interesting than number of function evaluations for the end user?

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [December 19, 2019, 11:20am UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/69 "2019-12-19T11:20:03Z")

</div>

Wall-clock time depends on the error function (here they are very fast compare to real world cases), so it’s better to count the number of function evaluation and to measure the overhead of the algorithm separately.

For the methodology I’m mostly following : [https://coco.gforge.inria.fr/COCOdoc/bbo\_experiment.html](https://coco.gforge.inria.fr/COCOdoc/bbo_experiment.html)

---

<div class="post-metadata">

**Author:** ![baggepinnen](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/baggepinnen/32/693_2.png) [@baggepinnen](https://discourse.julialang.org/u/baggepinnen)\
**Post date:** [December 19, 2019, 11:23am UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/70 "2019-12-19T11:23:33Z")

</div>

Yeah, but isn’t this case a bit different since the function itself takes longer to evaluate due to the intervals? For most other optimization algorithms the function evaluation takes a fixed amount of times, but called with intervals, this is not true.

To be fair, the number oräf arithmetic operations required to propagate intervals through the function compared to a simple floating point value should be reflected in the results somehow.

---

<div class="post-metadata">

**Author:** ![pkofod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pkofod/32/2179_2.png) [@pkofod](https://discourse.julialang.org/u/pkofod)\
**Post date:** [December 19, 2019, 11:45am UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/71 "2019-12-19T11:45:07Z")

</div>

I agree, the reason why you usually report f-calls is because it’s assumed to be the same. It’s not exactly the same, but it would be like comparing accuracy of a Float64 and Bigfloat run and only counting number of calls. I’m still impressed by the _quality_ of the interval method, but it could potentially be much more expensive (especially in higher dimensions I think?)

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [December 19, 2019, 12:15pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/72 "2019-12-19T12:15:49Z")

</div>

> [@pkofod](#):
>
> but it could potentially be much more expensive (especially in higher dimensions I think?)

It’s higher dimensions, and the expense scale with the condition of the method. The more ill-conditioned the `f` is, the more divides it needs to do, until it needs to start using BigFloats due to the blow up speed. I think it might be safe to say though that if intervals work on someone’s problem, it should be preferred though.

---

<div class="post-metadata">

**Author:** ![pkofod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pkofod/32/2179_2.png) [@pkofod](https://discourse.julialang.org/u/pkofod)\
**Post date:** [December 19, 2019, 12:43pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/73 "2019-12-19T12:43:36Z")

</div>

I agree it’s an awesome technique, but if you look at that plot, then time per f does matter. They appear to be “equally expensive”, but it’s not clear that that is true. Look at D: 6, 1:14 for example. They seem to be equally good for a high value of run length, but it’s not clear to me if 1e4 for BBO is equivalent to 1e3 for IO or if it’s 1e2? If it’s the latter, then BBO seems to take the lead. That’s why wall time would be a nice supplement.

Also, is it possible that IO is better without NelderMead?

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [December 19, 2019, 2:01pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/74 "2019-12-19T14:01:41Z")

</div>

It does pretty badly if I don’t chain it into NelderMead ; it gets close to the global minimum but final convergence doesn’t seem very good. That said that depend on the metric you use to measure performance.

For the runtime I noticed that it increases non-linearly with the number of iterations, which means that indeed it will become an issue at some point :

![runtime](https://global.discourse-cdn.com/julialang/original/3X/d/3/d3d33fc66861f0c67d7cf4c86f7eafe5c22c8bba.png)

```julia
julia> f = BBOB.F15
Rastrigin Function

plot(
    y = [@elapsed minimise(f, IntervalBox(-5.5..5.5, 6), f_calls_limit = calls ) for calls in 10:1000:10_000],
    Geom.line, Guide.ylabel("Runtime [s]")
)

```

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [December 20, 2019, 5:07am UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/75 "2019-12-20T05:07:02Z")

</div>

What do you mean by “chain it into melder mead”?

I agree that interval evaluations are more expensive - maybe 10 times more expensive than standard floating point to evaluate a given f (though that of course depends what f looks like and it would be good to benchmark that carefully).

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [December 20, 2019, 1:12pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/76 "2019-12-20T13:12:32Z")

</div>

At the end of the optimization I run a NelderMead starting from the minimum and using a % of the function evaluation budget. That allows algorithms that have good global properties but poor final convergence to have decent performance in the benchmark.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [May 29, 2020, 5:27pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/77 "2020-05-29T17:27:33Z")

</div>

That should hopefully be fixable using the “mean-value form”.  
Basically interval optimization suffers from a “cluster effect”, where you start producing more and more small boxes near the minimum.

If the function is differentiable then using a 1st-order Taylor approximation fixes this problem.

Which test function did you use?

---

<div class="post-metadata">

**Author:** ![jonathanBieler](https://avatars.discourse-cdn.com/v4/letter/j/82dd89/32.png) [@jonathanBieler](https://discourse.julialang.org/u/jonathanBieler)\
**Post date:** [June 8, 2020, 1:27pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/78 "2020-06-08T13:27:49Z")

</div>

In the plots above I’ve used 14 test functions from the BBOB set. To check the final convergence one should plot the function value in function of the number of iterations, some algorithms do good initially but then slow down and reach a plateau while other continue to decrease at a faster pace.

---

<div class="post-metadata">

**Author:** ![microprediction](https://avatars.discourse-cdn.com/v4/letter/m/d9b06d/32.png) [@microprediction](https://discourse.julialang.org/u/microprediction)\
**Post date:** [October 23, 2020, 4:39pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/79 "2020-10-23T16:39:12Z")

</div>

This might inform somewhat. For example, is SHGO in Julia yet?

> **[Comparing Python Global Optimization Packages](https://www.microprediction.com/blog/optimize)**
>
> Comparison of Python global optimization libraries Optuna, Hyperopt, PySOT, Scipy global optimizers (SHGO, Powell)

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [October 23, 2020, 5:45pm UTC](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718/80 "2020-10-23T17:45:28Z")

</div>

> [@microprediction](#):
>
> For example, is SHGO in Julia yet?

You can always call the Scipy version via PyCall. Unless you are optimizing an extremely cheap function, the inter-language call overhead is probably irrelevant.

[Previous page](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718.md?page=3)

[Next page](https://discourse.julialang.org/t/latest-recommendations-for-global-optimization/17718.md?page=5)
