非度量多维标度问题的矩阵优化模型与算法

Nonmetric multidimensional scaling (also referred as ordinal embedding) is a hot research topic in optimization, statistics and so on. It is to embed objects into a low dimensional space based on the dissimilarities between them, in order to discover underlying relations. Further, it requires the order of distances after embedding matches the order of dissimilarities as much as possible, i.e., keeping the order. As an important method of data analysis especially dimension reduction and visualization, it has wide applications in information sciences, particularly in data mining, machine learning and semantic analysis. This project aims at investigating the models and algorithms of nonmetric multidimensional scaling systematically, from matrix optimization point of view, including: (1) characterize the basic theories and approximations for ordinal constraints and rank constraints; (2) set up ordinal constrained and rank constrained matrix optimization models as well as the relaxed models and analyze the theoretical properties; (3) design efficient optimization algorithms, establish the convergence theory; (4) apply them to large-scale real data analysis such as drawing paths of ground moving targets in radar system. The conduction of this project can enrich the contents of optimization and statistics, and also provide efficient methods for big data analysis, therefore, has its significance both in theory and application.

非度量多维标度（又称保序嵌入）问题是最优化与统计学等学科共同关心的一个前沿研究课题。它是依据对象间的不相似性数据，将对象嵌入到低维空间以发现其内在规律，同时还要求嵌入后的对象间距与不相似性数据的排序尽量保持一致，即‘保序’。它作为大数据分析特别是降维和可视化的一种重要方法，在信息领域特别是数据挖掘、机器学习、语义分析等方面均有广泛应用。本项目拟从矩阵优化角度系统研究该问题的优化模型和算法，主要内容包括：（1）刻画序约束和低秩约束的基本理论以及近似表示；（2）建立保序低秩矩阵优化模型及其各种松弛模型，并分析其理论性质；（3）设计快速有效算法并建立其收敛性理论;（4）将算法应用于大规模实际数据分析，如雷达系统中地面动目标轨迹的绘制。本项目的实施可丰富优化与统计学内容，也可为大数据分析提供有效方法，具有重要的理论意义和应用价值。

非度量多维标度（又称保序嵌入）问题是最优化与统计学等学科共同关心的一个前沿.研究课题。它是依据对象间的不相似性数据，将对象嵌入到低维空间以发现其内在规律，.同时还要求嵌入后的对象间距与不相似性数据的排序尽量保持一致，即‘保序’。它作为.大数据分析特别是降维和可视化的一种重要方法，在信息领域特别是数据挖掘、机器学习.、语义分析等方面均有广泛应用。本项目从矩阵优化角度系统研究该问题的优化模型和.算法，取得如下研究进展：（i）完成了对序约束和秩约束刻画下解的可行性分析；（ii）构建了不同非度量多维标度问题的矩阵优化模型： 带序权重模型，一般损失函数模型及凸约束情形的模型。并讨论了不同模型的理论性质。（iii）基于不同的模型，设计了不同的算法进行求解。（iv）以上算法均形成数值软件。（v）特别的，将如上模型与算法用于不同的应用场景：图像排序，泵车臂架定位及蛋白质分子重构，取得了良好的效果。项目成果如下：（1）项目期间总计发表SCI文章13篇（其中项目组成员为一作或通讯的为10篇），专著2本，教材1本，上线慕课课程一门，在审文章2篇（2）通过如上研究工作建立了非度量多维标度问题的矩阵优化理论研究体系，设计了快速有效的算法，并具备了用于实际问题的数值软件。（3）培养具有统计、优化、信息处理交叉研究背景的硕士研究生毕业6名，目前在读硕士14名，博士1名。