Information-Based Complexity Analysis for Large-Scale Nonlinear Optimization

近年来，数据分析领域发展迅速，对各个学科都产生了影响。优化一直是解决数据分析应用中出现的问题的重要工具。海量数据集和复杂数据结构的现代应用对设计可扩展的、高效的大规模非线性优化问题的数值优化算法提出了巨大的挑战。虽然优化算法设计的目标是尽可能高效地解决感兴趣的问题，但研究感兴趣问题本身的复杂性同样重要。特别是，对一类非线性优化问题的复杂性分析揭示了解决这类问题的任何算法的基本性能限制。发现的性能限制将鼓励人们设计达到这种性能限制的有效算法。一阶方法是一类只需要访问函数值和一阶导数信息的数值优化算法。一阶方法由于其计算效率和可扩展性，已被广泛应用于求解大规模非线性优化问题。该方案通过基于信息的复杂性理论解决了一阶方法性能限制的重要问题。感兴趣的问题是具有不同特殊结构的非线性优化问题。为了加快计算速度，算法设计方面的文献探讨了许多特殊的问题结构。利用该问题结构，新设计的几种算法能够提高计算性能。然而，相对于结构化非线性优化的新算法数量的快速增长，复杂度分析和最坏情况的设计与算法设计的进步并不匹配。本提案旨在通过构建几个证明一阶方法性能限制的最坏情况示例来弥补上述一些差距，希望拓宽对一阶方法效率和某些非线性优化模型难度的理解。该项目由计算数学计划、DMS/MPS和既定计划刺激竞争研究（EPSCoR）共同资助。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.