MTU Library Catalogue

Syndetics cover image
Image from Syndetics

Introduction to stochastic search and optimization : estimation, simulation and control / James C. Spall.

By: Spall, James C.
Material type: materialTypeLabelBookSeries: Wiley-Interscience series in discrete mathematics and optimization.Publisher: Hoboken, N.J. : Wiley-Interscience, 2003Description: xx, 595 p. : ill. ; 26 cm. + hbk.ISBN: 0471330523 (hbk.).Subject(s): Stochastic processes | Search theory | Mathematical optimizationDDC classification: 519.2
Contents:
Stochastic search and optimization: Motivation and supporting results -- Direct methods for Stochastic search -- Recursive estimation for linear models -- Stochastic approximation for nonlinear root-finding -- Stochastic gradient form of Stochastic approximation -- Stochastic approximation and the finite-difference method -- Simultaneous perturbation stochastic approximation -- Annealing-type algorithms -- Evolutionary computation I: Genetic algorithms -- Evolutionary computation II: General methods and theory -- Reinforcement learning via temporal differences -- Statistical methods for optimization in discrete problems -- Model selection and statistical information -- Simulation-based optimization I: Regeneration, common random numbers and selection methods -- Simulation-based optimization II: Stochastic gradient and sample path methods -- Markov chain Monte Carlo -- Optimal design for experimental inputs.

Enhanced descriptions from Syndetics:

* Unique in its survey of the range of topics.
* Contains a strong, interdisciplinary format that will appeal to both students and researchers.
* Features exercises and web links to software and data sets.

Includes bibliographical references (pages 558-579) and index.

Stochastic search and optimization: Motivation and supporting results -- Direct methods for Stochastic search -- Recursive estimation for linear models -- Stochastic approximation for nonlinear root-finding -- Stochastic gradient form of Stochastic approximation -- Stochastic approximation and the finite-difference method -- Simultaneous perturbation stochastic approximation -- Annealing-type algorithms -- Evolutionary computation I: Genetic algorithms -- Evolutionary computation II: General methods and theory -- Reinforcement learning via temporal differences -- Statistical methods for optimization in discrete problems -- Model selection and statistical information -- Simulation-based optimization I: Regeneration, common random numbers and selection methods -- Simulation-based optimization II: Stochastic gradient and sample path methods -- Markov chain Monte Carlo -- Optimal design for experimental inputs.

Table of contents provided by Syndetics

  • Preface (p. xiii)
  • 1. Stochastic Search and Optimization: Motivation and Supporting Results (p. 1)
  • 1.1 Introduction (p. 1)
  • 1.1.1 General Background (p. 1)
  • 1.1.2 Formal Problem Statement; General Types of Problems and Solutions; Global versus Local Search (p. 3)
  • 1.1.3 Meaning of "Stochastic" in Stochastic Search and Optimization (p. 7)
  • 1.2 Some Principles of Stochastic Search and Optimization (p. 12)
  • 1.2.1 Some Key Points (p. 13)
  • 1.2.2 Limits of Performance: No Free Lunch Theorems (p. 18)
  • 1.3 Gradients, Hessians, and Their Connection to Optimization of "Smooth" Functions (p. 20)
  • 1.3.1 Definition of Gradient and Hessian in the Context of Loss Functions (p. 20)
  • 1.3.2 First- and Second-Order Conditions for Optimization (p. 21)
  • 1.4 Deterministic Search and Optimization: Steepest Descent and Newton-Raphson Search (p. 22)
  • 1.4.1 Steepest Descent Method (p. 22)
  • 1.4.2 Newton-Raphson Method and Deterministic Convergence Rates (p. 27)
  • 1.5 Concluding Remarks (p. 30)
  • Exercises (p. 31)
  • 2. Direct Methods for Stochastic Search (p. 34)
  • 2.1 Introduction (p. 34)
  • 2.2 Random Search with Noise-Free Loss Measurements (p. 36)
  • 2.2.1 Some Attributes of Direct Random Search (p. 36)
  • 2.2.2 Three Algorithms for Random Search (p. 37)
  • 2.2.3 Example Implementations (p. 46)
  • 2.3 Random Search with Noisy Loss Measurements (p. 50)
  • 2.4 Nonlinear Simplex (Nelder-Mead) Algorithm (p. 55)
  • 2.4.1 Basic Method (p. 55)
  • 2.4.2 Adaptation for Noisy Loss Measurements (p. 58)
  • 2.5 Concluding Remarks (p. 60)
  • Exercises (p. 61)
  • 3. Recursive Estimation for Linear Models (p. 65)
  • 3.1 Formulation for Estimation with Linear Models (p. 65)
  • 3.1.1 Linear Model (p. 66)
  • 3.1.2 Mean-Squared and Least-Squares Estimation (p. 68)
  • 3.2 Least-Mean-Squares and Recursive-Least-Squares for Static [theta] (p. 72)
  • 3.2.1 Introduction (p. 72)
  • 3.2.2 Basic LMS Algorithm (p. 73)
  • 3.2.3 LMS Algorithm in Adaptive Signal Processing and Control (p. 75)
  • 3.2.4 Basic RLS Algorithm (p. 87)
  • 3.2.5 Connection of RLS to the Newton-Raphson Method (p. 81)
  • 3.2.6 Extensions to Multivariate RLS and Weighted Summands in Least-Squares Criterion (p. 82)
  • 3.3 LMS, RLS, and Kalman Filter for Time-Varying [theta] (p. 83)
  • 3.3.1 Introduction (p. 83)
  • 3.3.2 LMS (p. 85)
  • 3.3.3 RLS (p. 86)
  • 3.3.4 Kalman Filter (p. 87)
  • 3.4 Case Study: Analysis of Oboe Reed Data (p. 88)
  • 3.5 Concluding Remarks (p. 92)
  • Exercises (p. 93)
  • 4. Stochastic Approximation for Nonlinear Root-Finding (p. 95)
  • 4.1 Introduction (p. 95)
  • 4.2 Potpourri of Stochastic Approximation Examples (p. 98)
  • 4.3 Convergence of Stochastic Approximation (p. 104)
  • 4.3.1 Background (p. 104)
  • 4.3.2 Convergence Conditions (p. 105)
  • 4.3.3 On the Gain Sequence and Connection to ODEs (p. 108)
  • 4.4 Asymptotic Normality and Choice of Gain Sequence (p. 111)
  • 4.5 Extensions to Basic Stochastic Approximation (p. 115)
  • 4.5.1 Joint Parameter and State Evolution (p. 115)
  • 4.5.2 Adaptive Estimation and Higher-Order Algorithms (p. 116)
  • 4.5.3 Iterate Averaging (p. 117)
  • 4.5.4 Time-Varying Functions (p. 120)
  • 4.6 Concluding Remarks (p. 121)
  • Exercises (p. 122)
  • 5. Stochastic Gradient Form of Stochastic Approximation (p. 126)
  • 5.1 Root-Finding Stochastic Approximation as a Stochastic Gradient Method (p. 126)
  • 5.1.1 Basic Principles (p. 127)
  • 5.1.2 Stochastic Gradient Algorithm (p. 131)
  • 5.1.3 Implementation in General Nonlinear Regression Problems (p. 134)
  • 5.1.4 Connection of LMS to Stochastic Gradient SA (p. 135)
  • 5.2 Neural Network Training (p. 138)
  • 5.3 Discrete-Event Dynamic Systems (p. 142)
  • 5.4 Image Restoration (p. 144)
  • 5.5 Concluding Remarks (p. 147)
  • Exercises (p. 147)
  • 6. Stochastic Approximation and the Finite-Difference Method (p. 150)
  • 6.1 Introduction and Contrast of Gradient-Based and Gradient-Free Algorithms (p. 150)
  • 6.2 Some Motivating Examples for Gradient-Free Stochastic Approximation (p. 153)
  • 6.3 Finite-Difference Algorithm (p. 157)
  • 6.4 Convergence Theory (p. 158)
  • 6.4.1 Bias in Gradient Estimate (p. 158)
  • 6.4.2 Convergence (p. 159)
  • 6.5 Asymptotic Normality (p. 162)
  • 6.6 Practical Selection of Gain Sequences (p. 164)
  • 6.7 Several Finite-Difference Examples (p. 166)
  • 6.8 Some Extensions and Enhancements to the Finite-Difference Algorithm (p. 172)
  • 6.9 Concluding Remarks (p. 174)
  • Exercises (p. 174)
  • 7. Simultaneous Perturbation Stochastic Approximation (p. 176)
  • 7.1 Background (p. 177)
  • 7.2 Form and Motivation for Standard SPSA Algorithm (p. 178)
  • 7.2.1 Basic Algorithm (p. 178)
  • 7.2.2 Relationship of Gradient Estimate to True Gradient (p. 179)
  • 7.3 Basic Assumptions and Supporting Theory for Convergence (p. 182)
  • 7.4 Asymptotic Normality and Efficiency Analysis (p. 186)
  • 7.5 Practical Implementation (p. 188)
  • 7.5.1 Step-by-Step Implementation (p. 188)
  • 7.5.2 Choice of Gain Sequences (p. 189)
  • 7.6 Numerical Examples (p. 191)
  • 7.7 Some Extensions: Optimal Perturbation Distribution; One-Measurement Form; Global, Discrete, and Constrained Optimization (p. 193)
  • 7.8 Adaptive SPSA (p. 196)
  • 7.8.1 Introduction and Basic Algorithm (p. 196)
  • 7.8.2 Implementation Aspects of Adaptive SPSA (p. 200)
  • 7.8.3 Theory on Convergence and Efficiency of Adaptive SPSA (p. 201)
  • 7.9 Concluding Remarks (p. 203)
  • 7.10 Appendix: Conditions for Asymptotic Normality (p. 204)
  • Exercises (p. 204)
  • 8. Annealing-Type Algorithms (p. 208)
  • 8.1 Introduction to Simulated Annealing and Motivation from the Physics of Cooling (p. 208)
  • 8.2 Simulated Annealing Algorithm (p. 211)
  • 8.2.1 Basic Algorithm (p. 211)
  • 8.2.2 Modifications for Noisy Loss Function Measurements (p. 214)
  • 8.3 Some Examples (p. 217)
  • 8.4 Global Optimization via Annealing Algorithms Based on Stochastic Approximation (p. 221)
  • 8.5 Concluding Remarks (p. 225)
  • 8.6 Appendix: Convergence Theory for Simulated Annealing Based on Stochastic Approximation (p. 226)
  • Exercises (p. 228)
  • 9. Evolutionary Computation I: Genetic Algorithms (p. 231)
  • 9.1 Introduction (p. 231)
  • 9.2 Some Historical Perspective and Motivating Applications (p. 235)
  • 9.2.1 Brief History (p. 235)
  • 9.2.2 Early Motivation (p. 236)
  • 9.3 Coding of Elements for Searching (p. 237)
  • 9.3.1 Introduction (p. 237)
  • 9.3.2 Standard Bit Coding (p. 237)
  • 9.3.3 Gray Coding (p. 240)
  • 9.3.4 Real-Number Coding (p. 241)
  • 9.4 Standard Genetic Algorithm Operations (p. 242)
  • 9.4.1 Selection and Elitism (p. 242)
  • 9.4.2 Crossover (p. 244)
  • 9.4.3 Mutation and Termination (p. 245)
  • 9.5 Overview of Basic GA Search Approach (p. 246)
  • 9.6 Practical Guidance and Extensions: Coefficient Values, Constraints, Noisy Fitness Evaluations, Local Search, and Parent Selection (p. 247)
  • 9.7 Examples (p. 250)
  • 9.8 Concluding Remarks (p. 255)
  • Exercises (p. 256)
  • 10. Evolutionary Computation II: General Methods and Theory (p. 259)
  • 10.1 Introduction (p. 259)
  • 10.2 Overview of Evolution Strategy and Evolutionary Programming with Comparisons to Genetic Algorithms (p. 260)
  • 10.3 Schema Theory (p. 263)
  • 10.4 What Makes a Problem Hard? (p. 266)
  • 10.5 Convergence Theory (p. 268)
  • 10.6 No Free Lunch Theorems (p. 273)
  • 10.7 Concluding Remarks (p. 275)
  • Exercises (p. 276)
  • 11. Reinforcement Learning via Temporal Differences (p. 278)
  • 11.1 Introduction (p. 278)
  • 11.2 Delayed Reinforcement and Formulation for Temporal Difference Learning (p. 280)
  • 11.3 Basic Temporal Difference Algorithm (p. 283)
  • 11.4 Batch and Online Implementations of TD Learning (p. 287)
  • 11.5 Some Examples (p. 289)
  • 11.6 Connections to Stochastic Approximation (p. 295)
  • 11.7 Concluding Remarks (p. 297)
  • Exercises (p. 298)
  • 12. Statistical Methods for Optimization in Discrete Problems (p. 300)
  • 12.1 Introduction to Multiple Comparisons Over a Finite Set (p. 301)
  • 12.2 Statistical Comparisons Test Without Prior Information (p. 306)
  • 12.3 Multiple Comparisons Against One Candidate with Known Noise Variance(s) (p. 310)
  • 12.4 Multiple Comparisons Against One Candidate with Unknown Noise Variance(s) (p. 319)
  • 12.5 Extensions to Bonferroni Inequality; Ranking and Selection Methods in Optimization Over a Finite Set (p. 322)
  • 12.6 Concluding Remarks (p. 325)
  • Exercises (p. 326)
  • 13. Model Selection and Statistical Information (p. 329)
  • 13.1 Bias-Variance Tradeoff (p. 330)
  • 13.1.1 Bias and Variance as Contributors to Model Prediction Error (p. 330)
  • 13.1.2 Interpretation of the Bias-Variance Tradeoff (p. 334)
  • 13.1.3 Bias-Variance Analysis for Linear Models (p. 337)
  • 13.2 Model Selection: Cross-Validation (p. 340)
  • 13.3 The Information Matrix: Applications and Resampling-Based Computation (p. 349)
  • 13.3.1 Introduction (p. 349)
  • 13.3.2 Fisher Information Matrix: Definition and Two Equivalent Forms (p. 350)
  • 13.3.3 Two Key Properties of the Information Matrix: Connections to the Covariance Matrix of Parameter Estimates (p. 356)
  • 13.3.4 Selected Applications (p. 357)
  • 13.3.5 Resampling-Based Calculation of the Information Matrix (p. 360)
  • 13.4 Concluding Remarks (p. 363)
  • Exercises (p. 364)
  • 14. Simulation-Based Optimization I: Regeneration, Common Random Numbers, and Selection Methods (p. 367)
  • 14.1 Background (p. 367)
  • 14.1.1 Focus of Chapter and Roles of Search and Optimization in Simulation (p. 367)
  • 14.1.2 Statement of the Optimization Problem (p. 370)
  • 14.2 Regenerative Systems (p. 372)
  • 14.2.1 Background and Definition of the Loss Function L([theta]) (p. 372)
  • 14.2.2 Estimators of L([theta]) (p. 375)
  • 14.2.3 Estimates Related to the Gradient of L([theta]) (p. 380)
  • 14.3 Optimization with Finite-Difference and Simultaneous Perturbation Gradient Estimators (p. 382)
  • 14.4 Common Random Numbers (p. 385)
  • 14.4.1 Introduction (p. 385)
  • 14.4.2 Theory and Examples for Common Random Numbers (p. 387)
  • 14.4.3 Partial Common Random Numbers for Finite Samples (p. 396)
  • 14.5 Selection Methods for Optimization with Discrete-Valued [theta] (p. 398)
  • 14.6 Concluding Remarks (p. 405)
  • Exercises (p. 406)
  • 15. Simulation-Based Optimization II: Stochastic Gradient and Sample Path Methods (p. 409)
  • 15.1 Framework for Gradient Estimation (p. 409)
  • 15.1.1 Some Issues in Gradient Estimation (p. 409)
  • 15.1.2 Gradient Estimation and the Interchange of Derivative and Integral (p. 412)
  • 15.2 Pure Likelihood Ratio/Score Function and Pure Infinitesimal Perturbation Analysis (p. 417)
  • 15.3 Gradient Estimation Methods in Root-Finding Stochastic Approximation: The Hybrid LR/SF and IPA Setting (p. 420)
  • 15.4 Sample Path Optimization (p. 425)
  • 15.5 Concluding Remarks (p. 432)
  • Exercises (p. 433)
  • 16. Markov Chain Monte Carlo (p. 436)
  • 16.1 Background (p. 436)
  • 16.2 Metropolis-Hastings Algorithm (p. 440)
  • 16.3 Gibbs Sampling (p. 445)
  • 16.4 Sketch of Theoretical Foundation for Gibbs Sampling (p. 450)
  • 16.5 Some Examples of Gibbs Sampling (p. 453)
  • 16.6 Applications in Bayesian Analysis (p. 457)
  • 16.7 Concluding Remarks (p. 461)
  • Exercises (p. 462)
  • 17. Optimal Design for Experimental Inputs (p. 464)
  • 17.1 Introduction (p. 464)
  • 17.1.1 Motivation (p. 464)
  • 17.1.2 Finite-Sample and Asymptotic (Continuous) Designs (p. 469)
  • 17.1.3 Precision Matrix and D-Optimality (p. 471)
  • 17.2 Linear Models (p. 473)
  • 17.2.1 Background and Connections to D-Optimality (p. 473)
  • 17.2.2 Some Properties of Asymptotic Designs (p. 477)
  • 17.2.3 Orthogonal Designs (p. 481)
  • 17.2.4 Sketch of Algorithms for Finding Optimal Designs (p. 485)
  • 17.3 Response Surface Methodology (p. 486)
  • 17.4 Nonlinear Models (p. 489)
  • 17.4.1 Introduction (p. 489)
  • 17.4.2 Methods for Coping with Dependence on [theta] (p. 492)
  • 17.5 Concluding Remarks (p. 500)
  • 17.6 Appendix: Optimal Design in Dynamic Models (p. 501)
  • Exercises (p. 502)
  • Appendix A. Selected Results from Multivariate Analysis (p. 505)
  • A.1 Multivariate Calculus and Analysis (p. 505)
  • A.2 Some Useful Results in Matrix Theory (p. 511)
  • Exercises (p. 514)
  • Appendix B. Some Basic Tests in Statistics (p. 515)
  • B.1 Standard One-Sample Test (p. 515)
  • B.2 Some Basic Two-Sample Tests (p. 518)
  • B.3 Comments on Other Aspects of Statistical Testing (p. 524)
  • Exercises (p. 525)
  • Appendix C. Probability Theory and Convergence (p. 526)
  • C.1 Basic Properties (p. 526)
  • C.2 Convergence Theory (p. 529)
  • C.2.1 Definitions of Convergence (p. 529)
  • C.2.2 Examples and Counterexamples Related to Convergence (p. 532)
  • C.2.3 Dominated Convergence Theorem (p. 534)
  • C.2.4 Convergence in Distribution and Central Limit Theorem (p. 535)
  • Exercises (p. 537)
  • Appendix D. Random Number Generation (p. 538)
  • D.1 Background and Introduction to Linear Congruential Generators (p. 538)
  • D.2 Transformation of Uniform Random Numbers to Other Distributions (p. 542)
  • Exercises (p. 545)
  • Appendix E. Markov Processes (p. 547)
  • E.1 Background on Markov Processes (p. 547)
  • E.2 Discrete Markov Chains (p. 548)
  • Exercises (p. 551)
  • Answers to Selected Exercises (p. 552)
  • References (p. 558)
  • Frequently Used Notation (p. 580)
  • Index (p. 583)

Author notes provided by Syndetics

James C. Spall is a member of the Principal Professional Staff at the Johns Hopkins University, Applied Physics Laboratory, and is the Chair of the Applied and Computational Mathematics Program within the Johns Hopkins School of Engineering.