Randomized Models for Nonlinear Optimization: Theoretical Foundations and Practical Numerical Methods

该项目涉及大型复杂系统数学优化的数值算法的设计、分析和实现。 特别地，所提出的算法的新颖特征是在求解确定性（即，非随机）问题。 尽管随机化成功，例如，虽然随机梯度技术用于机器学习，但它尚未在其他设置中积极使用，因为它在顺序计算环境中被认为过于昂贵。 然而，随着并行计算变得越来越普遍，以及随机算法的新进展和收敛理论，这些方法有很大的希望。 本项目的研究将侧重于使用“准确”的随机模型，扩大收敛理论，并实施有效的软件。 该方法的新奇在于，通过利用仅需要以足够高的概率准确的随机模型，在每个算法步骤都必须准确的确定性模型和仅在预期中准确的随机模型之间实现中间地带。所提出的策略将平衡每次迭代的优化例程的成本与收敛速度，同时利用并行计算。 该项目的优先事项是开发基于理论上合理的方法论的实用、通用数值方法，这巩固了拟议工作的优点。该项目的重点是开发新型数值算法及其分析，以解决工程设计两个相关领域的问题。 在第一种情况下，目标是使数量最小化，例如，成本、能源或预期数据和观测数据之间的差异-这些只能通过计算机模拟来确定。这些“黑箱”优化问题出现在分子几何优化，电路设计和地下水建模等重要领域。 第二个领域代表那些应用，其中给定的设计需要在各种输入条件下具有鲁棒性，这包括以下方面的问题，例如，医学图像配准和控制系统的优化。 该项目承诺通过利用随机化和并行计算的共同思路来推进解决所有这些类型问题的算法研究。这项工作的影响显然是跨学科的，将使学术界、政府研究实验室和私营企业的优化方法和软件用户受益。 它还将促进使用严格的经典算法与随机模型相结合来解决前沿科学问题。最后，教育计划将使本科生和研究生接触计算数学领域的现代努力和挑战，改善对科学感兴趣的学生的教育机会研究，并鼓励教师在地区学校互动。

This project involves the design, analysis, and implementation of numerical algorithms for the mathematical optimization of large-scale, complex systems. In particular, the novel feature of the proposed algorithms is the use of random sampling of objective function information in the context of solving deterministic (i.e., non-random) problems. Despite the success of randomization in, e.g., stochastic gradient techniques for machine learning, it has yet to be used actively in other settings as it has been deemed too expensive in sequential computing environments. However, with parallel computing becoming increasingly common, and with new advancements and convergence theory for randomized algorithms, these methods have great promise. The research in this project will focus on the use of ``accurate'' randomized models, broadening of convergence theory, and implementation of effective software. The novelty of the approach lies in achieving a middle ground between deterministic models that have to be accurate at each algorithmic step, and stochastic models that are accurate only in expectation, by exploiting random models that need to be accurate only with sufficiently high probability. The proposed strategies will balance per-iteration cost of the optimization routine with convergence speed while utilizing parallel computation. The priority in the project on developing practical, general-purpose numerical methods based on theoretically sound methodologies solidifies the merits of the proposed work.This project focuses on the development of novel numerical algorithms, and their analysis, for solving problems in two related realms of engineering design. In the first, the aim is to minimize a quantity---e.g., cost, energy, or the discrepancy between expected and observed data---that can only be determined via a computer simulation. These "black-box" optimization problems arise in important areas such as molecular geometry optimization, circuit design, and groundwater modeling. The second area represents those applications in which a given design needs to be robust under various input conditions, which includes problems in, e.g., medical image registration and the optimization of control systems. The project promises to advance the study of algorithms for solving all of these types of problems via the common thread of exploiting randomization and parallel computation.The impact of this work will clearly be cross-disciplinary, and will benefit users of optimization methods and software in academia, governmental research laboratories, and private industry. It will also promote the use of rigorous, classical algorithms in combination with randomized models for solving cutting-edge scientific problems.Finally, the educational plan will expose undergraduate and graduate students to modern efforts and challenges in computational mathematics, improve the educational opportunities for students interested in scientific research, and encourage faculty interaction in area schools.