带稀疏约束不适定问题的算法研究

项目名称： 带稀疏约束不适定问题的算法研究

项目编号： No.11471253

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 吕锡亮

作者单位： 武汉大学

项目金额： 70万元

中文摘要： 具有稀疏先验信息的不适定问题在信号处理，机器学习，图像恢复，高维统计数据分析，微分方程参数识别等领域有着广阔的应用。本项目主要研究带稀疏约束的不适定问题，通过Tikhonov型稀疏正则化将不适定问题转化成为非光滑优化问题，并发展半光滑牛顿（或原始对偶积极集）算法来进行求解。该算法在每一步迭代过程中，通过原始变量和对偶变量定义积极集，然后在积极集上求解一个小规模的优化问题得到新的原始变量，并用它来更新对偶变量。因为牛顿型算法具有局部超线性收敛性，并且每一步迭代仅需要求解一个小规模的最小二乘问题，半光滑牛顿法具有很高的求解效率。为了给半光滑牛顿法提供好的初值，同时选取合适的正则化参数，我们对正则化参数使用连续化技术并配合差异原则进行停机。通过对若干具体问题如求欠定线性系统稀疏解或者带稀疏约束的参数识别问题的研究，我们将分析牛顿型算法的局部和全局收敛性，并将其应用于实际工程问题中。

中文关键词： 稀疏约束；Tikhonov正则化；半光滑牛顿法；原始对偶积极集法；参数识别

英文摘要： Ill-posed problem with sparse constraints has been attracted a lot of attentions in signal processing, machine learning, image restoration, statistics and parameter identification in recent years. By sparse regularization, ill-posed problem is transformed into a non-smooth optimization problem. A semi-smooth Newton (or primal dual active set) algorithm is applied to solve it. In each iteration, the active set is defined by the primal variable and its dual variable, then a small size optimization problem on the active set is solved to obtain a new primal variable, and its dual variable is updated. Due to the locally superlinear convergence property of Newton type algorithms, primal dual active set method is very efficient. Combining with continuation strategy on regularization parameter and a discrepancy principle, we can find a good initial guess for Newton method, and choose a proper regularization parameter simultaneously. We will study several typical ill-posed problems with sparse constraints, which include the sparsest solution of a underdetermined linear system, and parameter identification problem with a priori sparse information. The local and global convergences are established. The method can be further applied to real data problem.

英文关键词： sparse constraints;Tikhonov regularization;semismooth Newton method;primal dual active set method;parameter identification