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

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

项目编号： No.11471088

项目类型： 面上项目

立项/批准年度： 2015

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

项目作者： 边伟

作者单位： 哈尔滨工业大学

项目金额： 72万元

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

中文关键词： 非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.

英文关键词： Non-Lipschitz optimization;Sparse reconstruction;Iterative algorithm;Dynamic algorithm;Complexity analysis