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

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

• 批准号: 9973308
• 负责人: Mark Gockenbach
• 金额: $ 8.29万
• 依托单位: Michigan Technological University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-01 至 2002-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9973308&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)算法。其次，地震数据处理所需的数据结构和接口明显地适应了“现成”优化软件所需的结构和接口。希尔伯特类库是一个面向对象的优化程序包，可以解决涉及任意复杂数据结构和接口的优化问题。SQP算法以及必要的地震数据结构和模拟器是在HCL中实现的。第三，大规模模拟通常需要使用并行计算。并行在模拟和优化中的使用是通过开发HCL类来解决的，这些类自动地在分布式工作站网络上分发数据。利用上述优化方法和软件的创新之处，详细研究了地震反问题的新提法。研究人员最近引入了这种配方，以克服标准配方中固有的某些最优化理论困难。最优化问题出现在科学和工程中，人们经常希望找到最好的设计、最好的数学模型、最好的策略等等。大规模优化问题涉及许多变量，提出了特殊的挑战，包括算法的选择、数据的表示以及优化软件与应用科学家编写的程序之间的接口。该项目在地震勘探这一重要应用的背景下解决了这些挑战。这位研究人员和他的同事开发了新的优化算法来识别地球地下的地质特征。这是一种解决大规模优化问题的通用方法，该算法也适用于其他科学和工程问题。此外，他们还开发了一个创新的软件包，称为希尔伯特类库(HCL)，允许使用优化算法来处理任意复杂的问题；该软件适应不同的数据结构和软件接口。最后，它们扩展了HCL以自动利用并行计算机的优势，使其更容易利用高性能硬件的优势。地震勘探问题对石油工业十分重要，对地质构造的准确认识对石油储量的有效利用至关重要。此外，HCL软件解决了与数值算法有关的技术转让的重要问题；由于优化软件和应用软件的接口不兼容，应用科学家往往无法获得算法方面的进步。