Contents
1 Introduction 1
1.1 Welcome to Dynamic Programming! . . . . . . . . . . . . . 2
1.2 How to Read This Book . . . . . . . . . . . . . . . . . . . . 6
I Science 9
2 Fundamentals 11
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2 Meta-Recipe Revisited . . . . . . . . . . . . . . . . . . . . . 13
2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Decomposition of the Solution Set . . . . . . . . . . . . . . . 16
2.5 Principle of Conditional Optimization . . . . . . . . . . . . 17
2.6 Conditional Problems . . . . . . . . . . . . . . . . . . . . . . 18
2.7 Optimality Equation . . . . . . . . . . . . . . . . . . . . . . 19
2.8 Solution Procedure . . . . . . . . . . . . . . . . . . . . . . . 19
2.9 Time Out: Direct Enumeration! . . . . . . . . . . . . . . . . 21
2.10 Equivalent Conditional Problems . . . . . . . . . . . . . . . 22
2.11 Modified Problems . . . . . . . . . . . . . . . . . . . . . . . 24
2.12 The Role of a Decomposition Scheme . . . . . . . . . . . . . 26
2.13 Dynamic Programming Problem — Revisited . . . . . . . . 30
2.14 Trivial Decomposition Scheme . . . . . . . . . . . . . . . . . 32
2.15 Summary and a Look Ahead . . . . . . . . . . . . . . . . . . 33
3 Multistage Decision Model 35
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2 A Prototype Multistage Decision Model . . . . . . . . . . . 37
3.3 Problem vs Problem Formulation . . . . . . . . . . . . . . . 41
3.4 Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.5 Markovian Policies . . . . . . . . . . . . . . . . . . . . . . . 52
3.6 Remarks on the Notation . . . . . . . . . . . . . . . . . . . 54
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 56
4 Dynamic Programming — An Outline 59
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 60
4.3 Markovian Decomposition Scheme . . . . . . . . . . . . . . 64
4.4 Optimality Equation . . . . . . . . . . . . . . . . . . . . . . 68
4.5 Dynamic Programming Problems . . . . . . . . . . . . . . . 70
4.6 The Final State Model . . . . . . . . . . . . . . . . . . . . . 75
4.7 Principle of Optimality . . . . . . . . . . . . . . . . . . . . . 81
4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5 Solution Methods 85
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.2 Additive Functional Equations . . . . . . . . . . . . . . . . . 87
5.3 Truncated Functional Equations . . . . . . . . . . . . . . . . 88
5.4 Nontruncated Functional Equations . . . . . . . . . . . . . . 101
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
6 Successive Approximation Methods 111
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
6.3 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.4 Functional Equations of Type One . . . . . . . . . . . . . . 121
6.5 Functional Equations of Type Two . . . . . . . . . . . . . . 125
6.6 Truncation Method . . . . . . . . . . . . . . . . . . . . . . . 131
6.7 Stationary Models . . . . . . . . . . . . . . . . . . . . . . . 135
6.8 Truncation and Successive Approximation . . . . . . . . . . 139
6.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 144
7 Optimal Policies 145
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
7.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 146
7.3 Truncated Functional Equations . . . . . . . . . . . . . . . . 150
7.4 Nontruncated Functional Equations . . . . . . . . . . . . . . 156
7.5 Successive Approximation in the Policy Space . . . . . . . . 165
7.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 168
8 The Curse of Dimensionality 169
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8.3 Discrete Problems . . . . . . . . . . . . . . . . . . . . . . . . 173
8.4 Special Cases . . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.5 Complete Enumeration . . . . . . . . . . . . . . . . . . . . . 179
8.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
9 The Rest Is Mathematics and Experience 183
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
9.2 Choice of Model . . . . . . . . . . . . . . . . . . . . . . . . . 184
9.3 Dynamic Programming Models . . . . . . . . . . . . . . . . 185
9.4 Forward Decomposition Models . . . . . . . . . . . . . . . . 188
9.5 Practice What You Preach! . . . . . . . . . . . . . . . . . . 189
9.6 Computational Schemes . . . . . . . . . . . . . . . . . . . . 190
9.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.8 Dynamic Programming Software . . . . . . . . . . . . . . . 193
9.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
II Art 195
10 Refinements 197
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
10.2 Weak-Markovian Condition . . . . . . . . . . . . . . . . . . 198
10.3 Markovian Formulations . . . . . . . . . . . . . . . . . . . . 204
10.4 Decomposition Schemes . . . . . . . . . . . . . . . . . . . . 206
10.5 Sequential Decision Models . . . . . . . . . . . . . . . . . . 218
10.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.7 Shortest Path Model . . . . . . . . . . . . . . . . . . . . . . 247
10.8 The Art of Dynamic Programming Modeling . . . . . . . . . 257
10.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
10.10 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 259
11 The State 261
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
11.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 262
11.3 Mathematically Speaking . . . . . . . . . . . . . . . . . . . . 271
11.4 Decomposition Revisited . . . . . . . . . . . . . . . . . . . . 285
11.5 Infeasible States and Decisions . . . . . . . . . . . . . . . . . 291
11.6 State Aggregation . . . . . . . . . . . . . . . . . . . . . . . . 294
11.7 Nodes as States . . . . . . . . . . . . . . . . . . . . . . . . . 304
11.8 Multistage vs Sequential Models . . . . . . . . . . . . . . . . 311
11.9 Models vs Functional Equations . . . . . . . . . . . . . . . . 313
11.10 Easy Problems . . . . . . . . . . . . . . . . . . . . . . . . . 317
11.11 Modeling Tips . . . . . . . . . . . . . . . . . . . . . . . . . . 318
11.12 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . 330
11.13 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
12 Parametric Schemes 333
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
12.2 Background and Motivation . . . . . . . . . . . . . . . . . . 334
12.3 Fractional Programming Scheme . . . . . . . . . . . . . . . 339
12.4 C-programming Scheme . . . . . . . . . . . . . . . . . . . . 344
12.5 Lagrange Multiplier Scheme . . . . . . . . . . . . . . . . . . 352
12.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
12.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 356
13 The Principle of Optimality 357
13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
13.2 Bellman’s Principle of Optimality . . . . . . . . . . . . . . . 362
13.3 Prevailing Interpretation . . . . . . . . . . . . . . . . . . . . 364
13.4 Variations on a Theme . . . . . . . . . . . . . . . . . . . . . 366
13.5 Criticism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
13.6 So What Is Amiss? . . . . . . . . . . . . . . . . . . . . . . . 370
13.7 The Final State Model Revisited . . . . . . . . . . . . . . . 370
13.8 Bellman’s Treatment of Dynamic Programming . . . . . . . 372
13.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
13.10 Post Script: Pontryagin’s Maximum Principle . . . . . . . . 377
14 Forward Decomposition 381
14.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
14.2 Function Decomposition . . . . . . . . . . . . . . . . . . . . 384
14.3 Initial Problem . . . . . . . . . . . . . . . . . . . . . . . . . 398
14.4 Separable Objective Functions Revisited . . . . . . . . . . . 398
14.5 Modified Problems Revisited . . . . . . . . . . . . . . . . . . 400
14.6 Backward Conditional Problems Revisited . . . . . . . . . . 403
14.7 Markovian Condition Revisited . . . . . . . . . . . . . . . . 404
14.8 Forward Functional Equation . . . . . . . . . . . . . . . . . 405
14.9 Impact on the State Space . . . . . . . . . . . . . . . . . . . 405
14.10 Anomaly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
14.11 Pathologic Cases . . . . . . . . . . . . . . . . . . . . . . . . 414
14.12 Summary and Conclusions . . . . . . . . . . . . . . . . . . . 416
14.13 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 417
15 Push! 419
15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
15.2 The Pull Method . . . . . . . . . . . . . . . . . . . . . . . . 422
15.3 The Push Method . . . . . . . . . . . . . . . . . . . . . . . . 427
15.4 Monotone Accumulated Return Processes . . . . . . . . . . 434
15.5 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . 441
15.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448
15.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . 449
III Epilogue 451
16 What Then Is Dynamic Programming? 453
16.1 Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454
16.2 Non-Optimization Problems . . . . . . . . . . . . . . . . . . 457
16.3 An Abstract Dynamic Programming Model . . . . . . . . . 459
16.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
16.5 The Towers of Hanoi Problem . . . . . . . . . . . . . . . . . 476
16.6 Optimization-Free Dynamic Programming . . . . . . . . . . 482
16.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . 484
IV Appendices 487
A Contraction Mapping 489
A.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
A.2 Metric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 489
A.3 Contraction in the Functional Space . . . . . . . . . . . . . 492
A.4 Contraction in the Domain Space . . . . . . . . . . . . . . . 494
A.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 502
B Fractional Programming 503
B.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
B.2 Dinkelbach’s Algorithm . . . . . . . . . . . . . . . . . . . . . 504
B.3 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 509
C Composite Concave Programming 511
C.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
C.2 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 513
C.3 Pseudolinear Problems . . . . . . . . . . . . . . . . . . . . . 516
C.4 Convex Problems . . . . . . . . . . . . . . . . . . . . . . . . 519
C.5 One-Dimensional Convex Additive Problems . . . . . . . . . 525
D The Principle of Optimality in Stochastic Processes 529
D.1 Preliminary Analysis . . . . . . . . . . . . . . . . . . . . . . 529
D.2 Common Interpretation of the Principle . . . . . . . . . . . 531
D.3 Principle of Optimality (stochastic models) . . . . . . . . . 533
D.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
D.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . 534
E The Corridor Method 535
E.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
E.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 536
E.3 Example: TSP . . . . . . . . . . . . . . . . . . . . . . . . . . 537
E.4 Generating Corridors . . . . . . . . . . . . . . . . . . . . . . 540
E.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . 547
Bibliography 549
Index 595
· · · · · · (收起)