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

合作研究：结构化优化中的二阶变分分析及算法及其应用

基本信息

批准号：
1816449
负责人：
Yunier Bello Cruz
金额：
$ 9.91万
依托单位：
Northern Illinois University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-09-01 至 2021-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1816449&HistoricalAwards=false
关键词：
Collaborative Research Second Order Variational

项目摘要

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.

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