Global optimization using nonparametric statistics
C.D. Perttunen · 1991
Some successful global optimization methods have been developed which model the unknown objective function as a random process. However, the performance of many of these methods depends on the selection of search parameters. This dissertation proposes a nonparametric approach to constrained global optimization. A one-dimensional nonparametric global optimization method based on a rank-transformed Brownian motion process (Wiener process) is developed. One-step and multistep methods of selecting the search parameter are formulated. A second nonparametric method, based on a normal-score transformed Brownian motion process, is also developed. The introduction of a nonparametric transformation is shown to make the resulting search unaffected by any monotonic transformation of the objective function. The univariate global optimization method based on the rank transformation is applied to the engineering problem of surface estimation in automated visual inspection. An n-dimensional extension of the one-dimensional methods is developed using a simplex-based approach. Delaunay triangulations are employed for a dynamic division of the feasible region into simplices. The performance of the n-dimensional method is compared to other methods using a standard set of test functions. The new n-dimensional method is shown to converge to within 1% error in less iterations than the other Bayesian/sampling methods considered in this dissertation. A nonparametric statistical approach is applied to an existing multi-univariate method of global optimization. This application is shown to decrease the number of evaluations needed for convergence within a specified tolerance for the standard set of test functions. The use of alternate stochastic models in conjunction with Kushner's criterion is investigated. The stochastic models considered are the Ornstein-Uhlenbeck process, Brownian motion with drift, geometric Brownian motion, fractional Brownian motion, and reflected Brownian motion. Similarly, the use of other search strategies with the Brownian motion model is investigated. The search strategies considered are the Bayesian criterion, a modified Kushner criterion, maximum likelihood, interval with maximum probability of reduction, and interval with maximum median reduction. Finally, the joint distribution of ranked samples of a Brownian motion process is derived.