Global constrained nonlinear optimisation with interval methods
2021-07-29, 19:30–20:00 (UTC), JuMP Track

We will present recent work in progress on guaranteed methods for inequality-constrained global nonlinear optimization in Julia. Using methods based on interval arithmetic allows us to guarantee (prove) that we return the true global minimum and minimizers for inequality-constrained optimization problems in low dimensions.

Interval arithmetic provides a computationally-cheap way to compute an over-estimate of the range of a function over an input set. These estimates are guaranteed to be correct (mathematically rigorous), even
though the computations are done using floating-point arithmetic, by using directed rounding.

This kind of range bounding can be used to design a conceptually-simple algorithm for guaranteed unconstrained global optimization, as in the talk presented at JuMP-dev Chile in 2019.
In this talk we show how to extend this to constrained optimization.

First we show how both the objective function and constraints can be modelled using symbolic expressions from the Symbolics.jl library. Based on these symbolic expressions we have a new implementation of interval constraint propagation, as implemented in the ReversePropagation.jl library, including common subexpression elimination.

One main difficulty in interval-based inequality-constrained optimization is deciding when a given box is feasible, i.e. satisfies all of the constraints. We have implemented what we believe to be a novel method to do so.

This is an extension to inequality-constrained optimization of th

Professor of Computational Science at the Universidad Nacional Autónoma de México and visiting professor at MIT.

Interested in computational science, interval arithmetic, and numeric-symbolic computing.

Author of the JuliaIntervals suite of packages for interval arithmetic, and various tutorials on Julia.

This speaker also appears in: