几类典型稀疏优化问题的算法、理论及应用

The sparse optimization problem has wide range of applications in image processing, machine learning, gene networks etc. This project aims to study the theory and fast algorihtms for sparse optimization problems and their applications. The main research content includes: (1) Inspired by Newton method in smooth optimization, we will study the nonmonotone spectral gradient method for L1-regularized minimization problems. Using the exact penalty function and variable splitting techniques, we will study the alternating directions method for Lp(0<p<1)-regularized minimization problems. The uncosntrained Lp-regularized model is reformulated as a linear constrained and separable convex minimization problem. Then, an alternating directions method is developed to solve the resulting problem, and it will be proved that the generated iterations converge to the KKT point of the resulting problem. (2) Based on the superiority of the two-step shringkage/thresholding method for recovering a large and sparse signal in compressive sensing, we will study the multi-step shringkage/thresholding algorithms for low-rank matrix optimization. Using the properties of dual norm, we will study the alternating directions method for matrix mixed-norm optimization problems. We will show that each subproblem admits closed-form solutions, and the dual version of the algorithm is superior to the primal one in theory and numerical performance. (3) Based on the linearized technique and proximal points method, we will study the alternating directions method for log-determinant sparse minimization problems. Finally, we will test the practical performance of each proposed algorithm and develop highly efficient software packages.

稀疏优化问题在图像处理、机器学习、基因网络等领域有着广泛的应用。本项目研究几类典型稀疏优化问题的理论、快速算法及应用。主要包括：(1)基于求解光滑优化问题的牛顿法思想，研究求解L1正则化问题非单调谱梯度算法；利用精确罚函数和变量分裂技术，研究求解Lp(0<p<1)正则化问题的交替方向法；无约束Lp正则化模型转化为具有线性等式约束可分离结构的凸规划问题，设计交替方向法求解，理论保证算法迭代点收敛到等价问题的KKT点。(2)基于两步收缩阀值算法在压缩感知稀疏信号重构方面的优势，研究求解低秩矩阵优化问题的多步迭代收缩阀值算法；利用对偶范数的特征，研究求解矩阵混合范数优化问题的对偶交替方向法；对偶算法的子问题的解具有解析表达式，且比原始算法更有理论和数值优势。(3)利用线性化和临近点技术，研究求解对数-行列式型稀疏优化问题的非精确交替方向法。 最后，测试算法求解实际问题的效率并编写相应软件程序。

经过四年的研究，基本完成了各项研究任务并且基本达到了预定各项目标。主要成果包括（1）提出了求解非光滑结构凸优化问题的广义交替方向乘子法；（2）提出了求解图像低秩纹理不变和批量图像重排问题的对称Gauss-Seidel的交替方向乘子法；（3）提出了高维协方差矩阵估计问题的对偶交替方向乘子法；（4）提出求解矩阵混合范数优化问题的谱梯度算法；（5）提出求解对称单调方程组的共轭梯度算法；（6）提出了求解矩阵极大特征值问题的有限记忆BFGS算法；（7）运用K均值聚类方法求解局部自适应Chan-Vese图像分割模型等。项目的研究成果都编写了相应的程序代码，并且比求解此类问题的相关算法提高了效率。项目的研究成果对于压缩感知、机器学习、基因网络等领域有着广泛应用的前景。共发表学术论文16篇，举办（承办）各级别学术会议、暑期夏令营活动5次，培养硕士研究生31人。项目组成员出境学术交流超过10人次，其中5人出境学术访问超过一年。项目研究成果主要发表在如下期刊：Mathematical Programming Computation, Journal of Mathematical Imaging and Vision, Computational Statistics and Data Analysis, Mathematical Methods of Operations Research, Communications in Statistics-Theory and Methods。