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

随着数据科学的重要性不断扩大，非凸优化模型在各种科学和工程应用中变得越来越普遍。尽管该领域发展迅速，但到目前为止，仍有许多理论和应用问题悬而未决，缺乏严格的分析和有效的解决方法。本项目以实用为导向，以严谨为强化，旨在对组合非凸优化问题及其对策进行全面的研究。开发的技术将为基础科学和工程研究提供宝贵的工具，对环境产生积极影响，并促进社会与大数据世界的融合。此外，该项目还将培养本科生和研究生，培养该领域的下一代专家。该项目寻求通过理论和计算方法提高解决非凸优化问题和博弈的最新技术。它的核心是“可接近凸差函数”的创新概念，它揭示了非凸和非光滑函数的多重组合中隐藏的、渐近可分解的结构。该项目将解决三个主要任务：(I)建立一类新的可计算服从非凸和非光滑复合函数的基本性质；(Ii)设计和分析单主体优化问题的计算方案，目标函数和约束函数属于上述类别；以及(Iii)将这些方法扩展到解决非凸博弈。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.