[Colloquium] Kalai talk tomorrow (1/15) 12:15pm at TTI
Meridel Trimble
mtrimble at tti-c.org
Wed Jan 14 13:29:53 CST 2004
TOYOTA TECHNOLOGICAL INSTITUTE TALK
Speaker: Adam Kalai
Toyota Technological Institute at Chicago
Speakers homepage: http://www.tti-c.org/kalai.shtml
Time: 12:15pm
Date: Thursday, January 15th, 2004
Place: TTI-C (1427 East 60th Street, Second Floor - Press Building)
*REFRESHMENTS PROVIDED*
Title: Simulated Annealing for Convex Optimization
Abstract:
Simulated annealing is a randomized search technique that has proven difficult
to analyze. We show that an algorithm strikingly similar to simulated
annealing gives the best-known polynomial bounds for the following
generalization of linear programming: minimize a linear function over a convex
set, where the convex set is specified by a membership oracle. This is a
difficult case of convex programming not amenable to interior point or simplex
methods.
More interesting is how closely the algorithm mimics the original definition
of simulated annealing, using a series of Boltzmann distributions and a
geometric temperature schedule. We motivate the Boltzmann distributions with
a geometric schedule by showing a lower bound: among a wide class of
stochastic search techniques, they are optimal for this problem.
This is joint work with Santosh Vempala.
If you have questions, or would like to meet the speaker, please contact
Meridel at: 4-9873 or mtrimble at tti-c.org
For information on future TTI-C talks or events, please go to the TTI-C Events
page: http://www.tti-c.org/events.shtml
More information about the Colloquium
mailing list