学位论文 > 优秀研究生学位论文题录展示

求解L1-正则项优化问题的两种算法

作　者: 朱红
导　师: 肖运海
学　校: 河南大学
专　业: 运筹学与控制论
关键词: 稀疏优化压缩感知共轭梯度法交替方向法对偶问题
分类号: O224
类　型: 硕士论文
年　份: 2012年
下　载: 176次
引　用: 0次
阅　读: 论文下载

内容摘要

求解欠定线性方程组在机器学习,信号处理,压缩感知,线性逆问题以及统计推断等领域有广泛的应用.作为稀疏优化的分支,压缩感知问题可通过求解极小化1-范数正则项问题处理.这样得到的问题因其正则项的非光滑性而颇具挑战.本论文提出两种求解压缩感知问题的算法,分别用修正的共轭梯度法和交替方向法求解大规模稀疏优化问题,给出一定条件下算法收敛性定理,并通过数值试验验证算法有效性.第一部分,给出稀疏优化和压缩感知的定义,列出应用稀疏优化求解压缩感知问题的算法的最新研究进展,给出本论文研究的理论基础并列出文中所用到的一些基本概念,符号,定义.第二部分,受Nesterov的光滑化技巧启发,提出一种利用三项结构的Polak-Ribi`ere-Polyak共轭梯度法求解稀疏信号恢复中的1-范数最小二乘问题的算法.每次迭代该算法只需求解三次矩阵-向量乘积运算.算法所应用的理论基础保证了算法的全局收敛性.其次,该算法通过连续性技巧加速,数值试验表明该连续性技巧明显提高了算法的执行效率.算法的执行效果优越于同样使用Nesterov的光滑化技巧和梯度法的NESTA算法.第三部分,分别基于原始模型和对偶模型,提出两种求解包含1-范数正则项和1-范数数据拟合项优化问题的交替方向法.该算法交替地极小化原始问题和对偶问题的增广Lagrangian函数.通过使用一维收缩算子或欧氏投影,所有子问题都存在显式解.算法每次迭代仅需求解两次矩阵-向量乘积运算,从而很容易实现.最后给出一定条件下算法的全局收敛性,并讨论了算法在非负信号复原问题以及赋权值的正则项极小化问题中的应用.数值试验说明该算法优于著名的YALL1算法.最后,给出本文的总结,并提出一些值得继续探讨的方向.

全文目录

摘要  4-5
ABSTRACT  5-9
第一章绪论  9-19
  §1.1 稀疏优化  9-10
  §1.2 压缩感知  10-13
    §1.2.1 压缩感知  10-12
    §1.2.2 经典算法  12-13
  §1.3 Nesterov的光滑化技巧  13-14
  §1.4 三项结构的PRP共轭梯度法  14-15
  §1.5 交替方向法  15-16
  §1.6 本文主要工作  16-19
第二章基于光滑化技巧和共轭梯度法的算法  19-27
  §2.1 引言  19
  §2.2 MPRP算法和收敛性分析  19-21
    §2.2.1 MPRP算法  19-20
    §2.2.2 收敛性分析  20-21
  §2.3 连续的MPRP算法  21
  §2.4 终止条件  21-22
  §2.5 数值实验  22-27
    §2.5.1 比较算法MPRP和MPRPμ  22-24
    § 2.5.2 比较算法MPRP和NESTA  24-27
第三章求解ll_1-l_1-范数极小化问题的原始对偶交替方向法  27-41
  §3.1 引言  27
  §3.2 PADM L1L1算法和收敛性分析  27-31
    §3.2.1 PADM L1L1算法  27-30
    §3.2.2 收敛性分析  30-31
  §3.3 DADM L1L1算法和收敛性分析  31-33
  §3.4 数值实验  33-41
    §3.4.1 带有脉冲噪声的信号  34-37
    §3.4.2 非负原始信号  37-38
    §3.4.3 赋权值的正则项  38-41
第四章总结  41-43
参考文献  43-49
致谢  49-51
附录 (攻读硕士学位期间发表的学术论文及参与的科研项目)  51-52

求解L1-正则项优化问题的两种算法

内容摘要

全文目录

相似论文