Collaborative Research: Second-Order Variational Analysis in Structured Optimization and Algorithms with Applications

这个项目专注于开发先进的数学分析工具来研究现代结构优化问题，并建立有效的算法来解决这些问题。这些问题出现在科学和工程的不同领域，包括海量数据分析、机器学习、信号处理、医学图像重建、统计学、交通和物流网络以及运筹学研究。它们中的大多数都具有非光滑或非凸性的不规则现象，这对计算提出了挑战。尽管最近提出了几个实际成功的算法来解决这类问题，但其基本理论还没有得到很好的理解和探索。只有分析这些问题和算法背后的复杂性和深奥的数学知识，才能为相关重要科学和工程领域的从业者提供新的工具，以理解它们的核心特征，能够设计更高效的算法，并解决实践中出现的更具挑战性的问题。研究人员从应用数学的一个相对年轻的子领域--变分分析--通过一种新的方法开发了这样的工具，变分分析与这些非光滑和复杂的结构自然兼容。这个项目的几个主题与教学主题课程和学生的培训相结合。本项目致力于发展二阶变分分析(SOVA)理论，并用它来研究求解结构化优化问题的算法的稳定性、敏感性和计算复杂性。本项目的第一部分是理论基础，它涉及到与稳定性和敏感性分析有关的SOVA理论。更具体地说，研究者打算研究：(I)一般优化问题的倾斜稳定性和完全稳定性，这些问题与Robinson的强正则性和Kojima的强稳定性有关；(Ii)通过SOVA的圆锥规划的次微分和Kurdyka-Lojasiewicz性质的度量(次)正则性；以及(Iii)通过SOVA的参数变分系统的稳定性，包括Nash平衡系统和变分不等式。本项目的第二部分包括设计和分析用于解决凸和非凸结构化问题的近似算法。直接的应用包括套索、群体套索、弹性网络、基本追踪法、稀疏性、低阶问题以及源于压缩传感、图像重建、机器学习和数据科学的完成矩阵问题。在第一部分中发展的稳定性理论在这里起着重要的作用，特别是在这些算法的复杂性分析中。它解释了为什么最近许多近邻算法的发展受到SOVA隐藏力量的强烈影响。这一部分的具体目标是：(I)加速正反向分裂方法，分析数值实验中经常遇到的线性收敛现象；(Ii)设计求解非凸优化和可行性问题的高效的Douglas-Rachford分裂型方法。其他重要的应用包括被泊松噪声破坏的逆问题和全变差去噪模型，这两个模型在成像科学和统计学学习中都得到了很好的认可。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project focuses on developing advanced tools of mathematical analysis to investigate modern structured optimization problems and building efficient algorithms to solve them. These problems arise in different areas of science and engineering, including massive data analysis, machine learning, signal processing, medical image reconstruction, statistics, traffic and logistical networks, and operations research. Most of them share the irregular phenomenon of nonsmoothness or nonconvexity that challenges computation. Despite several practically successful algorithms recently proposed to solve such problems, the underlying fundamental theory is not quite understood and explored. Only analyzing the complexity and the deep mathematics behind these problems and algorithms provides practitioners across related, vital science and engineering areas new tools to comprehend their core features, be able to design more efficient algorithms, and attack more challenging problems arising from practice. The investigators develop such tools via a novel approach from a relatively young subfield of applied mathematics, variational analysis, which is naturally compatible with these nonsmooth and complex structures. Several topics from this project are integrated with teaching topic courses and training of students.This project is devoted to developing the theory of second-order variational analysis (SOVA) and using it to study the stability, sensitivity, and computational complexity of algorithms for solving structured optimization problems. The first part of this project serves as the theoretical foundation; it concerns the theory of SOVA with connections to stability and sensitivity analysis. More specifically, the investigators intend to study: (i) tilt stability and full stability for general optimization problems with connections to Robinson's strong regularity and Kojima's strong stability for conic programming via SOVA; (ii) metric (sub)regularity of the subdifferential and Kurdyka-Lojasiewicz property on nonsmooth (possibly nonconvex) functions via SOVA; and (iii) stability for parametric variational systems including Nash equilibrium systems and variational inequalities via SOVA. The second part of this project consists of designing and analyzing proximal algorithms for solving convex and nonconvex structured problems. Immediate applications include Lasso, group Lasso, elastic net, basic pursuit, sparsity, low-rank problems, and completion matrix problems that originate from compressed sensing, image reconstruction, machine learning, and data science. Stability theory developed in the first part plays a significant role here, especially in the complexity analysis of these algorithms. It explains why the development of many recent proximal algorithms is strongly influenced by the hidden power of SOVA. The specific objectives of this part are: (i) to accelerate the forward-backward splitting method and analyze the phenomenon of linear convergence encountered frequently in numerical experiments; and (ii) to design efficient methods of Douglas-Rachford splitting type for solving nonconvex optimization and feasibility problems. Other important applications include inverse problems corrupted by Poisson noise and total variation denoising models, both of which are well recognized in imaging science and statistical learning.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.