Extending Sparse Optimization

扩展稀疏优化

• 批准号: 1216318
• 负责人: Stephen Wright
• 金额: $ 24.1万
• 依托单位: University of Wisconsin-Madison
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1216318&HistoricalAwards=false
• 关键词: 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.

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