约束Lp正则化问题算法及应用

The Lp regularization problem has wide range of applications in image processing, data mining, finance etc. It is an important tool for finding sparse solutions of some linear and nonlinear problems. When 0<p<1, the Lp regularization problem is nonsmooth and nonconvex. It is even NP-hard. On the other hand, the Lp (0<p<1) regularization can get sparser solution of the problem than the case of p>=1. The L1/2 regularization is a representative problem in Lp (0<p<1) regularization. This project further studies numerical algorithms for solving Lp regularization problems. We will pay particular attention to the unconstrained and constrained L1/2-regularization problems. We will study both unconstrained and constrained problems via two parths. One is to design algorithms based on the problem itself. The other is to design algorithms based on its equivalent constrained optimization problem. By the use of the special stucture of the problem, we will try to develop algorithms that are very welcome in the solution of smooth optimization problems. Our purpose is to design more efficient and robust algorithms. We will also study the applications of Lp regularization in image processing, data mining, finance and so on. We will try to design algorithms based on the special characteristics of the problems. We will also do some practical applications of the Lp regularization and hope the designed numerical algorithms are efficient for those problems.

Lp正则化问题在图像处理、数据挖掘、金融等领域有广泛的应用。该问题是求解某些线性与非线性问题稀疏解的重要途径之一。当0<p<1时，Lp正则化问题是非凸非光滑问题，而且，目标函数不是Lipschitz连续的。此时问题是一个NP难问题。另一方面，当P<1时，Lp正则化问题的解比p>=1时的解更稀疏。p=1/2时的Lp正则化是Lp(0<p<1)问题的一个代表性问题。本项目进一步研究Lp正则化问题的数值算法。侧重于对无约束和约束L1/2正则化问题的算法。拟研究基于问题本身的算法以及基于等价转换的约束最优化问题的算法。在求解光滑最优化问题的成熟的算法的基础上，结合Lp（L1/2）正则化问题的特点设计算法，力求所得到的算法比已有算法高效、鲁棒。同时，研究Lp正则化问题在某些实际等领域中的应用。拟结合实际问题的特点探索求解这些实际问题的有效算法。

项目按照申请书计划进行，在Lp正则化的理论和数值算法及其应用方面取得了如下成果：1. 研究了Lp正则化问题的几个理论问题：获得了约束Lp正则化问题解的最优性条件（必要条件、充分条件）. 该条件是通常约束最优化问题的最优性条件的一种自然推广和补充. 导出了一个保证Lp范数极小化模型重构原始信号的充分条件，该条件比常用的p-RIP 条件弱，研究了具有部分稀疏性质或部分可压缩性质的信号重构问题中的 RIP 性质；2.在求解Lp正在化问题的数值算法方面：首先将L1/2正则化问题转化为等价的光滑约束最优化问题，在此基础上提出了求解问题的一种可行下降算法并建立了收敛性理论；将求解大规模最优化问题数值效果较好的BB算法加以改进，应用与求解L1/2正则化问题，证明 了算法的收敛性；结合积极集技术，还研究了求解L1正则化问题的一阶算法；3.研究了某些实际应用问题，研究了L1/2正则化问题在特征选取方面的应用，还研究了车辆路径问题，随机博弈问题以及具有参数不确定性的线性中立型时变时滞系统的鲁棒稳定性等。.此外，还研究了优化界关注的稀疏拟Newton算法和张量计算问题。取得了好的研究成果。. 项目所获得的理论结果是已有结果的改进或重要推广；所提出的算法都进行了数值检验，具有好的数值效果。