Dynamic Programming pdf epub mobi txt 電子書 下載2025

想要找書就要到 小美書屋

立刻按 ctrl+D收藏本頁

你會得到大驚喜!!

Focusing on the modeling and solution of deterministic multistage decision problems, this book looks at dynamic programming as a problem-solving optimization method. With over 400 useful references, this edition discusses the dynamic programming analysis of a problem, illustrates the rationale behind this analysis, and clarifies the theoretical grounds that justify the rationale. It also explains the meaning and role of the concept of state in dynamic programming, examines the purpose and function of the principle of optimality, and outlines solution strategies for problems defiant of conventional treatment.

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
· · · · · · (收起)