二階微分方程系統(tǒng)求解極值映射不動點問題

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

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

本文將研究極值映射不動點問題，即求解v*∈K使得

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

(1)

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

對于問題(1)的解應(yīng)滿足不等式

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

(2)

顯然，不等式(2)是極值映射不動點問題(1)的等價定義。

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

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

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

1 預(yù)備知識

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

定義1[3]滿足式(3)的函數(shù)稱為對稱函數(shù)，滿足式(4)的函數(shù)稱為反對稱函數(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)。則對稱函數(shù)和反對稱函數(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)

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

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

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

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

(9)

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

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

(10)

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

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

(11)

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

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

(12)

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

(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對于所有的v∈Ω。這就意味著反對稱函數(shù)K(v,w)在Ω×Ω對角線上的元素為0。因此反對稱函數(shù)K(v,w)可寫作

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

(15)

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

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

(16)

顯然，反對稱函數(shù)一定是斜對稱函數(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)

如果目標函數(shù)Φ(v,w)關(guān)于第二元w可微時，則由式(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為Lipschitz常數(shù)。

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

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

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

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

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

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

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

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

(23)

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

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

(24)

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

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

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

(25)

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

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

(26)

(27)

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

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

(28)

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

(29)

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

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

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

(30)

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

(31)

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

(32)

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

(33)

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

(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)系

對式(36)的前兩項進行計算

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

(37)

(38)

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

(39)

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

(40)

求解該常微分方程得

(41)

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

繼續(xù)計算可得

(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ù)時，則v′是極值映射不動點問題(1)的解。

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

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

例1 考慮下面雙人博弈問題[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)為不動點函數(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描繪了雙人博弈問題式(46)的微分方程式(25)的解的軌跡隨時間的變化關(guān)系，而且該圖的曲線是微分方程式(25)的解的軌跡從9個不同隨機選取的初始點生成的。經(jīng)過微分方程式(25)求解得到該系統(tǒng)的軌跡v=(x,p)T收斂于平衡點v=(-1.007 2,2.004 4)T,即式(46)的近似解。

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

例2考慮下面極值映射不動點問題[2]

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

(47)

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

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

圖2 極值映射不動點問題式(47)的微分方程式(25)的解的軌跡

4 結(jié)論

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