Preface ......................................................... v
1. Discrete-time Singularly Perturbed Markov Chains ............. 1
G. Yin and Q. Zhang
1.1. Singularly Perturbed Markov Chains ...................... 2
1.1.1. Motivation ....................................... 2
1.1.2. Preliminary ...................................... 3
1.1.3. Singularly Perturbed Models ...................... 5
1.1.4. Motivating Examples .............................. 9
1.2. Asymptotic Expansions .................................. 12
1.3. Occupation Measures .................................... 18
1.4. Nonstationary Markov Chains and Applications ........... 23
1.4.1. Asymptotic Properties for Smooth Transition
Matrices ........................................ 23
1.4.2. Bounded and Measurable Transition Matrices ...... 29
1.4.3. Applications to Nearly Optimal Controls ......... 32
1.5. Notes and Remarks ...................................... 36
1.5.1. Notes on the Literature ......................... 36
1.5.2. Possible Future Research Topics ................. 37
1.6. References ............................................. 38
2. Nearly Optimal Controls of Markovian Systems ................ 43
Q. Zhang, R.H. Liu, and G. Yin
2.1. Singularly Perturbed MDP ............................... 44
2.1.1. Irreducible MDP under Discounted Cost ........... 46
2.1.2. Irreducible MDP under Long-Run Average Cost ..... 51
2.1.3. MDP with General Transition Matrices ............ 54
2.1.4. Historical Notes ................................ 61
2.2. Hybrid LQG Control ..................................... 62
2.2.1. Aggregation and Approximation ................... 66
2.2.2. Asymptotic Optimality ........................... 71
2.2.3. Hybrid LQG "with General Transition Matrices .... 75
2.2.4. A Numerical Example ............................. 80
2.2.5. Historical Notes ................................ 82
2.3. Conclusions ............................................ 83
2.4. References ............................................. 83
3. Stochastic Approximation, with Applications ................. 87
Han-Fu Chen
3.1. SA Algorithms .......................................... 87
3.2. General Convergence Theorems by TS Method .............. 90
3.3. Convergence Theorems Under State-Independent
Conditions ............................................. 99
3.4. Applications .......................................... 102
3.4.1. Application to Optimization .................... 102
3.4.2. Application to Signal Processing ............... 105
3.5. Notes ................................................. 107
3.6. References ............................................ 108
4. Performance Potential Based Optimization and MDPs .......... 111
Xi-Ren Cao
4.1. Sensitivity Analysis and Performance Potentials ....... 112
4.2. Markov Decision Processes ............................. 116
4.3. Problems with Discounted Performance Criteria ......... 118
4.4. Single Sample Path Based Implementations .............. 121
4.5. Time Aggregation ...................................... 123
4.6. Connections to Perturbation Analysis .................. 126
4.7. Application Examples .................................. 128
4.8. Notes ................................................. 130
4.9. References ............................................ 134
5. An Interior-Point Approach to Multi-Stage Stochastic Pro
gramming ................................................... 137
Shuzhong Zhang
5.1. Two-Stage Stochastic Linear Programming ............... 139
5.2. A Case Study .......................................... 142
5.3. Multiple Stage Stochastic Programming ................. 144
5.4. An Interior Point Method .............................. 146
5.5. Finding Search Directions ............................. 156
5.6. Model Diagnosis ....................................... 164
5.7. Notes ................................................. 167
5.8. References ............................................ 168
6. A Brownian Model of Stochastic Processing Networks ......... 171
Hong Chen
6.1. Preliminaries ......................................... 172
6.2. Stochastic Processing Network Model ................... 174
6.3. Examples of Stochastic Processing Networks ............ 176
6.3.1. Scheduling Control of Multiclass Queueing
Network ........................................ 176
6.3.2. A Simple Queueing Network with both
Scheduling and Routing ......................... 177
6.3.3. An Assemble-To-Order System .................... 179
6.4. Brownian Model for Stochastic Processing Network ...... 181
6.4.1. Comparison to Harrison's Brownian Model ........ 183
6.4.2. Extensions ..................................... 184
6.5. Brownian Approximation via Strong Approximation ....... 185
6.6. Notes ................................................. 186
6.7. Appendix: Strong Approximation vs. Heavy Traffic
Approximation ......................................... 187
6.8. References ............................................ 191
7. Stability of General Processing Networks ................... 193
Jim Dai and Otis B. Jennings
7.1. Motivating Simulations ................................ 195
7.2. Open Processing Networks .............................. 201
7.2.1. Network Description ............................ 202
7.2.2. The Standard Network and Dispatch Policies ..... 205
7.2.3. Production Policies and Sensible Policies ...... 206
7.2.4. Rate Stability ................................. 209
7.3. Network and Fluid Model Equations ..................... 210
7.3.1. Network Dynamics ............................... 210
7.3.2. Fluid Models ................................... 214
7.3.3. Connection between Processing Networks and
Fluid Models ................................... 217
7.4. Connection between Artificial and Standard Fluid
Models ................................................ 219
7.4.1. Batch Processing Networks and Normal
Policies ....................................... 219
7.4.2. Stability under Sensible Production Policies ... 222
7.5. Examples of Stable Policies ........................... 223
7.5.1. Early Steps First .............................. 223
7.5.2. Generalized Round Robin ........................ 228
7.6. Extensions ............................................ 230
7.7. Appendix .............................................. 232
7.7.1. Departures As a Function of Server Effort ...... 232
7.7.2. Proofs of Lemmas 7.12 and 7.18 ................. 236
7.8. Notes ................................................. 240
7.9. References ............................................ 241
8. Large Deviations, Long-Range Dependence, and Queues ........ 245
C.-S. Chang, David D. Yao and Tim Zajic
8.1. Fractional Brownian Motion and a Related Filter ....... 246
8.2. Moderate Deviations for Sample-Path Processes ......... 248
8.3. MDP for the Filtered Process .......................... 252
8.4. Queueing Applications: The Workload Process ........... 258
8.5. Verifying the Key Assumptions ......................... 267
8.6. Notes ................................................. 274
8.7. References ............................................ 275
9. Markowitz's World in Continuous Time, and Beyond ........... 279
Xun Yu Zhou
9.1. The Mean-Variance Portfolio Selection Model ........... 280
9.2. A Stochastic LQ Control Approach ...................... 283
9.3. Efficient Frontier: Deterministic Market Parameters ... 285
9.4. Efficient Frontier: Random Adaptive Market
Parameters ............................................ 292
9.5. Efficient Frontier: Markov-Modulated Market
Parameters ............................................ 296
9.6. Efficient Frontier: No Short Selling .................. 299
9.7. Mean-Variance Hedging ................................. 300
9.8. Notes ................................................. 303
9.9. References ............................................ 305
10.Variance Minimization in Stochastic Systems ................ 311
Duan Li, Fucai Qian and Peilin Fu
10.1.Variance Minimization Problem ......................... 311
10.2.General Variance Minimization Problem ................. 314
10.3.Variance Minimization in Dynamic Portfolio
Selection ............................................. 316
10.4.Variance Minimization in Dual Control ................. 323
10.5.Notes ................................................. 330
10.6.References ............................................ 330
11.A Markov Chain Method for Pricing Contingent Claims ........ 333
Jin-Chuan Duan, Genevieve Gauthier and Jean-Guy Simonato
11.1.The Markov Chain Pricing Method ....................... 334
11.2.The Black-Scholes (1973) Pricing Model ................ 336
11.2.1.Choosing the Set of Asset Prices ............... 337
11.2.2.Computing Transition Probabilities and Option
Prices ......................................... 338
11.2.3.An Illustrative Example ........................ 339
11.2.4.A Markov Chain Interpretation of Binomial
Tree ........................................... 341
11.2.5.Numerical Examples ............................. 343
11.3.The GARCH Pricing Model ............................... 347
11.3.1.Choosing the Set of Discrete Prices and
Volatilities ................................... 349
11.3.2.Computing Transition Probabilities and Option
Prices ......................................... 350
11.3.3.Numerical Examples ............................. 351
11.4.Valuing Exotic Options ................................ 355
11.5.Appendix: The Conditional Expected Value of
hT* and h2T* ........................................... 360
11.6.References ............................................ 361
12.Stochastic Network Models and Optimization of a Hospital
System ..................................................... 363
Xiuli Chao, Liming Liu and Shaohui Zheng
12.1.A Multi-Site Service Network Model .................... 364
12.2.Patient Flow Management ............................... 366
12.3.Capacity Design ....................................... 371
12.4.Switching Costs and Quality of Service ................ 382
12.5.Insights and Future Research Directions ............... 387
12.6.Notes ................................................. 390
12.7.References ............................................ 391
13.Optimal Airline Booking Control with Cancellations ......... 395
Youyi Feng, Ping Lin and Baichun Xiao
13.1.Preliminaries ......................................... 396
13.1.1.Model Description .............................. 396
13.1.2.Optimality Conditions and the Value Function ... 398
13.2.The Minimum Acceptable Fare and Threshold Control ..... 400
13.2.1.The Minimum Acceptable Fare .................... 400
13.2.2.Properties of MAF .............................. 402
13.2.3.Threshold Control and Computation of the Value
Function ....................................... 412
13.3.Extensions of the Basic Model ......................... 414
13.3.1.Time-Dependent Air Fares ....................... 414
13.3.2.Fare-Dependent Partial Refunds ................. 414
13.4.Numerical Experiments ................................. 418
13.5.Notes ................................................. 421
13.6.References ............................................ 424
14.Information Revision and Decision Making in Supply Chain
Management ................................................. 429
Houmin Yan and Hanqin Zhang
14.1.Industrial Examples ................................... 429
14.1.1.The Procurement of Micro-Controller ............ 430
14.1.2.Analysis of Demand Forecast Data ............... 431
14.1.3.The Deregulated Energy Markets ................. 435
14.2.A Multi-Period, Two-Decision Model .................... 435
14.3.A One-Period, Multi-Information Revision Model ........ 443
14.4.Applications .......................................... 450
14.4.1.Decision-Making with Two Procurement
Alternatives ................................... 450
14.4.2.The Application to Deregulated Energy
Markets ........................................ 450
14.5.Notes ................................................. 451
14.6.References ............................................ 455
About the Contributors ........................................ 459
|
