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.