Collaborative Research: Methods for Stochastic and Nonlinear Optimization

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

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.