一般混合變分不等式的新間隙函數(shù)

賴學(xué)李, 夏福全

(四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 四川 成都 610066)

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

本文在n維歐式空間Rn中研究一般混合變分不等式問題,且在該空間的范數(shù)和內(nèi)積分別表示為‖·‖和〈·〉.

定義 1.1設(shè)S是Rn上的非空閉凸集,F:Rn→Rn是一個(gè)映射,f:Rn→(-∞,+∞]是真凸下半連續(xù)泛函,而domf={x∈Rn:f(x)<+∞}為f的有效域,且S?domf,則一般混合變分不等式問題(簡記為MVIP(F,S))為:求x*∈S使得

〈F(x*),x-x*〉+f(x)-f(x*)≥0,

?x∈S,

(1)

若此時(shí)f是閉凸集S上的指示函數(shù),即

則一般混合變分不等式(1)退化為下列的經(jīng)典變分不等式問題,簡記為VIP(F,S):求x*∈S使得

〈F(x*),x-x*〉≥0, ?x∈S.

(2)

在利用變分不等式問題的間隙函數(shù),將變分不等式問題轉(zhuǎn)化為特殊的凸優(yōu)化問題進(jìn)行研究,已經(jīng)得到了許多廣泛而深入的研究成果.比如:Auslender[1]首先定義了問題(2)的間隙函數(shù)

(3)

與問題(2)等價(jià).

(4)

Taji等[3]此時(shí)在(4)式的基礎(chǔ)上取α=1,此時(shí)這個(gè)正則間隙函數(shù)變成了

(5)

以下是來自文獻(xiàn)[8]的一些與本文有關(guān)的定義和結(jié)論.

定義 1.2稱函數(shù)f:Rn→(-∞,+∞]為:

1) 凸函數(shù),若?x,y∈domf,α∈(0,1)使得不等式

f((1-α)x+αy)≤(1-α)f(x)+αf(y);

2) 嚴(yán)格凸函數(shù),若?x,y∈domf,α∈(0,1)使得不等式

f((1-α)x+αy)<(1-α)f(x)+αf(y);

3) 強(qiáng)凸函數(shù),若?x,y∈domf,α∈[0,1]，存在σ>0,使得不等式

f((1-α)x+αy)<(1-α)f(x)+αf(y)-

定義 1.3正常凸函數(shù)f:Rn→(-∞,+∞]在點(diǎn)x∈domf處沿方向d的方向?qū)?shù)記為

(6)

定義 1.4稱向量ξ為凸函數(shù)f在點(diǎn)x處的次梯度,即當(dāng)ξ∈Rn使得對(duì)任意的y∈Rn,均有

f(y)-f(x)≥〈ξ,y-x〉,

(7)

其中全體ξ的集合稱為f在點(diǎn)x處的次微分,記作?f(x).

引理 1.5設(shè)函數(shù)f:Rn→(-∞,+∞],其中domf為開凸集,若f在domf上可微,則在f為(嚴(yán)格)凸函數(shù)的充要條件即為?x,y∈domf,x≠y有

f(y)-f(x)≥q(>)〈▽f(x),y-x〉.

(8)

引理 1.6正常凸函數(shù)f:Rn→(-∞,+∞]以及x∈domf,則ξ∈?f(x)的充要條件是

f′(x;d)≥〈ξ,d〉,d∈Rn.

(9)

2 新的間隙函數(shù)

(10)

其中φ(x,y):Rn×Rn→R滿足以下條件:

(A1)φ在Rn×Rn上連續(xù);

(A2)φ在Rn×Rn上非負(fù)且φ(x,y)=0當(dāng)且僅當(dāng)x=y;

(A3)φ(x,·)關(guān)于x也是強(qiáng)凸的,也即存在η>0,對(duì)任意的x∈Rn滿足

φ(x,y1)-φ(x,y2)≥〈▽yφ(x,y2),y1-y2〉+

η‖y1-y2‖2, ?y1,y2∈Rn,

其中▽yφ表示φ關(guān)于第二變量的偏導(dǎo)數(shù);

(A4) ▽yφ(x,·)是Rn具有模μ≥2η的一致Lipschtz連續(xù)函數(shù),即存在大于零的常數(shù)μ≥2η,使得對(duì)任意的x∈Rn有

‖▽yφ(x,y1)-▽yφ(x,y2)‖≤

μ‖y1-y2‖, ?y1,y2∈Rn;

(A5) 對(duì)任意的x,y∈Rn,▽xφ(x,y)=-▽yφ(x,y).

此時(shí),若φ(x,y)=〈y-x,G(y-x)〉,可知φ(x,y)滿足(A1)?(A5),再取α=1,(10)式變形為

(11)

在本文中,假設(shè)集合S滿足

S={x∈Rn:gi(x)≤0,

i=1,2,…,m},

(12)

其中g(shù)i:Rn→R是二階連續(xù)可微的凸函數(shù),并且Slater約束規(guī)范成立,即存在x0∈Rn,滿足

gi(x0)<0,i=1,2,…,m.

(13)

i=1,2,…,m.

(14)

證明對(duì)于給定的

S={x∈Rn|gi(x)≤0,i=1,2,…,m},

若x*∈S是MVIP(F,S)的解,那么存在ξ(x*)∈?f(x*)滿足

-F(x*)-ξ(x*)∈Ns(x*).

又由于Cs(x*)?coTs(x*)(其中Ns(x*)、Cs(x*)、Ts(x*)分別表示集合S在x*處的法錐、線性化錐、切錐)，從而根據(jù)文獻(xiàn)[8]的性質(zhì)2.12有

Ns(x*)=Ts(x*)*=

(coTs(x*))*?Cs(x*)*,

那么

-F(x*)-ξ(x*)∈Cs(x*)*,

而由于

Cs(x*)={y∈Rn|〈▽gi(x*),y〉≤0,

i∈I(x*)},

其中I(x*)={i|gi(x*)=0}?{1,2,…,m}.

i=1,2,…,m.

證畢.

若S是一般的非空閉凸集,則(5)式所定義的間隙函數(shù)賦值非常困難.因此,Taji等[3]定義了一個(gè)新的多面體代替了(5)式中的集合S,其形式為

M(x)={y∈Rn|gi(x)+

〈▽gi(x),y-x〉≤0,i=1,2,…,m}.

(15)

相應(yīng)地,Taji等[3]定義了問題(2)的新的間隙函數(shù)

顯然，由于M(x)是一個(gè)凸多面集,該新的間隙函數(shù)賦值非常容易.首先證明M(x)所具有的一個(gè)性質(zhì).

定理 2.2設(shè)M(x)是由(15)式所定義的集合,則M(x)是一個(gè)包含(5)式中集合S的一個(gè)凸多面集.

證明任取y∈S?Rn,從而根據(jù)(10)式得gi(y)≤0,i=1,2,…,m.由于gi(x),i=1,2,…,m,是一列二階連續(xù)可微的凸函數(shù),從而根據(jù)引理1.6,對(duì)?x∈Rn有

gi(y)-gi(x)≥〈▽gi(x),y-x〉,

i=1,2,…,m,

從而有

gi(x)+〈▽gi(x),y-x〉≤gi(y)≤0,

i=1,2,…,m.

故y∈M(x),即S?M(x).證畢.

受到文獻(xiàn)[3]思想的啟發(fā),也將(11)式中的S替換為凸多面體M(x),重新定義下列函數(shù):

q(x)=max{-〈F(x),y-x〉+f(x)-f(y)-

(16)

對(duì)給定的x∈S,令

Q(y)=〈F(x),y-x〉-f(x)+f(y)+

定理 2.3設(shè)函數(shù)Q(y)由上式所定義,以及M(x)是由(15)式所定義的凸多面集,那么函數(shù)Q(y)具有唯一的最大值.

證明對(duì)給定的x∈S,令

Q(y)=〈F(x),y-x〉-f(x)+f(y)+

若要證明函數(shù)Q(y)具有唯一的最大值,只需要證明-Q(y)具有唯一的最小值,從而只需要證明-Q(y)是一個(gè)強(qiáng)凸函數(shù)即可.然而這是顯然的.因?yàn)椤碏(x),y-x〉關(guān)于y是線性函數(shù),f是真凸下半連續(xù)泛函，從而混合項(xiàng)部分f(y)-f(x)是凸的;而G-范數(shù)〈y-x,G(y-x)〉/2強(qiáng)凸的,故-Q(y)是強(qiáng)凸的,從而根據(jù)引理1.7可得Q(y)具有唯一的最小值.證畢.

根據(jù)定理2.3,設(shè)L(x)是關(guān)于y的一個(gè)二次規(guī)劃問題:

〈F(x),y-x〉+f(y)-f(x),

s.t.y∈M(x)

(17)

的唯一最大解.此時(shí)(16)式即

q(x)=-〈F(x),L(x)-x〉+f(x)-f(L(x))-

(18)

對(duì)給定的x∈S,設(shè)

N(y)=〈F(x),y-x〉+f(y)-f(x)+

(19)

令指示函數(shù)

且設(shè)

J(y)N(y)+δM(x)(y),

(20)

若y*∈M(x)是(16)式的解,此時(shí)根據(jù)(17)式的最優(yōu)性條件有

0∈?J(y*)=?N(y*)+?δM(x)(y*),

(21)

由于

?N(y*)=?(〈F(x),y-x〉+

F(x)+?f(y*)+G(y*-x).

所以,對(duì)任意的y∈M(x)有

(f+δM(x))(y)-(f+δM(x))(y*)≥

-〈y-y*,F(x)+G(y*-x)〉,

(22)

即

f(y)-(f+δM(x))(y*)≥

-〈y-y*,F(x)+G(y*-x)〉,

(23)

此時(shí)令y*=L(x)∈M(x),則得到變分不等式

〈F(x)+G(L(x)-x),y-L(x)〉+

f(y)-f(L(x))≥0, ?y∈M(x).

(24)

定理 2.4設(shè)x∈Rn,F:Rn→Rn是一連續(xù)映射,f:Rn→(-∞,+∞]是一真凸下半連續(xù)泛函,且x∈S?domf,則以下結(jié)論等價(jià):

(a)x是(1)式的解;

(b) -F(x)∈?(f+δM(x))(x);

(c)L(x)=x.

證明(a)?(b) 假設(shè)x∈S是一般混合變分不等式MVIP(F,S)的解,則對(duì)任意的y∈S有

〈F(x),y-x〉+f(y)-f(x)≥0,

(25)

由于S?M(x),從而

〈F(x),y-x〉+(f+δM(x))(y)-

(f+δM(x))(x)≥0, ?y∈Rn,

(26)

即對(duì)任意的y∈Rn得

(f+δM(x))(y)-(f+δM(x))(x)≥

〈-F(x),y-x〉,

(27)

從而

-F(x)∈?(f+δM(x))(x).

(b)?(c) 假設(shè)-F(x)∈?(f+δM(x))(x),那么0∈F(x)+?(f+δM(x))(x),則對(duì)任意的y∈M(x),

f(y)-f(x)≥〈-F(x),y-x〉.

在上式中令y=L(x)∈M(x),則

f(L(x))-f(x)≥〈-F(x),L(x)-x〉.

由于x∈S?M(x),在(24)式中取y=x有

〈F(x)+G(L(x)-x),x-L(x)〉+

f(x)-f(L(x))≥0.

根據(jù)上述兩式可得

〈G(L(x)-x),L(x)-x〉≤0.

再由G是對(duì)稱正定矩陣可知L(x)=x.

(c)?(a) 假設(shè)L(x)=x,根據(jù)(24)式顯然有

〈F(x),y-x〉+f(y)-f(x)≥0,

?y∈M(x),

(28)

因?yàn)镾?M(x),為了要證明x=L(x)∈M(x)是一般混合變分不等式MVIP(F,S)的解,只需要證明x∈S即可.事實(shí)上,由于x=L(x)=ymax∈M(x),根據(jù)(15)式給定的M(x)的定義,

gi(x)+〈▽gi(x),L(x)-x〉≤0,

i=1,2,…,m.

(29)

所以gi(x)=gi(L(x))≤0,所以x∈S,即x是MVIP(F,S)的解.證畢.

接下來,考慮優(yōu)化問題

minq(x),

s.t.x∈S,

(30)

其中函數(shù)q是由(16)式所定義的.接下來的定理建立了一個(gè)關(guān)于MVIP(F,S)和優(yōu)化問題(30)之間的等價(jià)關(guān)系.

定理 2.5令q:Rn→R是由(16)式所定義的函數(shù),則對(duì)任意的x∈S,都有q(x)≥0.此外x∈S以及q(x)=0當(dāng)且僅當(dāng)x是MVIP(F,S)的解.因此x∈S是MVIP(F,S)的解當(dāng)且僅當(dāng)它是優(yōu)化問題(30)的解并且q(x)=0.

證明由x∈S?M(x),那么根據(jù)定理2.3以及(16)式有

q(x)≥-〈F(x),x-x〉+f(x)-f(x)-

(31)

根據(jù)定理2.4得到x∈S是MVIP(F,S)的解當(dāng)且僅當(dāng)L(x)=x,故只需證明x∈S以及q(x)=0當(dāng)且僅當(dāng)L(x)=x.

必要性 首先,假設(shè)x∈S以及q(x)=0,由于x∈M(x),由(24)式有

〈F(x)+G(L(x)-x),x-L(x)〉+

f(x)-f(L(x))≥0,

從而有

-〈F(x),L(x)-x〉+f(x)-f(L(x))≥

〈L(x)-x,G(L(x)-x)〉,

(32)

不等式的兩邊同時(shí)減去

那么有

-〈F(x),L(x)-x〉+f(x)-f(L(x))-

而由于(18)式

q(x)=-〈F(x),L(x)-x〉+f(x)-f(L(x))-

從而

(33)

但由于G-范數(shù)正定且q(x)=0,則有L(x)=x.

充分性 反過來,假設(shè)L(x)=x,則根據(jù)(18)式,從而有q(x)=0.此外通過二次規(guī)劃問題(17)可知

gi(x)+〈▽gi(x),L(x)-x〉≤0,

i=1,2,…,m,

那么有L(x)=x滿足x∈S,從而有q(x)=0的x就是優(yōu)化問題(31)的最優(yōu)解.證畢.

3 q的連續(xù)性和可微性

定義 3.1[3]令φ:K→2K是一個(gè)集值映射,K是Rn中的一非空子集.

命題 3.2令gi:Rn→R(i=1,2,…,m)是連續(xù)可微的且滿足Slater約束規(guī)范成立,則由(15)式所定義的點(diǎn)集映射M在Rn上是連續(xù)映射.

gi(xk)+〈▽gi(xk),yk-xk〉≤0,

故

gi(x)+〈▽gi(x),y-x〉≤0,

從而

y∈M(x).

所以M(x)在每一個(gè)x處都是閉映射.

另一方面,根據(jù)凸函數(shù)的性質(zhì)有

gi(y)-gi(x)≥〈▽gi(x),y-x〉,

那么有

gi(x)+〈▽gi(x),y-x〉≤gi(y)≤0,

從而

y∈M(x).

gi(x)+〈▽gi(x),y-x〉,

而

M(x)={y∈Rn|gi(x)+

〈▽gi(x),y-x〉≤0,i=1,2,…,m},

從而

M(xk)={yk∈Rn|gi(xk)+

〈▽gi(xk),yk-xk〉≤0,i=1,2,…,m}.

引理 3.3令映射F:Rn→Rn和f:Rn→(-∞,+∞]都是連續(xù)的,如果Slater約束規(guī)范(13)成立,則映射L在任何有界集上是有界的.

證明假設(shè)L在某些有界集C上是無界的,從而存在序列{xk}?C,使得‖L(xk)‖→∞.而根據(jù)連續(xù)函數(shù)的有界性,從而F(xk)在C上是有界的.而f也是連續(xù)的,從而是有界的;而G-范數(shù)是正定的,則根據(jù)(18)式知q(xk)→-∞,即q(xk)無下界.

另一方面,對(duì)于任意的k,由Slater條件知x0∈M(xk),故有

q(xk)=max{-〈F(xk),y-xk〉+f(xk)-

-〈F(xk),x0-xk〉+f(xk)-f(x0)-

而根據(jù)上面{xk}、f(xk)、F(xk)的有界性可知,q(xk)有下界,此時(shí)與假設(shè)矛盾.故有映射L在任何有界集上是有界的.

定理 3.4(a) 假設(shè)F:Rn→Rn是連續(xù)映射,f:Rn→(-∞,+∞]是連續(xù)映射,以及gi:Rn→R(i=1,2,…,m)是連續(xù)可微的,也假設(shè)Slater約束規(guī)范成立,則由(18)式所定義的函數(shù)q在Rn上是連續(xù)的.

(b) 假設(shè)F:Rn→Rn是連續(xù)可微映射,f:Rn→(-∞,+∞]是二階連續(xù)可微映射,以及gi:Rn→R(i=1,2,…,m)是二階連續(xù)可微的,則函數(shù)q在任何方向d∈Rn上是方向可微的,以及它的方向?qū)?shù)為

[▽F(x)-▽2f(x)-G](L(x)-x)-

(34)

其中

Λ(x)={λ∈Rm|F(x)+

λi[gi(x)+〈▽gi(x),L(x)-x〉]=0,

λi≥0,i=1,2,…,m}.

(35)

(b) 的證明來自于文獻(xiàn)[10]的定理2.

如果要通過優(yōu)化問題(30)來獲得(1)式的解,必須要找到q在S上的全局最優(yōu)解,因此想要知道在那個(gè)條件下(30)式的穩(wěn)定點(diǎn)是一個(gè)全局最優(yōu)解,那么在接下來的定理中將回答這個(gè)問題.在回答這個(gè)問題之前,先給出一個(gè)引理.

引理 3.6令映射F:Rn→Rn是連續(xù)可微函數(shù),f:Rn→(-∞,+∞]是二階連續(xù)可微凸函數(shù),約束函數(shù)集gi:Rn→R(i=1,2,…,m)是二階連續(xù)可微的,若d=L(x)=x,那么此時(shí)有

q′(x;d)≤-〈d,(▽F(x)-▽2f(x))d〉+

(36)

其中I+={i|gi(x)>0}.

證明由于d=L(x)-x,那么通過二次規(guī)劃問題(17)的KKT條件,以及找到一個(gè)拉格朗日乘子向量λ有

gi(x)+〈▽gi(x),d〉≤0,λi≥0,

(38)

λi[gi(x)+〈▽gi(x),d〉]=0,

i=1,2,…,m.

(39)

通過(34)、(37)和(39)式可以得到

q′(x;d)≤-〈d,(▽F(x)-▽2f(x))d〉+

定理 3.7假設(shè)映射F:Rn→Rn連續(xù)可微,f:Rn→(-∞,+∞]是二階連續(xù)可微凸函數(shù),且▽F(x)-▽2f(x)是正定的,凸約束函數(shù)集gi:Rn→R(i=1,2,…,m)是二階連續(xù)可微的,以及Slater約束規(guī)范(12)式成立,如果x∈S對(duì)任意的y∈S都有

q′(x;y-x)≥0,

(41)

那么x是一般混合變分不等式MVIP(F,f)的解.

證明假設(shè)x∈S滿足(41)式，根據(jù)Slater條件以及文獻(xiàn)[1]中143頁的結(jié)果可知

M(x)?x+cl{α(y-x):y∈S,α>0}, (42)

那么此時(shí)根據(jù)(41)和(42)式以及q′(x;·)的正齊次性,那么有

q′(x;y-x)≥0, ?y∈M(x),

(43)

由于當(dāng)x∈S時(shí)滿足I+=?,此時(shí)根據(jù)引理3.6有

q′(x;L(x)-x)≤-〈L(x)-x,

(▽F(x)-▽2f(x))(L(x)-x)〉,

(44)

而由于L(x)∈M(x),再根據(jù)(43)和(44)式得到

〈L(x)-x,(▽F(x)-▽2f(x))(L(x)-x)〉≤0.

而根據(jù)題設(shè)條件▽F(x)-▽2f(x)是正定的,從而L(x)=x,再根據(jù)定理2.4,此時(shí)x就是MVIP(F,f)的一個(gè)解.