[Colloquium] *REMINDER* Kalai talk today 12:15pm at TTI

[Meridel Trimble]

TOYOTA TECHNOLOGICAL INSTITUTE TALK 

Speaker: Adam Kalai 
Toyota Technological Institute at Chicago 

Speaker’s 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