Global constrained nonlinear optimisation with interval methods

07/29/2021, 7:30 PM8:00 PM UTC
JuMP Track

Abstract:

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.

Description:

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

Platinum sponsors

Julia Computing

Gold sponsors

Relational AI

Silver sponsors

Invenia LabsConningPumas AIQuEra Computing Inc.King Abdullah University of Science and TechnologyDataChef.coJeffrey Sarnoff

Media partners

Packt Publication

Fiscal Sponsor

NumFOCUS