Matrix-Free Methods for Optimization and Linear Systems

点击翻译按钮获取中文摘要

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.