JuliaCon 2017

How can we find all solutions of a system of nonlinear equations, the “feasible set” satisfied by a collection of inequalities, or the global optimum of a complicated function? These are all known to be difficult problems in numerical analysis.

In this talk, we will show how to solve these, in a guaranteed way, using a collection of related methods based on interval arithmetic, provided by the IntervalArithmetic.jl package. The starting point is a simple dimension-independent bisection code, which can be enhanced in a variety of ways. This method is rigorous: it is guaranteed to find all roots, or to find the global minimum, respectively.

One key idea is the use of continuous constraint propagation, which allows us to remove large portions of the search space that are infeasible. We will explain the basics of this method, in particular the “forward-backward contractor”, and describe the implementation in the IntervalConstraintProgramming.jl package.

This package generates forward and backward code automatically from a Julia expression, using metaprogramming techniques. These are combined into “contractors”, i.e. operators that contract a box without removing any portion of the set of interest. These, in turn, give a rigorous answer to the question whether a given box lies inside the feasible set or not. In this way, a paving (collection of boxes) is built up that approximates the set.