王 莉，陳星旭，孫菊賀，楊 崢

(1.沈陽(yáng)航空航天大學(xué) 理學(xué)院，沈陽(yáng) 110136；2.遼寧省實(shí)驗(yàn)學(xué)校 數(shù)學(xué)教研組，沈陽(yáng) 110031)

本文將研究極值映射不動(dòng)點(diǎn)問(wèn)題，即求解v*∈K使得

v*∈Argmin{Φ(v*,w)|w∈Ω}

(1)

這里Φ是定義在內(nèi)積空間Rn×Rn上的極值映射，Ω?Rn是非空閉凸集合。假設(shè)Φ(v,·)關(guān)于第一元v是凸函數(shù)；對(duì)任意的v∈Ω，都有集值映射w(v)≡Argmin{Φ(v,w)|w∈Ω}，且原始問(wèn)題(1)的解集Ω*={v*∈Ω|v*∈w(v*)}?Ω是非空的。

對(duì)于問(wèn)題(1)的解應(yīng)滿足不等式

Φ(v*,v*)≤Φ(v*,w),?w∈Ω

(2)

顯然，不等式(2)是極值映射不動(dòng)點(diǎn)問(wèn)題(1)的等價(jià)定義。

Antipin[1-3]提出極值映射的不動(dòng)點(diǎn)問(wèn)題(1)，并指出該問(wèn)題是不同類型、不同領(lǐng)域問(wèn)題的一般表示，同時(shí)指出鞍點(diǎn)問(wèn)題、具有納什均衡的n人博弈問(wèn)題、逆優(yōu)化問(wèn)題、變分不等式問(wèn)題、不動(dòng)點(diǎn)求解問(wèn)題等都可以轉(zhuǎn)化為極值映射不動(dòng)點(diǎn)問(wèn)題(1)。Antipin[1]研究了極值映射不動(dòng)點(diǎn)問(wèn)題的鄰近方法。Antipin[2]研究了極值映射不動(dòng)點(diǎn)問(wèn)題的一階微分方程方法。Antipin[3]首先研究了優(yōu)化問(wèn)題的一階微分方程方法，進(jìn)而提出了鞍點(diǎn)問(wèn)題的具有控制過(guò)程的一階微分方程方法，最后研究了極值映射不動(dòng)點(diǎn)問(wèn)題的具有控制過(guò)程的一階微分方程方法。Wang等[4]研究了具有不等式約束的極值映射不動(dòng)點(diǎn)問(wèn)題的增廣拉格朗日方法。Antipin[5]研究了一類優(yōu)化問(wèn)題的二階微分方程方法。Wang等[6]運(yùn)用二階微分方程系統(tǒng)求解了具有不等式約束的極值映射問(wèn)題。

值得指出的是，Antipin等學(xué)者的微分方程方法與Zhou等[7]、Jin等[8]與Zhou等[9]所使用的微分方程方法求解變分不等式和互補(bǔ)問(wèn)題是完全不同的；不僅如此，與Gao等[10]、He等[11]與Liao等[12]的神經(jīng)網(wǎng)絡(luò)方法求解優(yōu)化方面問(wèn)題也不同。以往的方法是把原始問(wèn)題轉(zhuǎn)化成光滑的無(wú)約束優(yōu)化問(wèn)題，運(yùn)用該優(yōu)化問(wèn)題的負(fù)梯度來(lái)構(gòu)造微分方程系統(tǒng)，并構(gòu)造李亞普諾夫函數(shù)來(lái)證明微分方程系統(tǒng)的穩(wěn)定性。而Antipin等學(xué)者直接利用非光滑的投影算子構(gòu)成的方程組建立微分方程系統(tǒng)，運(yùn)用投影定理及內(nèi)積與范數(shù)的運(yùn)算得到微分方程系統(tǒng)的軌跡收斂性。但是Antipin等學(xué)者的工作卻沒(méi)有得到足夠的重視，F(xiàn)acchinei等[13]的專著幾乎收錄了變分不等式和互補(bǔ)問(wèn)題的所有重要成果，但卻沒(méi)有記錄該方法。王莉[14]關(guān)注了Antipin等學(xué)者的工作，并進(jìn)一步用該思想解決了具有循環(huán)單調(diào)映射的變分不等式的微分方程方法。

在以上研究結(jié)果的基礎(chǔ)上，本文研究極值映射不動(dòng)點(diǎn)(1)的二階微分方程系統(tǒng)。在第一部分將介紹本文將要用到的預(yù)備知識(shí)如投影算子、對(duì)稱函數(shù)和反對(duì)稱函數(shù)的一系列性質(zhì)；在第二部分運(yùn)用函數(shù)Φ(v,w)及投影算子的性質(zhì)，建立二階微分方程系統(tǒng)，并證明二階微分方程系統(tǒng)軌跡的聚點(diǎn)就是極值映射不動(dòng)點(diǎn)問(wèn)題的解；最后給出具體的算例說(shuō)明二階微分方程系統(tǒng)求解極值映射不動(dòng)點(diǎn)問(wèn)題的有效性。

1 預(yù)備知識(shí)

為了建立二階微分方程系統(tǒng)，首先介紹關(guān)于對(duì)稱函數(shù)與反對(duì)稱函數(shù)的性質(zhì)。

定義1[3]滿足式(3)的函數(shù)稱為對(duì)稱函數(shù)，滿足式(4)的函數(shù)稱為反對(duì)稱函數(shù)。

Φ(w,v)-Φ(v,w)=0,?v∈Ω,?w∈Ω

(3)

Φ(w,v)+Φ(v,w)=0,?v∈Ω,?w∈Ω

(4)

Antipin[3]給出函數(shù)Φ(v,w)轉(zhuǎn)置的定義，即ΦT(v,w)=Φ(w,v)。則對(duì)稱函數(shù)和反對(duì)稱函數(shù)的轉(zhuǎn)置可以分別表示為

Φ(v,w)=ΦT(w,v),?v∈Ω,?w∈Ω

(5)

Φ(v,w)=-ΦT(w,v)，?v∈Ω,?w∈Ω

(6)

因此函數(shù)Φ(v,w)可以做如下分解

Φ(v,w)=S(v,w)+K(v,w)

(7)

其中函數(shù)S(v,w)和K(v,w)定義如下

(8)

則容易驗(yàn)證S(v,w)為對(duì)稱函數(shù)，K(v,w)為反對(duì)稱函數(shù)。

Antipin[3]證明了對(duì)稱函數(shù)和反對(duì)稱函數(shù)的性質(zhì)如下

性質(zhì)1[3]對(duì)稱函數(shù)S(v,w)在Ω×Ω的對(duì)角線上的關(guān)于第一元v和第二元w的偏導(dǎo)數(shù)相等，即

?Sv(v,v)=?Sw(v,v),?v∈Ω

(9)

更進(jìn)一步，Antipin[3]討論了當(dāng)函數(shù)S(v,w)中v=w時(shí)可以得到

2?Sw(v,w)|v=w=?S(v,v),?v∈Ω

(10)

定義2[3]函數(shù)S(v,w)稱為偽對(duì)稱函數(shù)，如果存在函數(shù)P(v)使得

?P(v)=2?wS(v,w)|v=w，?v∈Ω

(11)

顯然，對(duì)稱函數(shù)一定是偽對(duì)稱函數(shù)。在這種情況下

?P(v)=?S(v,v)，?v∈Ω

(12)

Antipin[3]給出了定義2中的函數(shù)P(v)，梯度?P(v)滿足下面的Lipschitz條件，其Lipschitz常數(shù)為L(zhǎng)p如下

(13)

梯度?P(v)滿足單調(diào)性條件

〈?P(v+h)-?P(v),h〉≥0，?v∈Ω

(14)

由反函數(shù)的定義式(4)，如果v=w，可以得到K(v,v)=-K(v,v)，即K(v,v)=0對(duì)于所有的v∈Ω。這就意味著反對(duì)稱函數(shù)K(v,w)在Ω×Ω對(duì)角線上的元素為0。因此反對(duì)稱函數(shù)K(v,w)可寫(xiě)作

K(w,w)-K(w,v)-K(v,w)+K(v,v)=0，?v∈Ω?w∈Ω

(15)

定義3[3]函數(shù)K(v,w)在Ω×Ω上為斜對(duì)稱函數(shù)，如果滿足下面的不等式

K(w,w)-K(w,v)-K(v,w)+K(v,v)≥0，?w∈Ω，?v∈Ω

(16)

顯然，反對(duì)稱函數(shù)一定是斜對(duì)稱函數(shù)。

如果K(v,w)關(guān)于第二元w是凸的，則有

〈?wK(w,w)-?wK(v,v),w-v〉≥0，

?w∈Ω?v∈Ω

(17)

由式(7)的形式能得到

?wΦ(v,w)|w=v=?wS(v,w)|w=v+?wK(v,w)|w=v

(18)

如果目標(biāo)函數(shù)Φ(v,w)關(guān)于第二元w可微時(shí)，則由式(2)可以得到

〈?wΦ(v*,v*),w-v*〉≥0，?w∈Ω

(19)

將式(11)和式(18)代入到式(19)可以得到

w-v*〉≥0 ?w∈Ω

(20)

另一方面，若K(v,w)關(guān)于第二元w都是凸的，則根據(jù)式(14)和式(17)可以得到

再根據(jù)式(18)可以得到

(21)

此外，?wΦ(v,v)滿足Lipschitz條件如下

|?wΦ(v+h,v+h)-?wΦ(v,v)|≤L|h|

(22)

其中L為L(zhǎng)ipschitz常數(shù)。

投影算子在將變分不等式問(wèn)題轉(zhuǎn)化為等式時(shí)起著重要的作用，下面介紹投影算子的定義及與其相關(guān)的重要引理。

引理1[15]設(shè)H是實(shí)希爾伯特空間，C?H是閉凸集合。對(duì)給定的z∈H，u∈C滿足不等式

〈u-z,v-u〉≥0, ?v∈C,

當(dāng)且僅當(dāng)u-ΠC(z)=0。

2 二階微分方程系統(tǒng)

本節(jié)將要討論運(yùn)用二階微分方程系統(tǒng)求解極值映射不動(dòng)點(diǎn)問(wèn)題(1)的方法。

當(dāng)Φ(v,w)關(guān)于第二元w∈Ω可微時(shí)，如果v*∈Ω*是問(wèn)題(1)的不動(dòng)點(diǎn)，則v*一定滿足下面的變分不等式

〈?wΦ(v*,v*),w-v*〉≥0，?w∈Ω

(23)

根據(jù)引理1變分不等式(23)可等價(jià)為下面的方程

v*=ΠΩ(v*-α?wΦ(v*,v*))

(24)

其中α>0，πΩ(·)為集合Ω上的投影算子。

注1：顯然式(23)和方程(24)是極值映射不動(dòng)點(diǎn)問(wèn)題(1)的必要條件；若Φ(v,w)關(guān)于第二元w∈Ω可微且凸時(shí)，則式(23)和方程(24)與原始問(wèn)題(1)等價(jià)。

為求解變分不等式(23)和方程(24)，建立二階微分方程系統(tǒng)。與Antipin[3]相似，建立下面的具有控制過(guò)程的二階微分方程系統(tǒng)。

(25)

其中μ>0,β>0和α>0是參數(shù)。

根據(jù)引理1，可將微分方程系統(tǒng)(25)轉(zhuǎn)化為變分不等式

(26)

(27)

下面給出二階微分方程系統(tǒng)的軌跡聚點(diǎn)是變分不等式問(wèn)題(23)的解。

證明：在式(26)中w=v*得到

(28)

利用內(nèi)積與范數(shù)的關(guān)系計(jì)算得

(29)

運(yùn)用式(22)，式(25)及投影算子的非擴(kuò)張性和內(nèi)積與范數(shù)的關(guān)系，對(duì)式(29)中的第3項(xiàng)進(jìn)行處理

?wΦ(v,v)‖‖ΠΩ(v-α?wΦ(v,v))-

將上式代入式(29)可以表示為

(30)

利用內(nèi)積與范數(shù)的關(guān)系計(jì)算得到

(31)

將式(30)與式(31)相加得到

(32)

由于已知條件?Sw(v,w)|w=v存在，P(v)是凸函數(shù)，K(v,w)關(guān)于第二元w可微且凸，根據(jù)式(7)和式(21)可以得到

(33)

根據(jù)式(33)的估計(jì)，式(34)可以寫(xiě)成

(34)

利用內(nèi)積和范數(shù)的關(guān)系得到

‖x+y‖2=‖x‖2+2〈x,y〉+‖y‖2, ?x,y∈Rn

(35)

根據(jù)式(35)可以得到

將上式代入到式(34)中可得

(36)

再由下面的關(guān)系

對(duì)式(36)的前兩項(xiàng)進(jìn)行計(jì)算

將上面的結(jié)果代入到式(36)中得到

(37)

(38)

對(duì)式(38)從t0到t積分可以得到

(39)

其中C1=μφ′(v0)+βφ(v0)+

(40)

求解該常微分方程得

(41)

對(duì)式(41)從t0到t積分可以得到

繼續(xù)計(jì)算可得

(42)

由式(42)可得‖v-v*‖2有界。

再根據(jù)式(39)可得

(43)

在上式中令t→∞，則有

(44)

v′=ΠΩ(v′-α?wΦ(v′,v′))

則有v′滿足式(24)，即v′是變分不等式(23)的解。根據(jù)注1，如果函數(shù)Φ(v,w)關(guān)于第二元w是凸函數(shù)時(shí)，則v′是極值映射不動(dòng)點(diǎn)問(wèn)題(1)的解。

3 數(shù)值結(jié)果

用微分方程式(25)求解兩個(gè)實(shí)際問(wèn)題，應(yīng)用Matlab R2019a軟件進(jìn)行計(jì)算。在求解過(guò)程中,所采用的具體算法是微分方程求解函數(shù)ode45,這個(gè)函數(shù)采用的是四階五級(jí)的Runge-Kutta方法。選取參數(shù)α=0.01,μ=0.1,β=0.5。計(jì)算機(jī)的配置為：CPU Intel(R)Core(TM)i7-7700HQ @2.80 GHz；內(nèi)存為16.0 GB。

例1 考慮下面雙人博弈問(wèn)題[1]

x*∈argmin{f(z)+L(z,p*):z∈Q},

p*∈argmin{φ(y)-L(x*,y):y∈P}

(45)

其中函數(shù)f(z),φ(y)為凸函數(shù)，L(z,p)為不動(dòng)點(diǎn)函數(shù)。其典型的具體情況如下

x*∈argmin{0.5(z-1)2+zp*:z∈R1},p*∈argmin{0.5(y-3)2+x*y:y∈R1}

(46)

Antipn[1]給出了式(46)的解(x*,p*)T=(-1，2)T。

為了應(yīng)用微分方程式(25)求解，設(shè)

Φ(v,ω)=f(ω1)+L(ω1,v2)-L(v1,ω2)+

φ(ω2),

其中ω=(ω1,ω2)T=(z,y)T,v=(v1,v2)T=(x,p)T。

圖1描繪了雙人博弈問(wèn)題式(46)的微分方程式(25)的解的軌跡隨時(shí)間的變化關(guān)系，而且該圖的曲線是微分方程式(25)的解的軌跡從9個(gè)不同隨機(jī)選取的初始點(diǎn)生成的。經(jīng)過(guò)微分方程式(25)求解得到該系統(tǒng)的軌跡v=(x,p)T收斂于平衡點(diǎn)v=(-1.007 2,2.004 4)T,即式(46)的近似解。

圖1 雙人博弈問(wèn)題式(46)的微分方程系統(tǒng)式(25)的解的軌跡

例2考慮下面極值映射不動(dòng)點(diǎn)問(wèn)題[2]

v*∈arg min{0.5〈Nw,w〉+〈Mv*+m,w〉|w∈Ω}

(47)

其中N和M是非負(fù)矩陣，并假設(shè)矩陣N是對(duì)稱的。

圖2描繪了極值映射不動(dòng)點(diǎn)問(wèn)題式(47)的微分方程式(25)解的軌跡隨時(shí)間的變化關(guān)系，而且該圖的曲線是微分方程式(25)的解的軌跡從8個(gè)不同隨機(jī)選取的初始點(diǎn)生成的。經(jīng)過(guò)計(jì)算微分方程式(25)求解該系統(tǒng)的軌跡v=(v1,v2,v3)T收斂于(-0.372 7,-0.093 6,-0.044 6)T,即問(wèn)題式(47)的近似解。

圖2 極值映射不動(dòng)點(diǎn)問(wèn)題式(47)的微分方程式(25)的解的軌跡

4 結(jié)論

Antipin[3]研究了極值映射的不動(dòng)點(diǎn)問(wèn)題(1)的一階微分方程方法，提出了對(duì)稱函數(shù)、偽對(duì)稱函數(shù)、反對(duì)稱函數(shù)及斜對(duì)稱函數(shù)的定義，并指出了對(duì)稱函數(shù)與偽對(duì)稱函數(shù)、反對(duì)稱函數(shù)與斜對(duì)稱函數(shù)的關(guān)系，同時(shí)得到了這些函數(shù)偏導(dǎo)數(shù)的一系列性質(zhì)。運(yùn)用這些性質(zhì)建立了一階微分方程系統(tǒng)，本文在此基礎(chǔ)之上建立了具有控制過(guò)程的二階微分方程系統(tǒng)，并證明了具有控制過(guò)程的二階微分方程系統(tǒng)的軌跡的聚點(diǎn)是極值映射不動(dòng)點(diǎn)問(wèn)題(1)的解。除得出理論結(jié)果，本文也具體計(jì)算了Antipin[1]和Antipin[2]提出的兩個(gè)具體問(wèn)題，得到了運(yùn)行結(jié)果，證明了具有控制過(guò)程的二階微分方程系統(tǒng)求解極值映射不動(dòng)點(diǎn)問(wèn)題(1)的有效性。