L1范数正则化连续二次背包问题算法研究

发布时间：2020-06-08 07:39

【摘要】：生活中,优化问题十分常见,力学中的优化更是无处不在.l_1范数正则化连续二次背包问题(CQKPL1)是一类重要的最优化问题,在结构分析、图像处理、压缩传感等领域都具有广泛的应用背景.尤其l_1范数正则化良好的稀疏性早已在计算机领域有较好的应用.对该问题理论和算法的研究早已备受国内外优化领域学者的关注,尤其在工程力学中,成为近年来研究的一个热点问题.本文在以上应用背景下,重点对求解_1l范数正则化连续二次背包问题的算法进行研究,通过数据实验比较几种算法的优劣.论文内容可概括如下:第1章首先介绍了二次背包问题的演化过程和发展历程,介绍了几种常用的求解可分离二次背包问题的算法.第2章在上述的研究背景下,提出了对CQKPL1算法进行研究.通过对模型的子问题及含参量问题的分析将该模型转化为求解方程根的问题并在此基础上提出三种求解算法.第3章提出改进二分法,算法首先对断点进行分类,其次对包含断点的方程进行二分迭代搜索,同时加入加速迭代的步骤,加快算法收敛,搜索到最优解终止.第4章研究了改进割线法,算法包括两个步骤:步骤1(Bracketing Phase):目的是确定方程根的存在区间;步骤2(Secant Phase):在确定的区间内用割线法搜索方程的根.第5章对改进牛顿法进行讨论,首先引入了Moreau-Yosida正则化的概念将问题显示解进行重新研究,得到更多良好的解析性质.算法中利用改进的导数值得到迭代方向,利用Armijo线搜索产生迭代步长.最后,给出了改进牛顿法的全局收敛性定理,从理论上证明了算法的可行性.第6章对本文提出的三个算法进行数据实验,将实验结果与当前商业中广泛使用的优化器Gurobi和Mosek的结果进行对比,验证本文算法的可行性和高效性.
【学位授予单位】：沈阳航空航天大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O224

【相似文献】

相关期刊论文 前10条

1 吴祈宗;几种分式背包问题的解法[J];北京工业学院学报;1984年03期

2 张立昂,耿素云;多背包问题的计算[J];北京大学学报(自然科学版);1987年01期

3 华中生,张斌;求解可分离连续凸二次背包问题的直接算法[J];系统工程与电子技术;2005年02期

4 宋海洲;魏旭真;;求解0-1背包问题的混合遗传算法[J];华侨大学学报(自然科学版);2006年01期

5 王昌晶;薛锦云;;一类0-1背包问题算法程序的形式化推导[J];武汉大学学报(理学版);2009年06期

6 樊小毛;马良;;0-1背包问题的蜂群优化算法[J];数学的实践与认识;2010年06期

7 程跃;;多背包问题的一种求解方法[J];产业与科技论坛;2011年20期

8 戴秋萍;马良;郗莹;;求解0-1背包问题的细菌觅食算法[J];数学的实践与认识;2013年03期

9 马绍汉;一类背包问题的可解性[J];山东大学学报(自然科学版);1985年04期

10 刘朝霞;;求解0-1背包问题的两种算法设计[J];阴山学刊(自然科学版);2014年03期

相关会议论文 前6条

1 乔善平;朱波;赵玲;;基于移动Agent的0-1背包问题分布式求解[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

2 高尚;;背包问题的分布估计算法[A];2013年中国智能自动化学术会议论文集（第五分册）[C];2013年

3 徐俊杰;忻展红;;粒子群优化在0/1背包问题中的应用[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

4 姜宇;苏中滨;郑萍;;求解O/1背包问题的算法综述[A];黑龙江省计算机学会2009年学术交流年会论文集[C];2010年

5 刘裴寰;姜青山;王备战;史亮;;基于K均值聚类求解多维背包问题的算法[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

6 李伟;吕克伟;;类背包DH问题的比特安全性研究[A];第28次全国计算机安全学术交流会论文集[C];2013年

相关博士学位论文 前2条

1 黄斌超;限制性多重背包问题的研究[D];云南大学;2015年

2 TRUONG KHAC TUNG;[D];湖南大学;2013年

相关硕士学位论文 前10条

1 史如意;带流量约束的星型图背包问题[D];浙江大学;2015年

2 聂大干;森林优化算法的改进及离散化研究[D];兰州大学;2016年

3 包宗藩;风力驱动优化算法及其应用研究[D];广西民族大学;2016年

4 张悦;价值可变的0-1多背包问题模型及其优化算法研究[D];北京交通大学;2017年

5 陈乌吉玛;基于综合背包问题的混合贪婪算法的研究[D];吉林大学;2017年

6 温亚楠;L1范数正则化连续二次背包问题算法研究[D];沈阳航空航天大学;2018年

7 潘夏福;混合蚁群算法求解0-1背包问题[D];厦门大学;2008年

8 朱阅岸;解0-1背包问题的算法比较和改进[D];暨南大学;2011年

9 史今驰;背包问题的实用求解算法研究[D];山东大学;2005年

10 郑杨凡;基于属性论的0-1背包问题算法研究[D];上海海事大学;2005年

，

本文编号：2702754