Matrix-Free Methods for Optimization and Linear Systems

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

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.