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