非Lipschitz优化问题的理论算法研究及其在稀疏解还原问题中的应用

Non-Lipschitz optimization is an important and difficult optimization problems, which has wide applications in the sparse reconstruction. By the non-Lipschitz property of the objective function, theoretical and algorithmic research on this kind of problems is just the beginning with no general method. Based on the nonsmooth analysis and optimization theory, this project focuses on a class of nonsmooth non-Lipschitz optimization problems with general constraints and explores the geometric algebraic properties of the optimizal solution by the space and algebra techniques. In theory, we find the equivalent model of the problem, which can be solved in polynomial time, and extend the ?ojasiewicz inequality around the optimal solution of it, which help us establish the intrinsic relationship between the considered non-Lipschitz optimization model and the sparse reconstruction problem. In algorithm, the key study is on the complexity and convergent rate analysis, which includes designing the first and second order iterative algorithm with the worst-case complexity analysis, and the dynamic algorithm with the stability and convergent rate result. In application, we enrich the theoretical analysis and improve the optimization algorithms for three kinds of particular practical problems. For non-Lipschitz optimization, the research of this project has the breakthrough in theory, the innovation in algorithm designing, and the theoretical and algorithmic improvement in application.

非Lipschitz优化是一重要且复杂的优化问题，其在稀疏解还原等问题中具有广泛应用背景。鉴于目标函数的非Lipschitz性质，此类问题的理论与算法研究才刚刚起步，目前尚无统一的处理方法。 本项目立足于带有一般约束的非光滑非Lipschitz优化问题，以非光滑分析、最优化理论为基础，以空间、代数等手段挖掘此类问题最优解附近的几何代数性质。理论上，建立其与稀疏解还原问题的直接联系；寻找与其等价的多项式时间可解模型；推广其最优解附近的Lojasiewicz不等式。算法上，着重研究此类问题算法的复杂性和收敛速率，设计带有最坏复杂性分析的一阶与二阶迭代算法；建立带有稳定性分析和收敛速率估计的动态算法。应用上，针对三类具体应用问题的特殊模型，丰富理论研究并改进优化算法。 本项目的研究既对非Lipschitz优化问题有理论研究上的突破，又有算法设计上的创新，更有应用上理论与方法的改进。

非凸、非Lipschitz 优化是重要且复杂的优化问题，在许多实际问题中有着广泛的应用背景。本项目以非光滑分析、最优化方法、微分动力系统分析为理论基础，对几类带有约束的非凸、非Lipschitz连续优化问题，开展了理论、迭代算法、动态算法及相关系统动力学性质的研究，取得了一定的研究成果。主要研究成果包括（1）论证了带有非凸正则项优化问题最优解的下界性质、必要性最优条件和一般情况下的计算复杂性；对带有基数正则项的优化问题提出了精确的连续松弛模型，并建立了序列收敛于其局部最优解的迭代算法；（2）对一类图像还原问题中的非Lipschitz连续优化模型，建立了具有最坏复杂性分析的二次正则化算法；分别对带有连续非凸正则项和基数正则项的优化模型，建立了带有外插项的加速算法，并在一定条件下论证了算法的R线性收敛性；（3）分别对带有lp(0<p<1)范数罚和基数罚的稀疏优化模型，设计了具有收敛性分析的动态算法；对几类带有不同约束条件的实变量和复变量的非凸但伪凸的优化模型，建立了避免罚参数估计、具有全局收敛性的动态算法；对一类分布式优化问题，建立了动态算法的理论与分析；（4）分别对非线性微分包含系统、半线性微分包含系统、带有脉冲且分布时滞的微分包含系统，建立了其解轨线的周期性、生存性、稳定性等理论。. 本项目的完成对非凸、非Lipschitz优化问题，不仅建立了一套更完善的理论分析体系，而且从迭代算法与动态算法两方面丰富了其算法研究，还从动力系统的理论研究出发，为优化问题算法的设计和分析提供了新的理论基础和设计思路。