矩阵秩最小化问题的逼近方法研究

Matrix rank minimization problem is a kind of problem aiming to minimize the rank of the matrix on a feasible region. It is widely applied in the fields of engineering and scientific computing, such as system control, machine learning, image reconstruction, compressive sensing, etc. But this kind of problem is NP-hard. The general method for solving the above problem is to get the approximation problem of the matrix rank minimization problem by using certain continuous function to replace matrix rank function, to estimate the solution of the original problem by the solution of the approximation problem. In most of the existing methods, the conclusion that the solution of the approximation problem equals to the exact solution of the original problem holds only if some relatively strict conditions hold. In this project, we will construct a series of parameterized smooth functions to approximate the matrix rank function, and formulate the corresponding approximation problems by combining the new approximation functions with some techniques such as equivalent transformation and proper relaxation. The solution of the approxination problem can get close to that of the original problem with arbitrary precision by proper choice of the parameter. By analyzing the structure of the new approximation, we will design the algorithms on the basis of the idea of approximation. The convergence and stability of these algorithms will be discussed. Finally, by analyzing and comparing the different approximation problems of matrix rank minimization problem and the corresponding algorithms, we will further improve the efficiency and the stability of approximation method.

矩阵秩最小化问题是一类以极小化可行域中矩阵的秩为目标的优化问题。它在工程及科学计算领域中有着广泛应用，如系统控制、机器学习、图像重构、压缩传感等，但是此类问题是NP-难的。求解上述优化问题的一般做法是利用某种连续函数来代替矩阵秩函数以得到矩阵秩最小化问题的近似问题，并利用近似问题的解来估计原问题的解。目前已有的方法所求得的近似解普遍需要在相对严格条件下才等于精确解。本项目拟通过一族含参光滑函数来近似矩阵秩函数，并结合等价变换、适当松弛等技巧给出相应的近似问题，再利用参数控制促使近似问题的解逐步逼近原问题的解。此外，在分析新的近似问题结构的基础上，拟设计基于逼近思想的相应算法，并讨论算法的收敛性与稳定性。最后，通过对矩阵秩最小化问题的不同近似问题及相应算法的比较与分析，进一步提高逼近方法的效率与稳定性。

本项目研究的对象是矩阵秩最小化问题，此类问题在工程及科学计算领域中有着广泛的应用，如系统控制、机器学习、图像重构、压缩传感等。自项目开展以来，我们从三个不同方面入手进行研究，第一，直接构造出一族含参光滑函数来近似矩阵秩函数，并结合等价变换、适当松弛等技巧给出相应的近似问题，再利用参数控制促使近似问题的解逐步逼近原问题的解，最后还把此算法有效的应用到了物流管理中。同时，我们也利用交替方向法与正则化相结合的方式来求解此类问题，并得到了相应的理论与数值结果。上述两种方法在求解矩阵秩最小化问题时均可达到较高精度。例如，对于已知数据很少的矩阵恢复问题，我们算法比其它常用方法更容易恢复这个未知矩阵。第二，众所周知，矩阵秩最小化问题可以通过正则化松弛为矩阵最小二乘问题进行求解，因此在本项目中我们对某种有着简单约束的广义半正定最小二乘问题进行研究，并针对其特性设计出求解此问题的类近似点算法。此方法与传统的解半定规划的方法（如内点法）相比，有着更高的效率与更好的精度。第三，对于某些与矩阵秩优化相关的问题，本项目中也做了一定的研究，例如对包含半正定矩阵锥在内的一般锥优化问题的利普希茨误差理论以及流形夹角问题的理论分析。