Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


"Randomized optimization with an expected value criterion: Finite sample bounds and applications to air traffic control"

Simulated annealing, Markov Chain Monte Carlo, and genetic algorithms are all randomized methods that can be used in practice to solve (albeit approximately) complex optimization problems. Many of these methods come with asymptotic convergence guarantees, that establish conditions under which the algorithm converges to a globally optimal solution in an appropriate probabilistic sense. An interesting question that is usually not covered by asymptotic convergence results is the rate of convergence: How long should the randomized algorithm be executed to obtain a near optimal solution with high probability? Answering this question allows one to determine a level of accuracy and confidence with which approximate optimality claims can be made, as a function of the amount of time available for computation. In this talk we present some new results on finite sample bounds of this type, primarily in the context of optimization of expected value criteria using Markov Chain Monte Carlo methods. The application of these methods to collision avoidance problems in air traffic management will also be discussed.
Type of Seminar:
Public Seminar
Prof. John Lygeros
Automatic Control Lab., ETH Zurich
May 21, 2007   16:30-18:00 (Coffee: 16:00-16:30)

ETH Zentrum, HG E41
Contact Person:

No downloadable files available.
Biographical Sketch:
John Lygeros received a B.Eng. degree in electrical engineering and an M.Sc. degree in control from Imperial College, London, U.K., in 1990 and 1991, respectively. He then received a Ph.D. degree from the Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, in 1996. He has held a series of postdoctoral research appointments with the National Automated Highway Systems Consortium, the Massachusetts Institute of Technology, and the University of California, Berkeley. In parallel, he was also a part-time Research Engineer with SRI International, Menlo Park, CA, and a Visiting Professor with the Department of Mathematics, Universite de Bretagne Occidentale, Brest, France. Between July 2000 and March 2003, he was a University Lecturer with the Department of Engineering, University of Cambridge, Cambridge, U.K. and a Fellow of Churchill College. Between March 2003 and July 2006, he was an Assistant Professor with the Department of Electrical and Computer Engineering, University of Patras, Patras, Greece. Since July 2006, he has been an Associate Professor with the Automatic Control Laboratory, ETH Zurich, Switzerland. His research interests include modeling, analysis, and control of hierarchical, hybrid and stochastic systems with applications to biochemical networks and large-scale engineering systems such as automated highways and air traffic management.