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进行圆锥编程的强大稳定性，倾斜稳定性和完全优化问题的倾斜稳定性和全面稳定性；（ii）通过SOVA在非滑动（可能是nonConvex）函数上的子差异和kurdyka-lojasiewicz属性的度量（sub）规律性；（iii）参数变分系统的稳定性，包括NASH平衡系统和通过SOVA变异不等式。该项目的第二部分包括设计和分析用于解决凸和非凸结构问题的近端算法。直接应用包括套索，集团套索，弹性网，基本追求，稀疏性，低级别问题和完成矩阵问题，这些问题来自压缩感应，图像重建，机器学习和数据科学。在第一部分中开发的稳定理论在这里起着重要作用，尤其是在这些算法的复杂性分析中。它解释了为什么许多最近的近端算法的发展受Sova的隐藏力量的强烈影响。该部分的特定目标是：（i）加速前后分裂方法并分析数值实验中经常遇到的线性收敛现象；（ii）设计有效的道格拉斯 - 拉赫福德分裂类型的方法，以解决非凸优化和可行性问题。其他重要的应用程序包括由Poisson噪声损坏的逆问题和Denoising模型的总变化，这两者在成像科学和统计学习中都得到了很好的认可。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛影响的审查标准通过评估来获得支持的。

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

On the circumcentered-reflection method for the convex feasibility problem

凸可行性问题的外心反射法

DOI：
10.1007/s11075-020-00941-6
发表时间：
2020
期刊：
Numerical Algorithms
影响因子：
2.1
作者：
Behling, Roger;Bello-Cruz, Yunier;Santos, Luiz-Rafael
通讯作者：
Santos, Luiz-Rafael

Conditional Extragradient Algorithms for Solving Variational Inequalities

求解变分不等式的条件超梯度算法

DOI：
发表时间：
2019
期刊：
Pacific journal of optimization
影响因子：
0.2
作者：
Bello Cruz, Yunier;Diaz Millan, R.;Phan, H.M.
通讯作者：
Phan, H.M.

On inexact projected gradient methods for solving variable vector optimization problems

求解变向量优化问题的不精确投影梯度法

DOI：
10.1007/s11081-020-09579-8
发表时间：
2020
期刊：
Optimization and Engineering
影响因子：
2.1
作者：
Bello-Cruz, J. Y.;Bouza Allende, G.
通讯作者：
Bouza Allende, G.

The circumcentered-reflection method achieves better rates than alternating projections

外心反射方法比交替投影获得更好的速率

DOI：
10.1007/s10589-021-00275-6
发表时间：
2021
期刊：
Computational Optimization and Applications
影响因子：
2.2
作者：
Arefidamghani, Reza;Behling, Roger;Bello-Cruz, Yunier;Iusem, Alfredo N.;Santos, Luiz-Rafael
通讯作者：
Santos, Luiz-Rafael

The block-wise circumcentered–reflection method

分块外心反射法