MPVCC問題的M穩(wěn)定性的序列最優(yōu)性條件研究

許 娜， 姜 姍， 沈 潔

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

本文主要研究帶有垂直互補約束的數(shù)學規(guī)劃 (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)是連續(xù)可微函數(shù).

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

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

1 基礎知識

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

?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松弛正線性約束規(guī)范(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穩(wěn)定性的序列最優(yōu)性條件

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

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

(1)

(2)

(3)

(4)

(5)

為了證明AM穩(wěn)定性條件是序列最優(yōu)性條件，MPVCC問題寫為下述帶有幾何約束的形式

(6)

定理2.2假設x*是MPVCC問題的局部最優(yōu)解,則x*是AM穩(wěn)定點.

(7)

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

(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穩(wěn)定點.

3 保證M穩(wěn)定性的新的約束規(guī)范

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

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

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

(9)

再由

可推出

其中,

(10)

由AM正則性可知，

所以x*是MPVCC問題的M穩(wěn)定點.

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

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

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

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

(11)

(12)

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

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

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

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

則存在序列{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穩(wěn)定點，由定理3.2可知x*也是M穩(wěn)定點,可以推出

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

4 小 結(jié)

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