一种求解单调包含问题的惯性混合邻近外梯度算

1 引言

对于单调包含问题, 即: 找到x?∈X 使得

其中B:X ?X 是极大单调算子, X 是实Hilbert 空间.凸优化问题, 平衡问题和单调变分不等式等许多问题都可以归结为单调包含问题(1.1).单调包含问题在图像处理和聚类等实际问题中有着广泛的应用[1].

邻近点算法是解单调包含问题的一类经典算法, 它由Martinet[2]提出, Rockafellar[3]进一步发展而成.其迭代格式为

其中正则参数λk>0,Id是单位算子.Alvarez 和Attouch 于2001 年在文献[4]中提出解含有单调算子的广义方程的惯性邻近点算法, 并证明了该算法的弱收敛性.

混合邻近外梯度算法是由Solodov 和Svaiter[5]在1999 年针对单调包含问题提出的另一类算法.即

初始化任取初始点x0∈X, 任意给定令k=1.

步骤1选择容差参数并找到yk,vk∈X,εk≥0 使其满足

步骤2执行一个外梯度步:xk+1=xk?λkvk.令k:=k+1, 返回步骤1.

实质上, 混合邻近外梯度算法是邻近点算法的一种不精确版本, 在每一次迭代中, 对应的近似子问题都应在一个相对误差准则内求解, 这与Rockafellar 提出的邻近点算法的可加误差准则不同.混合邻近外梯度算法的另一个特点是它还允许通过文献[6]中提出的极大单调算子的ε-enlargement 来松弛单调算子.

混合邻近外梯度算法作为设计新方法和分析现有方法的复杂性的框架特别有用.例如Monteiro 和Svaiter[7]在2013 年提出块状分解混合邻近外梯度算法, 并证明了该算法的迭代复杂性, 且在该算法的框架下证明了交替方向乘子法的遍历迭代复杂度; Goncalves, Melo 和Monteiro[8]在2017 年提出一种新的正则化混合邻近外梯度算法, 并建立了该算法的迭代复杂性, 且证明了交替方向乘子法的变体是该算法的特殊实例; Alves 和Svaiter[9]在2016 年提出了一种新的求解强单调包含问题的混合邻近外梯度算法:

初始化任取初始点x0∈X, 任意给定σ∈[0,1),k=1.

步骤1选定0<λk≤λk?1, 并找到yk,vk∈X,εk≥0, 使得

步骤2计算xk:

并用混合邻近外梯度算法的框架证明了Korpelevich 外梯度算法的迭代复杂性.

近年来, 惯性邻近点类算法被大量用于设计和分析各种具有惯性的一阶邻近算法.例如Chen[10]等人提出求解具有可分结构的线性约束凸优化问题的惯性交替方向乘子法, 并建立了渐近收敛率和非渐近收敛率; Bot, Csetnek 和Hendrich 在文献[11]中提出了求解单调包含问题的惯性Douglas-Rachford 分裂算法, 并证明了该算法在希尔伯特空间中的收敛性;Bot 和Csetnek[12]在2015 年提出求解单调包含问题的惯性混合邻近外梯度算法, 并建立了该算法的弱收敛性和渐近收敛性; Alves 和Marcavillaca 于2018 年在文献[1]中提出一种求解单调包含问题的新的惯性混合邻近外梯度算法, 并得到了它的渐近收敛率和非渐近全局收敛率.

受上述文献的启发, 本文提出了一种新的求解单调包含问题的惯性混合邻近外梯度算法,并得到了它的收敛性和非渐近全局收敛率.不同的是, 本文中的惯性系数的范围得到了扩大,其系数区间为特别的, 当μ=0 时, 惯性区间为[0,1], 正好与文献[12]中的区间一致.

本文结构如下: 首先是预备知识, 对概念和符号进行说明, 并对证明过程中所需的定理进行说明; 然后是本文的主要内容, 本文提出了一种用于求解单调包含问题的惯性混合邻近外梯度算法, 并证明了它的非渐近全局收敛率.最后本文提出了惯性混合邻近外梯度算法的两种特殊情况: 求解含有Lipschitz 连续算子的强单调包含问题的惯性Tseng’s 向前向后算法,并建立了该算法的弱收敛性和非渐近全局收敛率; 求解含有强单调算子和Lipschitz 连续算子的原始―对偶问题的惯性非精确Spingarn’s 部分逆算法, 并得到了该算法的弱收敛性和非渐近全局收敛率.

2 预备知识

令X 是内积为范数为的实Hilbert 空间.对于集值算子S:X ?X,它的图和定义域分别为

若S?1(v)={x:v∈S(x)}, 则称S?1:X ?X 是集值算子S的逆.

本文主要研究单调包含问题的求解算法, 即含有(极大) 单调算子的包含问题.在本节接下来的内容中将回顾一些基本概念和结论.

定义2.1[12]若集值算子A:X ?X 满足

则称算子A是μ-强单调的.特别地, 如果μ=0 则称A是单调的.

定义2.2[12]设算子A:X ?X 是单调的, 如果不存在其他单调算子B真包含于A, 则称算子A是极大单调的.即如果单调算子B:X ?X 满足Gr(A)?Gr(B), 则A=B.

集值算子S,:X ?X 的和S+:X ?X 定义为

上一篇：教育的技术、技巧和文化：打破铁三角
下一篇：没有了