凸可分离优化问题的原始对偶不动点算法及其应用

摘要

在基于有界变差的图像处理领域,很多问题可以表示为求解两个可分离的凸函数的最小化问题,近年来该问题得到了广泛研究与应用。本文从原始对偶不动点算法的观点提出一系列的算法求解两个可分离的凸函数的最小化问题,问题中一个函数为凸函数和线性变换的复合,一个函数的梯度是Lipschitz连续的.所提出的算法具体包括基于邻近算子的原始对偶不动点算法(PDFP2O)、凸集上的基于邻近算子的原始对偶不动点算法(PDFP2OC)、基于邻近算子和预处理算子的原始对偶不动点算法(PDFP3O)。本研究分为三个部分：
　　⑴在基于邻近算子的前向后向算子分裂算法(PFBS)和基于邻近算子的不动点算法(FP2O)的基础上,首先从直观上得到PDFP2O.然后利用一阶优化条件,通过引入对偶变量,利用邻近算子与次梯度的等价关系,通过两步额外的迭代,可以将提出的算法表示成算子的不动点迭代形式,并因此得到PDFP2O的拓展版本PDFP2Oκ.利用邻近算子的强非扩张性,在特殊构造的范数的帮助下,证明了PDFP2Oκ的收敛性.在稍强的条件下,进一步给出了算法PDFP2Oκ的收敛速度.接下来,通过等价变形,进一步解释了算法PDFP2 O,并给出了与其他已有算法的联系和区别.最后通过关于图像放大、CT重构、并行核磁共振成像的数值实验说明了算法的有效性.总体来说,PDFP2O的性能和当前顶尖的算法的性能是可比较的,而PDFP2O的参数的选择相对容易,这在求解具体的实际问题中是很有意义的。
　　⑵对于很多实际问题,根据不同的物理背景,解的取值都有一定的限制.所以,进一步考虑求解带凸集约束的可分离凸优化问题.通过将凸集的约束表示成示性函数而加入目标函数中的技巧,适当重新组合,可直接利用PDFP2O求解,利用函数的可分离性,得到PDFP2OC.因为PDFP2OC本质上就是利用PDFP2O求解与原问题等价的无约束优化问题,根据PDFP2O的证明结果,可以方便的得到PDFP2OC的收敛性以及收敛速度.在解位于凸集内部的假设条件下,利用示性函数的邻近算子为投影算子,类似于PDFP2 O的推导,通过算子的不动点迭代得到求解解位于凸集内部的可分离凸优化问题的基于邻近算子的原始对偶不动点算法(PDFP2OC0).利用投影算子也是强非扩张算子的性质,并利用PDFP2O的证明结果,得到PDFP2OC0的收敛性以及收敛速度.一般来说,算法PDFP2OC具有很好的通用性,算法PDFP2OC0只适用于解位于凸集内部的情形,但其迭代形式更简单、直观.最后通过CT重构和并行核磁共振成像说明了算法PDFP2OC和PDFP2OC0的有效性。
　　⑶从收敛速度的估计中,以及CT重构的数值实验结果中,可以看出PDFP2O的收敛速度和相应矩阵的条件数有关,当其中一个矩阵的条件数变差时,PDFP2O的收敛速度会变慢.所以,进一步考虑利用预处理算子来加速,提出PDFP3O.类似于PDFP2O的推导,通过额外引入两个预处理算子可以得到PDFP3 O.通过引入另一个特殊构造的范数,类似于PDFP2 O的证明,可以证明PDFP3 O的收敛性与收敛速度.并进一步将PDFP3O与精确Uzawa、不精确Uzawa算法和非线性不精确Uzawa算法比较,并利用不动点算法框架导出这些算法.最后,通过第二类椭圆变分不等式中的两个实例,说明当问题条件数较差时,PDFP3O的确优于PDFP2O.在简化的摩擦问题中,根据一阶优化条件,将退化的问题转化为非退化的问题;根据新问题中的迭代矩阵的内蕴性质,给出了选择预处理矩阵的方法.在管中的粘塑性流体问题中,尝试采用共轭梯度法获得预处理矩阵的效果。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景和意义

1.2 研究现状

1.3 本文的主要工作

1.4 一些常用记号

第二章 基于邻近算子的原始对偶不动点算法（PDFP2O）

2.1 预备知识

2.2 PDFP2 Oκ的导出

2.3 收敛性

2.4 收敛速度

2.5 算法的等价形式及与其他算法的联系

2.6 数值实验

2.7 结论与讨论

第三章 凸集上基于邻近算子的原始对偶不动点算法（PDFP2 OC ）

3.1 PDFP2 OC的导出

3.2 PDFP2 OC 0的导出

3.3 收敛分析

3.4 数值实验

3.5 结论与讨论

第四章 基于邻近算子和预处理算子的原始对偶不动点算法（PDFP3O）

4.1 PDFP3 O的导出

4.2 收敛性

4.3 收敛速度

4.4 与Uzawa算法的联系

4.5 数值实验

4.6 结论与讨论

总结与展望

参考文献

致谢

在学期间的研究成果及发表的论文