New model-based methods for non-differentiable optimization

simulation-based optimization;stochastic search;model-based methods

Chen, Xi

关键词: simulation-based optimization;    stochastic search;    model-based methods;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/78366/CHEN-DISSERTATION-2015.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Model-based optimization methods are effective for solving optimization problems with little structure, such as convexity and differentiability. Such algorithms iteratively find candidate solutions by generating samples from a parameterized probabilistic model on the solution space, and update the parameter of the probabilistic model based on the objective function evaluations. This dissertation explores new model-based optimization methods, and mainly consists of three topics.The first topic of the dissertation proposes two new model-based algorithms for discrete optimization, discrete gradient-based adaptive stochastic search (discrete-GASS) and annealing gradient-based adaptive stochastic search (annealing-GASS), under the framework of gradient-based adaptive stochastic search (GASS), where the parameter of the probabilistic model is updated based on a direct gradient method. The first algorithm, discrete-GASS, converts the discrete optimization problem to a continuous problem on the parameter space of a family of independent discrete distributions, and applies a gradient-based method to find the optimal parameter such that the corresponding distribution has the best capability to generate optimal solution(s) to the original discrete problem. The second algorithm, annealing-GASS, uses Boltzmann distribution as the parameterized probabilistic model, and derives a gradient-based temperature schedule, which changes adaptively with respect to the current performance of the algorithm, for updating the Boltzmann distribution. We prove the convergence of the two proposed methods, and conduct numerical experiments to compare these two methods as well as some other existing methods.The second topic of the dissertation proposes a framework of population model-based optimization (PMO) in order to better capture the multi-modality of the objective functions than the traditional model-based methods which use only a single model at every iteration. This PMO framework uses a population of models at every iteration with an adaptive mechanism to propagate the population over iterations. The adaptive mechanism is derived from estimating the optimal parameter of the probabilistic model in a Bayesian manner, and thus provides a proper way to determine the diversity in the population of the models. We provide theoretical justification on the convergence of this framework by showing that the posterior distribution of the parameter asymptotically converges to a degenerate distribution concentrating on the optimal parameter. Under this framework, we develop two practical algorithms by incorporating sequential Monte Carlo methods, and carry out numerical experiments to illustrate their performance.The last topic of the dissertation considers simulation optimization, where the objective function cannot be evaluated exactly and must be estimated by stochastic simulation. The idea of model-based methods for deterministic optimization is extended to stochastic optimization. We propose two algorithms: approximate Bayesian computation simulation optimization (ABC-SO) and its extension approximate Bayesian computation simulation optimization with multiple function evaluations (ABCM-SO). These algorithms view the simulation optimization problem as an estimation problem, and use the approximate Bayesian computation (ABC) technique to estimate the optimal solution. We carry out numerical experiments of the proposed algorithms, and compare them with gradient-based adaptive stochastic search for simulation optimization (GASSO), and cross-entropy method with optimal computing budget allocation (CE-OCBA).