基于秩一近似的大规模矩阵优化算法及其应用

Matrix optimization algorithms have been applied in a wide spectrum of applications such as image processing, machine learning and data mining. However, the main solution strategy to date for matrix optimization has been based on eigenvalue value decomposition, which is still a daunting task when the matrix size of the solution is large. Motivated by this, we plan to employ rank-one approximation strategy and fast local search optimization technique to study large-scale constrained convex matrix optimization problem. One remarkable feature of our method is that full eigenvalue decomposition can be avoided. There are three main themes within this proposal. (a) Employ rank-one approximation algorithm to solve the unconstrained matrix optimization problem, and then consider alternating direction method of multipliers to handle the constrained optimization problem. (b) Present a theoretical analysis of the algorithm which converts the contained problem into an unconstrained problem, including the optimality and the accuracy control issue of the unconstrained sub-problem, the convergence and iteration complexity of the constrained master problem. (c) Apply the optimization techniques to other scientific computing problems (e.g. matrix optimization with rank constraint) and other data mining applications (e.g. differential privacy optimization). .Finally, we conduct extensive numerical experiments for the proposed algorithm. Our research results can not only enrich the theory of matrix optimization, but also provide an effective and practical matrix optimization tool for the industrial community..

矩阵优化算法在图像处理、机器学习和数据挖掘等诸多领域中有着广泛的应用。然而，当前最具代表性的矩阵优化算法却是基于特征值分解，当问题规模很大时这仍然是一项非常耗时的操作。有鉴于此，本课题采用秩一近似策略和局部快速搜索技术来开展大规模的矩阵优化算法的研究。这种算法最显著的优点就是能够避免特征值分解。总的来说，本课题研究内容包括（a）采用秩一近似方法求解无约束矩阵优化问题；结合交替方向法求解一般约束的矩阵优化问题（b）进行对有约束转换成无约束问题求解的算法的理论分析，其中包括无约束子问题的最优性条件与精度控制的分析，以及主问题收敛性质与迭代复杂度的分析（c）把该矩阵优化技术拓展到其他的科学计算问题上（如带低秩约束的矩阵优化问题），以及拓展到数据挖掘的应用问题上（如差分隐私问题）。.最后，我们对新算法编写代码和数值实验，该成果不仅能丰富矩阵优化的理论，而且还为工业界提供一种实用有效的矩阵计算工具。

在本项目中，我们主要从在算法设计、理论分析以及实际应用几个方面讨论了矩阵优化问题。我们主要的研究进展、重要结果、关键数据以及科学意义情况主要包括以下六点：.(a) 低秩优化。我们提出了一个高效而且收敛的半正定低秩优化方法，该方法能够精确地求解原来的秩优化问题，我们把它用在传感器网络定位上并取得较好的精度。.(b) 差分隐私优化。我们提出了一个差分隐私约束下的快速准确的矩阵低秩优化模型，该模型可以实现对批线性查询的优化。此外，由于高斯噪音有着旋转不变性的特性，我们提出一个半正定凸优化方法来求解线性差分隐私优化问题，该方法在没有数据先验前提下取得最好的精度，在不违反用户隐私前提下提供数据的最大有用性。.(c) 复合函数优化。我们提出矩阵分块策略来求解复合函数优化问题和多块复合函数优化问题，这些方法都是线性系统经典方法高斯赛德尔算法或坐标下降方法的拓展。我们把这些方法应用到压缩感知和矩阵分解问题上，大量实验表明我们的方法取得了最好的精度和最快的速度。.(d) 稀疏优化。我们把脉冲噪音去除过程建模为一个L0范的优化问题并提出一个互补约束的交替方向法来求解。此外，我们拓展了这项工作来求解广义稀疏约束优化问题，提出精确罚函数方法和自惩罚交替方向法并且严格证明算法的收敛性。.(e) 离散优化。我们把一个(-1,+1)离散优化问题规约为一个等价的双线性双凸问题并提出一个精确罚函数来求解来求解密集子图发现问题。此外，我们进一步系统地完善了我们之前提出的互补约束优化方法并提出自惩罚的交替方向乘子法。.(f) 分解方法。我们把一个稀疏或离散的非凸优化问题分解为许多小规模的子问题，此后通过使用全局优化的非凸优化方法从而实现近似地求解原来的非凸NP难问题。我们证明了算法的收敛性和收敛速度。