Seminar Announcement

An Almost Embarrassingly Parallel Interval Global Optimization Method

Rasmus Munk Larsen
Stanford University

Wednesday, March 8, 2000
Bldg. 921, Room 137
2:00 p.m. - 3:00 p.m.

We describe a branch-and-bound interval search algorithm designed to find the global minimum and all of the global minimizers of a non-linear function f(X), X = (x1,x2,...,xn)^T, on an n-dimensional interval D. During the search we maintain

1. a finite number of number of subintervals S_i of D, This set of boxes is called the candidate set S.
2. lower bounds LB(S_i) on the value of f(X) in S_i, obtained using the interval extension F(X) of f(X).
3. an upper bound f_bound on the global minimum.

The purpose of the search is to reduce the total volume of the candidate set S until it only consists of "terminated" boxes, for which the width of S_i or F(S_i) is smaller than some convergence tolerance. This is done as follows: At each iteration of the search, the box with the smallest lower bound is selected from S (Best-First), split into two subboxes (bisection), for each box a lower bound is obtained and finally each box is either eliminated, marked as terminated or put back into S. Also f_bound may be updated and further elements (those with LB(S_i) > f_bound) in the candidate set eliminated.

This basic procedure has been studied by Skelboe, Moore, Hansen and others and here we present the results of adding a number of so-called "accelerating devices" such as monotonicity test, concavity test, search for stationary points using an interval Newton method and improvements of f_bound using a scalar optimization algorithm.

We describe a parallel version of the Branch-and-Bound method which uses a static work distribution and very little interprocessor communication. This is well suited for parallel architectures with high latency, low bandwidth interconnects, such as clusters of PC's or workstations connected via Ethernet.

The algorithm has been implemented in C++ and uses among others the FAD/BAD package for automatic differentiation from the Technical University of Denmark and the PROFIL/BIAS interval arithmetic package from the Technical University of Hamburg. The algorithm can be executed via a web-based interface, where the user can type in a C++ function defining the function to be minimized, and select various algorithmic options by clicking a few buttons.

This is joint work with Ole Caprani and Jens Benner, Aarhus University and Kaj Madsen, Technical University of Denmark.

This seminar is hosted by the Computational Sciences and Mathematics Research Department at Sandia National Labs in Livermore, CA. For more information on this or other events, visit http://csmr.ca.sandia.gov/news.html. Visitors from outside Sandia require advance arrangements in order to attend. For more information, please contact the CSMR office management assistant Doretha Smith at dahall@sandia.gov or (925) 294-4630.