Collaborative Research: Methods for Stochastic and Nonlinear Optimization

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

• 批准号: 1216567
• 负责人: Jorge Nocedal
• 金额: $ 30万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1216567&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正则化问题的正交方法。我们的新算法被证明是收敛的，适用于更广泛的应用。第三个项目解决了在不可行的情况下提高非线性优化方法鲁棒性的需要。我们的第一个目标是设计一种具有不可行性检测能力的内点方法，并展示其主要机制如何扩展到其他内点方法。第二个目标是发展一种既适用于活动集法又适用于内点法的收敛理论，该收敛理论由三个部分组成：优化阶段、可行性阶段和两个阶段之间的过渡机制。该项目开发的方法在大数据分析中非常有用，在基因组学、材料科学、气象学、气候建模和信息科学中发挥着至关重要的作用。在所有这些学科中，大量的数据在过去十年中变得可用，生成速度呈指数级增长。我们面临的挑战是如何处理大量的信息来进行推断和预测，从而加快我们对物理和社会系统的基本理解。例如，在设计先进材料、气象和气候模型时采用的复杂物理模拟，需要使用从大量情景中获得的详细信息。本项目开发的优化和机器学习方法可以集成在一起，以支持这种模拟，从而避免了对难以研究和推广的极其复杂的模型的需要。我们的工作对基因组学和其他生物学领域有直接影响。例如，我们计划研究其在宏基因组学中的应用，特别是下一代DNA测序数据的从头组装。序列可以用标记标记，或者在转录组等参考数据集中找到。目标是利用这些新信息实现更快、更准确的从头组装。在计算机科学和信息技术领域，我们的新算法将有助于新一代语音识别和计算机视觉系统的开发。语音识别将在许多技术应用中发挥越来越重要的作用，它只能通过更智能地整合更多数据来推进，而本提案中描述的算法正是为此目的而设计的。