Collaborative Research: Methods for Stochastic and Nonlinear Optimization

协作研究：随机和非线性优化方法

• 批准号: 1216554
• 负责人: Richard Byrd
• 金额: $ 12万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1216554&HistoricalAwards=false
• 关键词: Collaborative; Research; Methods; Stochastic; Nonlinear

The projects described in this proposal are designed to advance the capabilities of optimization methods for a class of stochastic and deterministic optimization problems. The first project focuses on problems where the objective function is given by an expectation or a loss function. We propose dynamic sample algorithms that attempt to bridge the gap between stochastic and batch methods. Their essential characteristic is that they adapt the sample size during the progression of the optimization in a manner that leads to low computational effort and high accuracy in the solution, when so desired. The second project deals with the design of new active-set methods for solving constrained optimization and convex regularized L1 problems. Our work builds on two algorithms recently proposed in the literature: the block active-set method (also called the primal-dual active-set method), and the orthant-wise method for solving L1 regularized problems. Our new algorithms are provably convergent and applicable to a wider class of applications. The third project addresses the need to improve the robustness of nonlinear optimization methods in the presence of infeasibility. Our first goal is to design an interior point method endowed with infeasibility detection capabilities, and to show how its main mechanism can be extended to other interior point methods. The second goal is to develop a convergence theory that is applicable to both active set and interior point methods consisting of three components: an optimization phase, a feasibility phase, and a mechanism for transitioning between the two phases.The methods developed in this project are useful in big data analysis, which is playing a vital role in genomics, materials science, meteorology, climate modeling and information science. In all these disciplines, vast amounts of data have become available in the last decade, with the rate of generation accelerating exponentially. The challenge is to process this large amount of information to make inferences and predictions, thereby accelerating our basic understanding of physical and social systems. For example, the complex physics simulations employed in the design of advanced materials, meteorology and climate modeling, require the use of detailed information obtained over a large set of scenarios. The optimization and machine learning methods developed in this project can be integrated in support of such simulations, thereby obviating the need for extremely complex models that are difficult to study and generalize. Our work has direct impact in genomics and other areas of biology. For example, we plan to investigate its use in metagenomics, specifically de novo assembly of next generation DNA sequencing data. Sequences can be tagged with markers, or found in reference data sets like transcriptomes. A goal is to use this new information to enable faster and more accurate de novo assembly. In computer science and information technology, our new algorithms will be useful in the development of a new generation of speech recognition and computer vision systems. Speech recognition, which will play an increasingly important role in many technological applications, can only advance by incorporating more data more intelligently, and the algorithms described in this proposal are designed precisely for that purpose.

本提案中描述的项目旨在提高一类随机和确定性优化问题的优化方法的能力。第一个项目重点关注目标函数由期望或损失函数给出的问题。我们提出了动态样本算法，试图弥合随机方法和批处理方法之间的差距。它们的基本特征是，它们在优化过程中调整样本大小，从而在需要时减少计算量并提高解决方案的准确性。第二个项目涉及设计新的活动集方法来解决约束优化和凸正则化 L1 问题。 我们的工作建立在文献中最近提出的两种算法的基础上：块活动集方法（也称为原始对偶活动集方法）和用于解决 L1 正则化问题的 orthant-wise 方法。我们的新算法已被证明是收敛的，并且适用于更广泛的应用程序。第三个项目解决了在不可行的情况下提高非线性优化方法鲁棒性的需要。我们的第一个目标是设计一种具有不可行性检测能力的内点方法，并展示其主要机制如何扩展到其他内点方法。第二个目标是开发一种适用于主动集和内点方法的收敛理论，该理论由三个部分组成：优化阶段、可行性阶段和两个阶段之间的转换机制。该项目开发的方法可用于大数据分析，在基因组学、材料科学、气象学、气候建模和信息科学中发挥着至关重要的作用。在所有这些学科中，过去十年中出现了大量数据，并且生成速度呈指数级增长。 挑战在于处理如此大量的信息以做出推断和预测，从而加速我们对物理和社会系统的基本理解。例如，先进材料设计、气象学和气候建模中采用的复杂物理模拟需要使用从大量场景中获得的详细信息。该项目中开发的优化和机器学习方法可以集成以支持此类模拟，从而无需使用难以研究和推广的极其复杂的模型。我们的工作对基因组学和其他生物学领域有直接影响。例如，我们计划研究其在宏基因组学中的应用，特别是下一代 DNA 测序数据的从头组装。 序列可以用标记进行标记，或者在转录组等参考数据集中找到。 我们的目标是利用这些新信息来实现更快、更准确的从头组装。 在计算机科学和信息技术领域，我们的新算法将有助于开发新一代语音识别和计算机视觉系统。语音识别将在许多技术应用中发挥越来越重要的作用，只有通过更智能地整合更多数据才能取得进步，本提案中描述的算法正是为此目的而设计的。