解变分不等式与不动点问题的一种修正的惯性投影算法_陈晶晶.pdf

山东大学学报（理学版）年 月 第 卷 第 期：（），：山东大学科技期刊社版权所有：收稿日期：；网络出版时间：网络出版地址：基金项目：国家自然科学基金资助项目（）；榆林市科技计划项目（）第一作者简介：陈晶晶（），女，硕士研究生，研究方向为非线性泛函分析：通信作者简介：杨延涛（），男，副教授，硕士生导师，研究方向为非线性泛函分析：文章编号：（）：解变分不等式与不动点问题的一种修正的惯性投影算法陈晶晶，杨延涛（延安大学数学与计算机科学学院，陕西 延安）摘要：提出了一种修正的惯性投影算法，用以寻找伪单调变分不等式问题的解集与带有半压缩映射的不动点集的公共元，在 连续及自适应步长的条件下，证明了由该算法所产生的迭代序列强收敛于某公共元。最后，用数值实验验证了该算法的有效性。关键词：伪单调变分不等式；不动点；惯性收缩投影算法；半压缩映射；强收敛中图分类号：文献标志码：引用格式：陈晶晶，杨延涛解变分不等式与不动点问题的一种修正的惯性投影算法 山东大学学报（理学版），（）：，（，）：，：；引言设 为实的 空间，和分别表示 中的内积和范数，为非空闭凸子集，：是一给定的映射，经典变分不等式问题（，）就是寻求一点，满足不等式（），。如果：是一单调映射，即，则称变分不等式问题为单调变分不等式。如果映射：满足（）（），则称：是非扩张映射。设：是非扩张映射，不动点问题就是寻求一点，满足（）。记（）为 的不动点集。第 期陈晶晶，等：解变分不等式与不动点问题的一种修正的惯性投影算法 变分不等式与不动点问题的公共解为：求，使得（）且（），。变分不等式模型最初来源于对物理学问题的研究，其理论如今已广泛应用于数学规划、运筹学、非线性优化理论、微分方程和交通运输等领域，也是求解许多应用科学问题的有力工具之一。此外，国内外许多学者也深入研究变分不等式问题的解集与不动点集的公共元问题，其原因在于这类问题可以解决图像恢复、信号处理、网络资源分配等实际问题。年，和 提出了一种求解变分不等式与不动点问题公共元的超梯度算法，迭代形式为（），（）（），其中步长，|，（，）。映射算子：是单调且 连续，映射算子：是非扩张且公共解集非空的条件下，证明了由迭代算法生成的序列弱收敛到变分不等式与不动点问题的公共元。年，等提出了一种求解变分不等式与不动点问题公共元的收缩投影算法，迭代形式为（），（，）（）（），（，），（），|其中，（，）（，），若（，），若（，），|步长，（，）。在映射算子：是单调且 连续，映射算子：是非扩张且公共解集非空的条件下，证明了由迭代算法生成的序列弱收敛到变分不等式与不动点问题的公共元。文献需在每一次的迭代循环中计算 次到闭凸集 上的投影，由于每次计算到 上的投影都需耗费大量的时间，为了避免较大的计算量，文献减少向可行集 的投影，仅需计算一次到 上的投影，体现了计算量较小的优势。文献介绍了一种隐式离散化方法，该方法来源于 对重型球系统的研究，它的主要特点是每个新迭代点的生成都由前 个迭代点所确定。惯性类型算法便由此产生，该算法加快了收敛速度，也受到了越来越多学者的关注。其中文献提出了一种求解单调变分不等式的惯性收缩投影算法，证明了算法的弱收敛性定理。文献 提出了一种求解单调变分不等式的惯性收缩投影算法，证明了算法的强收敛定理，修正了文献的结论。最近文献引入了一种 半压缩映射，给出了一种改进的次梯度超梯度算法，得到了算法的强收敛结果，使得算法较文献更具有效性和实用性。本文受文献的启发，提出了一种修正的惯性投影算法，即在文献所提算法的基础上，选取了自适应步长，引入了惯性项和粘性项，并将单调映射算子减弱为伪单调映射算子，非扩张映射算子推广为 半压缩映射算子。由此，扩大了算法的适用范围并加快了收敛速度，推广了文献与不动点问题的应用，且收敛速度较文献更快。最后，通过数值实验验证了理论结果。预备知识设 为实 空间，中的内积和范数分别表示为，和。用 表示序列弱收敛到，表示序列强收敛到。设 为 中的非空闭凸子集，则，中存在唯一的最近点，山 东 大 学 学 报（理 学 版）第 卷用（）表示，即（），。定义 在原点是次闭的：假设：为非线性算子并且（），若对，满足 且（），则有（）。定义 对映射：称为（）连续，如果存在常数，满足，；（）单调的，如果，；（）伪单调的，如果，；（）弱序列连续的，如果对任意的序列弱收敛到，则有序列弱收敛到。注 在定义（）中，如果，），则称映射：是压缩的。定义 算子：称为 半压缩映射，如果存在常数，对，（），满足（），或，或，。引理 设 为实的 空间，则：（），；（）（）（）（），。引理 设 为 中的非空闭凸子集，对于距离投影：，有（）（），（），；（）（）（），（）（），。引理 设为非负实序列，且存在子序列使得 对 都成立，则存在非递减序列 使得，当 充分大时满足如下性质：和，事实上 是集合，中满足 的最大数。引理 设和为非负实序列且（，），如果存在序列，当 时使得（），成立，则有。引理 假设：是 半压缩映射的满足（），令（），其中 是恒等映射，（，），则有（）（）（）；（）（）（），（）；（）（）是一个闭凸集。主要结果假设以下条件成立：（）算子：是 连续的伪单调映射，并且在 上是弱序列连续；（）算子：是 半压缩映射以及 在原点次闭；第 期陈晶晶，等：解变分不等式与不动点问题的一种修正的惯性投影算法 （）算子：是 压缩映射，压缩参数，）；（）（）（，）；（）设为正序列，使得 ，其中序列（，），序列（，），其中。算法 步骤 选取初始点，（，），令，计算（），其中，|（，）；（）步骤 计算（），步长，；|（）步骤 计算（）；步骤 计算，其中（，），；|（）步骤 计算（）（）（）；步骤 令 且返回步骤。引理 假设（）成立，则算法 产生的步长是一个非增序列，且满足，。证明 由式（）得，故是一个非增序列。当，由 的 连续性与定义（）得，再由的定义与数学归纳法得，因此是一个非增的并且有下界的序列。故存在，。引理 设序列是由算法 迭代产生，假设（）成立，对于（，），有；（）（）（）。（）证明 由（，）与 得，（）由式（）与 的伪单调性得 山 东 大 学 学 报（理 学 版）第 卷，。（）由、的定义，（），式（）及引理（）得，（，）（，）（，），。（）使用 的定义，有。（）使用 不等式，的定义及式（）得，（），|。（）由 的定义，三角不等式及式（）得（）|。（）将式（）与式（）代入式（）得，（）（）（）（）。（）由 的定义得。（）将，代入式（），结合式（）得，（），由此可得。（）将，、式（）与式（）代入式（），有，（）（），（）（），（）第 期陈晶晶，等：解变分不等式与不动点问题的一种修正的惯性投影算法 故（）（）。定理 假设（）（）成立，则由算法 生成的迭代序列依范数强收敛到（）（，），其中（）（，）（）。证明 第 步 证明序列、及（）有界。由式（）得，。（）由式（）得，再由条件 得，（）故存在，有。（）由式（）、式（）及 的定义得（）。（）使用 的定义与三角不等式得（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）。（）令（），由式（）及定义 得（）（）（）（）（），（）（）|（），（）将式（）与式（）代入式（）得（）（）（）（）（）（）（）（）（）（）（），（），（），（）因此序列是有界的，则，（）也有界。第 步 证明 山 东 大 学 学 报（理 学 版）第 卷（）（）（）（）（）（）（）。使用定义 得 （）（）（），（）（），（）使用引理（）得（）（）（）（）（）（）（）（）。（）由引理（）、式（）、式（）及式（）得（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（），（）整理得（）（）（）（）（）（）（）。（）第 步 证明（）（）（）（），|。使用 的定义及 不等式，有（）（），（）其中，。使用式（）、式（）及引理，有（）（）第 期陈晶晶，等：解变分不等式与不动点问题的一种修正的惯性投影算法 （）（）（）（）（）（）（）（）（）（），（）（）（）（），（）（）（），（）（）（）（），|。（）第 步 证明序列强收敛到，分 种情形讨论序列。情形 假设，有，由此可知存在。由式（）、式（）、及，有，（）由式（）与式（），有，。（）由 的定义与式（），有，（）结合式（）与式（），有，。（）由（）与式（）得（），（）由 的定义，式（）及式（）得 （）（）（）（）（），。由于是有界的，因此存在的子序列，有，故（），（），（），。（）由（）及引理（）得，（）式（）也可写为，（）由式（）、式（）、的有界性、不等式及 的 连续性，有，。（）设是一个非负递减序列，使得。记 为使下式成立的最小正整数，。（）假设当 时，存在一正整数 使式（）成立，此时有，。由于是一个非负递减序列，有，再由，得，。山 东 大 学 学 报（理 学 版）第 卷而对，由式（）得，结合，与，得。再由 与 都为整数，有，因此是递增的。由于是有界的，因此存在的子序列，有，。由，且 是序列弱连续得，。当 时，由 得，因此（，）。当 时，令，有，。由式（），有，再由 的伪单调性，有（），。（）由范数映射是弱下半连续，有，从而是有界的，故。（）由式（）、式（）及 的伪单调性得，（）证得（，）。下证（）。由式（）与式（）得，（）使用式（）、式（）及定义 得（），因此（）（，）。（）由 的定义、引理（）、式（）、式（）及，有（），（），（），（），（），（）第 期陈晶晶，等：解变分不等式与不动点问题的一种修正的惯性投影算法 使用式（）、式（）、式（）及引理 得，因此证得，。情形 存在的子序列，满足，。由引理 知存在一个非减序列，有，并且，。（）由式（）、式（）、式（）及，有，（）由式（）与式（），有，。类似于情形 的证明，有（），。（）由式（）与式（）得（）（）（）（），|，故（）（），。（）将式（），式（）代入式（）并结合式（），有，即，因此证得，。数值实验本小节对所提出的算法与已有算法进行比较，给出了一些数值实验。所有代码均在 和 系统下运行，当 时迭代停止。用、及 分别表示文献中的算法、文献中的算法、文献中的算法 及本文算法。例 定义算子：为（），其中，其中 是 阶矩阵，是阶斜对称矩阵，是 阶对角矩阵，定义算子：为。不难发现，算子 是单调的并且 连续，进而有，算子：为 半压缩映射并且在原点次闭，当可行集（，）：，时，（）（，）（，），即（，）。对例 迭代初始点为（，），矩阵 和 中的元素在，随机取值，对角矩阵 的对角元素在（，）中取值，选取。针对本文算法 选取，（）。文献中的算法 选取，。文献中的算法 选取，并且参数，与本文算法 的取值相同。文献中的算法 选 山 东 大 学 学 报（理 学 版）第 卷取，并且参数，（）与本文算法 的取值相同。迭代终止条件为，数值实验结果见表 和图。表 例 中 种算法的数值实验结果 算法 图 例 中随运行时间变化图 例 设（，），内积，（）（），。范数（），。令 为单位球。设算子：满足（）（），（），算子：（，）（，）定义为（）（），。不难发现，算子 是单调的并且 连续，为 半压缩映射（，），并且在原点次闭，（）（，）即不动点集与单调变分不等式解集的公共元为。对例 选取 为，迭代初始点为（）（）和（）（）。针对本文算法 选取，（）。文献中的算法 选取，。文献中的算法 选取，并且参数，与本文算法的取值相同。文献中的算法 选取，并且参数，（）与本文算法 的取值相同。迭代终止条件为，数值对比结果见图。通过对算法 的数值实验结果与文献、文献及文献中算法的数值实验结果对比，可以看出算法 优于 算法、算法和 算法，并且在无需提前知道 常数及伪单调映射的条件下，证明了算法 的强收敛性。由此进一步验证了算法 的有效性和实用性。第 期陈晶晶，等：解变分不等式与不动点问题的一种修正的惯性投影算法 （）（）（）（）（）（）图 例 中随运行时间变化图 总结本文结合半压缩映射和惯性收缩投影方法，提出了一种修正的惯性投影算法，用以寻找伪单调变分不等式问题的解集与带有半压缩映射的不动点集的公共元，在不需要预先知道 常数的条件下，证明了由所提的迭代算法产生的迭代序列强收敛于该公共元，并且通过数值实验验证了本文所提迭代算法的有效性和适用性。文中所得结论是对现有文献结论的改进和推广。参考文献：，（）：，：，（）：，（）：，：，（）：，（）：，（）：，（）：，（）：，（）：，（）：，（）：山 东 大 学 学 报（理 学 版）第 卷 ，（）：，（）：，（）：，：，（）：，：，（）：贺月红，龙宪军 求解伪单调变分不等式问题的惯性收缩投影算法 数学物理学报，（）：，（）：杨延涛 求解单调变分不等式问题的一种修正的次梯度超梯度方法 山东大学学报（理学版），（）：（），（）：杨延涛，陈晶晶，周海云 涉及拟反向强单调算子零点的一个弱收敛结果及其应用 浙江大学学报（理学版），（）：，（），（）：，（）：，（）：（编辑：胡春燕）