Single Observation Simulation Optimization

University Of Washington, Seattle WA

Investigators

Abstract

Many systems in diverse areas, spanning engineering, economics, computer science, business and biological science, rely on optimizing the performance of the system to choose design or decision variables. In these complex systems, the system performance is typically observed numerically by running a computer discrete-event simulation many times to both estimate the performance of the system and explore the design space to determine the optimal values of the variables. Striking a balance between exploration of new points and estimation of potentially good points is critical for computationally efficient algorithms. Ideally one would perform exactly one simulation per design point, or single observation simulation optimization. This award supports fundamental research in proving that it is possible to estimate the objective function at a point by averaging observed values from nearby points. The research will lead to new algorithms with theoretical foundations that potentially change the way a diverse set of users make system-wide decisions. The PIs are committed to fostering diversity and will recruit and mentor underrepresented groups, and participate in the Women in Science and Engineering program and the summer Minority Scholars Engineering Program at the University of Washington. The idea of simulating a single observation per design has roots in classic stochastic approximation algorithms, although their convergence proofs were to a local optimum. Since we do not presume that the objective function for a simulated system is convex, we seek a global optimum. Previous research introduced the idea of estimating the objective function at a specific design point using other designs within shrinking balls around it, thus never repeating a simulation at a design vector. However, the analysis assumed that the optimization algorithm generated independently sampled random points, thus avoiding dependencies among errors. However, the computational performance of such non-adaptive algorithms is known to scale badly (e.g., exponentially) in terms of the dimension of the problem. If successful, this award will help create a class of adaptive random search algorithms that converge to a global optimum in probability using a single observation per candidate point. The challenge is in accounting for the complex dependencies and their influence in exploring new candidates. By eliminating inherent biases in adaptive algorithms, the new methodology will contribute to intellectual merit by integrating optimization and simulation for convergent global algorithms with theoretical foundations. By decreasing computational effort, a broad range of applications will benefit by being able to optimize system performance.