IOE 712 Infinite Horizon Optimization Winter, 1994

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.

Course Outline


Introduction 1/2

Markov Decision Processes 4 1/2

Infinite Horizon Optimization 4 1/2

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

Weak and strong duality, economic interpretation

Stochastic infinite horizon optimization
Nonhomogeneous MDPs

Shortest paths in infinite directed networks (equipment
replacement under technological change)
Doubly infinite mathematical programming (infinite horizon
production planning, linear dynamic quadratic criteria

Student Presentations 4 1/2