Dynamic Optimization and Differential Games

1. Auflage 2010
ISBN: 978-0-387-72778-3
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 502 Seiten

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.

Autoren/Hrsg.

Inhaltsverzeichnis

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