Single Observation Simulation Optimization

不同领域的许多系统，包括工程、经济学、计算机科学、商业和生物科学，都依赖于优化系统的性能来选择设计或决策变量。在这些复杂系统中，通常通过多次运行计算机离散事件模拟来数值观察系统性能，以估计系统性能并探索设计空间以确定变量的最佳值。在探索新点和估计潜在的好点之间取得平衡对于计算效率的算法至关重要。理想情况下，每个设计点只执行一次模拟，或者单个观察模拟优化。该奖项支持基础研究，证明可以通过对附近点的观测值取平均值来估计某一点上的目标函数。这项研究将产生具有理论基础的新算法，有可能改变不同用户做出全系统决策的方式。这些学院致力于促进多样性，将招募和指导代表性不足的群体，并参加华盛顿大学的“女性参与科学与工程项目”和“少数族裔学者暑期工程项目”。模拟每个设计的单个观察的想法源于经典的随机逼近算法，尽管它们的收敛证明是局部最优的。因为我们不假设模拟系统的目标函数是凸的，所以我们寻求全局最优。先前的研究引入了在特定设计点使用周围收缩球内的其他设计来估计目标函数的思想，因此不会在设计向量上重复模拟。然而，分析假设优化算法产生独立采样的随机点，从而避免了误差之间的依赖关系。然而，就问题的维度而言，这种非自适应算法的计算性能被认为是糟糕的（例如，指数级）。如果成功，该奖项将有助于创建一类自适应随机搜索算法，该算法使用每个候选点的单个观察，在概率上收敛到全局最优。挑战在于考虑复杂的依赖关系及其对探索新候选对象的影响。通过消除自适应算法的固有偏差，新方法将收敛全局算法的优化和仿真与理论基础相结合，从而为智力贡献价值。通过减少计算工作量，广泛的应用程序将受益于能够优化系统性能。

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.