关于约束稀疏优化问题的理论、算法及应用研究

With more and more developments in information science and sparse optimization, unconstrained sparse optimization models, which contain only the sparsity constraint, cannot meet practical needs any more (such as kernel density learning, SPCA, sparse SVM and sparse portfolio selection). Based on the existing theories and algorithms for unconstrained sparse optimization, this project attempts to study theory and algorithms for constrained sparse optimization models, which contain not only the sparsity constraint but also other constraints. Specifically, we shall (1) study optimality conditions for constrained sparse optimization models and derive recovery upper bounds in compressed sensing applications by introducing the concepts of tangent and normal cones and a new definition of RIP condition; (2) work out explicit expressions for the solutions of non-convex projected sub-problems, and then propose fast gradient projection algorithms for solving constrained sparse optimization problems by utilizing suitable line searches. Convergence properties of the proposed algorithms will be analyzed. Then we shall extend the models and algorithms for constrained sparse optimization to constrained sparse matrix optimization problems and constrained group sparse optimization problems; (3) study special applications from kernel density learning, sparse SVM in machine learning and sparse portfolio optimization model in financial optimization by building related constrained sparse optimization models and studying their corresponding basic theory and solution algorithms. The results of the project are expected to lay a foundation on the theoretical analysis, algorithm design and applications for constrained sparse optimization.

随着信息处理技术的飞速发展和稀疏优化研究的深入，仅只考虑含稀疏约束的无约束稀疏优化模型已很难满足实际需要（如：核密度学习、稀疏支撑向量机及稀疏金融投资组合等）。本项目以稀疏优化的实际应用为背景，在深入发展无约束稀疏优化理论与算法基础上，系统研究稀疏约束与其它约束共存下的约束稀疏优化理论与算法。主要包括：（1）借助于切锥和法锥，定义新的RIP条件，刻画约束稀疏优化模型的一阶和二阶最优性条件及其在压缩传感中的可重构上界。（2）推导特殊约束下投影子问题的显式解，设计单调与非单调线性搜索，提出求解约束稀疏优化问题的快速算法，分析其收敛性，并将约束稀疏优化的模型与算法推广到约束矩阵稀疏和约束群稀疏优化问题。（3）应用所发展的约束稀疏优化理论与方法到核密度学习、稀疏支撑向量机与稀疏金融投资组合等约束稀疏优化问题。项目期待在约束稀疏优化的理论分析、算法设计及应用研究等方面做出突破性进展。

本项目以稀疏优化的实际应用为背景，在深入发展无约束稀疏优化理论与算法基础上，系统研究稀疏约束与其它约束共存下的约束稀疏优化理论与算法。截至本报告完成之日，本项目已在国内外期刊杂志上正式发表论文13篇（其中SCI收录10篇），硕士论文5篇。.项目的主要研究成果可以分为如下：.(1) 在约束稀疏优化问题的理论研究方面，主要完成了特殊约束集合下的稀疏优化问题的投影梯度算法设计、收敛性分析及特殊非凸约束集合下的投影问题的显式表达解的研究；在稀疏投影问题显式表达解的推导过程中，巧妙地设计了一套可以确定最优解的最优指标集的方法，其实质是求解满足最优指标集函数值为零的Lagrange乘子；给出了求解带有Lq（q=1/2）正则项的稀疏正则化问题的理论；构建了用于参数估计的稀疏双层规划框架，对其中的特殊情形给出显式表达解，并进行了理论分析。(2) 在约束稀疏优化问题的算法研究方面，主要设计了带有约束非凸稀疏优化问题的投影梯度算法，稀疏线性优化问题的ADMM算法，带有Lq（0<q<1）正则项的稀疏约束问题的高效算法以及同时含有机会约束和稀疏约束的高效求解算法等。数值试验与比较表明，上述算法能有效求解对应的稀疏约束优化问题，在一些适当假设条件下，我们证明了算法的局部收敛性。(3) 约束稀疏优化问题的应用研究主要集中在金融投资组合领域内的应用。首先根据证券市场的实际投资需要，设计了相应的约束条件，并在此基础上建立稀疏指数追踪，超越指数模型和组合调整模型。针对这些模型设计了快速有效的求解算法，建立了一套全新投资策略,模型与算法被陕西景唐投资有限公司，陕西蒙特卡罗投资有限公司等进行实证应用。