Sparse and Regularized Optimization

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

Most algorithmic research in optimization has focused on modelsconsisting of a single objective together with a number ofconstraints, all defined precisely and deterministically, where anexact solution is required. This paradigm is inadequate in manyapplications. First, there is often uncertainty in the model and data;this is being dealt with by a recent upsurge of work in stochastic androbust optimization. Second, users often require a simple approximatesolution rather than a more complicated exact solution. When theproblem is formulated in the appropriate space, simplicity is oftenmanifested as sparsity - the vector of variables has relatively fewnonzeros. Inclusion of nonsmooth regularization terms in theformulation can steer the model toward sparse solutions. This proposalfocuses chiefly on algorithms and theory for sparse and regularizedoptimization, and on application of the methods to such importantareas as compressed sensing, machine learning, computationalstatistics, and image processing. The project also takes ahigher-level view, cross-fertilizing algorithmic ideas acrossdifferent application areas, and devising and analyzing algorithms ingeneral settings that encompass many specific applications. Optimization methods can be used to solve a great variety of practicalproblems, such as design of cancer treatment plans, removing noise andblur from images and videos, identifying genomic and environmentalrisk factors for diseases, and reconstructing pictures, signals, andother data sets from limited random samples. Precise mathematicalformulations of these optimization problems are available, and exactsolutions can often be obtained, but what is needed in many cases is asimple, approximate solution that is easy to compute, understand, andapply. To take one example: Many images can be stored by taking asmall number of random combinations of the pixels that make up theimage. The optimization algorithm that reconstructs the originalpicture from the samples should look for the simplest picture that isroughly consistent with the random observations; this image is likelyto appear more natural than complicated images that give an exactmatch to the data. This project investigates how the mathematicalstatements of problems like this one, and the mathematical methodsthat solve them, can be modified to produce simple solutions.