论文部分内容阅读
二十一世纪的大数据时代中,各个领域涌现的大规模优化问题对传统的优化算法是一个巨大的挑战,稀疏优化逐渐成为研究的热点之一.稀疏优化中非凸稀疏恢复问题的稳定恢复误差界依然有许多亟待研究的内容.传统的优化算法如何用于快速高效的求解稀疏优化问题也是优化工作者很关心的问题. 本论文将从理论、算法和应用三个角度分别研究稀疏优化中相关的问题.其中,第二章研究关于非凸压缩感知问题中的稀疏恢复误差界的估计;第三章研究于大规模e1范数正则化问题的快速二阶算法;第四章研究关于稀疏优化算法在金融投资组合问题中的应用. 更具体的,第二章针对压缩感知中的eq(0<q≤1)最小化问题证明了一个稳定恢复误差界.已有的稳定恢复误差界结果往往依赖一个常数RIC(Restricted Isometry Constant).众所周知的是,给定一个矩阵,计算它的RIC常数本身就是一个十分困难的问题.本章中提出的稳定恢复误差界并不依赖于RIC常数,而是跟一个更加容易计算的矩阵列相关系数有关.研究结果表明,带噪声的eq最小化问题恢复出的最优解与原始最优稀疏信号之间的误差是有上界的,该上界是噪声的常数倍.该结果对原始最优稀疏信号的稀疏度也有相应的要求.为此我们引入了一个参数γ,研究表明该参数可以反映误差向量的稀疏程度.研究结果显示,当γ>2时,非凸eq(0<q<1)模型的稳定恢复误差界要比凸e1模型的稳定恢复误差界更小,同时非凸模型对原始最优解稀疏度的要求也更弱.这在某种程度上表明,非凸eq(0<q<1)模型的信号恢复效果比凸e1模型的恢复效果更好. 第三章提出了一个非精确的临近拟牛顿算法,用于求解大规模的e1范数正则化优化问题.该问题的目标函数由两部分组成,一部分是一个光滑的凸函数,另一部分是e1范数正则化项.算法中用拟牛顿的框架构建一个二次函数来逼近原问题中的光滑项部分,然后用带宽邻域的内点方法来求解每一步得到的子问题.我们采用了Shermon-Morrison-Woodbury公式来降低迭代过程中矩阵求逆的复杂度,并且提出了几项技巧降低迭代过程中的计算误差.证明了所提算法的全局收敛性和局部Q-超线性收敛速度.数值实验表明,与同类算法相比,我们的算法可以更快速的求得一个同等精度的解. 第四章研究一个金融领域的投资组合优化问题.该问题在传统的Markowitz投资组合模型基础上添加了两个约束,一个是加入了行业特征和股票特征的线性不等式约束,一个是股票权重的零范数约束.零范数约束本身的组合特性导致该问题的求解十分困难,同时变量的高维度也使得该问题的求解具有极大挑战性.通过分析该问题的特点,我们设计了三块的交替方向法求解该问题.在子问题求解过程中,针对问题结构设计了相应的非单调投影梯度算法和投影牛顿算法.与cvx中mosek模块比较的数值实验表明,算法可以有效快速的求解该问题.