JuliaCon 2017 has ended
Back To Schedule
Wednesday, June 21 • 3:40pm - 4:16pm
Equations, inequalities and global optimisation: guaranteed solutions using interval methods and constraint propagation

Sign up or log in to save this to your schedule, view media, leave feedback and see who's attending!

Feedback form is now closed.
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.

avatar for David Sanders

David Sanders

Associate Professor, Universidad Nacional Autonoma de Mexico (UNAM)
David P. Sanders is associate professor of computational physics in the Department of Physics of the Faculty of Sciences at the National University of Mexico in Mexico City. His Julia tutorials on YouTube have a total of over 100,000 views and he is a principal author of the Juli... Read More →

Wednesday June 21, 2017 3:40pm - 4:16pm PDT
West Pauley Pauley Ballroom, Berkeley, CA