The investigator develops theory and algorithms to solve optimization problems arising in present-day business, science, and engineering applications, often specifically related to data analysis problems where the aim is to better inform decisions about alternative choices. The project's topics arise in model selection techniques (used in applications such as the identification of social networks and the selection of covariates that best inform health outcomes), in imaging applications, and in the dynamics, tracking, and control of waste streams and of vehicles. Commonly in applications the objective function (the function to be optimized) may be nonsmooth, nonconvex, or high-dimensional; each of these features presents major challenges for classical optimization methods. A key aspect of the project is the use of nonsmooth techniques that allow for the introduction or discovery of special properties in the desired solution, such as sparsity, stability, and robustness. The work falls into four main areas. The first concerns study of the BFGS method and matrix secant methods for nonsmooth convex optimization (why BFGS works as well as it does is unclear), and the design of algorithms that automatically discover a so-called UV-decomposition of the objective function. Here the U is the smooth part and the V is the nonsmooth part. Such decompositions are essential for rapid solution identification as they allow one to follow a smooth valley (U) with steep sides (V) toward the optimal solution. The second examines the rate at which a solution is obtained as well as its accuracy, depending on functional and parameter inputs. The third examines the determination of optimal stability and control of linear dynamical systems occurring, for example, in orbital dynamics or drug metabolism. The goal here is to help recognize optimal solutions. Indeed, in many cases methods for identifying optimality remain unknown. The final task concerns the development of novel smoothing methodologies for optimization problems over matrix spaces, such as those occurring in social network discovery. These problems are typically very high-dimensional, and nonsmoothness of the objective function is the key to discovering hidden structures within the data. Here the goal is to develop smooth approximations whose solution can be rapidly computed and whose proximity to the true solution is precisely controlled. Graduate students participate in the research.

More technically, the areas of study are (i) BFGS and matrix secant methods for nonsmooth convex optimization, (ii) local and global convergence theory for convex-composite optimization, (iii) variational analysis of spectral functions for non-symmetric matrices, and (iv) the generalized matrix fractional function and smoothing on matrix spaces. The study of BFGS methods focuses on the relationship between the iterates and smooth, convex, uniform approximations. The study of convex composite problems analyses the behavior of algorithms using Robinson's method of generalized equation. The study of nonsymmetric matrices focuses on extending variational techniques to the difficult nonderogatory case. The final area considers the embedding of a wide range of matrix optimization problems in a smooth setting by the use of infimal projection with the generalized matrix fractional function introduced by the investigator and collaborators. Graduate students participate in the research.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

National Science Foundation (NSF)
Division of Mathematical Sciences (DMS)
Standard Grant (Standard)
Application #
Program Officer
Pedro Embid
Project Start
Project End
Budget Start
Budget End
Support Year
Fiscal Year
Total Cost
Indirect Cost
University of Washington
United States
Zip Code