一類典型非凸域動約束函數(shù)構(gòu)造

吳 錚，劉慶懷，商玉鳳

(1.長春工業(yè)大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，吉林 長春 130012;2.長春財經(jīng)學(xué)院 經(jīng)濟(jì)學(xué)院，吉林 長春 130122)

0 引 言

考慮如下形式的非凸規(guī)劃問題

minf(x),

s.t.gi(t)≤0,i=1,2,…,m,

(1)

其中f:Rn→R,g:Rn→Rm,g=(g1,g2,…,gm)T,f(x),gi(x)∈Cr(r≥2)。

易知(1)的KKT系統(tǒng)為

f(x)+g(x)y=0,

Yg(x)=0,y≥0,

(2)

其中

Y=diag{y1,y2,…,ym},

假設(shè)條件1：

(A1)Ω連通有界,Ω0非空;

(A2)當(dāng)x∈?Ω時,{gi(x)|i∈I(x)}是正獨立的,即對任意給定的vi≥0,如果方程

成立,則必有

vi=0，i∈I(x)，

其中

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

Ω0={x|gi(x)<0,i=1,2,…,m},

?Ω=ΩΩ0,

I(x)={i|gi(x)=0,i=1,2,…,m}。

文獻(xiàn)[1]給出了一個求解非凸規(guī)劃問題的動約束同倫方法(簡稱CSCH方法),通過構(gòu)造動約束組合同倫方程,在弱條件下證明了CSCH方法的全局收斂性,并運用算例表明了CSCH方法的有效性和可行性。文獻(xiàn)[2-6]將CSCH方法應(yīng)用到解無界非凸域上多目標(biāo)規(guī)劃問題、變分不等式問題、不動點問題上;文獻(xiàn)[7]利用凝聚光滑化方法,給出了求解非凸優(yōu)化問題的凝聚CSCH方法。在利用CSCH方法求解非凸規(guī)劃問題時,如何構(gòu)造動約束函數(shù)成為關(guān)鍵點。

文中首先給出了多尖非凸域的定義,在該區(qū)域上構(gòu)造了動約束函數(shù),并在較弱條件下證明了該動約束函數(shù)滿足邊界正則性條件及法錐條件,最后,通過數(shù)值例子表明構(gòu)造方法是可行的、有效的。

1 預(yù)備知識

定義1(正則性定義) 設(shè)φ:D?Rm→Rn是光滑映射,任意的y∈Rn,記φ-1(y)={x∈D|φ(x)=y}為y在映射φ下的逆像。如果φ在x(0)∈D處的Jacobi矩陣?φ(x(0))?x行滿秩,則稱x(0)是映射φ的正則點;否則稱x(0)是映射φ的臨界點。如果對所有的x(0)∈φ-1(y(0))都是映射φ的正則點;則稱y(0)是映射φ的正則值;否則稱y(0)是映射φ的臨界值。

引理1(參數(shù)化的Sard定理) 設(shè)V?Rn,U?Rm均為開集,φ:V×U→RP是Cr映射,這里r>max{0,m-p}。如果0∈RP是φ的一個正則值,則對幾乎所有a∈V,0是φ(a,·)的一個正則值。

引理2(逆映像定理) 如果0是映射φ(a,·)的正則值,則逆映射φ-1(a,·)由有限條一維光滑流形組成。

引理3(一維流形分類定理) 一維帶邊光滑流形的每個連通分支,或者微分同胚于單位圓周S1,或者微分同胚于實數(shù)區(qū)間(0,1]或[0,1)或[0,1]。

為求解非凸優(yōu)化問題(1),構(gòu)造含參變量t的非凸優(yōu)化問題

(3)

假設(shè)條件2:

(B3)對任意給定的t∈(0,1],Ω(t)是連通有界非空閉集;

(B5)Ω(1)滿足法錐條件,即對任意的x∈?Ω(1),

其中符號說明如下:

?Ω(t)=Ω(t)〗Ω0(t);

(4)

式中：D=t(x-x0)。

H-1(0)={t∈(0,1],x∈Ω(t),

2 典型非凸域的動約束函數(shù)構(gòu)造

首先給出2維情形下多尖非凸域上的動約束函數(shù)構(gòu)造方法,然后將該構(gòu)造方法從2維情形推廣到n維情形。

定義2設(shè)

(5)

i=1,2,…,n,

若

Ω={x|gi(x)≤0，i=1,2,…,2n}

為含原點的連通有界閉區(qū)域,則稱該區(qū)域為多尖非凸域,其中aij,bi(i=1，2，…,n,j=1，2，…,n)均為正值常數(shù)。

當(dāng)n=2時，

(6)

圖1 多尖非凸域(陰影部分)

為了證明非凸集Ω的有界性,在2維情形下給出如下定理。為方便討論在式(6)中取

aij=a，j≠i,i=1,2,j=1,2,3,4,

bi=b，i=1,2,3,4，

令

Ω1={x|x1≥0，x2≥0，g1(x)≤0,g2(x)≤0},

Ω2={x|x1≤0，x2≥0，g1(x)≤0,g4(x)≤0},

Ω3={x|x1≥0，x2≤0，g2(x)≤0,g3(x)≤0},

Ω4={x|x1≤0，x2≤0，g3(x)≤0,g4(x)≤0},

其中

i=1,2,3,4,

且

圖示意圖(陰影部分)

為此僅需證方程組

(7)

即

(8)

一般情形,當(dāng)aij

bi=b，i=1,2,3,4,

可同證Ω為有界閉集。

證畢。

類似地,在n維情形下可得到如下定理。為方便討論在式(5)中取

aij=a，j≠i,i=1,2,…,n,j=1,2,…,n,

bi=b，i=1,2,…,n。

根據(jù)約束函數(shù)的構(gòu)成方式,只需證方程組

(9)

即

(10)

有解。

因為00,且

即

易知式(10)有解

證畢。

構(gòu)造動約束函數(shù)如下

(11)

t=1時圍成區(qū)域(圓形區(qū)域)如圖3所示。

圖3 t=1時圍成區(qū)域(圓形區(qū)域)

在2維情形有如下邊界正獨立性結(jié)論:

1)當(dāng)t=0時,由假設(shè)條件1知原可行域滿足正獨立性。

(12)

由x1>0可知，

xg1(x,t)≠0,

(13)

所以,當(dāng)#I(x,t)=1時,正獨立性成立。

若#I(x,t)=2,不妨設(shè)I(x,t)={1，2};若存在vi>0,i=1,2給出證明。由式(11)得到

v1

(14)

往證,當(dāng)且僅當(dāng)v1=0,v2=0時,有

v1

成立,利用反證法,即證明v1,v2不全為零。由類似定理2取a12=a,a21=a,x1=x2且x1,x2均非零,則

v1((1-t)+2tx1)+v2((1-t)(-2ax1)+2tx1)=0,

v1((1-t)(-2ax1)+2tx1)+v2((1-t)+2tx1)=0,

(15)

因此v1=v2,若

(1-t)+2tx1+(1-t)(-2ax1)+2tx1=0,

(16)

由式(16)解得

(17)

3)當(dāng)t=1時,若vi≠0,則必有

故滿足正獨立性。

綜上所述,當(dāng)t∈[0,1]時,可行域滿足正獨立性。

在n維情形給出如下定理。

成立,則必有

vi=0，i∈I(x,t)。

證明

3)由定理2可知,Ω=Ω(0)是連通有界閉集,Ω(1)是連通有界閉凸集,對任意給定的t∈[0,1],由動約束函數(shù)構(gòu)造方法可知Ω(0)?Ω(t)?Ω(1),因此Ω(t)為有界連通閉集。滿足假設(shè)條件(B3);

4)由定理4可知，對任意給定的t∈[0,1],滿足動邊界正獨立性,即滿足假設(shè)條件(B4);

成立,從而滿足假設(shè)條件(B5)。

證畢。

例:解如下非凸規(guī)劃問題

構(gòu)造動約束函數(shù)如下:

求解非凸規(guī)劃問題路徑跟蹤時區(qū)域的變化過程曲線形狀如圖4所示。

(a) 當(dāng)t=1時約束區(qū)域Ω(1)

3 結(jié) 語

對一類典型多尖非凸區(qū)域上的非凸規(guī)劃問題給出了動約束函數(shù)的構(gòu)造方法,并在假設(shè)條件下證明了動可行域的有界性以及邊界正獨立性,數(shù)值算例表明構(gòu)造方法的有效性和可行性,從而進(jìn)一步擴(kuò)大了CSCH方法求解非凸規(guī)劃的范圍，將動約束函數(shù)的構(gòu)造方法推廣到一般的非凸區(qū)域是后續(xù)的研究工作。