Collaborative Research: Large-scale Optimization: Matrix-free Algorithms, Data Parallelism, and Applications in Seismic Inversion

合作研究：大规模优化：无矩阵算法、数据并行性及其在地震反演中的应用

• 批准号: 9973310
• 负责人: Anthony Kearsley
• 金额: $ 5.85万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-01 至 2002-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9973310&HistoricalAwards=false
• 关键词: Collaborative; Research; Large; scale; Optimization

In this collaborative interdisciplinary project, theinvestigators Mark Gockenbach, Anthony Kearsley, and WilliamSymes develop and implement algorithms for large-scaleoptimization problems that arise in a variety of applications,focusing on techniques particularly suited to parallelarchitectures, and apply the methods to the seismic velocityestimation problem. Large-scale optimization problems oftenpresent difficulties to standard algorithms and software. Manyof these difficulties arise in the seismic velocity estimationproblem. First, the sheer data volume makes it impractical toexplicitly form and factor matrices, as required by many standardoptimization algorithms. To address this, a new matrix-freeSequential Quadratic Programming (SQP) algorithm is developed,based on recent advances in matrix-free algorithms for theso-called trust region subproblem. Second, the data structuresand interfaces required for seismic data processing are noteasily adapted to those required by "off-the-shelf" optimizationsoftware. The Hilbert Class Library (HCL), an object-orientedoptimization package, can solve optimization problems involvingdata structures and interfaces of arbitrary complexity. The SQPalgorithm, along with the necessary seismic data structures andsimulators, is implemented in HCL. Third, large-scalesimulations often require the use of parallel computation. Theuse of parallelism in simulation and optimization is addressedthrough the development of HCL classes that automaticallydistribute data over a network of distributed workstations. Theabove innovations in optimization methods and software are usedto study in detail a new formulation of the seismic inverseproblem. The investigators have recently introduced thisformulation in order to overcome certain optimization-theoreticdifficulties inherent in standard formulations. Optimization problems arise in science and engineering,where one often wishes to find the best design, the bestmathematical model, the best strategy, and so forth. Large-scaleoptimization problems, which involve many variables, presentspecial challenges, including the choice of algorithm, therepresentation of data, and the interface between optimizationsoftware and programs written by the application scientist. Thisproject addresses these challenges in the context of an importantapplication, seismic exploration. The investigator and hiscolleagues develop new optimization algorithms to identifygeological features of the subsurface of the earth. Included isa general method for solving large-scale optimization problems;this algorithm is applicable to other science and engineeringproblems. Moreover, they also develop an innovative softwarepackage, called the Hilbert Class Library (HCL), that allowsoptimization algorithms to be used with problems of arbitrarycomplexity; the software adapts to different data structures andsoftware interfaces. Finally, they extend HCL to automaticallytake advantage of parallel computers, making it easier to takeadvantage of high performance hardware. The seismic explorationproblem is important to the petroleum industry; a preciseknowledge of geological structures is essential for efficientutilization of petroleum reserves. In addition, the HCL softwareaddresses the important issue of technology transfer as itpertains to numerical algorithms; too often algorithmic advancesare unavailable to application scientists because optimizationsoftware and application software have incompatible interfaces.

在这个跨学科的合作项目中，研究人员Mark Gockenbach，Anthony Kearsley和WilliamSymes开发并实现了各种应用中出现的大规模优化问题的算法，专注于特别适合并行架构的技术，并将这些方法应用于地震速度估计问题。 大规模的优化问题通常给标准算法和软件带来困难。 许多这些困难出现在地震速度估计问题。 首先，庞大的数据量使得显式地形成和分解矩阵变得不切实际，而这正是许多标准优化算法所要求的。 为了解决这个问题，一个新的无矩阵序列二次规划（SQP）算法的基础上，最近的进展无矩阵算法的所谓的信赖域子问题。 第二，地震数据处理所需的数据结构和接口很难适应“现成的”优化软件所需的数据结构和接口。 Hilbert类库（HCL）是一个面向对象的优化软件包，可以解决涉及任意复杂数据结构和接口的优化问题。 SQP算法沿着必要的地震数据结构和模拟器在HCL中实现。 第三，大规模的模拟通常需要使用并行计算。 在模拟和优化中使用并行性是通过开发HCL类来解决的，HCL类可以在分布式工作站网络上自动分发数据。 利用上述优化方法和软件的创新，详细研究了一种新的地震反演问题。 研究人员最近介绍了这个配方，以克服某些优化理论的困难，固有的标准配方。 优化问题出现在科学和工程中，人们常常希望找到最佳设计、最佳数学模型、最佳策略等等。 大规模的优化问题，其中涉及到许多变量，presentspecial挑战，包括算法的选择，representation的数据，和优化软件和应用科学家编写的程序之间的接口。 这个项目解决了这些挑战的背景下，一个重要的应用，地震勘探。 研究人员和他的同事开发了新的优化算法来识别地球地下的地质特征。 包括伊萨个求解大规模优化问题的一般方法，该算法适用于其他科学和工程问题。 此外，他们还开发了一个创新的软件包，称为希尔伯特类库（HCL），允许优化算法用于任意复杂性的问题;该软件适应不同的数据结构和软件接口。 最后，他们扩展了HCL以自动利用并行计算机，使其更容易利用高性能硬件。 地震勘探问题对石油工业很重要，精确地了解地质构造对有效地利用石油储量是必不可少的。 此外，HCL软件解决了技术转让的重要问题，因为它涉及到数值算法;由于优化软件和应用软件的接口不兼容，应用科学家往往无法获得算法的进步。