Stochastic Global Optimization (Springer Optimization and Its Applications)

Contents......Page 8
Introduction......Page 11
Notation......Page 13
1.1.1 General Minimization Problem......Page 14
1.1.2 Global Minimization Versus Local Minimization......Page 17
1.1.3 Combining Locality and Globality of Search......Page 19
1.1.4 Theory and Heuristics......Page 21
1.2 Stochastic Methods......Page 22
1.2.1 Determinism Versus Stochasticity......Page 23
1.2.2 Methods Based on Statistical Models......Page 26
1.2.3 Basic Ideas of Global Random Search......Page 27
1.3.1 Testing......Page 28
1.3.2 Software......Page 31
1.3.3 Applications......Page 32
2.1.1 Main Assumptions......Page 37
2.1.2 Formal Scheme of Global Random Search Algorithms......Page 41
2.1.3 Convergence of Global Random Search Algorithms......Page 42
2.1.4 Random Errors in Observations......Page 44
2.2.1 Pure Random Search and the Associated c.d.f.......Page 46
2.2.2 Rate of Convergence of Pure Random Search......Page 49
2.2.3 Pure Adaptive Search and Related Methods......Page 56
2.2.4 Pure Adaptive Search of Order k......Page 58
2.3 Order Statistics and Record Values: Probabilistic Aspects......Page 59
2.3.1 Order Statistics: Non-Asymptotic Properties......Page 60
2.3.2 Extreme Order Statistics: Asymptotic Properties......Page 62
2.3.3 Record Values and Record Moments......Page 67
2.4 Statistical Inference About m: Known Value of the Tail Index......Page 72
2.4.1 Estimation of m......Page 73
2.4.3 Choice of n and k......Page 81
2.5.1 Statistical Inference......Page 83
2.5.2 Using an Incorrect Value of the Tail Index......Page 85
2.5.3 Exact Determination of the Value of the Tail Index......Page 88
2.6.1 Using Statistical Inference in Global Random Search......Page 89
2.6.2 Statistical Inference in Random Multistart......Page 93
2.6.3 Sampling on Surfaces......Page 96
2.7 Proofs......Page 98
3.1 Random and Semi-Random Coverings......Page 101
3.1.1 Covering with Balls and Optimization......Page 102
3.1.2 Dispersion......Page 107
3.1.3 Uniform Sequences and Discrepancies......Page 114
3.2.1 Stratified Sampling......Page 118
3.2.2 Asymptotic Criteria......Page 120
3.2.3 Stochastic Dominance with Respect to Record Values......Page 122
3.3.1 Construction of Markovian Algorithms......Page 123
3.3.2 Simulated Annealing......Page 125
3.4 Markov Monotonous Search......Page 130
3.4.1 Statement of the Problem......Page 131
3.4.3 Homogeneous Search......Page 136
3.5.1 Construction of Algorithms and Their Convergence......Page 140
3.5.2 Special Cases; Genetic Algorithms......Page 145
3.5.3 Homogeneous Transition Probabilities......Page 149
3.6 Proofs......Page 152
4.1.1 Introduction......Page 156
4.1.2 Random Processes......Page 157
4.1.3 Random Fields......Page 161
4.1.4 Axiomatic Definition of a Statistical Model......Page 162
4.1.5 Response Surfaces......Page 166
4.1.6 Estimation of Parameters......Page 167
4.1.7 Illustrative Comparison......Page 168
4.2.1 Introduction......Page 171
4.2.2 Passive Methods......Page 173
4.2.3 Bayesian Methods......Page 175
4.2.4 P-algorithm......Page 177
4.2.5 Information Theory Based Approach......Page 181
4.2.6 Response Surface Based Methods......Page 183
4.2.7 Modifications......Page 187
4.2.8 Proofs of Theorems......Page 188
4.3.2 One-step Bayesian Algorithm......Page 191
4.3.3 P-algorithm......Page 192
4.3.4 P-algorithm for a Model with Derivatives......Page 195
4.3.5 Comparison of P-algorithms......Page 197
4.3.6 P*-algorithm......Page 199
4.3.7 Convergence......Page 200
4.3.8 Convergence Rates......Page 201
4.3.9 Probabilistic Convergence Rates......Page 207
4.3.10 Testing and Applications......Page 210
4.3.11 Proofs of Theorems and Lemmas......Page 213
4.4.2 P-algorithm......Page 228
4.4.3 Two Dimensional Select and Clone......Page 231
4.4.4 P-algorithm With Simplicial Partitioning......Page 234
4.4.5 Testing of the P-algorithm with Simplicial Partitioning......Page 240
4.4.6 Proofs of Theorems......Page 247
References......Page 252
E......Page 266
M......Page 267
S......Page 268
Z......Page 269