25-10-2012, 05:11 PM
Pattern Search Ranking and Selection Algorithms for Mixed-Variable Optimization of Stochastic Systems
ABSTRACT
A new class of algorithms is introduced and analyzed for bound and linearly constrained optimization problems with
stochastic objective functions and a mixture of design variable types. The generalized pattern search (GPS) class of algorithms
is extended to a new problem setting in which objective function evaluations require sampling from a model of a stochastic
system. The approach combines GPS with ranking and selection (R&S) statistical procedures to select new iterates. The
derivative-free algorithms require only black-box simulation responses and are applicable over domains with mixed variables
(continuous, discrete numeric, and discrete categorical) to include bound and linear constraints on the continuous variables.
A convergence analysis for the general class of algorithms establishes almost sure convergence of an iteration subsequence
to stationary points appropriately defined in the mixed-variable domain. Additionally, specific algorithm instances are
implemented that provide computational enhancements to the basic algorithm. Implementation alternatives include the use
modern R&S procedures designed to provide efficient sampling strategies and the use of surrogate functions that augment the
search by approximating the unknown objective function with nonparametric response surfaces. In a computational evaluation,
six variants of the algorithm are tested along with four competing methods on 26 standardized test problems. The numerical
results validate the use of advanced implementations as a means to improve algorithm performance.