This event has ended. View the official site or create your own event → Check it out
This event has ended. Create your own
View analytic
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 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

Universidad Nacional Autonoma de Mexico
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 previous Julia tutorials on YouTube have a total of more than 80,000 views. He is a principal author of the packages in the... Read More →

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