求解均衡問題的分離慣性算法

2020-12-03 05:20:30高輝，張明堃，王曉亮，龐麗萍*

大連理工大學學報 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)，推出