基于交替方向乘子法和算子分裂的优化算法

论文摘要

具有线性约束和可分结构的凸优化模型在半定规划、图像处理、压缩感知、机器学习等领域应用广泛.如何充分利用问题的可分结构,设计有效且收敛的求解算法是最优化领域的一个热门课题.交替方向乘子法（ADMM）由于简单、易于实现以及适用范围广等优点成为应用最广泛的算法之一,并由此掀起了研究一阶分布式算法的热潮.本文针对三种不同结构的可分凸优化问题,基于ADMM和算子分裂算法基本框架设计一阶算法,并系统研究它们的收敛性、复杂度和数值效率.针对二次半定规划问题提出了一种修正ADMM,求解其具有3分块可分结构的对偶问题.该算法每一次迭代不需要求解二次分块对应的子问题,相比已有的3分块ADMM既节省存储空间又降低了迭代复杂度.通过对偶理论,证明了该修正ADMM的本质是将Davis和Yin提出的three-operator分裂算法应用到原问题.针对具有特殊结构的二次半定规划――H权重最近相关系数矩阵问题,获得了直接推广的3分块ADMM收敛的充分初始条件.最后利用对偶理论平衡原问题和对偶问题误差,设计了自适应动态调节罚参数系统,以获得更好的数值效果.针对含有二次或者线性目标函数的多分块可分问题,基于求解变分不等式的预测-校正框架提出了一种收敛的预测-校正ADMM,并研究了收敛性.在预测步采用对称Gauss-Seidel更新方式产生预测点,然后利用预测点和上一迭代点的线性组合设计具有低复杂度的校正步,以保证算法的收敛性.在至少有一个线性约束的系数矩阵是可逆的情况下,证明了该算法不需要校正步也具有收敛性.应用到图像纹理动画分解问题的数值实验验证了算法的有效性.针对一般的多分块可分问题,通过添加不定临近项线性化子问题的二次项,提出了不定临近线性化对称ADMM.该方法将问题的数据变量分为两组,每次迭代结合使用Gauss-Seidel和Jacobian更新策略,组间变量采用Gauss-Seidel更新方式,而组内变量以Jacobian方式更新,这样的更新对求解大数据问题更有吸引力.通过预测-校正框架研究了临近参数、步长和分块数之间的关系以保证算法的收敛性,并获得了最优临近参数取值.数值仿真实验结果表明,求解统计学习中的拉索回归（LASSO）和稀疏逆协方差估计问题,不定临近线性化ADMM优于已有的一些成熟算法.

论文目录

• 摘要
• ABSTRACT
• 符号对照表
• 缩略语对照表
• 第一章 绪论
•   1.1 应用背景
•   1.2 相关方法的研究现状
•   1.3 预备引理
•   1.4 主要内容与结构安排
• 第二章 修正ADMM求解二次半定规划
•   2.1 二次半定规划及其对偶问题
•   2.2 3分块修正ADMM
•   2.3 3算子分裂解释
•   2.4 进一步推广和扩展
•   2.5 特殊的二次半定规划—-H-权重相关系数矩阵最小化问题
•     2.5.1 直接推广3分块ADMM和2分块sp ADMM的关系
•     2.5.2 保证ADMM3d收敛的充分初始条件
•   2.6 数值实验结果
•     2.6.1 随机产生的二次半定规划问题
•     2.6.2 H-权重相关系数矩阵最小化问题
• 第三章 收敛的预测-校正多分块ADMM
•   3.1 基于预测-校正的ADMM
•     3.1.1 变分不等式问题描述
•     3.1.2 预测-校正ADMM算法设计
•   3.2 收敛性分析
•   3.3 数值实验结果
• 第四章 线性化不定临近ADMM
•   4.1 线性化对称ADMM
•   4.2 预测-校正框架解释
•   4.3 收敛性分析
•     4.3.1 基本性质
•     4.3.2 收敛性分情况讨论
•   4.4 数值实验结果
•     4.4.1 LASSO问题
•     4.4.2 隐变量高斯图形模型选择问题 （LVGGMS）
• 第五章 总结与展望
•   5.1 总结
•   5.2 展望
• 参考文献
• 致谢
• 作者简介

文章来源

类型: 博士论文

作者: 常小凯

导师: 刘三阳

关键词: 可分凸问题,交替方向乘子法,算子分裂法,不定临近项,预测校正框架

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安电子科技大学

分类号: O224

DOI: 10.27389/d.cnki.gxadu.2019.003139

总页数: 110

文件大小: 3383K

下载量: 107