Stochastic search methods for large -scale optimization.
Stephen Baumert · Deep Blue (University of Michigan) · 2004
This dissertation considers several common notions of complexity that arise in large-scale systems optimization; namely, noisy objective functions, difficult to fathom feasible regions and high dimensional problems with highly interdependent decision variables. While deterministic optimization methods for such problem classes is either not possible or impractical, we develop novel stochastic search algorithmic frameworks to address each of these challenging notions of complexity. We lend support to each of these techniques in theory and in practice. For the optimization of noisy objective functions (e.g. simulation optimization), we consider a new method of estimation that requires only samples of size one from the objective function. This method, called estimating shrinking balls, approximates the objective function at a point by averaging the observed samples of the objective function within a small ball around the point. For the simplest of stochastic search algorithms, Pure Random Search, we provide a sufficient rate to shrink the ball so that the algorithm converges to an optimum in probability. For optimization problems on difficult to fathom feasible regions on finite state spaces, we propose a new Markov chain sampler called Discrete Hit-and-Run which makes global moves over the state space. Under weak conditions on the objective function, for a fixed temperature, a Metropolis version of this algorithm converges to the Boltzmann distribution in variational distance in polynomial order O(n 4 ), where n is the dimension of the problem. We apply this method to a problem in spot welding pattern optimization. For problems with a large state space and highly interdependent variables, such as large scale dynamic programming, we consider a framework for using a behavioral paradigm for optimization called Sampled Fictitious Play. We illustrate an application of this framework through a proof of concept production systems problem for the joint optimization of capital investment, revenue management and production scheduling.