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

该项目的重点是开发先进的数学分析工具，以研究现代结构优化问题，并建立有效的算法来解决这些问题。这些问题出现在科学和工程的不同领域，包括海量数据分析、机器学习、信号处理、医学图像重建、统计、交通和物流网络以及运筹学。它们中的大多数都具有非光滑或非凸的不规则现象，这对计算提出了挑战。尽管最近提出了一些实际上成功的算法来解决这些问题，但其基本理论还没有得到充分的理解和探索。只有分析这些问题和算法背后的复杂性和深层数学，才能为相关的重要科学和工程领域的从业者提供新的工具，以理解其核心特征，能够设计更有效的算法，并解决实践中出现的更具挑战性的问题。研究人员通过应用数学相对年轻的子领域变分分析的一种新颖方法开发了此类工具，该方法自然与这些非光滑和复杂的结构兼容。该项目的几个主题与主题课程的教学和学生的培训相结合。 该项目致力于发展二阶变分分析（SOVA）理论，并使用它来研究解决结构优化问题的算法的稳定性，灵敏度和计算复杂性。本项目的第一部分作为理论基础，它涉及SOVA理论与稳定性和灵敏度分析的连接。更具体地说，研究人员打算研究：（i）一般优化问题的倾斜稳定性和完全稳定性，并通过SOVA将其与罗宾逊强正则性和Kojima强稳定性联系起来;（ii）次微分的度量（次）正则性和非光滑上的Kurdyka-Lojasiewicz性质（可能非凸）功能通过SOVA;（iii）稳定性参数变分系统，包括纳什均衡系统和变分不等式通过SOVA。本计画的第二部分是设计与分析求解凸与非凸结构化问题的近似演算法。直接的应用包括Lasso，群Lasso，弹性网络，基本追求，稀疏性，低秩问题和来自压缩感知，图像重建，机器学习和数据科学的完成矩阵问题。稳定性理论在第一部分中发挥了重要作用，特别是在这些算法的复杂性分析。它解释了为什么许多最近的近似算法的发展受到SOVA隐藏力量的强烈影响。这一部分的具体目标是：（i）加速向前向后分裂方法，并分析在数值实验中经常遇到的线性收敛现象;和（ii）设计有效的道格拉斯-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.