Pattern search ranking and selection algorithms for mixed variabl

Air Force Institute of Technology AFIT Scholar Theses and Dissertations Student Graduate Works 9-2004 Pattern Search Ranking and Selection Algorithms for Mixed- Variable Optimization of Stochastic Systems Todd A. Sriver Follow this and additional works at: https://scholar.edu/etd Part of the Theory and Algorithms Commons Recommended Citation Sriver, Todd A., "Pattern Search Ranking and Selection Algorithms for Mixed-Variable Optimization of Stochastic Systems" (2004). Theses and Dissertations.edu/etd/3903 This Dissertation is brought to you for free and open access by the Student Graduate Works at AFIT Scholar. It has been accepted for inclusion in Theses and Dissertations by an authorized administrator of AFIT Scholar.

For more information, please contact richard. Pattern Search Ranking and Selection Algorithms for Mixed-Variable Optimization of Stochastic Systems DISSERTATION Todd A. Major, USAF AFIT/DS/ENS/04-02 DEPARTMENT OF THE AIR FORCE AIR UNIVERSITY AIR FORCE INSTITUTE OF TECHNOLOGY Wright-Patterson Air Force Base, Ohio Approved for public release; distribution unlimited The views expressed in this dissertation are those of the author and do not reflect the official policy or position of the United States Air Force, the Department of Defense, or the United States Government. AFIT/DS/ENS/04-02 Pattern Search Ranking and Selection Algorithms for Mixed-Variable Optimization of Stochastic Systems DISSERTATION Presented to the Faculty of the Graduate School of Engineering and Management Air Force Institute of Technology Air University In Partial Fulfillment for the Degree of Doctor of Philosophy Specialization in: Operations Research Todd A.

Major, USAF September, 2004 Sponsored by the Air Force Office of Scientific Research Approved for public release; distribution unlimited AFIT/DS/ENS/04-02 Abstract A new class of algorithms is introduced and analyzed for bound and linearly con- strained 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 (con- tinuous, 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 appro- priately defined in the mixed-variable domain. Additionally, specific algorithm instances are implemented that provide computational enhancements to the basic algorithm. Im- plementation alternatives include the use of 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 com- peting methods on 26 standardized test problems.

The numerical results validate the use of advanced implementations as a means to improve algorithm performance. iv Acknowledgments I express my heartfelt gratitude to many individuals who directly or indirectly sup- ported me in the challenging, but rewarding, endeavor of completing a Ph. I begin with the most important person — my wife — whose strength and encouragement were essential to my success. I am also grateful for our three children (who make me very proud) for the ability to make me smile during those times when the road ahead seemed difficult.

I owe a deep thanks my research advisor, Professor Jim Chrissis. His expertise, guid- ance, and friendship kept me on the right track while enabling me to enjoy the ride. I am also grateful to the remainder of my research committee, Lt Col Mark Abramson, Professor Dick Deckro, and Professor J. Miller for all of the positive support they provided me.

In particular, Lt Col Abramson’s help on some of the more theoretical issues was crucial to the development of the material presented in Chapter 3. I also thank the Air Force Office of Scientific Research for sponsoring my work. I would be negligent if I did not acknowledge my friends and colleagues in the B. The synergy amongst the Ph.

students in that small building led to some novel ideas incorporated in my research (Major Trevor Laine gets credit for introducing me to kernel regression); but, perhaps more importantly, the moments of levity kept things in the proper perspective. Finally, I offer a special thanks to both my mother and father. Their love and guidance throughout my life has inspired me to seek achievement. Sriver v Table of Contents Page Abstract.

v List of Figures. x List of Tables .2 Purpose of the Research .1 Methods for Stochastic Optimization .3 Ranking and Selection .5 Response Surface Methods .7 Summary of Methods .2 Generalized Pattern Search .1 Pattern Search for Continuous Variables .2 Pattern Search for Mixed Variables .3 Pattern Search for Random Response Functions. ALGORITHMIC FRAMEWORK AND CONVERGENCE THEORY .2 Positive Spanning Sets and Mesh Construction .3 Bound and Linear Constraint Handling .4 The MGPS Algorithm for Deterministic Optimization .5 Iterate Selection for Noisy Response Functions .6 The MGPS-RS Algorithm for Stochastic Optimization .1 Controlling Incorrect Selections .2 Mesh Size Behavior .1 Specific Ranking and Selection (R&S) Procedures .2 Use of Surrogate Models .1 Building the Surrogate During Initialization .2 Algorithm Search Steps and Termination .1 Continuous-Variable Problems .2 Mixed-Variable Problems .1 Performance Measures and Statistical Model .2 Selection of Parameter Settings .5 Results and Analysis .1 Analysis of MGPS-RS Variant Implementations .2 Comparative Analysis of All Algorithm Implementations .3 Termination Criteria Analysis .4 Summary of the Analysis. 140 viii Page Chapter 6.

CONCLUSIONS AND RECOMMENDATIONS .1 Modifications to Existing Search Framework .2 Extensions to Broader Problem Classes. TEST PROBLEM DETAILS. TEST RESULT DATA .1 Iteration History Charts .2 Statistical Analysis Data Summary. 235 ix List of Figures Figure Page 1.1 Model for Stochastic Optimization via Simulation .1 Robbins-Monro Algorithm for Stochastic Optimization (adapted from [10]) .2 General Random Search Algorithm (adapted from [11]) .3 Nelder-Mead Search (adapted from [141]) .1 Directions that conform to the boundary of Θc (from [81]) .2 MGPS Algorithm for Deterministic Optimization (adapted from [1]) .4 MGPS-RS Algorithm for Stochastic Optimization .5 Example Test Function.6 Asymptotic behavior of MGPS-RS, shown after 2 million response samples.1 Rinott Selection Procedure (adapted from [27]) .2 Combined Screening and Selection (SAS) Procedure (adapted from [99]) .3 Sequential Selection with Memory (adapted from [109]) .4 Smoothing effect of various bandwidth settings for fitting a surface to eight design sites in one dimension.5 Examples of Latin Hypercube Samples of Strengths 1 and 2 for p = 5.6 Demonstration of the surrogate building process during MGPS-RS algorithm execution.7 Growth of response samples required per Rinott R&S procedure for a fixed response variance of S 2 = 1.8 Growth in response samples for Rinott’s R&S procedure as α decreases for fixed ratio Sδ = 1.9 Algorithm flow chart for MGPS-RS using surrogates.10 MGPS-RS Algorithm using Surrogates for Stochastic Optimization .11 Algorithm for Generating Conforming Directions (adapted from [1] and [81]).1 Illustration of Corrective Move Method for Infeasible Iterates Used in SA Algorithms.2 Random Search Algorithm Used in Computational Evaluation .3 Mixed-variable Test Problem Illustration for nc = 2.

117 xi List of Tables Table Page 3.1 MGPS-RS Average Performance for Noise Case 1 over 20 Replications.2 MGPS-RS Average Performance for Noise Case 2 over 20 Replications.1 Summary of MGPS-RS parameters.1 Continuous-Variable Test Problem Properties.2 Mixed-variable Test Problems.3 Parameter Settings for All Algorithms — Continuous-variable Problems.4 Summary of “Tunable” Parameter Settings for all Algorithms — Continuous-variable Problems.5 Parameter Settings for MGPS-RS and RNDS Algorithms — Mixed-variable Problems.6 Significance Tests of Main Effects for Performance Measures Q and P — Continuous-variable Test Problems .7 Significance Tests of Main Effects for Performance Measures Q and P — Mixed-variable Test Problems.8 Terminal Value for Performance Measure Q Averaged over 60 Replications (30 for each noise case) — MGPS-RS Algorithms.9 Terminal Value for Performance Measure P Averaged over 60 Replications (30 for each noise case) — MGPS-RS Algorithms.10 Number of Switches SW at Termination Averaged over 60 Replications (30 for each noise case) — MGPS-RS Algorithms. 132 xii Table Page 5.11 Terminal Value for Performance Measure Q Averaged over 60 Replications (30 for each noise case) — FDSA, SPSA, RNDS, NM, and Best MGPS-RS Algorithms.12 Terminal Value for Performance Measure P Averaged over 60 Replications (30 for each noise case) — FDSA, SPSA, RNDS, NM, and Best MGPS-RS Algorithms.13 Termination Criteria Analysis for S-MGPS-RIN — Noise Case 1.14 Termination Criteria Analysis for S-MGPS-RIN — Noise Case 2.1 Transformation functions and Shapiro-Wilk Nonnormality Test Results.2 P-values for Nonparametric Tests — Performance Measure Q.3 P-values for Nonparametric Tests — Performance Measure P. 195 xiii Pattern Search Ranking and Selection Algorithms for Mixed-Variable Optimization of Stochastic Systems Chapter 1 - Introduction 1.1 Problem Setting Consider the optimization of a stochastic system in which the objective is to find a set of controllable system parameters that minimize some performance measure of the system. This situation is representative of many real-world optimization problems in which random noise is present in the evaluation of the objective function.

In many cases, the system is of sufficient complexity so that the objective function, representing the performance measure of interest, cannot be formulated analytically and must be evaluated via a representative model of the system. In particular, the use of simulation is emphasized as a means of characterizing and analyzing system performance. The term simulation is used in a generic sense to indicate a numerical procedure that takes as input a set of controllable system parameters (design variables) and generates as output a response for the measure of interest. It is assumed that the variance of this measure can be reduced at the expense of additional computational effort, e., repeated sampling from the simulation.

Applications involve the optimization of system designs where the systems under analy- sis are represented as simulation models, such as those used to model manufacturing sys- tems, production-inventory situations, communication or other infrastructure networks, lo- gistics support systems, or airline operations. In these situations, a search methodology is used to drive the search for the combination of values of the design variables that optimize a system measure of performance. A model of such a stochastic optimization methodology via simulation is depicted in Figure 1. Vector of design variable values Initial guess, Parameter Optimization ⎡ X1 ⎤ settings Routine X = ⎢⎢ M ⎥⎥ ⎢⎣ X n ⎥⎦ Stochastic Prescribes improved Simulation vector via search technique {Fi ( X)}is=1 “Black-box” system response samples Figure 1.

Model for Stochastic Optimization via Simulation The random performance measure may be modeled as an unknown response function F (x, ω) which depends upon an n-dimensional vector of controllable design variables x ∈ Rn , and the vector ω, which represents random effects inherent to the system. The objective function f of the optimization problem is the expected performance of the system, given by f(x) = EP [F (x, ω)] = F (x, ω)P (dω), (1.1) Ω where ω ∈ Ω can be considered an element of an underlying probability space (Ω, F, P ) with sample space Ω, sigma-field F, and probability measure P. It is assumed that the probability distribution that defines the response F (x, ω) is unknown but can be sampled. Even for noise-free system responses obtained via simulation, finding optimal solutions using traditional optimization approaches can be difficult since the structure of f is un- known, analytical derivatives are unavailable, and numerical evaluation of f may involve 2 expensive simulation runs.

The presence of random variation further complicates matters because f cannot be evaluated exactly and derivative approximating techniques, such as finite differencing, become problematic. Estimating f requires the aggregation of repeated samples of the response F , making it difficult to determine conclusively if one design is better than another and further hindering search methods that explicitly rely on directions of improvement.