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
Topic Weeks
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