压缩感知和稀疏优化中的非凸优化算法设计

In Big Data Era, the demand for compressing, saving and recovering large amount of data has been becoming stronger and stronger. Designing efficient models and algorithms based on the "sparsity" of big data has played a key role in many problems, such as compressed sensing in engineering, protofolio management and optimization in economics and business management, bridge estimator in statistics. It has been developed to an important new field in operations research and optimization theory: sparse optimization. Our proposal plans a further discussion on a classical model in this subject: L2-Lp Model. In this proposal we provide some potentially different approaches, try to deliver detailed possible techniques in implementation, and forcast its possible applications in real situation.

大数据时代对海量数据的压缩，储存和恢复提出了更高的要求。因此，根据大数据的稀疏性特点，设计相关的模型和算法，成为当前在工程的压缩感知，经济与管理学的资产管理与优化，统计学的桥估计量的重要问题。也成为运筹与优化理论中一个新的方向，稀疏优化。本申请书提出了对此类问题常见的一个模型，L2-Lp模型的深入理论探讨。并为此类非凸优化问题如何寻求近似最优解（KKT近似点），提出了一些新的不同于以往的算法，并对算法的具体实施中的技巧进行了探讨，也对此类稀疏算法在实际问题中的可能应用做了前景预测。

过去五到十年，大数据和人工智能的兴起成为科学界的主要趋势，大规模优化理论，算法和应用起到了至关重要的作用。本研究项目主要关注和研究了大规划优化理论的几点。.第一，对热点问题，基本回归模型结合罚函数下结果的稀疏性和计算的复杂性。第一次给出了岭回归模型的对数级别收敛算法（局部KKT点），发表在Math Prog上，彻底证明了对于一切非减凹函数的惩罚项，问题都是强NP难级别，发表在AI顶级会议ICML上。.第二，对随机稀疏图模型做了深入分析，并应用于器官移植模型上，对目前病患常用的链式法则和圈式法则做了困难分析，首次实现了真实规模下的理论指导，发表在运筹学旗舰Operations Research上。.第三，项目按照进展做了一定的调整，将注意力放在了大规模数学规划求解器开发的重要任务上。至今已经发布了国内首个线性规划求解器LEAVES，其可以解决五十万变量以下问题。发布的LEMO求解器能够在普遍性的AI模型，如回归，分类模型上，比TensorFlow等国际知名平台快50倍（单机版）。.第四，对二次规划，鲁棒优化，在线优化等多个相关问题做了研究，发表了多篇论文。.总结发表了七篇论文，其中OR，MP，ICML，分别为为运筹学，数学规划，人工智能领域的旗舰级期刊或会议论文，获得了Machael Jordan等国际泰斗级学者等引用和注意。主导的并行优化实验室建设的开源算法平台带动了我国第一个开源的数学规划求解器平台建设。