Theory and algorithms for a new class of computationally amenable nonconvex functions

随着数据科学的重要性不断扩大，非凸优化模型在各种科学和工程应用中越来越普遍。尽管该领域发展迅速，但迄今仍存在大量的理论和应用问题，缺乏严谨的分析和有效的解决方法。本项目以实用性为驱动，以严谨性为强化，旨在对复合非凸优化问题和博弈进行全面研究。所开发的技术将为基础科学和工程研究提供有价值的工具，对环境产生积极影响，并促进与大数据世界的社会融合。此外，该项目还将教育本科生和研究生，培养该领域的下一代专家。该项目旨在通过理论和计算方法推进解决非凸优化问题和游戏的最先进技术。其核心是“可接近的凸函数差分”的创新概念，它揭示了在非凸和非光滑函数的多重组合中隐藏的，渐近可分解的结构。该项目将解决三个主要任务：(i)建立一类新的计算上可适应的非凸和非光滑复合函数的基本性质；（ii）设计和分析单智能体优化问题的计算方案，目标函数和约束函数属于上述类别；(3)将这些方法扩展到解决非凸博弈。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

As the significance of data science continues to expand, nonconvex optimization models become increasingly prevalent in various scientific and engineering applications. Despite the field's rapid development, there are still a host of theoretical and applied problems that so far are left open and void of rigorous analysis and efficient methods for solution. Driven by practicality and reinforced by rigor, this project aims to conduct a comprehensive investigation of composite nonconvex optimization problems and games. The technologies developed will offer valuable tools for fundamental science and engineering research, positively impacting the environment and fostering societal integration with the big-data world. Additionally, the project will educate undergraduate and graduate students, cultivating the next generation of experts in the field.This project seeks to advance state-of-the-art techniques for solving nonconvex optimization problems and games through both theoretical and computational approaches. At its core is the innovative concept of "approachable difference-of-convex functions," which uncovers a hidden, asymptotically decomposable structure within the multi-composition of nonconvex and non-smooth functions. The project will tackle three main tasks: (i) establishing fundamental properties for a novel class of computationally amenable nonconvex and non-smooth composite functions; (ii) designing and analyzing computational schemes for single-agent optimization problems, with objective and constrained functions belonging to the aforementioned class; and (iii) extending these approaches to address nonconvex games.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.