一般混合變分不等式的新間隙函數

賴學李, 夏福全

(四川師范大學 數學科學學院, 四川 成都 610066)

1 預備知識

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

定義 1.1設S是Rn上的非空閉凸集,F:Rn→Rn是一個映射,f:Rn→(-∞,+∞]是真凸下半連續泛函,而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)

若此時f是閉凸集S上的指示函數,即

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

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

(2)

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

(3)

與問題(2)等價.

(4)

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

(5)

以下是來自文獻[8]的一些與本文有關的定義和結論.

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

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

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

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

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

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

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

定義 1.3正常凸函數f:Rn→(-∞,+∞]在點x∈domf處沿方向d的方向導數記為

(6)

定義 1.4稱向量ξ為凸函數f在點x處的次梯度,即當ξ∈Rn使得對任意的y∈Rn,均有

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

(7)

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

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

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

(8)

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

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

(9)

2 新的間隙函數

(10)

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

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

(A2)φ在Rn×Rn上非負且φ(x,y)=0當且僅當x=y;

(A3)φ(x,·)關于x也是強凸的,也即存在η>0,對任意的x∈Rn滿足

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

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

其中▽yφ表示φ關于第二變量的偏導數;

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

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

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

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

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

(11)

在本文中,假設集合S滿足

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

i=1,2,…,m},

(12)

其中gi:Rn→R是二階連續可微的凸函數,并且Slater約束規范成立,即存在x0∈Rn,滿足

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

(13)

i=1,2,…,m.

(14)

證明對于給定的

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*處的法錐、線性化錐、切錐)，從而根據文獻[8]的性質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)式所定義的間隙函數賦值非常困難.因此,Taji等[3]定義了一個新的多面體代替了(5)式中的集合S,其形式為

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

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

(15)

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

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

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

證明任取y∈S?Rn,從而根據(10)式得gi(y)≤0,i=1,2,…,m.由于gi(x),i=1,2,…,m,是一列二階連續可微的凸函數,從而根據引理1.6,對?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).證畢.

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

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

(16)

對給定的x∈S,令

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

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

證明對給定的x∈S,令

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

若要證明函數Q(y)具有唯一的最大值,只需要證明-Q(y)具有唯一的最小值,從而只需要證明-Q(y)是一個強凸函數即可.然而這是顯然的.因為〈F(x),y-x〉關于y是線性函數,f是真凸下半連續泛函，從而混合項部分f(y)-f(x)是凸的;而G-范數〈y-x,G(y-x)〉/2強凸的,故-Q(y)是強凸的,從而根據引理1.7可得Q(y)具有唯一的最小值.證畢.

根據定理2.3,設L(x)是關于y的一個二次規劃問題:

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

s.t.y∈M(x)

(17)

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

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

(18)

對給定的x∈S,設

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

(19)

令指示函數

且設

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

(20)

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

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

(21)

由于

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

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

所以,對任意的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)

此時令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設x∈Rn,F:Rn→Rn是一連續映射,f:Rn→(-∞,+∞]是一真凸下半連續泛函,且x∈S?domf,則以下結論等價:

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

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

(c)L(x)=x.

證明(a)?(b) 假設x∈S是一般混合變分不等式MVIP(F,S)的解,則對任意的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)

即對任意的y∈Rn得

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

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

(27)

從而

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

(b)?(c) 假設-F(x)∈?(f+δM(x))(x),那么0∈F(x)+?(f+δM(x))(x),則對任意的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.

根據上述兩式可得

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

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

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

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

?y∈M(x),

(28)

因為S?M(x),為了要證明x=L(x)∈M(x)是一般混合變分不等式MVIP(F,S)的解,只需要證明x∈S即可.事實上,由于x=L(x)=ymax∈M(x),根據(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)的解.證畢.

接下來,考慮優化問題

minq(x),

s.t.x∈S,

(30)

其中函數q是由(16)式所定義的.接下來的定理建立了一個關于MVIP(F,S)和優化問題(30)之間的等價關系.

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

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

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

(31)

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

必要性 首先,假設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)

不等式的兩邊同時減去

那么有

-〈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-范數正定且q(x)=0,則有L(x)=x.

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

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

i=1,2,…,m,

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

3 q的連續性和可微性

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

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

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

故

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

從而

y∈M(x).

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

另一方面,根據凸函數的性質有

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→(-∞,+∞]都是連續的,如果Slater約束規范(13)成立,則映射L在任何有界集上是有界的.

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

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

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

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

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

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

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

[▽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) 的證明來自于文獻[10]的定理2.

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

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

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

(36)

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

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

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假設映射F:Rn→Rn連續可微,f:Rn→(-∞,+∞]是二階連續可微凸函數,且▽F(x)-▽2f(x)是正定的,凸約束函數集gi:Rn→R(i=1,2,…,m)是二階連續可微的,以及Slater約束規范(12)式成立,如果x∈S對任意的y∈S都有

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

(41)

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

證明假設x∈S滿足(41)式，根據Slater條件以及文獻[1]中143頁的結果可知

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

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

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

(43)

由于當x∈S時滿足I+=?,此時根據引理3.6有

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

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

(44)

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

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

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