Instructors: Professor Robert L. Smith

Professor Chelsea White

Course Descriptions: This is a seminar on the foundations of optimization over an infinite time horizon. The course consists of three modules. The first module, taught by Professor White, covers the field of time homogeneous Markov Decisions Processes. The second module, taught by Professor Smith, covers the nonhomogeneous case, where data are allowed to be time dependent. The third module, consists of student presentations of current research in the area of infinite horizon optimization. The presentations my be based upon papers of others or upon the students dissertation in the field.

Text: Class Notes and (Puterman?)

References: 0. Coursepack of papers.

1. Denardo, E., Dynamic Programming: Models and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1982

2. Ross, S., Introduction to Stochastic Dynamic Programing, Academic Press, NY, 1983.

3. Bertsekas, D., Dynamic Programming: Deterministic and Stochastic Models, Prentice-Hall, Englewood Cliff, NJ, 1987.

4. Ross, S., Applied Probability Models with Optimization Applications, Chapter 6, Holden-Day, San Francisco, 1970.

5. Anderson, E.J. and Nash, P, Linear Programming in Infinite Dimensional Spaces, Wiley, NY, 1987.

6. Carlson, D.A. and Haurie, A. Infinite Horizon Optimal Control, Springer- Verlag NY, 1987.

7. Milne, R.D., Applied Functional Analysis, Pitman Advanced Publishing Program, Boston, 1980.

8. Berge, C., Topological Spaces, Oliver and Boyd, London, 1963.

9. Rudin, W., Principles of Mathematical Analysis, McGraw-Hill, NY, 1964.

Grading: Grades will be based upon homework, class participation, and the student presentation tin the third module.

Topic

Introduction 1/2

Markov Decision Processes 4 1/2

Infinite Horizon Optimization 4 1/2

Introduction

Discounted knapsack problem

Mathematical background

Topological spaces, set convergence and selections

Deterministic infinite horizon optimization

Optimality criteria (discounted versus average optimality)

Solution Concepts

Exact: variable rolling horizons versus approximate: fixed

rolling horizons

Solution Existence and Discovery

Policy and value convergence

Efficient solutions, reachability, tie-breaking, and stopping

rules

Duality

Weak and strong duality, economic interpretation

Stochastic infinite horizon optimization

Nonhomogeneous MDPs

Applications

Shortest paths in infinite directed networks (equipment

replacement under technological change)

Doubly infinite mathematical programming (infinite horizon

production planning, linear dynamic quadratic criteria

control)

Student Presentations 4 1/2