Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$39,000.00
Matrix-Free Methods for Optimization and Linear Systems
FY 2014-15
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2014-04269
Name nom
Orban, Dominique
Department département
Mathematics and Industrial Engineering
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2014
Award amount
39000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
703
Area of application group en
Transportation systems and services
Area of application group fr
Services et systèmes de transport
Area of application en
Aerospace
Area of application fr
Aérospatial
Research subject code
2956
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Optimisation and optimal control theory
Research subject fr
Optimisation et théories de commande optimale
Partie
1
Nb partie
5
Application title
Matrix-Free Methods for Optimization and Linear Systems
Keyword
NSERC
Application summary
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.