Dynamic Optimization and Differential Games (eBook)

Terry L. Friesz (Autor)

eBook Download: PDF

2010 | 2010
XIV, 502 Seiten
Springer US (Verlag)
978-0-387-72778-3 (ISBN)

Infos

This book has been written to address the increasing number of Operations Research and Management Science problems (that is, applications) that involve the explicit consideration of time and of gaming among multiple agents. It is a book that will be used both as a textbook and as a reference and guide by those whose work involves the theoretical aspects of dynamic optimization and differential games.

---

Dynamic Optimization and Differential Games has been written to address the increasing number of Operations Research and Management Science problems that involve the explicit consideration of time and of gaming among multiple agents. With end-of-chapter exercises throughout, it is a book that can be used both as a reference and as a textbook. It will be useful as a guide to engineers, operations researchers, applied mathematicians and social scientists whose work involves both the theoretical and computational aspects of dynamic optimization and differential games. Included throughout the text are detailed explanations of several original dynamic and game-theoretic mathematical models which are of particular relevance in today's technologically-driven-global economy: revenue management, oligopoly pricing, production planning, supply chain management, dynamic traffic assignment and dynamic congestion pricing. The book emphasizes deterministic theory, computational tools and applications associated with the study of dynamic optimization and competition in continuous time. It develops the key results of deterministic, continuous time, optimal control theory from both the classical calculus of variations perspective and the more modern approach of infinite dimensional mathematical programming. These results are then generalized for the analysis of differential variational inequalities arising in dynamic game theory for open loop environments. Algorithms covered include steepest descent in Hilbert space, gradient projection in Hilbert space, fixed point methods, and gap function methods.

Inhalt

Contents 
5 
Preface 12
Chapter 
14 
1.1 Brief History of the Calculus of Variations and Optimal Control 15
1.2 The Brachistochrone Problem 17
1.3 Optimal Economic Growth 18
1.3.1 Ramsey's 1928 Model 18
1.3.2 Neoclassical Optimal Growth 19
1.4 Regional Allocation of Public Investment 20
1.4.1 The Dynamics of Capital Formation 21
1.4.2 Population Dynamics 23
1.4.3 Technological Change 25
1.4.4 Criterion Functional and Final Form of the Model 26
1.5 Dynamic Telecommunications Flow Routing 27
1.5.1 Assumptions and Notation 27
1.5.2 Flow Propagation Mechanism 28
1.5.3 Path Delay Operators 30
1.5.4 Dynamic System Optimal Flows 31
1.5.5 Additional Constraints 31
1.5.6 Final Form of the Model 33
1.6 Brief History of Dynamic Games 33
1.7 Dynamic User Equilibrium for Vehicular Networks 34
1.8 Dynamic Oligopolistic Network Competition 35
1.8.1 Notation 36
1.8.2 Extremal Problems and the Nash Game 36
1.8.3 Differential Variational Inequality Formulation 39
1.9 Revenue Management and Nonlinear Pricing 40
1.9.1 The Decision Environment 40
1.9.2 The Role of Denial-of-Service Costs and Refunds 42
1.9.3 Firms' Extremal Problem 42
1.10 The Material Ahead 43
List of References Cited and Additional Reading 44
Chapter 
46 
2.1 Nonlinear Program Defined 47
2.2 Other Types of Mathematical Programs 48
2.3 Necessary Conditions for an Unconstrained Minimum 50
2.4 Necessary Conditions for a Constrained Minimum 51
2.4.1 The Fritz John Conditions 51
2.4.2 Geometry of the Kuhn-Tucker Conditions 52
2.4.3 The Lagrange Multiplier Rule 54
2.4.4 Motivating the Kuhn-Tucker Conditions 56
2.5 Formal Derivation of the Kuhn-Tucker Conditions 59
2.5.1 Cones and Optimality 60
2.5.2 Theorems of the Alternative 61
2.5.3 The Fritz John Conditions Again 62
2.5.4 The Kuhn-Tucker Conditions Again 63
2.6 Sufficiency, Convexity, and Uniqueness 65
2.6.1 Quadratic Forms 65
2.6.2 Concave and Convex Functions 66
2.6.3 Kuhn-Tucker Conditions Sufficient 71
2.7 Generalized Convexity and Sufficiency 73
2.8 Numerical and Graphical Examples 75
2.8.1 LP Graphical Solution 75
2.8.2 NLP Graphical Example 77
2.8.3 Nonconvex, Nongraphical Example 79
2.8.4 A Convex, Nongraphical Example 81
2.9 Discrete-Time Optimal Control 82
2.9.1 Necessary Conditions 84
2.9.2 The Minimum Principle 87
2.9.3 Discrete Optimal Control Example 88
2.10 Exercises 90
List of References Cited and Additional Reading 91
Chapter 
92 
3.1 The Calculus of Varations 93
3.1.1 The Space C1[ t0,tf] 93
3.1.2 The Concept of a Variation 93
3.1.3 Fundamental Lemma of the Calculus of Variations 95
3.1.4 Derivation of the Euler-Lagrange Equation 98
3.1.5 Additional Necessary Conditions in the Calculus of Variations 100
3.1.6 Sufficiency in the Calculus of Variations 106
3.1.7 Free Endpoint Conditions in the Calculus of Variations 108
3.1.8 Isoperimetric Problems in the Calculus of Variations 108
3.1.9 The Beltrami Identity for f0t=0 109
3.2 Calculus of Variations Examples 110
3.2.1 Example of Fixed Endpoints in the Calculus of Variations 111
3.2.2 Example of Free Endpoints in the Calculus of Variations 112
3.2.3 The Brachistochrone Problem 113
3.3 Continuous-Time Optimal Control 116
3.3.1 Necessary Conditions for Continuous-Time Optimal Control 118
3.3.2 Necessary Conditions with Fixed Terminal Time, No Terminal Cost, and No Terminal Constraints 122
3.3.3 Necessary Conditions When the Terminal Time Is Free 124
3.3.4 Necessary Conditions for Problems with Interior Point Constraints 126
3.3.5 Dynamic Programming and Optimal Control 127
3.3.6 Second-Order Variations in Optimal Control 130
3.3.7 Singular Controls 132
3.3.8 Sufficiency in Optimal Control 133
3.3.8.1 The Mangasarian Theorem 133
3.3.8.2 The Arrow Theorem 135
3.4 Optimal Control Examples 137
3.4.1 Simple Example of the Minimum Principle 137
3.4.2 An Example Involving Singular Controls 140
3.4.3 Approximate Solution of Optimal Control Problems by Time Discretization 143
3.4.4 A Two-Point Boundary-Value Problem 143
3.4.5 Example with Free Terminal Time 147
3.5 The Linear-Quadratic Optimal Control Problem 151
3.5.1 LQP Optimality Conditions 151
3.5.2 The HJPDE and Separation of Variables for the LQP 153
3.5.3 LQP Numerical Example 154
3.5.4 Another LQP Example 155
3.6 Exercises 157
List of References Cited and Additional Reading 158
Chapter 
160 
4.1 Elements of Functional Analysis 161
4.1.1 Notation and Elementary Concepts 161
4.1.2 Topological Vector Spaces 162
4.1.3 Convexity 170
4.1.4 The Hahn-Banach Theorem 171
4.1.5 Gâteaux Derivatives and the Gradient of a Functional 172
4.1.6 The Fréchet Derivative 175
4.2 Variational Inequalities and Constrained Optimization of Functionals 176
4.3 Continuous-Time Optimal Control 178
4.3.1 Analysis Based on the G-Derivative 179
4.3.2 Variational Inequalities as Necessary Conditions 182
4.4 Optimal Control with Time Shifts 187
4.4.1 Some Preliminaries 188
4.4.2 The Optimal Control Problem of Interest 189
4.4.3 Change of Variable 189
4.4.4 Necessary Conditions for Time-Shifted Problems 190
4.4.5 A Simple Abstract Example 196
4.5 Derivation of the Euler-Lagrange Equation 198
4.6 Kuhn-Tucker Conditions for Hilbert Spaces 199
4.7 Mathematical Programming Algorithms 203
4.7.1 The Steepest Descent Algorithm 203
4.7.1.1 Structure of the Steepest Descent Algorithm 204
4.7.1.2 Convergence of the Steepest Descent Algorithm 205
4.7.2 The Projected Gradient Algorithm 211
4.7.2.1 The Minimum Norm Projection 211
4.7.2.2 Structure of the Gradient Projection Algorithm 213
4.7.2.3 Coerciveness 215
4.7.2.4 Convergence of the Gradient Projection Algorithm 215
4.7.3 Penalty Function Methods 217
4.7.3.1 Definition of a Penalty Function 217
4.7.3.2 Description of the Penalty Function Algorithm 218
4.7.3.3 Convergence of the Penalty Function Method 218
4.7.4 Example of the Steepest Descent Algorithm 219
4.7.5 Example of the Gradient Projection Algorithm 222
4.7.6 Penalty Function Example 227
4.8 Exercises 229
List of References Cited and Additional Reading 230
Chapter 
232 
5.1 Some Basic Notions 233
5.2 Nash Equilibria and Normal Form Games 233
5.3 Some Related Nonextremal Problems 235
5.3.1 Nonextremal Problems and Programs 236
5.3.2 Kuhn-Tucker Conditions for Variational Inequalities 237
5.3.3 Variational Inequality and Complementarity Problem Generalizations 239
5.3.4 Relationships Among Nonextremal Problems 239
5.3.5 Variational Inequality Representation of NashEquilibrium 244
5.3.6 User Equilibrium 244
5.3.7 Existence and Uniqueness 248
5.4 Sensitivity Analysis of Variational Inequalities 250
5.5 The Diagonalization Algorithm 252
5.5.1 The Algorithm 254
5.5.2 Converence of Diagonalization 255
5.5.3 A Nonnetwork Example of Diagonalization 256
5.6 Gap Function Methods for VI ( F, 
261 
5.6.1 Gap Function Defined 261
5.6.2 The Auslender Gap Function 262
5.6.3 Fukushima-Auchmuty Gap Functions 263
5.6.4 The D-Gap Function 264
5.6.5 Gap Function Numerical Example 266
5.7 Other Algorithms for VI( F, 
268 
5.7.1 Methods Based on Differential Equations 269
5.7.2 Fixed-Point Methods 270
5.7.3 Generalized Linear Methods 271
5.7.4 Successive Linearization with Lemke's Method 272
5.8 Computing Network User Equilibria 273
5.9 Exercises 276
List of References Cited and Additional Reading 276
Chapter 
280 
6.1 Infinite-Dimensional Variational Inequalities 281
6.2 Differential Variational Inequalities 284
6.2.1 Problem Definition 284
6.2.2 Naming Conventions 285
6.2.3 Regularity Conditions for DVI(F, f,., 
286 
6.2.4 Necessary Conditions 287
6.2.5 Existence 289
6.2.6 Nonlinear Complementarity Reformulation 289
6.3 Differential Nash Games 290
6.3.1 Differential Nash Equilibrium 290
6.3.2 Generalized Differential Nash Equilibrium 294
6.4 Fixed-Point Algorithm 295
6.4.1 Formulation 295
6.4.2 The Unembellished Algorithm 296
6.4.3 Solving the SubProblems 299
6.4.4 Numerical Example 300
6.5 Descent in Hilbert Space with Gap Functions 302
6.5.1 Gap Functions in Hilbert Spaces 302
6.5.2 D-gap Equivalent Optimal Control Problem 305
6.5.3 Numerical Example 310
6.6 Differential Variational Inequalities with Time Shifts 311
6.6.1 Necessary Conditions 313
6.6.2 Fixed-Point Formulation and Algorithm 316
6.6.3 Time-Shifted Numerical Examples 318
6.7 Exercises 323
List of References Cited and Additional Reading 324
Chapter 
326 
7.1 Alternative Models of Optimal Economic Growth 327
7.1.1 Ramsey's 1928 Model 327
7.1.2 Optimal Growth with the Harrod-Domar Model 328
7.1.3 Neoclassical Optimal Growth 329
7.2 Optimal Regional Growth Based on the Harrod-Domar Model 331
7.2.1 Tax Rate as the Control 338
7.2.2 Tax Rate and Public Investment as Controls 341
7.2.3 Equal Public and Private Savings Ratios 346
7.2.4 Sufficiency 352
7.3 A Computable Theory of Regional Public Investment Allocation 356
7.3.1 The Dynamics of Capital Formation 357
7.3.2 Population Dynamics 358
7.3.3 Technological Change 360
7.3.4 Criterion Functional and Final Form of the Model 361
7.3.5 Numerical Example Solved by Time Discretization 362
7.4 Exercises 363
List of References Cited and Additional Reading 364
Chapter 
366 
8.1 The Aspatial Price-Taking Firm 367
8.1.1 Optimal Control Problem for Aspatial Perfect Competition 368
8.1.2 Numerical Example of Aspatial Perfect Competition 368
8.1.3 The Aspatial Price Taking Firm with a Terminal Constraint on Inventory 371
8.2 The Aspatial Monopolistic Firm 375
8.2.1 Necessary Conditions for the Aspatial Monopoly 376
8.2.2 Numerical Example 377
8.3 The Monopolistic Firm in a Network Economy 380
8.3.1 The Network Firm's Extremal Problem 380
8.3.2 Discrete-Time Approximation 383
8.3.3 Numerical Example 384
8.3.4 Solution by Discrete-Time Approximation 386
8.3.5 Solution by Continuous-Time Gradient Projection 386
8.4 Dynamic Oligopolistic Spatial Competition 389
8.4.1 Some Background and Notation 390
8.4.2 The Firm's Objective and Constraints 391
8.4.3 The DVI Formulation 393
8.4.4 Discrete-Time Approximation 397
8.4.5 A Comment About Path Variables 399
8.4.6 Numerical Example 399
8.4.7 Interpretation of Numerical Results 402
8.5 Competitive Supply Chains 408
8.5.1 Inverse Demands 408
8.5.2 Producers' Extremal Problem 409
8.5.3 Retailers' Extremal Problem 412
8.5.4 Supply Chain Extremal Problem 413
8.5.5 The Differential Variational Inequality 414
8.5.5.1 Maximum Principle for the Producers 414
8.5.5.2 Maximum Principle for the Retailers 415
8.5.5.3 Minimum Principle for the Supply Chain 416
8.5.6 The DVI 417
8.5.7 Numerical Example 418
8.6 Exercises 421
List of References Cited and Additional Reading 422
Chapter 
424 
9.1 Some Background 425
9.2 Arc Dynamics 426
9.2.1 Dynamics Based on Arc Exit Flow Functions 426
9.2.2 Dynamics with Controlled Entrance and Exit Flows 427
9.2.3 Cell Transmission Dynamics 428
9.2.4 Dynamics Based on Arc Exit Time Functions 429
9.2.5 Constrained Dynamics Based on Proper Flow Propagation Constraints 431
9.3 The Measure-Theoretic Nature of DUE 434
9.4 The Infinite-Dimensional Variational Inequality Formulation 436
9.5 When Delays Are Exogenous 441
9.6 When the Delay Operators Are Endogenous 448
9.6.1 Nested Operators 450
9.6.2 The Problem Setting 451
9.6.3 Analysis 452
9.6.4 Computation with Endogenous Delay Operators 458
9.6.4.1 Dealing with Time Shifts 458
9.6.4.2 A Numerical Example 460
9.7 Conclusions 465
9.8 Exercises 466
List of References Cited and Additional Reading 468
Chapter 
470 
10.1 Dynamic Pricing with Fixed Inventories 471
10.1.1 Infinite-Dimensional Variational Inequality Formulation 473
10.1.2 Restatement of the Isoperimetric Constraints 476
10.1.3 Differential Variational Inequality Formulation 477
10.1.4 Numerical Example 477
10.2 Revenue Management as an Evolutionary Game 480
10.2.1 Assumptions and Notation 481
10.2.2 Demand Dynamics 482
10.2.3 Constraints 483
10.2.4 The Firm's Optimal Control Problem 484
10.2.5 Differential Quasivariational Inequality Formulation 486
10.2.6 Numerical Example 488
10.3 Network Revenue Management 494
10.3.1 Discrete-Time Notation 494
10.3.2 Demand Functions 496
10.3.3 Denial-of-Service Costs and Refunds 498
10.3.4 Firms' Extremal Problem 498
10.3.5 Market Equilibrium Problem as a Quasivariational Inequality 500
10.3.6 Numerical Example 501
10.4 Exercises 503
List of References Cited and Additional Reading 505
Index 508

Produkt-Details

• Erscheint lt. Verlag: 20.8.2010
• Reihe/Serie: International Series in Operations Research & Management Science
• Reihe/Serie: International Series in Operations Research & Management Science
• Zusatzinfo: XIV, 502 p.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Finanz- / Wirtschaftsmathematik
• Themenwelt: Technik
• Themenwelt: Wirtschaft ► Allgemeines / Lexika
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Logistik / Produktion
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Themenwelt: Wirtschaft ► Volkswirtschaftslehre
• Schlagworte: algorithms • Calculus • Game Theory • linear optimization • Nonlinear Optimization • Operations Research • Optimization
• ISBN-10: 0-387-72778-7 / 0387727787
• ISBN-13: 978-0-387-72778-3 / 9780387727783