求解均衡问题的分离惯性算法

2020-12-03高辉，张明堃，王晓亮，庞丽萍*

大连理工大学学报 2020年6期

关键词：收敛性惯性单调

高辉，张明堃，王晓亮，庞丽萍*

( 1.大连理工大学数学科学学院，辽宁大连 116024；2.大连海洋大学信息工程学院，辽宁大连 116023 )

0 引言

假设C是实希尔伯特空间H的一个非空闭凸集，对于每个x∈C，函数f：C×C→R都有f(x，x)=0.考虑下面的均衡问题：

求x*∈C，使得f(x*，y)≥0，∀y∈C

在本文中，假设f(x，y)=f1(x，y)+f2(x，y)，其中fi(x，x)=0(i=1，2)，∀x∈C，于是均衡问题转化为：求x*∈C，使得

f1(x*，y)+f2(x*，y)≥0，∀y∈C

用S(f，C)表示均衡问题的解集，而且假设解集非空.许多数学模型都能看成均衡问题的特殊情形，例如：变分不等式、不动点问题、优化问题、鞍点问题、互补问题等.近年来，求解均衡问题的方法很多，其中外梯度法是一个比较受欢迎的方法.该方法由Korpelevich[1]在解单调变分不等式问题时引入.随后，为提高这个方法的有效性，它的一些改进方法被提出，如非精确梯度法[2]、投影梯度法[3]、内部外梯度法[4]、黄金比方法[5]、分离法[6-8]等.

本文采用分离算法来解强伪单调的均衡问题.在文献[7]中，算法的收敛性需要假设每个分离出的函数满足Hölder连续.为避免Hölder连续条件，在文献[8]中，Muu等提出了一个结合梯度方法和Mann迭代的分离算法来解均衡问题和非扩张映射的不动点问题，其中函数不需要满足Lipschitz连续和Hölder连续的条件.对比文献[8]，本文引入惯性(inertial)技术.惯性思想最早由Alvarez等[9]提出，它可以有效地加快邻近点算法的收敛速度.近年来，惯性思想被广泛地用于各类算法中.例如：Douglas-Rachford算子分裂惯性算法[10]、惯性邻近法[11]、邻近梯度法[12]等.基于分离方法，本文将惯性思想应用到其中，提出分离惯性算法.同时，结合文献[2-3]，其迭代的步长不依赖Lipschitz常数.

1 预备知识

定义1[13]函数f：C×C→R∪{+∞}被称为

(1)在C上强γ-单调，如果存在常数γ>0使得

(2)在C上单调，如果

f(x，y)+f(y，x)≤0； ∀x，y∈C

(3)在C上伪单调，如果

f(x，y)≥0⟹f(y，x)≤0； ∀x，y∈C

(4)在C上强γ-伪单调，如果存在常数γ>0，且f(x，y)≥0，则

定义2[13]设g：Rn→R∪{+∞}是正常下半连续凸函数，t>0，函数g在x处的邻近映射定义为

引理1[14]设g：Rn→R∪{+∞}是正常下半连续凸函数，u∈Rn，t>0，令v=proxtg(u)，则

tg(w)-tg(v)≥〈u-v，w-v〉；∀w∈Rn

而且，进一步有

(1)

αk+1≤(1-γk)αk+γkαk-1+δk

αk+1≤(1-tk-γk)αk+γkαk-1+δk

2 算法和收敛性

为证明算法的收敛性，做如下假设：

(1)每个x∈C，函数fi(x，·)(i=1，2)是下半连续凸函数；

(2)函数f在C上强γ-伪单调；

(3)如果{xk}⊂C有界，则序列{gik∈∂(fi(xk，·))(xk)}(i=1，2)有界.

算法1

(2)

迭代步：给定xn-1，xn∈C，计算

wn=xn+αn(xn-1-xn)

(3)

计算：

(4)

和

(5)

如果xn+1=yn=wn，则算法停止.

关于算法1解释如下：

(1)对于wn=xn+αn(xn-1-xn)，0≤αn<1，其中wn是xn和xn-1的一个凸组合，本文wn与文献[15]相同.当然对于wn还有其他选择，如在文献[3]中，wn=xn+αn(xn-xn-1)，0≤αn<1，其中αn(xn-xn-1)被称为惯性效果，可以加速算法的收敛性.

(2)当αn=0，本文算法是不带加速步的分离算法.

定理1假设{xn}是由本文算法生成的序列，对于每个y∈C，有

证明根据式(1)，且t=λn，g(·)=f1(wn，·)，w=y，v=yn，u=wn，则

整理得

(6)

对于式(5)中的xn+1，按照类似的方法，有

(7)

式(6)和(7)相加，则有

2λn(f1(wn，yn)+f2(wn，xn+1))

(8)

f1(wn，yn)=f1(wn，yn)-f1(wn，wn)≥

(9)

其中式(9)的第2个不等式由柯西-施瓦茨不等式和式(4)得到.

类似地，估计式(8)的-2λnf2(wn，xn+1)为

(10)

将式(9)、(10)代入式(8)，得

定理2假设条件(1)～(3)成立，由本文算法生成的序列{xn}强收敛于均衡问题的解.

证明假设p∈S(f，C)，由定理1知，

(11)

因为f强γ-伪单调，式(11)可转换成

智慧教育的技术特征智慧教育在技术层面是指通过物联网、移动互联网等技术，对教育信息进行汇聚和分析，辅助智能化的教育管理与决策[2]。基于技术观的观点，智慧教育是一个高度集中性质的信息系统工程，它主要由五部分构成其核心技术特征：对教育资源环境服务等信息的智能化管理；根据情境的感知得到具体数据为用户提供服务；实现网络之间的完美对接，既包括人与人直接的对接，也包括人与物之间的交互；按照资源的需求分配教育资源；实现信息时代数据处理与显示的可视化。

(12)

(13)

结合式(12)、(13)，推出