This grant provides travel support for US scientists to a three-day "Workshop on Numerical Linear Algebra and Optimization", to be held August 8-10, 2013 at the University of British Columbia, Vancouver, Canada. The workshop has the following three objectives: (1) to bring together the community of linear algebra and optimization in order to foster interaction and explore the rich area at the intersection of these two research fields; (2) to seek application of these problems in fields like machine learning and control; and (3) to promote and discuss the issue of actively using large-scale numerical linear algebra tools in scientific and industrial optimization. One of the main areas the workshop will focus on is eigenvalue optimization, which has received a lot of attention recently and which is studied by the two communities from different perspectives.
Optimization is a large field of research, with applications ranging from economics and engineering to national security, energy, and climate understanding. Examples of problems that can be solved with the help of optimization include maximizing profit or minimizing waste when manufacturing a variety of goods under raw material constraints; computer-based learning to classify objects (e.g., distinguishing tanks from trees); designing stronger buildings subject to volume and environmental constraints; and making planes safer by avoiding certain undesirable vibration frequencies. Solutions to such optimization problems need to make use of linear algebra quantities (like eigenvalues), and extensive calculations of such quantities must be done with care and in the most efficient way. This is a central task in numerical linear algebra, the tools of which have been adopted and adapted by various optimization communities to suit their needs. There is a very rich area of research at the interface between these two fields of optimization and numerical linear algebra, and the organizers of this workshop aim to see both communities work together toward addressing the important problems that arise in industry.
Intellectual merit. Eigenvalue optimization problems in the convex and non-convex settings possess intrinsic similarities, yet they are typically studied by different communities: convex problems, especially those that can be formulated as SDPs, received immense attention in optimization, while non-convex problems, such as those concerning pseudospectra, have been hot research directions in numerical linear algebra. The workshop brought these two communities together and provided the opportunity to exchange ideas. One of the themes of the workshop was to focus on eigenvalue problems in optimization. The first session of the workshop was partly dedicated to matrices with multiple eigenvalues, in particular distances to such matrices, that are of interest to the numerical linear algebra community, with notable talks by Lloyd Trefethen and by Nicola Guglielmi. Various other talks, for instance the ones by Shreemayee Bora and Daniel Kressner, focused on similar distance problems popular in numerical linear algebra, leading to non-convex eigenvalue optimization problems. On the side of the optimization community, quite a few talks concerned SDP relaxations of NP-hard problems, e.g., the talks by Henry Wolkowicz, Stephen Vavasis and Franz Rendl. Thus the workshop provided opportunity for each of the two communities to become better acquainted with the problems that are of interest to the other community. Another theme was to highlight the modern applications of optimization problems involving eigenvalues; this theme was present throughout the workshop. For example, the talk by James Burke elaborated on applications to machine learning; the talks by Volker Mehrmann and Didier Henrion illustrated applications to control theory; and the talk by Franz Rendl considered a classical application from graph theory. Finally, the third main theme of the workshop was the effective use of large-scale numerical linear algebra tools. An important tool from numerical linear algebra Krylov subspace methods was covered in a session consisting of lectures by Michael Saunders, Daniel Szyld, and Josef Sifuentes. Use of appropriate matrix factorizations were highlighted by the lectures by Paul Van Dooren and Charles Van Loan, while the lecture by Jim Demmel focused on efficient parallel implementation of numerical linear algebra routines. In conclusion, the workshop was very successful in achieving the stated intellectual merit goals. Broader impact. The workshop had a great impact on the two communities involved, through knowledge dissemination and by creating a fruitful dialogue which will lead to successful collaborations between the theoretical and the application-driven participants. In addition, we organized a poster session during which the junior attendees were able to present their research. Finally, the participant demographics were fairly diverse: of the twenty-seven speakers, eight were within fifteen years from their PhD; all nine poster-presenters were graduate students; six of the twenty-seven speakers and three of the nine poster-presenters were women; and five of the seventeen North American speakers were minorities.