Numerical Methods for Structured Nonsmooth Optimization

University Of Washington, Seattle WA

Investigators

Abstract

Nonsmoothness is inherent in applications such as signal denoising and image smoothing. For example, a signal may have jumps, and an image may have sharp boundary lines. The proposed research will focus on the design, analysis, implementation, and testing of efficient methods for solving structured nonsmooth optimization problems arising in these and related applications such as regression, and data mining/classification. In these problems, the objective function is the sum of a smooth function and a nonsmooth, typically convex and separable, function. This class of optimization problems includes box-constrained problems and problems with 1-norm regularization. The solution approaches will focus on derivative-based methods that distribute the computation componentwise and are highly parallelizable. They will extend ideas from unconstrained and box-constrained smooth optimization, such as SOR, gradient-projection, parallel variable/gradient distribution, Gauss-Newton, incremental gradient. The research will also study derivative-free methods, direct search and/or model-based, for problems where derivative information is unavailable. The proposed research thus focusses on designing fast computer algorithms for detecting and extracting underlying key features in noisy signals, images, and large data sets. This is achieved by formulating a parametric model and optimizing a weighted combination of: (1) goodness-of-fit of the model to the data, and (2) sparsity of the model, over a (possibly high-dimensional) parameter space. Optimization will be done using algorithms based on successive approximations, which distribute the computation componentwise and are highly parallelizable. The applications to signal denoising, image smoothing, and feature extraction from (large) data sets may be pertinent to some areas of national security.