一种新参数条件的线性化逐块交替方向乘子法

论文摘要

交替方向乘子法（ADMM）对于求解带有两块变量线性约束优化问题来说,是一种行之有效的方法,在统计学、信息等领域有着很强的应用.但是直接将此方法推广到多块变量的情况时,若无适当假设,算法不一定收敛.由于该算法在相关领域的重要应用价值,近几年关于多块ADMM算法的研究呈增长趋势.其中何炳生等人提出的逐块ADMM算法是一种很好的方法,该方法首先将多块变量分成两组,在求解子问题时,组与组之间采用Gauss-Seidel格式（及时利用新信息）,组内块与块之间采用Jacobi格式（使用老的信息）.该算法兼具Gauss-Seidel格式收敛快和Jacobi格式可并行计算的特点,单步计算量较低,且可保证全局收敛性.但是在原问题没有特殊结构时,对于求解算法的子问题时,可能有点困难.韩德仁等人基于线性化技术提出了对子问题线性化并增加邻近点项的策略简化子问题计算,缩短了计算时间.然而该算法的邻近点项的因子选取通常受每组变量约束矩阵的最大特征值限制,使得算法的收敛速度可能较慢.本文在ADMM算法的基础上,提出一种新参数条件的线性化逐块ADMM算法,改进了韩德仁等人提出算法中的邻近因子,在保持每步计算量不变的前提下加快了算法的收敛速度,并证明了新算法的收敛性.本文具体研究的内容框架安排如下:第一章,主要介绍了论文背景,以及ADMM算法的研究历程.第二章,介绍了新算法需要用到的一些预备知识,以及关于BADMM算法.第三章,我们介绍了本文研究的一种新算法,即改进的线性化逐块ADMM算法.第四章,给出了本文新算法的收敛性分析.第五章,通过数值实验,将两种算法进行比较,验证其中的收敛性.第六章,对本文的研究内容进行总结以及关于ADMM算法的研究展望.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 论文背景
•   1.2 ADMM算法的研究历程
•   1.3 本文内容及结构安排
• 第二章 预备知识
•   2.1 引言
•   2.2 预备知识
•   2.3 总结
• 第三章 新算法
•   3.1 新算法
•   3.2 总结
• 第四章 新算法的收敛性分析
•   4.1 线性化逐块ADMM算法的收敛性
•   4.2 总结
• 第五章 数值实验
•   5.1 实验问题
•   5.2 数值结果
• 第六章 总结与展望
• 参考文献
• 攻读硕士学位期间完成的工作
• 致谢

文章来源

类型: 硕士论文

作者: 纪磊

导师: 申远

关键词: 凸优化,交替方向乘子法,线性化交替方向乘子法,多块,结构型凸优化问题

来源: 南京财经大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 南京财经大学

分类号: O224

DOI: 10.27705/d.cnki.gnjcj.2019.000219

总页数: 34

文件大小: 1301K

下载量: 14