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

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

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.