关于交替方向乘子法一些问题的研究

发布时间：2020-09-11 20:07

　　 由于目前数据呈爆炸性增长,原有的机器学习算法已无法应对新的挑战.然而,分布式算法是解决大数据问题的一个有效方法.因此,将分布式算法和传统的机器学习算法结合是很有必要的.交替方向乘子法(ADMM)是一个优秀的分布式算法,本文的研究正是基于ADMM的一些分布式算法,我们研究该算法针对l_1问题的最优步长、分布式支持向量机的ADMM算法和在线的分布式支持向量机的ADMM算法.具体内容如下:1.ADMM算法已经成为求解大规模优化问题的有效方法.尽管已经有较多的关于该算法收敛性的研究,但关于该算法参数对收敛性的影响仍然需要进一步的研究,在实验中参数通常是经验性的选择.本文研究基于ADMM算法l_1正则最小问题的最优步长.我们发现Lasso的解用软阈值算子表示后,软阈值的三种情况可以转化为算法收敛因子的两种情况,然后通过最小化收敛因子可以解出最优步长.数值仿真实验表明,应用该方法选出的步长,其算法的收敛速度明显快于其它情况.此外,我们将该方法应用到压缩感知问题,给出一个计算最优步长的近似值策略,获得了较好的实验结果.2.众所周知,支持向量机是一个有效的机器学习算法,针对大数据,我们提出了master-slave网络模型下的分布式SVM算法(MS-DSVM).该算法结合了分布式ADMM算法和SVM算法,该网络结构下master节点和slave节点相连,传递计算结果.分布式SVM可以看作是一个正则化优化问题,ADMM算法把原问题分解成一系列的子问题求解,最后合并得到全局解.我们引入了过松弛技术增加所提出算法的收敛速度.理论分析显示:本文提出的MS-DSVM算法具有线性收敛速率,这也是现有分布式ADMM算法中最好的结果.实验结果也表明该算法的收敛速度和分类准确率都好于现有的方法.3.在现实世界中,很多任务是需要实时计算的,传统的批量处理算法无法胜任.因此我们提出基于ADMM算法的在线分布式SVM算法,通过对数据矩阵引入时间参数,对MS-DSVM算法做修改,得到在线的MS-DSVM算法.其中数据的流入随时间变化,流入节点的方式也没有限制,即任意节点在任意时间可以接受任意量的数据,实验显示在线的算法对数据的变化做出了及时且正确的回应,对实时数据具有较好的分类结果.
【学位单位】：中国计量大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP181;O224
【部分图文】：

大数据已是研究热点.图1.1是百度指数中“big data”的热搜趋势图,从中可以清楚的看到,人们对大数据的高关注度从未下降.图1.1百度指数中Big Data的热搜度.大数据的产生与存储方式也给现有的机器学习方法带来了巨大挑战,比如现在的数据规模远远超越了单机的容量.所以,数据往往采取分布式存储的方式,而集中处理分布式数据会产生巨大的额外开销,因此,传统的算法不再适用.于是

大数据分析的一般框架.

砺圩钣挪匠?此时迭代次数是13,实线是不同步长条件下,算法收敛时所需的迭代次数,实线的最小值正好出现在理论最优步长的位置,说明此时理论与实际相符合.图3.2则是最优步长时对应的收敛因子,纵坐标是原始误差与对偶误差之和.图3.1正则化参数 λ = 1 时的迭代结果. 图 3.2 正则化参数 λ = 1, 步长为最优时的收敛情况.当选取最优的步长时, ADMM算法迭代13次达到收敛,表3.1给出了迭代过程中z的值,此时向量z是3维的,迭代次数为1时z = 0 表示初始值选取零向量. 在后续整个迭代中,z1和z3都不等于零，说明它们是按照(3.15)式的第一种情况更新的, z2在整个迭代中几乎都等于零，说明它是按照(3.15)式第二种更新的,只有一次迭代进行了变化,在如此极端的情况下,图1中的理论最优步长和实际结果也相符,这也基本验证了上一节的理论的正确性.表3.1选取最优步长时,迭代到收敛时的z的值迭代次数1 2 3 4 5 6 7 8z10 0

【相似文献】

相关期刊论文 前10条

1 付强,刘长军;交替方向隐式时域有限差分算法的应用与发展[J];成都信息工程学院学报;2005年01期

2 J.R.Bates,A.Mcdonald,杨世莹;积分多层原始方程的半拉格朗日交替方向隐式法[J];海洋预报;1988年S1期

3 黄康乐;求解二维饱和-非饱和溶质运移问题的交替方向特征有限单元法[J];水利学报;1988年07期

4 吴美娟,M.A.Letchziner;速度、压力耦合方程组的块隐式解[J];华东化工学院学报;1988年02期

5 黄伟祥;;一类非线性发展方程的交替方向格式[J];内蒙古民族大学学报(自然科学版);2006年04期

6 孙敏;徐健腾;时贞军;;一种新的投影型变分不等式交替方向方法[J];工程数学学报;2006年06期

7 刘波,高本庆,薛正辉,胡沥;无条件稳定的交替方向隐式FDTD算法[J];电波科学学报;2002年05期

8 黎丽梅;;交替方向隐式差分法在分数次微分方程中的应用[J];湖南理工学院学报(自然科学版);2012年03期

9 来翔;袁益让;;一类三维拟线性双曲型方程交替方向有限元法[J];计算数学;2010年01期

10 张争茹;带有迁移的疟疾病与疟蚊数学模型的交替方向有限元法及其数值分析[J];生物数学学报;2003年01期

相关会议论文 前10条

1 刘波;高本庆;薛正辉;胡沥;;交替方向隐式FDTD法[A];全国电磁兼容学术会议论文集[C];2001年

2 张宝琳;;交替差分块方法及其差分图[A];中国工程物理研究院科技年报（1998）[C];1998年

3 杨义校;康学净;陶然;;基于交替方向乘子法的分数傅里叶相位恢复算法[A];第十二届全国信号和智能信息处理与应用学术会议论文集[C];2018年

4 张娇娇;丛爽;郑凯;李克之;;进一步改进的交替方向乘子法及其在量子态估计的应用[A];第17届中国系统仿真技术及其应用学术年会论文集（17th CCSSTA 2016）[C];2016年

5 宋万均;张厚;;磁化等离子体ADE-ADI FDTD算法[A];2017年全国微波毫米波会议论文集（上册）[C];2017年

6 张坤;丛爽;;基于交替方向乘子法的在线量子态估计算法[A];第二十届中国系统仿真技术及其应用学术年会论文集（20th CCSSTA 2019）[C];2019年

7 郑忠;胡燕;罗小刚;占贤辉;;基于交替方向隐式差分算法的连铸坯凝固传热模型[A];2008年全国冶金物理化学学术会议论文集[C];2008年

8 王林年;褚庆昕;;二维ADI-FDTD算法的PML[A];2003'全国微波毫米波会议论文集[C];2003年

9 张良;韩立国;刘争光;常傲;;基于压缩感知的交替方向乘子算法恢复地震数据[A];2017中国地球科学联合学术年会论文集（二十一）——专题44：深部资源探测技术与矿集区立体探测[C];2017年

10 王燕;田振夫;魏剑英;;Navier-Stokes方程组的一种四阶紧致交替方向隐式差分方法[A];第七届全国水动力学学术会议暨第十九届全国水动力学研讨会文集（上册）[C];2005年

相关博士学位论文 前10条

1 马宁;发展型方程的高阶正交配置方法[D];山东大学;2006年

2 来翔;几类双曲型方程交替方向有限元分析[D];山东大学;2007年

3 邓定文;高精度交替方向隐式差分法的理论与应用[D];华中科技大学;2012年

4 黎丽梅;分数阶偏微分方程交替方向有限元误差分析[D];湖南师范大学;2013年

5 王慧慧;分布式交替方向乘子法研究[D];南京大学;2017年

6 谢家新;稀疏信号恢复问题的几类算法及应用研究[D];湖南大学;2017年

7 尤燕飞;鞍点问题和约束优化的几个一阶算法[D];南京大学;2015年

8 冯民权;大型湖泊水库平面及垂向二维流场与水质数值模拟[D];西安理工大学;2003年

9 杨晓波;稀疏信号的联合恢复与低秩稀疏恢复的理论及数值方法[D];湖南大学;2017年

10 杨真真;压缩感知重构技术及其在图像融合中的应用研究[D];南京邮电大学;2014年

相关硕士学位论文 前10条

1 王楠;求解多块可分凸优化问题的并行分裂法[D];南京师范大学;2019年

2 陈庆国;关于交替方向乘子法一些问题的研究[D];中国计量大学;2018年

3 李小玉;基于稀疏优化方法的地铁节能时刻表研究[D];北京交通大学;2019年

4 骆江耀;外逼近法和分布式交替方向乘子法在电力系统优化调度中的应用研究[D];广西大学;2019年

5 王吉;泊松噪声下的低秩张量复原[D];电子科技大学;2019年

6 王晔涛;视频去雨的模型和算法研究[D];电子科技大学;2019年

7 陆晨茜;计算几何中经典问题的交替方向乘子解法[D];南京大学;2019年

8 王朵;低秩矩阵优化问题的算法研究[D];河南科技大学;2019年

9 解丽洁;基于交替方向乘子法的二阶总广义变分图像去噪算法[D];吉林大学;2019年

10 徐秋云;分块低秩矩阵回归的线性化乘子交替方向算法[D];北京交通大学;2018年

本文编号：2817115