Optimization has played a key role in making the task of decision making from art to science in the past century. An important challenge that still remains is our ability to incorporate the uncertainty in our knowledge and risk-aversion in our objective. A simple but insightful example of this is encapsulated in the decision question: given a number of route choices, which shall I choose? This simple question (easily solvable in a deterministic setting) becomes highly non-trivial when we incorporate the uncertainty of delays and the individual's risk-aversion.

This graduate seminar will survey the state-of-art in optimization under uncertainty, with an emphasis on

**Professor: Evdokia Nikolova**. Office: HRBB 515A.

Office Hours: Thursdays 2-3 pm or send me an email.**Lecture:****Tuesdays and Thursdays 12:45-2 pm @ HRBB 204.****Textbook:**There is no required textbook; however, the following text may be helpful:*Lectures on Stochastic Programming: Modeling and Theory*by Shapiro, Dentcheva & Ruszczynski (SDR).

Additional relevant research papers and surveys will be posted as the class develops the list.**Prerequisites:**A course in algorithms (CSCE 411 or equivalent).

**Assessment:**Students will be required to present relevant research papers, participate in class discussions and do a research-oriented final project. This could be either a survey, or original research; students will be encouraged to relate the project to their own research interests.

The final grade will be based on the class presentations/participation (60%) and the final project (40%).

**Von Neumann-Morgenstern expected utility theory**

Suggested reading:- Lecture Notes in Microeconomic Theory by Ariel Rubinstein, Princeton University Press, 2006. (Lectures 8,9)
- Expected Utility Theory Handbook by Simon Grant & Timothy Van Zandt.

**Coherent measures of risk**

Suggested reading:- Coherent Approaches to Risk in Optimization Under Uncertainty by R. Tyrrell Rockafellar. (Tutorials in Operations Research INFORMS 2007, 38-61)

**Two-stage and multistage stochastic optimization**

Suggested reading:- SDR Chapters 2,3

**Robust optimization**

Suggested reading:- Robust and Data-Driven Optimization: Modern Decision-Making Under Uncertainty by Dimitris Bertsimas and Aurelie Thieley. (Tutorials on Operations Research, INFORMS, Chapter 4, 195-122, 2006)

**Models with probabilistic constraints**

Suggested reading:- SDR Chapter 4

**Risk-averse optimization**

Suggested reading:- SDR Chapter 6

**Game-theoretic extensions (time permitting)**

Suggested reading:- TBD

**Multicriteria Optimization (time permitting)**

Suggested reading:- TBD

**Statistical inference (time permitting)**

Suggested reading:- SDR Chapter 5

**Lecture 1**(August 30, 2011): Expected Utility Theory and overview of class. Allais paradox, lotteries, preferences, Von Neumann-Morgenstern Axiomatization: Independence and Continuity Axioms, von Neuman-Morgenstern Theorem. Notes (based on Lecture 8 of Rubinstein.)**Lecture 2**(September 1, 2011): Risk-aversion. Uniqueness of vNM utilities, St. Petersburg Paradox for unbounded vNM utilities, first-order stochastic dominance. Notes (Based on Lecture 9 of Rubinstein.)**Lecture 3**(September 6, 2011): Risk-aversion continued. Certainty equivalence, Risk premium, Comparing risk-aversion, Coefficient of Absolute Risk Aversion (CARA). Notes (second half of Lecture 2's Notes. Based on Lecture 9 of Rubinstein.)**Lecture 4**(September 8, 2011): Alternatives to Expected Utility Theory. Presentation by Dheeban Govindarajan. Reading:- Machina, M. (1987). Choice under uncertainty: Problems solved and unsolved. Journal of Economic Perspectives 1: 121-154
- MIT 14.123 Lecture Notes on Alternatives to Expected Utility Theory

**Lecture 5**(September 13, 2011): Two-stage Stochastic Optimization. Presentation by Arupa Mohapatra. Arupa's Notes. Reading:- Chapter 2 of SDR.

**Lecture 6**(September 15, 2011): Approximation Algorithms for Two-stage Stochastic Optimization. Presentation by Ye Tian. Reading:- Chaitanya Swamy, David B. Shmoys. Approximation Algorithms for 2-Stage Stochastic Optimization Problems.

**Lecture 7**(September 20, 2011): Stochastic Optimization Models: Two-stage, Multi-stage, Chance-constraints. Presentation by Szu-Yu Chen. Reading:**Lecture 8**(September 22, 2011): Approximation Algorithms for Multi-stage Stochastic Optimization. Presentation by Haidong Shi. Reading:- Gupta, Pal, Ravi, and Sinha. What about Wednesday? Approximation Algorithms for Multistage Stochastic Optimization..

**Lecture 9**(September 27, 2011): Stochastic Optimization with probabilistic (chance) constraints. Presentation by Kai Yin. Reading:- Chapter 4 of SDR.

**Lecture 10**(September 29, 2011): Approximation Algorithms for Chance-constrained Optimization. Presentation by Timothy A. Mann. Reading:**Lecture 11**(October 4, 2011): Markov Decision Processes. Presentation by Wenzhe Li. Reading:- Chapters 1, 2 of Handbook of Markov Decision Processes.
- Bob Givan and Ron Parr. Introduction to Markov Decision Processes.
- Dimitri P. Bertsekas and John N. Tsitsiklis. An Analysis of Stochastic Shortest Path Problems.

**Lecture 12**(October 6, 2011): Risk-averse Markov Decision Processes. Presentation by Arupa Mohapatra. Reading:- S. Mannor and J. N. Tsitsiklis, Mean-Variance Optimization in Markov Decision Processes (conference version in Proceedings of the 28th International Conference on Machine Learning (ICML 2011), June 2011.
- E. Delage and S. Mannor. Percentile Optimization for Markov Decision Processes with Parameter Uncertainty. 2010. Operations Research, 58(1):203-213.

**Lecture 13**(October 11, 2011): Robust Optimization. Guest lecture by Prof. Constantine Caramanis, UT Austin. Reading:- Dimitris Bertsimas, David B. Brown and Constantine Caramanis. Theory and Applications of Robust Optimization.

**Lecture 14**(October 13, 2011): Multi-armed Bandit and Markov Decision Processes. Presentation by Timothy A. Mann. Reading:- Eyal Even-Dar, Shie Mannor, and Yishay Mansour. PAC Bounds for Multi-Armed Bandit and Markov Decision Processes.
- Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time Analysis of the Multiarmed Bandit Problem.

**Lecture 15**(October 20, 2011): Optimization with Probabilistic Constraints II. Presentation by Kai Yin. Reading:- Lejeune, M., and N. Noyan, 2010. Mathematical programming approaches for generating p-efficient points, European Journal of Operational Research 207, 590-600.
- Miller, N., and A. Ruszczynski, 2011. Risk-Averse Two-Stage Stochastic Linear Programming: Modeling and Decomposition, Operations Research 59, 125-132.

**Lecture 16**(October 25, 2011): Algorithms for Risk-averse Combinatorial Optimization. NOTE: No Class on this date. Make-up lectures: 9/5/2011; 9/20/2011. Assignment posted in Class Calendar. Reading:**Lecture 17**(October 27, 2011): Algorithms for Risk-averse Combinatorial Optimization. Presentation by Szu-Yu Chen. Reading:- Jian Li, Amol Deshpande. Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

**Lecture 18**(November 1, 2011): Coherent risk measuers. Presentation by Wenzhe Li. Reading:- Coherent Approaches to Risk in Optimization Under Uncertainty by R. Tyrrell Rockafellar. (Tutorials in Operations Research INFORMS 2007, 38-61)

**Lecture 19**(November 3, 2011): Risk-averse optimization. Presentation by Dheeban Govindarajan. Reading:- First half of Chapter 6 of SDR.

**Lecture 20**(November 8, 2011): Statistical Inference. Presentation by Ye Tian. Reading:- First half of Chapter 5 of SDR.

**Lecture 21**(November 10, 2011): Statistical Inference. Presentation by Haidong Shi. Reading:- Second half of Chapter 5 of SDR.

**Lecture 22**(November 15, 2011): Statistical Inference. Presentation by Haidong Shi (continued). Reading:- Second half of Chapter 5 of SDR.

**Lecture 23**(November 17, 2011): Coherent risk measures. Presentation by Mahsa Hanifi. Reading:- Pavlo Krokhmala, Michael Zabarankinb, Stan Uryasev. "Modeling and optimization of risk." Available online here.

**Lecture 24**(November 22, 2011): Introduction to Network Congestion Games. Wardrop's first and second principles; Wardrop Equilibrium; Nash flow; Social Optimum; Price of Anarchy. Notes.**Lecture 25**(November 29, 2011): Risk-aversion in Stochastic Network Congestion Games. Equilibria existence and characterization; Exogenous and endogenous noise; Equilibria as Variational Inequalities; Succinct representations of Equilibria; Price of Anarchy. Notes. Reading:- Evdokia Nikolova, Nicolas Stier-Moses. Stochastic Selfish Routing. (conference version, full version).

- Lecture Notes in Microeconomic Theory by Ariel Rubinstein, Princeton University Press, 2006. (Lectures 8,9)
- Expected Utility Theory Handbook by Simon Grant & Timothy Van Zandt.
- Coherent Approaches to Risk in Optimization Under Uncertainty by R. Tyrrell Rockafellar. (Tutorials in Operations Research INFORMS 2007, 38-61)
- Robust and Data-Driven Optimization: Modern Decision-Making Under Uncertainty by Dimitris Bertsimas and Aurelie Thieley. (Tutorials on Operations Research, INFORMS, Chapter 4, 195-122, 2006)

- For the first four lectures on Expected Utility Theory and Risk-aversion: MIT 14.123 Microeconomic Theory III taught by Prof. Muhamet Yildiz.