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

高 輝， 張 明 堃， 王 曉 亮， 龐 麗 萍*

( 1.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院， 遼寧 大連 116024；2.大連海洋大學(xué) 信息工程學(xué)院， 遼寧 大連 116023 )

0 引 言

假設(shè)C是實希爾伯特空間H的一個非空閉凸集，對于每個x∈C，函數(shù)f：C×C→R都有f(x，x)=0.考慮下面的均衡問題：

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

在本文中，假設(shè)f(x，y)=f1(x，y)+f2(x，y)，其中fi(x，x)=0(i=1，2)，?x∈C，于是均衡問題轉(zhuǎn)化為：求x*∈C，使得

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

用S(f，C)表示均衡問題的解集，而且假設(shè)解集非空.許多數(shù)學(xué)模型都能看成均衡問題的特殊情形，例如：變分不等式、不動點問題、優(yōu)化問題、鞍點問題、互補問題等.近年來，求解均衡問題的方法很多，其中外梯度法是一個比較受歡迎的方法.該方法由Korpelevich[1]在解單調(diào)變分不等式問題時引入.隨后，為提高這個方法的有效性，它的一些改進方法被提出，如非精確梯度法[2]、投影梯度法[3]、內(nèi)部外梯度法[4]、黃金比方法[5]、分離法[6-8]等.

本文采用分離算法來解強偽單調(diào)的均衡問題.在文獻[7]中，算法的收斂性需要假設(shè)每個分離出的函數(shù)滿足H?lder連續(xù).為避免H?lder連續(xù)條件，在文獻[8]中，Muu等提出了一個結(jié)合梯度方法和Mann迭代的分離算法來解均衡問題和非擴張映射的不動點問題，其中函數(shù)不需要滿足Lipschitz連續(xù)和H?lder連續(xù)的條件.對比文獻[8]，本文引入慣性(inertial)技術(shù).慣性思想最早由Alvarez等[9]提出，它可以有效地加快鄰近點算法的收斂速度.近年來，慣性思想被廣泛地用于各類算法中.例如：Douglas-Rachford算子分裂慣性算法[10]、慣性鄰近法[11]、鄰近梯度法[12]等.基于分離方法，本文將慣性思想應(yīng)用到其中，提出分離慣性算法.同時，結(jié)合文獻[2-3]，其迭代的步長不依賴Lipschitz常數(shù).

1 預(yù)備知識

定義1[13]函數(shù)f：C×C→R∪{+∞}被稱為

(1)在C上強γ-單調(diào)，如果存在常數(shù)γ>0使得

(2)在C上單調(diào)，如果

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

(3)在C上偽單調(diào)，如果

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

(4)在C上強γ-偽單調(diào)，如果存在常數(shù)γ>0，且f(x，y)≥0，則

定義2[13]設(shè)g：Rn→R∪{+∞}是正常下半連續(xù)凸函數(shù)，t>0，函數(shù)g在x處的鄰近映射定義為

引理1[14]設(shè)g：Rn→R∪{+∞}是正常下半連續(xù)凸函數(shù)，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 算法和收斂性

為證明算法的收斂性，做如下假設(shè)：

(1)每個x∈C，函數(shù)fi(x，·)(i=1，2)是下半連續(xù)凸函數(shù)；

(2)函數(shù)f在C上強γ-偽單調(diào)；

(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，則算法停止.

關(guān)于算法1解釋如下：

(1)對于wn=xn+αn(xn-1-xn)，0≤αn<1，其中wn是xn和xn-1的一個凸組合，本文wn與文獻[15]相同.當(dāng)然對于wn還有其他選擇，如在文獻[3]中，wn=xn+αn(xn-xn-1)，0≤αn<1，其中αn(xn-xn-1)被稱為慣性效果，可以加速算法的收斂性.

(2)當(dāng)αn=0，本文算法是不帶加速步的分離算法.

定理1假設(shè){xn}是由本文算法生成的序列，對于每個y∈C，有

證明根據(jù)式(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假設(shè)條件(1)～(3)成立，由本文算法生成的序列{xn}強收斂于均衡問題的解.

證明假設(shè)p∈S(f，C)，由定理1知，

(11)

因為f強γ-偽單調(diào)，式(11)可轉(zhuǎn)換成

智慧教育的技術(shù)特征 智慧教育在技術(shù)層面是指通過物聯(lián)網(wǎng)、移動互聯(lián)網(wǎng)等技術(shù)，對教育信息進行匯聚和分析，輔助智能化的教育管理與決策[2]?；诩夹g(shù)觀的觀點，智慧教育是一個高度集中性質(zhì)的信息系統(tǒng)工程，它主要由五部分構(gòu)成其核心技術(shù)特征：對教育資源環(huán)境服務(wù)等信息的智能化管理；根據(jù)情境的感知得到具體數(shù)據(jù)為用戶提供服務(wù)；實現(xiàn)網(wǎng)絡(luò)之間的完美對接，既包括人與人直接的對接，也包括人與物之間的交互；按照資源的需求分配教育資源；實現(xiàn)信息時代數(shù)據(jù)處理與顯示的可視化。

(12)

(13)

結(jié)合式(12)、(13)，推出

(14)

(15)

整理式(14)得

(16)

□

3 數(shù)值實驗

本文通過初步數(shù)值實驗來說明算法的可行性和有效性.在數(shù)值實驗中，采用Matlab R2015b軟件編寫程序，軟件的運行環(huán)境為PC Desktop Intel(R) Core(TM) i5-8250U CPU @ 1.60 GHz， RAM 8.00 GB.

考慮均衡問題滿足

f：R5×R5→R，f=f1+f2

f1(x，y)=〈Px+Qy+q，y-x〉

其中

q=(-1 -2 -1 2 -1)T

可行集C={x∈R5：x-(5 -3 -2 4 2)T≤1}.

例1研究本文算法的數(shù)值效果.從本文算法可知，若xn+1=yn=wn，則xn+1是均衡問題的解.因此，使用

由表1可以看出，實驗結(jié)果跟p的取值有關(guān).在給定停止準則，且p=1.0時，本文算法迭代次數(shù)最少.

由表2可以看出，本文算法比SA在迭代次數(shù)和所用時間上都要少.本文算法比IEGA在迭代過程中CPU運行的時間少.通過比較，說明了本文算法的有效性.

表2 本文算法、SA、IEGA的比較

例3考慮均衡問題滿足

f：Rn×Rn→R，f=f1+f2

f1(x，y)=〈Ax，y-x〉

由表3可以看出，本文算法盡管需要多的迭代次數(shù)，但在CPU運行時間上都比EGA少，說明本文算法對維數(shù)高的算例也是有效的.

表3 本文算法和EGA的比較

4 結(jié) 語

本文采用分離算法來解強偽單調(diào)的非光滑均衡問題.本文算法結(jié)合了慣性，同時，其迭代步長不依賴Lipschitz常數(shù)，在滿足一定條件的假設(shè)下，證明了本文算法的強收斂性.與已有的幾個算法進行比較，說明了本文算法的有效性.