Matrix-Free Methods for Optimization and Linear Systems

这个NSERC提案的主要主题是为大型应用程序设计计算效率高的优化方法。优化是指在满足一定数量的期望属性的所有候选解决方案中确定一个问题的“最佳”（在特定应用的意义上）解决方案。 在实际的大规模光滑优化中的一个挑战是求解线性方程组，其目的是计算改进的猜测。这些系统通常很大，有时有数百万个方程和未知数，但结构非常复杂。它们的特定结构，对称性和准定性（SQD），必须利用计算效率。典型的实现可能会因为不利用结构和问题大小而挑战内存约束。本提案的主题围绕设计高效的方法，利用特定的线性系统结构中遇到的应用，如空气动力学设计，天气预报，流体流动模拟或控制，稀疏信号重建。 我开发了四种定制的迭代方法，它们充分利用了SQD结构，并可证明执行了标准方法的一半工作。每个家庭都有自己的长处和短处，可能并不适合所有情况。初步实验表明，将这些方法应用到最先进的优化求解器中，可以产生有效的实现，每一步都利用结构。另一方面，现实生活中的应用，如数据同化，用于天气预报，需要某些属性进行验证，在解决方案的过程中。反过来，这种需求要求特定的有效方法来解决线性系统。 我还建议建立某些国家的最先进的优化框架产生的系统与SQD结构，虽然这一事实并不立即明显。除了解释性的贡献，好处是，定制的数值方法的SQD线性系统现在可以有利地使用在这些框架内，产生更直观，独立，强大和强大的实施。 此外，具有SQD结构的系统可以用于加速某些问题的解决，其中系统具有与SQD结构足够相似的结构。在某些流体流动问题和最先进的优化方法中就是这种情况。 本提案的最后一个主题涉及所谓的最小二乘问题，它出现在大类的应用程序，如稀疏信号重建和数据同化。SQD结构和最小二乘问题之间存在着很强的联系，这反过来又表明了自然和强大的数值方法。最小二乘问题在实践中的压倒性发生是这样的，改进的数值方法可以对图像处理，信号重建，天气预报模型，医学成像，地震数据采集和许多其他领域产生巨大的影响。

The main topic of this NSERC proposal is the design of computationally-efficient optimization methods for large classes of applications. Optimization is concerned with the identification of a "best" (in an application-specific sense) solution to a problem among all candidate solutions satisfying a number of desirable properties. A challenge in practical large-scale smooth optimization is the solution of linear systems of equations whose purpose is to compute an improved guess. Those systems are typically large, sometimes in the millions of equations and unknowns, but highly structured. Their specific structure, symmetry and quasi definiteness (SQD), must be exploited for computational efficiency. Typical implementations may challenge memory constraints for not exploiting structure and because of problem size. The themes of this proposal hinge around the design of efficient methods exploiting a specific linear system structure encountered in applications such as aerodynamic design, weather forecast, fluid flow simulation or control, and sparse signal reconstruction. I developed four families of tailored iterative methods that fully exploit the SQD structure and provably perform half of the work of standard methods. Each family has its strength and weaknesses and may not be appropriate in all situations. Preliminary experiments suggest that working those methods into state-of-the-art optimization solvers can yield effective implementations that exploit structure every step of the way. On the other hand, real-life applications such as data assimilation, as used in weather forecast, demand certain properties to be verified during the solution process. In turn, this demand calls for specific efficient methods to solve the linear systems. I also propose to establish that certain state-of-the-art optimization frameworks give rise to systems with the SQD structure, although this fact is not immediately apparent. Beyond the explanatory contribution, the benefit is that tailored numerical methods for SQD linear systems may now be used advantageously within those frameworks, yielding more intuitive, self-contained, powerful and robust implementation. In addition, systems with the SQD structure can be used to accelerate the solution of certain problems where systems have a structure that sufficiently resembles the SQD structure. This is the case in certain fluid flow problems and in state-of-the-art optimization methods. The last theme of this proposal concerns so-called least-squares problems, which appear in large classes of applications such as sparse signal reconstruction and data assimilation. There exist strong connections between the SQD structure and least-squares problems that in turn suggest natural and powerful numerical methods. The overwhelming occurrence of least-squares problems in practice is such that improved numerical methods can have a dramatic impact on image processing, signal reconstruction, weather forecast models, medical imaging, seismic data acquisition, and numerous other areas.