数据分析中的大规模矩阵优化模型求解算法研究

Recently, with the rapid development of modern information technology, people always deal with high dimensional data analysis problems in various fields. As a result of high dimensionality, traditional statistical methods become inadequate or break down, rending high dimensional data analysis to the area full of challenges and opportunities. To meet the challenges, statisticians has been developing new methods and introducing new concepts, among which large scale matrix optimization models are widely applied. Motivated by this, our proposed project is to study the algorithm design and the application of several common class of large scale matrix optimization models arising in high dimensional data analysis. Specifically, we firstly utilize the structure of high dimensional data to design fast and efficient algorithms including first order algorithms, first order-Newton CG mixed algorithms and Newton methods.With this preparation, we will write a matlab software to solve the matrix programmings according to user's requirements. Then, we will apply the results into the fields of finance and management science, and extract valuable information via data analysis.

近年来，随着现代信息技术的快速发展，人们在各个领域均会遇到高维数据的统计分析问题。由于数据的维数过高，传统的统计方法往往失效，使得它成为目前应用数学中最困难也最有机遇的领域之一。为此，统计学家纷纷提出新方法、引入新概念来应对这一挑战，在其中矩阵优化模型被广泛的应用。本项目以此为背景，着重研究数据分析中的常见矩阵优化模型的算法和应用。具体而言，在本项目中，我们(1)将通过分析数据的结构，设计基于数据本身结构的各类高效算法，具体包括一阶算法、一阶—Newton CG混合算法和Newton方法等。并在此基础上，研制满足各种不同求解要求的matlab软件包。(2)将结果应用于金融、管理科学中，进行数据分析处理，提取有效信息。

在数据分析中，经常会遇到向量、矩阵、图像等庞大的数据，维数可以达到上万、甚至更高，对于该类数据样本数目可能远小于数据的维数。因而需要利用数据的结构（如稀疏性、低秩）降维以提取潜在的信息。这些数特性一般可以通过对模型作适当的正则化而实现，其中矩阵优化模型被广泛应用在矩阵和图像数据的正则化中。本项目以此为背景，拟集合一阶算法、半光滑Newton邻近点算法、Newton法等研究数据分析中常见模型的求解算法，研制软件包，应用于图像科学、金融等各个领域中。. 项目组与斯坦福大学、新加坡国立大学、香港中文大学、香港浸会大学、中国科学院等科研机构开展了深入的合作研究，并已经超额完成预计任务；在国外知名刊物上发表论文7 篇，均被SCI收录，其中SCI一区 4 篇（两篇论文发表在Mathematical Programming, 两篇论文发表在SIAM系列杂志），并且有一篇论文入选ESI高被引论文，一篇论文获得华裔世界数学家联盟颁发的杰出论文奖励。项目主持人参加了众多的国内外学术会议并作报告，并且主持了2015年国际数学规划分会的分组报告、以及担任2016年国际连续优化大会的其中两个小组的组织者。. 项目按照申请书设计的技术路线与年度计划有序进行。项目在理论与方法方面的贡献主要包含：1）当数据分析中的模型目标函数为2块的可分函数时，设计了带惯性的交替方向法来求解上述问题，较经典的交替方向法相比算法的表现有了明显的提高；2）当问题的块数不少于3时，证明了交替方向法在求解该问题时可能不收敛，回答了交替方向法研究中的一个主要的公开问题。为了克服交替方向法可能的不收敛性，提出将其随机排列的变形用于求解上述不可分问题，并在某些情形下得到了收敛性；3）当用户需要高精度解时，提出了两阶段优化算法，起始用交替方向法，若难以达到目标，则在第二阶段利用半光滑Newton-CG邻近点算法进行加速。. 此外，算法被应用在求解鲁棒主成份分析、压缩图像重建、稀疏投资组合等模型中，并预期在数据分析中发挥更多重要，帮助从数据中提取潜在信息、进行优化决策。