Seminars & Events

Mathematics and Computer Science Division Seminar
"Optimization Heuristics for Cost Function Minimization: Extremal and Hysteretic Optimization"

DATE: February 29, 2008
TIME: 10:30 am
SPEAKER: Bruno Goncalves, Emory University
LOCATION: Building 221 Conference Room A216, Argonne National Laboratory
HOST: Mihai Anitescu

Description:
A wide range of problems can be formulated in terms of determining the minimal value of a cost function defined in terms of discrete two valued variables. Examples from Physics, Mathematics and Computer Science include the Constraint Satisfaction Problem, the Voter Model, and finding the ground state of magnetic systems. We present two
distinct algorithms that can be applied to this class of problems, and analyze their performance. Extremal Optimization performs a search of solution space, not by preserving the best adjusted variables, but by eliminating the worst. This approach preserves enough variability to
keep the algorithm from becoming stuck in poor local minima.
Hysteretic Optimization, on the other hand, uses a global field to drive the system through barriers and force it to explore solution space in search of the global minimum. The dynamics of each method are analyzed and advantages and disadvantages are presented.

Save the event to your calendar [schedule.ics]