Extending Sparse Optimization

稀疏优化不是精确地解决优化问题，而是寻求满足某些结构性质的近似解，例如解向量中很少有非零。稀疏优化问题和公式现在在广泛的应用中得到了认可，解决这些问题的技术利用了各种各样的算法工具，包括旧的和新的。本项目旨在从两个方面对稀疏优化进行扩展。首先，提出了从稀疏优化角度受益的应用领域：极端规模的机器学习和数据挖掘、接触动力学、对象打包、医学图像重建和无导数优化。算法的发展将针对这些领域的关键问题公式，特别注意可以利用并行计算机体系结构和专用硬件的方法。要考虑的算法技术包括随机逼近、随机方向、增广拉格朗日和使用高阶信息的约简空间搜索。其次，该项目将使用一般框架来分析诸如流形识别、连续、一阶算法、不精确以及收敛和复杂性结果等算法思想。这些研究的一般性质将使创新能够在广泛的配方和应用中传播。优化领域为许多应用领域中的问题的表述、建模和解决提供了一个重要的框架。在稀疏优化中，我们注意到许多应用需要具有易于指定的特殊结构的解决方案，但很难将其纳入传统算法和模型中。例如，稀疏优化出现在信号和图像的重建中，我们知道信号应该只包含几个频率，或者图像应该看起来像自然图像而不是白噪声。过去几年的重要事态发展表明，解决方案的结构要求不但不会成为有效解决的障碍，反而可以导致更有效的公式和更快的方法。在压缩感知和图像去噪等领域取得了显著的成功。本项目将在这些成功的基础上，开发可用于许多新的和现有的稀疏优化应用的算法。为了与现代优化研究保持一致，将考虑一组算法技术。将发展理论，以支持在广泛的背景下使用这些技术。

Rather than solving an optimization problem exactly, sparse optimization seeks approximate solutions that satisfy certain structural properties, such as few nonzeros in the solution vector. Sparse optimization problems and formulations are now recognized across a wide range of applications, and techniques for solving these problems draw on a large variety of algorithmic tools, old and new. This project aims to extend sparse optimization in two respects. First, work is proposed in application areas that can benefit from the sparse optimization perspective: machine learning and data mining at extreme scale, contact dynamics, object packing, medical image reconstruction, and derivative-free optimization. Algorithmic developments will target key problem formulations in these areas, paying particular attention to methods that can exploit parallel computer architectures and specialized hardware. Algorithmic techniques to be considered include stochastic approximation, randomized directions, augmented Lagrangian, and reduced-space search using higher-order information. Second, the project will use general frameworks to analyze such algorithmic ideas as manifold identification, continuation, first-order algorithms, inexactness, and convergence and complexity results. The general nature of these investigations will enable innovations to be spread across a wide range of formulations and applications. The field of optimization provides a vital framework for formulating, modeling, and solving problems in many application areas. In sparse optimization, we note that many applications require solutions with a special structure that is easy to specify, but hard to incorporate in traditional algorithms and models. Sparse optimization arises, for example, in reconstruction of signals and images, where we know that the signal should contain only a few frequencies, or that the image should look like a natural image rather than white noise. Important developments of the past few years have shown that the requirement of structure in solutions, rather than being a hindrance to efficient solution, can actually lead to more efficient formulations and faster methods. Notable successes have been achieved in such areas as compressed sensing and image denoising. This project will build on these successes by developing algorithms that can be leveraged in many new and existing applications of sparse optimization. In keeping with modern optimization research, a bevy of algorithmic techniques will be considered. Theory will be developed to support the use of these techniques in a wide range of contexts.