Introduction to Stochastic Search and Optimization
This book presents the notes of graduate courses taught by the author on the title theme. His experience is transmitted also in some recommendations for the possible structuring of courses on Stochastic Optimization and on Simulation and Monte Carlo Methods. Chapters 1--11 constitute a cluster, where the main algorithms used in stochastic search are discussed. In the first chapter a background is given (global search vs. local search, gradients, Hessians, Steepest Descent, Newton-Raphson methods). The second chapter introduces different search methods for optimisation and the third chapter presents discrete search linear models where the loss function \(L({\theta})\) is a quadratic function of \({\theta}\). The 5th chapter tackles the problem of root finding in nonlinear models (Robbins-Moro stochastic approximation [SA] search) when direct unbiased measurements of the gradient are available. In chapter 6 a sensible change is introduced: the stochastic gradient is not available. Then, when we look for the minimisation of \(L({\theta})\) the optimisation is performed using only its measurements (gradient free methods). Chapter 7 completes the basics on SA by presenting a method that is usable both for stochastic gradient and gradient free settings (simultaneous perturbation SA). Chapter 8 presents a broad discussion on Simulated Annealing Algorithms (SAA). Metropolis methods based on Boltzman-Gibbs distribution are studied and the Markov chain based justification of its convergence is discussed. An important addition to current results is the discussion of the role of the injection of random inputs in the basic SA procedures (studied through chapters 4--7) to derive global optima. The stochastic rates of convergence are analysed using the results of \textit{G. Yin} [SIAM. J. Optim. 10, 99--120 (1999; Zbl 0958.60020)] and \textit{S. B. Gelfand} and \textit{S. K. Mitter} [SIAM J. Control Optimization 31, 111--131 (1993; Zbl 0814.65059)]. The fact that evolutionary computation permits to develop computational abstraction of natural processes is analysed in the next two chapters. Chapter 9 is devoted to the classic computational counterpart of a biological process: Genetic Algorithms (GA) . The next one is devoted to the discussion of the general theory. We may quote that chapter 9 follows a pattern similar to previous chapters when GA is presented as a particular approach to global optimisation. The method is not only studied but characterised historically and in terms of its non convergence, see Theorem 3 and 4 of \textit{G. Rudolph} [IEEE Trans. Neural Networks 5, 96--101 (1994)]. The way of studying the non-convergence or convergence of a particular algorithm is illustrated with two excellent examples. Chapter 11 discusses the delayed reinforcement problem and connects learning with the idea of temporal differences. It is applied to parameter estimation and implementation (batch and online cases). Temporal differential algorithms are also analysed. They are able to use prior information, present in the model, for obtaining improved predictions. Then the basic algorithm connection with stochastic gradient algorithm or stochastic approximation is discussed. Some examples of the connection to root-finding stochastic approximation are also discussed. Chapters 12 and 13 deal with statistical models. The first of them displays a set of statistical models for establishing the admissibility of the quality of options, based on a loss function, characterised by a finite set of parameters. Some of them are sequential methods. The other chapter focusses on the determination of an adequate model to be used for describing a set of data. Three main approaches are considered: Bias-variance trade-off, (as in portfolio selection), Cross validation (as in multivariate analysis) and the use of the Information Matrix and resampling. Chapter 17 returns to statistical methods and the recommendability of some optimal designs of experiments is analysed. Chapters 14--16 visit Monte Carlo (MC) Simulation theory: model building, validation, gradient-based methods, Markov chains. The role of MC methods in Bayesian analysis is discussed together with Metropolis-Hastings and Gibbs samplers. Five appendices contain prerequisites, needed for beginners: Multivariate Analysis, Hypothesis Testing, Probability Theory, Random Numbers Generation and Markov Processes. The book discusses the theoretical basis of the algorithms avoiding large proofs and placing the coordinates of the references. A large set of worked out examples is included for illustrating the results. More than 300 references are listed and a web site is disposable for obtaining extra information and computation codes. I consider that an outstanding feature of the book is its successful synthesis and the direct applicability of computer algorithms. I warmly recommend it for those specialists involved with work on optimisation.
- How does a stochastic optimization/approximation algorithm adapt to a randomly evolving optimum/root with jump Markov sample paths
- Ordinal optimization of \(G/G/1/K\) polling systems with \(k\)-limited service discipline
- Adaptive population-based search: application to estimation of nonlinear regression parameters
- Global optimization of higher order moments in portfolio selection
- Statistical inferences for termination of Markov type random search algorithms
- Pattern search ranking and selection algorithms for mixed variable simulation-based optimization
- An extended empirical saddlepoint approximation for intractable likelihoods
- Multiple stopping time POMDPs: structural results \& application in interactive advertising on social media
- Accelerated random search for constrained global optimization assisted by radial basis function surrogates
- Stochastic optimization using a trust-region method and random models
- A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs
- Heuristic decision rules for short-term trading of renewable energy with co-located energy storage
- Theoretical connections between optimization algorithms based on an approximate gradient
- Adaptive importance sampling for optimization under uncertainty problems
- Approximate maximum likelihood estimation for population genetic inference
- An efficient simulation optimization method for the generalized redundancy allocation problem
- Predictive coarse-graining
- Polynomial chaos representation of databases on manifolds
- Adaptive stochastic approximation algorithm
- Calculating quantiles of noisy distribution functions using local linear regressions
- Gaussian variational approximation with sparse precision matrices
- A second-order iterated smoothing algorithm
- Asymptotic bias of stochastic gradient search
- Robustness analysis of an uncertain computational model to predict well integrity for geologic \(\mathrm{CO}_{2}\) sequestration
- A simple numerical method based simultaneous stochastic perturbation for estimation of high dimensional matrices
- Generalization of a result of Fabian on the asymptotic normality of stochastic approximation
- A unified framework for stochastic optimization
- Optimizing stimulus waveforms for electroceuticals
- Variable sample size method for equality constrained optimization problems
- Computing equilibrium prices for a capital asset pricing model with heterogeneous beliefs and margin-requirement constraints
- Methods to compare expensive stochastic optimization algorithms with random restarts
- Cyclic seesaw process for optimization and identification
- New stochastic approximation algorithms with adaptive step sizes
- Stochastic Nelder-Mead simplex method -- a new globally convergent direct search method for simulation optimization
- Newsvendor-type models with decision-dependent uncertainty
- Approximate stochastic annealing for online control of infinite horizon Markov decision processes
- Sequential Monte Carlo simulated annealing
- A new hybrid stochastic approximation algorithm
- False discovery rate control with multivariate p-values
- Disease spread in coupled populations: minimizing response strategies costs in discrete time models
- Periodic step-size adaptation in second-order gradient descent for single-pass on-line structured learning
- Design optimization under uncertainties of a mesoscale implant in biological tissues using a probabilistic learning algorithm
- Gradient-free method for nonsmooth distributed optimization
- Convergence and convergence rate of stochastic gradient search in the case of multiple and non-isolated extrema
- Stochastic optimization with adaptive restart: a framework for integrated local and global learning
- Local-maximum-and-minimum-preserving solution remapping technique to accelerate flow convergence for discontinuous Galerkin methods in shape optimization design
- An accelerated directional derivative method for smooth stochastic convex optimization
- Stochastic approximation: from statistical origin to big-data, multidisciplinary applications
- Revisiting the ODE method for recursive algorithms: fast convergence using quasi stochastic approximation
- A genetic algorithm with a self-reproduction operator to solve systems of nonlinear equations
- Pure random search with virtual extension of feasible region
- From reinforcement learning to optimal control: a unified framework for sequential decisions
- \texttt{CAMERA}: a method for cost-aware, adaptive, multifidelity, efficient reliability analysis
- Self-guided quantum state learning for mixed states
- Computation for latent variable model estimation: a unified stochastic proximal framework
- Noisy zeroth-order optimization for non-smooth saddle point problems
- Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference
- Multilevel estimation of normalization constants using ensemble Kalman-Bucy filters
- Combined sensitivity analysis for multiple failure modes
- A theoretical and empirical comparison of gradient approximations in derivative-free optimization
- Improved exploitation of higher order smoothness in derivative-free optimization
- Zeroth-order methods for noisy Hölder-gradient functions
- Enhance chaotic gravitational search algorithm (CGSA) by balance adjustment mechanism and sine randomness function for continuous optimization problems
- The method of averaged models for discrete-time adaptive systems
- Remarks about discrete Young measures and their Monte Carlo simulation
- Conditionally structured variational Gaussian approximation with importance weights
- Entropy-based closure for probabilistic learning on manifolds
- Strong averaging principle for two-time-scale stochastic McKean-Vlasov equations
- Simulation-based optimization. Parametric optimization techniques and reinforcement learning
- A simulation-optimization approach for integrated sourcing and inventory decisions
- Research on probabilistic methods for control system design
- Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants
- A multi-strategy enhanced sine cosine algorithm for global optimization and constrained practical engineering problems
- Accelerated gradient-free optimization methods with a non-Euclidean proximal operator
- The time buffer approximated buffer allocation problem: a row-column generation approach
- Conditionally conjugate mean-field variational Bayes for logistic models
- A transport-based multifidelity preconditioner for Markov chain Monte Carlo
- Sequential approximate optimization for design under uncertainty problems utilizing Kriging metamodeling in augmented input space
- Optimal design of measurements on queueing systems
- Nonmonotone line search methods with variable sample size
- An information guided framework for simulated annealing
- Spatial interaction models with individual-level data for explaining labor flows and developing local labor markets
- On sample size control in sample average approximations for solving smooth stochastic programs
- An overview of the design and analysis of simulation experiments for sensitivity analysis
- A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions
- Complex-step derivative approximation in noisy environment
- A stochastic adaptive radial basis function algorithm for costly black-box optimization
- A solution to the weak instrument bias in 2SLS estimation: indirect inference with stochastic approximation
- Stochastic global optimization.
- Convergence properties of the cross-entropy method for discrete optimization
- Design selection criteria for discrimination/estimation for nested models and a binomial re\-sponse
- Almost sure convergence of stochastic gradient processes with matrix step sizes
- A stochastic quasi-Newton method for simulation response optimization
- Optimization and analysis aid via data-mining for simulated production systems
- Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms
- On the construction and analysis of stochastic models: characterization and propagation of the errors associated with limited data
- Simulation-based optimization of process control policies for inventory management in supply chains
- Estimating a semi-parametric duration model without specifying heterogeneity
- Gradient free parameter estimation for hidden Markov models with intractable likelihoods
- Broadcast control of multi-agent systems
This page was built for publication: Introduction to Stochastic Search and Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4417313)
