Single Observation Simulation Optimization

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

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.