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

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.