结构稀疏优化的最优性理论与算法

Structured sparse optimization is an optimization problem with group structured feature, which plays the core role of the mathematical model in the fields of signal and image processing, pattern recognition, gene expression data, etc. However, it is a non-convex and non-continuous optimization with special structure. This project aims to study the optimality condition and algorithm for the structured sparse optimization in three aspects: (1) the investigation of the variational properties, including subdifferential, F-conjugate, hard thresholding operator; (2) the derivation of the tangent cone, normal cone and second-order tangent set of the structured sparse set, the establishment of the first-order and second-order optimality conditions; (3) the design of an iterative hard thresholding algorithm to solve the problem and development of the theoretical analysis and numerical experiments. This project is scientific significant and extremely valuable, not only for sparse optimization theory, but also for effective algorithm.

结构稀疏优化是指带有群结构稀疏特征的优化问题，在信号与图像处理、模式识别、基因数据表达等领域的实际应用中扮演着核心数学模型的角色。然而它是一个带有特殊结构的非凸非连续优化问题，传统优化理论与算法面临极大挑战。本项目拟开展结构稀疏优化问题的最优性理论与算法研究，主要内容包括：(1)研究结构零范数的变分性质，包括次微分、F-共轭、硬阈值算子等；(2)导出结构稀疏集的切锥、法锥和二阶切集，建立该问题的一阶二阶最优性条件；(3)设计求解该问题的一类硬阈值迭代算法，并进行理论分析和数值实验。本项目的实施不仅能够进一步完善稀疏优化理论，而且能够提供一类有效算法，具有重要的科学意义和实用价值。

结构稀疏优化在信号与图像处理、模式识别、统计等领域备受关注，广泛应用于神经成像、基因数据表示、生物信息学等多个领域。结构稀疏优化是带有特殊结构的稀疏优化问题。本项目根据不同的实际问题，研究不同结构的稀疏优化问题的最优性理论和算法。同时将相应的理论结果进行推广，并应用于解决实际问题，取得了较好的研究成果。主要包括：（1）研究组稀疏问题不同模型的最优性条件以及解的关系。针对矩阵行选择问题，研究三个常见涉及行零范数的优化模型的最优性条件和最优解之间的等价关系；针对带有多面集和广义椭球约束的组稀疏极小化问题，研究其水平折叠凹松弛问题和相应罚问题的最优性条件，分析上述问题解的关系，设计光滑化算法求解水平折叠凹松弛罚问题，将算法应用于稀疏图像恢复证实算法的有效性。（2）研究一般稀疏问题的二阶算法。针对零范数正则问题，设计牛顿型算法，证明算法在一定条件下具有二阶全局收敛速度；针对稀疏线性互补问题，将问题转化为零范数约束优化问题，设计牛顿硬阈值追踪算法并证明算法的二阶收敛性。（3）研究结构稀疏优化问题的二阶算法。针对0/1损失函数正则问题，研究其最优性条件并设计光滑的牛顿算法，将算法应用于机器学习和1-bit压缩感知，该算法大大提高了计算的效率与精度，为算法应用于实际问题提供了理论保证。上述研究成果不仅丰富了传统的优化理论与方法，特别是非凸非光滑优化的理论与算法的研究，而且在信号与图像恢复，机器学习等带有稀疏特征的实际问题中有重要应用，兼具理论研究意义与实际应用价值。