Guaranteed constrained and unconstrained global optimisation in Julia
2019-07-24, 11:30–11:40, Room 349

Set computations with interval arithmetic allow us to write surprisingly efficient software for guaranteed unconstrained and constrained global optimisation in pure Julia.


We will show how set computations, using interval-based methods, enable us to find the global minimum for difficult nonlinear, non-convex optimization problems of functions $f:\mathbb{R}^n \to \mathbb{R}$, even when the number of local minima is huge, with guaranteed bounds on the optimum value and on the set of minimizers. We can often also find all stationary points in a given box.

We will explain the underlying ideas and some details of the Julia implementation in IntervalOptimisation.jl, which relies on spatial branch and bound, as well as showing examples. We can tackle some "weakly non-convex" functions ranging up to a few hundred variables, whereas highly oscillatory functions can be very challenging even for $n < 10$.

For constrained optimization, we apply constraint propagation, as implemented in IntervalConstraintProgramming.jl, to eliminate infeasible regions and prove the existence of feasible points. We will show how the above techniques are combined to allow efficient and guaranteed calculations for optimization problems.

The CharibdeOptim.jl package combines these methods with the heuristic Differential Evolution technique to get an efficient global optimisation tool.