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

非线性优化的随机模型：理论基础和实用数值方法

• 批准号: 1319356
• 负责人: Katya Scheinberg
• 金额: $ 20万
• 依托单位: Lehigh University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-15 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319356&HistoricalAwards=false
• 关键词: Randomized; Models; Nonlinear; Optimization; Theoretical

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.

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