Professor Bertsimas of MIT to Speak on Multistage Optimization Next Friday

We are delighted that Professor Bertsimas of MIT will be speaking in our Speaker Series next Friday, April 23, 2010. Complete information can be found in the announcement below, which was circulated by the officers of the UMass Amherst INFORMS Student Chapter. These students are a wonderful group and I enjoy serving as the chapter's Faculty Advisor. The talk is co-hosted by the Finance group at the Isenberg School.

Professor Dimitris Bertsimas will speak on "Advances in Multistage Optimization."

Biography: Dr. Dimitris Bertsimas is the Boeing Professor of Operations Research and the Co-director of the Operations Research Center at the MIT. He received a BS in Electrical Engineering and Computer Science from the National Technical University of Athens, Greece in 1985, an MS in Operations Research from MIT in 1987, and a PhD in Applied Mathematics and Operations Research from MIT in 1988. Since 1988, he has been on the MIT faculty.

His research interests include: optimization, stochastic systems, data mining, and their applications. In recent years he has worked on robust optimization, health care, and finance. He has co-authored more than 110 scientific papers and he has co-authored the following books: Introduction to Linear Optimization (with J. Tsitsiklis, Athena Scientific and Dynamic Ideas, 2008), Data, Models and Decisions (with R. Freund, Dynamic Ideas, 2004), and Optimization over Integers (with R. Weismantel, Dynamic Ideas, 2005). He is currently department editor in Optimization for Management Science and former area editor of Operations Research in Financial Engineering. He has supervised 42 doctoral students and he is currently supervising 10 others.

He is a member of the National Academy of Engineering. He has received numerous research awards including the Farkas Prize (2008), the Erlang Prize (1996), the SIAM Prize in Optimization (1996), the Bodossaki Prize (1998), and the Presidential Young Investigator Award (1991-1996).

PRESENTATION TITLE: "Advances in Multistage Optimization."

Abstract: This talk explores several recent advances in multistage stochastic and adaptive optimization. We consider a multi-stage mixed integer stochastic optimization problems and show that a static finitely adaptable solution (it reduces to a robust solution in two stages) that can be computed in polynomial time is a good approximation to the fully-adaptable multi-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as a hypercube, ellipsoid or norm-ball) and the probability measure is also symmetric, then the cost of the optimal fixed solution to the corresponding robust problem is at most twice the optimal expected cost of the multistage-stage stochastic problem. Furthermore, we show that the bound is tight for symmetric uncertainty sets and can be arbitrarily large if the uncertainty set is not symmetric. We refer to the ratio of the optimal cost of the robust problem and the optimal cost of the two-stage stochastic problem as the stochasticity gap. We also extend the bound on the stochasticity gap for another class of uncertainty sets referred to as positive. If both the objective coefficients and right hand side are uncertain, we show that the stochasticity gap can be arbitrarily large even if the uncertainty set and the probability measure are both symmetric. However, we prove that the adaptability gap (ratio of optimal cost of the robust problem and the optimal cost of a multi-stage fully-adaptable problem) is at most four even if both the objective coefficients and the right hand side of the constraints are uncertain and belong to a symmetric uncertainty set. The bound holds for the class of positive uncertainty sets as well. Moreover, if the uncertainty set is a hypercube (special case of a symmetric set), the adaptability gap is one under an even more general model of uncertainty where the constraint coefficients are also uncertain. A class of affine policies has been extensively studied in the literature for multistage optimization. We show that affine policies are with O(m^(1/2)) from optimal in multistage problems and the bound is tight, thus giving a tight characterization of this class of tractably computed policies.
(joint work with Vineet Goyal, MIT)

Date: Friday, April 23, 2010
Time: 11:00AM - Noon
Place: Room ISOM 112

The Announcement for this talk can be found at:
http://supernet.som.umass.edu/informs/speakernew.html

INFORMS Student Chapter website:
http://student.som.umass.edu/informs/