Information-Based Complexity Analysis for Large-Scale Nonlinear Optimization

大规模非线性优化的基于信息的复杂性分析

• 批准号: 1913006
• 负责人: Yuyuan Ouyang
• 金额: $ 24.38万
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1913006&HistoricalAwards=false
• 关键词: Information; Based; Complexity; Analysis; Large

Recent years have seen rapid advances in the fields of data analysis, which has impacts in various disciplines. Optimization has been an important tool in solving problems arising from data analysis applications. Modern applications with large volume datasets and sophisticated data structures bring great challenges to designing scalable and efficient numerical optimization algorithms for large-scale nonlinear optimization problems. While the goal of optimization algorithm design is to solve the problems of interest as efficiently as possible, it is equally important to study the complexity of the problems of interest themselves. In particular, the complexity analysis of a class of nonlinear optimization problems reveals the fundamental performance limits of any algorithms for solving problems in such class. The discovered performance limits would then encourage one to design efficient algorithms that reach such performance limits. First-order methods are a class of numerical optimization algorithms that only need to access the information on function value and first-order derivatives. Due to the computational efficiency and scalability, first-order methods have been widely used to solve large-scale nonlinear optimization problems. This proposal addresses the important question of performance limits of first-order methods through the information-based complexity theory. The problems of interests are nonlinear optimization with different special structures. In order to accelerate computation, many special problem structures have been explored in the literature on algorithm design. By utilizing the problem structure, several newly designed algorithms are able to achieve improved computational performance. However, comparing with the rapidly growing number of new and novel algorithms on structured nonlinear optimization, the complexity analysis and the design of worse-case instances does not match with the advancement in algorithm design. This proposal aims to close some of the aforementioned gaps by constructing several worst-case examples that demonstrate the performance limits of first-order methods, in the hope of broaden the understanding of efficiency of first-order methods and the difficulty of certain nonlinear optimization models.This project is jointly funded by Computational Mathematics Program, DMS/MPS, and the Established Program to Stimulate Competitive Research (EPSCoR).This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

近年来，数据分析领域取得了快速发展，对各个学科产生了影响。优化一直是解决数据分析应用中出现的问题的重要工具。大规模数据集和复杂数据结构的现代应用给大规模非线性优化问题的可扩展性和高效数值优化算法的设计带来了巨大挑战。虽然优化算法设计的目标是尽可能有效地解决感兴趣的问题，但研究感兴趣的问题本身的复杂性也同样重要。特别是，一类非线性优化问题的复杂性分析揭示了解决此类问题的任何算法的基本性能限制。所发现的性能极限将鼓励人们设计达到这种性能极限的有效算法。 一阶方法是一类只需要获取函数值和一阶导数信息的数值优化算法。由于一阶方法具有计算效率高、可扩展性好等优点，被广泛应用于求解大规模非线性优化问题。该建议通过基于信息的复杂性理论解决了一阶方法性能极限的重要问题。利益相关问题是具有不同特殊结构的非线性优化问题。为了加速计算，许多特殊的问题结构已在算法设计的文献中进行了探索。通过利用问题结构，一些新设计的算法能够实现更好的计算性能。然而，与结构化非线性优化算法的不断涌现相比，算法的复杂性分析和最坏情况实例的设计与算法设计的先进性并不匹配。本研究的目的是通过构建几个最坏情况的例子来证明一阶方法的性能极限，从而弥补上述一些差距，希望扩大对一阶方法的效率和某些非线性优化模型的难度的理解。本项目由计算数学计划DMS/MPS，该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Some worst-case datasets of deterministic first-order methods for solving binary logistic regression

用于求解二元逻辑回归的确定性一阶方法的一些最坏情况数据集

• DOI: 10.3934/ipi.2020047
• 发表时间: 2021
• 期刊: Inverse Problems & Imaging
• 影响因子: 1.3
• 作者: Ouyang, Yuyuan;Squires, Trevor
• 通讯作者: Squires, Trevor

Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems

• DOI: 10.1007/s10107-019-01420-0
• 发表时间: 2019-08
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Yuyuan Ouyang;Yangyang Xu