Puterman Dynamic Programming and Its Applications

Proceedings of the International Conference on Dynamic Programming and Its Applications, University of British Columbia, Vancouver, British Columbia, Canada, April 14-16, 1977
1. Auflage 2014
ISBN: 978-1-4832-5894-2
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 426 Seiten, Web PDF

Dynamic Programming and Its Applications provides information pertinent to the theory and application of dynamic programming. This book presents the development and future directions for dynamic programming. Organized into four parts encompassing 23 chapters, this book begins with an overview of recurrence conditions for countable state Markov decision problems, which ensure that the optimal average reward exists and satisfies the functional equation of dynamic programming. This text then provides an extensive analysis of the theory of successive approximation for Markov decision problems. Other chapters consider the computational methods for deterministic, finite horizon problems, and present a unified and insightful presentation of several foundational questions. This book discusses as well the relationship between policy iteration and Newton's method. The final chapter deals with the main factors severely limiting the application of dynamic programming in practice. This book is a valuable resource for growth theorists, economists, biologists, mathematicians, and applied management scientists.

Autoren/Hrsg.

Puterman, Martin L.

Inhaltsverzeichnis

1;Front Cover;1
2;Dynamic Programming and its Applications;4
3;Copyright Page;5
4;Table of Contents;8
5;Dedication
;6
6;CONTRIBUTORS;12
7;PREFACE;14
8;PART 1: SURVEYS;18
8.1;CHAPTER 1. RECURRENCE CONDITIONS IN DENUMERABLE STATE MARKOV DECISION PROCESSES;20
8.1.1;I. INTRODUCTION;20
8.1.2;II. RECURRENCE CONDITIONS;22
8.1.3;III. THE OPTIMALITY EQUATION;34
8.1.4;REFERENCES;38
8.2;CHAPTER 2. DISCOUNTED AND UNDISCOUNTED VALUE-ITERATION IN MARKOV DECISION PROBLEMS: A SURVEY;40
8.2.1;1. INTRODUCTION;40
8.2.2;II. DISCOUNTED CASE: ASYMPTOTIC BEHAVIOUR OF v(n);42
8.2.3;III. DISCOUNTED CASE; ASYMPTOTIC BEHAVIOUR OF S(n) AND THE EXISTENCE OF INITIALLY STATIONARY e-OPTIMAL STRATEGIES;46
8.2.4;IV. UNDISCOUNTED CASE: ASYMPTOTIC BEHAVIOUR OF v(n) - ng;49
8.2.5;V. UNDISCOUNTED CASE; ASYMPTOTIC BEHAVIOUR OF S(n) AND THE EXISTENCE OF INITIALLY STATIONARY OR PERIODIC e-OPTIMAL STRATEGIES;60
8.2.6;VI. DATA-TRANSFORMATIONS;63
8.2.7;REFERENCES;65
8.3;CHAPTER 3. COMPUTATIONAL ADVANCES IN DYNAMIC PROGRAMMING;70
8.3.1;I. COMPUTATIONAL REQUIREMENTS;71
8.3.2;II. COMPUTATIONAL ADVANCES;73
8.3.3;III. DISCUSSION;91
8.3.4;ACKNOWLEDGEMENT;92
8.3.5;REFERENCES;93
8.4;CHAPTER 4. THE ANALYTIC THEORY OF POLICY ITERATION;108
8.4.1;I. INTRODUCTION;108
8.4.2;II. THE POLICY ITERATION PROCEDURE;110
8.4.3;III. RELAXATION OF ASSUMPTION 2;114
8.4.4;IV. RELAXATION OF ASSUMPTION 3;117
8.4.5;V. CONVERGENCE RATE RESULTS;121
8.4.6;VI. APPLICATIONS TO MARKOV DECISION PROBLEMS;124
8.4.7;ACKNOWLEDGEMENT;127
8.4.8;REFERENCES;128
8.5;CHAPTER 5. DYNAMIC PROGRAMMING IN BOREL SPACES;132
8.5.1;I. INTRODUCTION;132
8.5.2;II. A TWO-STAGE EXAMPLE;133
8.5.3;III. MEASURABLE SELECTION;137
8.5.4;IV. THE GENERAL FINITE HORIZON MODEL;143
8.5.5;REFERENCES;147
8.6;CHAPTER 6. ELIMINATION OF NON-OPTIMAL ACTIONS IN MARKOV DECISION PROCESSES;148
8.6.1;I. INTRODUCTION;148
8.6.2;II. DEFINITIONS;153
8.6.3;III. KNOWN RESULTS AND EXTENSIONS;155
8.6.4;IV. BOUNDS;157
8.6.5;V. ELIMINATION TESTS;162
8.6.6;VI. COMPUTATIONAL CONSIDERATIONS;166
8.6.7;ACKNOWLEDGEMENTS;168
8.6.8;REFERENCES;168
9;PART 2: APPLICATIONS;178
9.1;CHAPTER 7. ON RENEWAL DECISIONS;180
9.1.1;I. STATEMENT OF PROBLEM;180
9.1.2;II. FIXED HORIZON CASE;181
9.1.3;III. RANDOM HORIZON CASE;184
9.1.4;REFERENCES;188
9.2;CHAPTER 8. STEADY-STATE POLICIES, DYNAMIC PROGRAMMING, AND OPTIMAL ECONOMIC GROWTH;190
9.2.1;I. INTRODUCTION;190
9.2.2;II. FORMAL DEFINITIONS;194
9.2.3;III. STEADY STATE RESULTS: EXISTENCE;197
9.2.4;IV. STEADY STATE RESULTS: COMPUTATION;200
9.2.5;V. OPTIMAL GROWTH APPLICATIONS;202
9.2.6;VI. STEADY STATE RESULTS VERSUS TURNPIKE THEOREMS;215
9.2.7;REFERENCES;215
9.3;CHAPTER 9. COMMENTS ON THE ORIGIN AND APPLICATION OF MARKOV DECISION PROCESSES;218
9.3.1;REFERENCES;221
9.3.2;APPENDIX;221
9.4;CHAPTER 10. THE APPLICATION OF MARKOV DECISION PROCESSES TO FOREST MANAGEMENT;224
9.4.1;PREVIOUS WORK IN FOREST MANAGEMENT;226
9.4.2;STAND MANAGEMENT MODEL FORMULATION;226
9.4.3;APPLICATIONS;230
9.4.4;MAX VOLUME RESULTS;230
9.4.5;REFERENCES;235
9.5;CHAPTER 11. AN APPLICATION OF DYNAMIC PROGRAMMING IN STATISTICS;238
9.5.1;I. INTRODUCTION;238
9.5.2;II. THE MODEL;239
9.5.3;III. A RELATED OPTIMAL STOPPING PROBLEM;241
9.5.4;IV. APPROXIMATE SOLUTIONS;244
9.5.5;V. AN ASSOCIATED PROBLEM;245
9.5.6;VI. DISCUSSION;248
9.5.7;REFERENCES;248
9.6;CHAPTER 12. SOME DYNAMIC PROGRAMMING APPLICATIONS IN FISHERIES MANAGEMENT;250
9.6.1;I. INTRODUCTION;250
9.6.2;II. STOCHASTIC PRODUCTION MODELS;251
9.6.3;III. SIMPLE FEEDBACK POLICIES;254
9.6.4;IV. ADAPTIVE CONTROL PROBLEMS;255
9.6.5;V. CONSTRAINED CONTROL PROBLEMS;258
9.6.6;VI. DISCUSSION;260
9.6.7;REFERENCES;261
10;PART 3. THEORY;264
10.1;CHAPTER 13. BUCKETS, SHORTEST PATHS, AND INTEGER PROGRAMMING;266
10.1.1;REFERENCES;270
10.2;CHAPTER 14. AFFINE DYNAMIC PROGRAMMING;272
10.2.1;I. INTRODUCTION;272
10.2.2;II. AFFINE STRUCTURE;273
10.2.3;III. DETERMINISTIC TRANSITIONS;274
10.2.4;IV. FINITE PLANNING HORIZON;275
10.2.5;V. A DISCOUNTED MODEL;277
10.2.6;VI. A TRANSIENT MODEL;278
10.2.7;VII. EXAMPLES;281
10.2.8;REFERENCES;283
10.3;CHAPTER 15. OPTIMAL CONTROL OF A DIFFUSION PROCESS WITH REFLECTING BOUNDARIES AND BOTH CONTINUOUS AND LUMP COSTS;286
10.3.1;I. INTRODUCTION;286
10.3.2;II. FORMULATION AND BASIC ASSUMPTIONS;288
10.3.3;III. OPTIMALITY CONDITIONS;292
10.3.4;IV. COMPUTATIONAL ASPECTS;302
10.3.5;REFERENCES;305
10.4;CHAPTER 16. ON APPROXIMATE SOLUTIONS OF FINITE STAGE DYNAMIC PROGRAMS;306
10.4.1;INTRODUCTION AND SUMMARY;306
10.4.2;I. ADVANTAGES OF FINITE-HORIZON MODELS;307
10.4.3;II. THE MODELS DMN AND DPN;309
10.4.4;III. CHANGING THE HORIZON AND TOE TERMINAL VALUE FUNCTION;312
10.4.5;IV. APPROXIMATION BY A SMALLER MODEL;317
10.4.6;V. APPROXIMATION BY A LARGER MODEL;329
10.4.7;ACKNOWLEDGEMENTS;332
10.4.8;REFERENCES;332
10.5;CHAPTER 17. AN INVERSE THEOREM BETWEEN MAIN AND INVERSE DYNAMIC PROGRAMMING: INFINITE-STAGE CASE;336
10.5.1;I. INTRODUCTION AND SUMMARY;336
10.5.2;II. INVERSE THEOREM;337
10.5.3;III. EXAMPLES;343
10.5.4;IV. INVERSE CONTROL PROCESS;348
10.5.5;ACKNOWLEDGEMENT;350
10.5.6;REFERENCES;351
10.6;CHAPTER 18. ON THE TRANSIENT CASE FOR MARKOV DECISION CHAINS WITH GENERAL STATE SPACES;352
10.6.1;I. INTRODUCTION;352
10.6.2;II. THE MAIN RESULTS;355
10.6.3;III. TRANSIENT STATIONARY POLICIES;359
10.6.4;IV. CONTROLLED BRANCHING PROCESSES;363
10.6.5;REFERENCES;365
10.7;CHAPTER 19. AN OPERATOR-THEORETICAL TREATMENT OF NEGATIVE DYNAMIC PROGRAMMING;368
10.7.1;I. INTRODUCTION;368
10.7.2;II. THE DECISION MODEL;369
10.7.3;III. OPTIMAL POLICIES;372
10.7.4;IV. THE FILTERING-UPWARDS PROPERTY;373
10.7.5;V. SEVERAL RESULTS ON COMPACTNESS;375
10.7.6;VI. THE COMPACTNESS-PROPERTY;378
10.7.7;VII. ORDINARY NEGATIVE DYNAMIC PROGRAMS;381
10.7.8;ACKNOWLEDGEMENT;384
10.7.9;REFERENCES;384
10.8;CHAPTER 20. EXISTENCE OF AVERAGE OPTIMAL STRATEGIES IN MARKOVIAN DECISION PROBLEMS WITH STRICTLY UNBOUNDED COSTS;386
10.8.1;I. INTRODUCTION;386
10.8.2;II. PRELIMINARIES;387
10.8.3;III. AVERAGE OPTIMAL STRATEGIES;390
10.8.4;REFERENCES;402
11;PART 4: INTERNATIONAL CONFERENCE ON DYNAMIC PROGRAMMING: PANEL DISCUSSION;404
11.1;CHAPTER 21. Comments of Professor Karl Hinderer;406
11.1.1;REFERENCES;408
11.2;CHAPTER 22. Comments of Professor Eric V. Denardo;410
11.2.1;REFERENCES;412
11.3;CHAPTER 23. Comments of Professor Arthur F. Veinott Jr;414
11.3.1;DYNAMIC PROGRAMMING: SOME OPEN PROBLEMS;414
11.3.2;NEW OPTIMALITY CRITERIA;414
11.3.3;LARGE-SCALE DYNAMIC PROGRAMS;415
11.3.4;PLANNING HORIZONS;415
11.3.5;CERTAINTY EQUIVALENTS;416
11.3.6;APPROXIMATION;417
11.3.7;REDUCTION OF STATE-ACTION SPACES;417
11.3.8;EXPLOITING SPECIAL STRUCTURES;418
11.3.9;COMPUTATIONAL COMPLEXITY;420
11.3.10;MORE OPEN PROBLEMS;421
11.3.11;CONCLUSIONS;422
11.3.12;REFERENCES;422
12;PARTICIPANTS;426