高维约束最小二乘问题的快速稳健算法设计及应用

Many real problems in big data analysis can be modeled as high-dimensional constrained least squares problems. Due to the high-dimension of the decision vector, the complex constraints, and the nonsmooth nonconvex regularization terms, it is a challenge to design fast and robust algorithms for solving such problems. Based on the demand from the real applications, we plan to do the following research work. (1) Investigate the duality theory, the smoothing approximation theory, and the optimality conditions, with respect to the concrete nonsmooth nonconvex constrained least squares problems. (2) Design algorithms like smoothing projected Newton method, the projection method on nonconvex sets, and so on. Guarantee that the algorithms are globally convergent, fast and robust. Provide computational complexity analysis of the algorithms. (3) Study the automatic adjustment of the regularization parameter in the high-dimensional constrained least squares problems arising from data mining and image processing. Solve the problems using the designed algorithms and provide effective software for the real applications.

大数据分析中的许多实际问题可归结为高维约束最小二乘问题。鉴于它具有决策变量维数高、约束复杂、正则项非凸非光滑之特点，使得设计快速稳健的算法并能够应用到实际问题变得具有挑战性。本项目拟紧密结合实际问题的需求，展开如下研究。（1）针对具体的非凸非光滑高维约束最小二乘模型，研究其对偶理论、光滑逼近理论和最优性条件。（2）设计求解这些模型的光滑投影牛顿算法、非凸集上的投影算法，使之具有全局收敛性、快速稳健性，并给出算法的计算复杂度分析。（3）针对数据挖掘和图像处理中的高维约束最小二乘问题，研究正则参数的选取，利用设计的算法求解，编写实用有效的数值软件。

本项目针对高维约束最小二乘问题的算法展开了三方面的研究工作。（一）针对投资组合中的指数追踪问题，在经典高维最小二乘的基础上,给出了带禁止卖空约束的赋权 l_2-l_p (0<p<1) 正则项的稳健稀疏投资组合模型，分别用以得到更好的样本外表现、减少交易费用和考虑禁止卖空约束。我们利用光滑投影梯度方法求解此带单纯形约束的非凸非Lipschitz模型，证明了该方法产生的任何聚点都是一个特殊的极限稳定点。（二）对一般的线性约束的非凸非Lipschitz优化模型提出一个新的光滑积极集方法。该方法的每一次迭代，利用固定的光滑因子的光滑化函数逼近原先的非Lipschitz连续的目标函数，再用一个新的积极集方法求解光滑逼近最小化问题，直到满足一个特定的光滑因子更新准则。由于求解光滑优化问题的新的积极集方法会使得算法所得序列的投影梯度至少一个子序列趋于零，因此光滑因子的更新准则在有限步一定能得到满足。证明了光滑积极集方法的任何聚点都是与所使用的光滑函数相关的稳定点，是原问题局部最优解的必要条件。对于l_2-l_p稀疏优化模型，该光滑积极集方法产生的任意稳定点都是极限稳定点，并在一个二阶条件下是局部极小值点。在大规模3D超谱图象解混这一实际问题中，利用我们的光滑积极集方法求解带线性约束及正则项的变量为矩阵的高维最小二乘问题作为模型。数值实验表明模型和算法的有效性和高效性。（三）探讨了带稀疏约束的逻辑回归问题（SLR），该模型被广泛应用到神经网络、深度学习和生物信息等领域的分类和特征选择中。提出了一种贪婪投影梯度-牛顿法（GPGN）求解稀疏逻辑回归问题。下面的特征表明该方法不仅有优美的理论结果，而且有很好的数值表现: 1）GPGN方法产生的整个迭代序列在较弱的条件下收敛到SLR的全局/局部最小值点；2）GPGN方法在有限步内能找到最优支撑集，从而保证了局部二次收敛性；3）数值实验表明与一系列当前最先进的求解方法相比，该方法能够获得更高的精确度和更快的计算速度。