MPVCC問題的M穩定性的序列最優性條件研究

許 娜， 姜 姍， 沈 潔

(遼寧師范大學 數學學院，遼寧 大連 116029)

本文主要研究帶有垂直互補約束的數學規劃 (Mathematical program with vertical complementarity constraints) 問題，簡稱MPVCC，

minf(x)
s.t. min{Fk1(x),Fk2(x),…,Fkl(x)}=0,k=1,…,m,g(x)≤0,h(x)=0.

其中，f：n→,g：n→p,h：n→q,Fki：n→(k=1,…,m,i=1,…,l)是連續可微函數.

MPVCC問題在工程設計、交通運輸、通信與管理等許多領域都有著廣泛的應用,因而研究該問題具有重要的理論意義和實際價值.由于垂直互補約束的特殊結構，往往不能直接用非線性規劃的理論結果來研究MPVCC問題．在2000年，Scheel和Scholtes[1]提出了MPVCC問題的C-,B-,S-穩定性條件.基于上述研究工作，梁彥超等人[2]給出了MPVCC的M-穩定性條件. 2013年,張杰等人[3]給出了一種求解MPVCC問題的正則化方法，然后討論了MPVCC問題的常用約束規范,例如：MPVCC-CRCQ,MPVCC-CPLD,MPVCC-rCPLD等約束規范[4].

基于序列最優性條件在算法的收斂性分析和數值表現等方面的重要應用, Andreani等人[5]和Ramos[6]給出了帶有互補約束的數學規劃(MPCC)問題的序列最優性條件.本文給出了比MPCC問題更一般的MPVCC問題的序列最優性條件,即AM穩定性. 然后, 給出與MPVCC問題的AM穩定性相關的AM正則性，證明了MPVCC問題的局部最優解在AM穩性條件下是M穩定點，這說明了AM正則性是一種能夠保證M穩定性的約束規范. 最后，討論了AM正則性與其他的MPVCC約束規范的關系．

1 基礎知識

本節給出文中需要用到的一些基本概念.

?Fki(x*)Γki=0,k=1,…,m,i=1,…,l,g(x*)Tλg=0,

當Fki(x*)=Fki′(x*)=0時,或者Γki>0,Γki′>0或者ΓkiΓki′=0.

下面給出指標集的定義，對于一個給定的MPVCC問題的可行點x*，令

Ig=Ig(x*)={i|gi(x*)=0},

K(x*)={k∈{1,…,m}|?i,j,i≠js.t.Fki(x*)=Fkj(x*)=0},

Jk(x*)={i∈{1,…,l}|?i,j,j≠i,Fki(x*)=Fkj(x*)=0},

定義1.4[4](MPVCC-rCPLD)設x*是MPVCC問題的一個可行點，{?hi(x*),i∈Ih}是空間span{?hi(x*),i=1,…,q}的一組基，稱MPVCC松弛正線性約束規范(MPVCC-rCPLD)在x*點處成立，如果存在x*的鄰域N(x*)使得

(1)對任取的x∈N(x*),{?hi(x*),i=1,…,q}有相同的秩;

(2)對?J0?Ig,?K0?IF(x*),若

{ ?gi(x*),i∈J0},{?hi(x*),i∈Ih},{ ?Fij(x*)=0,(i,j)∈K0}

是正線性相關的,那么對于每個x∈N(x*),

{?gi(x),i∈J0},{?hi(x),i∈Ih},{?Fij(x)=0,(i,j)∈K0}

是線性相關的.

2 關于M穩定性的序列最優性條件

本節給出了關于MPVCC問題M穩定性的近似條件(AM穩定性)的定義，并證明AM穩定性條件是一個合理的序列最優性條件.顯然，AM穩定性條件有助于MPVCC算法的收斂性分析.

定義2.1(AM穩定點)MPVCC的可行點x*是近似M穩定點(AM穩定點),如果存在序列{xt}?n和,k=1,…,m,i=1,…,l,使得

(1)

(2)

(3)

(4)

(5)

為了證明AM穩定性條件是序列最優性條件，MPVCC問題寫為下述帶有幾何約束的形式

(6)

定理2.2假設x*是MPVCC問題的局部最優解,則x*是AM穩定點.

(7)

令(xt,zt)是問題(7)的全局最優解，接下來證明{(xt,zt)}→(x*,Φ(x*)),由于(xt,zt)是全局最優解，所以得到

(8)

整理得

由文獻[6]中定理6.12得到

其中，

其中，γt=(γg,t,γh,t,γF,t)∈NΛ(zt),zt=(zg,t,zh,t,zF1,t,…,zFm,t),

所以式(3)成立.

進而有

所以式(4)和式(5)成立,綜上所述x*是AM穩定點.

3 保證M穩定性的新的約束規范

衡量序列最優性條件的一種方法是將其與精確的穩定性聯系起來. 也就是說，需要研究在MPVCC問題的約束規范下，證明AM穩定點就是M穩定點. 為此，首先給出與MPVCC問題的AM穩定性相關的AM正則性，然后證明了AM正則性實際上是一種能夠保證M穩定性的新的約束規范．最后，基于上述結果， 比較AM正則性與MPVCC-rCPLD、MPVCC-CCP約束規范的關系，可以得到AM正則性是一個非常弱的約束規范．

定理3.2假設x*是MPVCC問題的一個可行點,AM正則性在x*處成立當且僅當對于任意連續可微的目標函數,x*是AM穩定點就意味著x*是M穩定點.

證(必要性)令f是一個連續可微的函數,x*是AM穩定點,存在一個序列{xt}?n且,k=1,…,m,i=1,…,l.由于以下兩個式子成立

(9)

再由

可推出

其中,

(10)

由AM正則性可知，

所以x*是MPVCC問題的M穩定點.

由定理2.2和定理3.2，可以得到下面的結果．

推論3.3假設x*是MPVCC問題的一個局部最優解,如果AM正則性在x*點處成立，則x*是M穩定點.

該結果意味著AM正則性確實是關于M穩定點的約束規范，下面將比較AM正則性與其他的MPVCC約束規范的關系．

定理3.4假設x*是MPVCC問題的一個可行點,如果MPVCC-rCPLD約束規范在可行點x*處成立,那么AM正則性在x*點處也成立.

(11)

(12)

定義3.5假設x*是問題(6)的可行點，如果集值映射n×Λ?Φ(x)TNΛ(z)在(x*,Φ(x*)) 點處是外半連續的,即

則稱MPVCC錐連續性(MPVCC-CCP)約束規范在x*點處成立.

定理3.6假設x*是MPVCC問題的一個可行點,如果AM正則性在x*點處成立，那么MPVCC-CCP約束規范在x*點處成立.

證如果AM正則性在x*點處成立,由定理3.2可知,若x*是AM穩定點,能推出x*是M穩定點，令

則存在序列{xt},{ωt},{γt}和{zt}使得

xt→x*,zt→Φ(x*),ωt=?Φ(xt)Tγt→ω*,

其中,zt=(zg,t,zh,t,zF1,t,…,zFm,t),γt=(γg,t,γh,t,γF,t)∈NΛ(zt),

下面驗證

定義f(x)=-(ω*)Tx,則有?f(xt)+ωt=-ω*+ωt→0,可知x*是AM穩定點，由定理3.2可知x*也是M穩定點,可以推出

所以MPVCC-CCP約束規范在x*點處成立.

4 小 結

本文主要研究了MPVCC問題的序列最優性條件，得到了MPVCC問題的AM穩定性條件，并證明AM穩定性條件是一個合理的序列最優性條件. 然后，給出與MPVCC問題的AM穩定性相關的AM正則性，并證明了AM正則性實際上是一種能夠保證M穩定性的新的約束規范．最后，比較了AM正則性與其他的MPVCC約束規范的關系．