Most algorithmic research in optimization has focused on models consisting of a single objective together with a number of constraints, all defined precisely and deterministically, where an exact solution is required. This paradigm is inadequate in many applications. First, there is often uncertainty in the model and data; this is being dealt with by a recent upsurge of work in stochastic and robust optimization. Second, users often require a simple approximate solution rather than a more complicated exact solution. When the problem is formulated in the appropriate space, simplicity is often manifested as sparsity - the vector of variables has relatively few nonzeros. Inclusion of nonsmooth regularization terms in the formulation can steer the model toward sparse solutions. This proposal focuses chiefly on algorithms and theory for sparse and regularized optimization, and on application of the methods to such important areas as compressed sensing, machine learning, computational statistics, and image processing. The project also takes a higher-level view, cross-fertilizing algorithmic ideas across different application areas, and devising and analyzing algorithms in general settings that encompass many specific applications.
Optimization methods can be used to solve a great variety of practical problems, such as design of cancer treatment plans, removing noise and blur from images and videos, identifying genomic and environmental risk factors for diseases, and reconstructing pictures, signals, and other data sets from limited random samples. Precise mathematical formulations of these optimization problems are available, and exact solutions can often be obtained, but what is needed in many cases is a simple, approximate solution that is easy to compute, understand, and apply. To take one example: Many images can be stored by taking a small number of random combinations of the pixels that make up the image. The optimization algorithm that reconstructs the original picture from the samples should look for the simplest picture that is roughly consistent with the random observations; this image is likely to appear more natural than complicated images that give an exact match to the data. This project investigates how the mathematical statements of problems like this one, and the mathematical methods that solve them, can be modified to produce simple solutions.
