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

吳 錚，劉慶懷，商玉鳳

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

0 引 言

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

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∈?Ω時(shí),{gi(x)|i∈I(x)}是正獨(dú)立的,即對(duì)任意給定的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]給出了一個(gè)求解非凸規(guī)劃問(wèn)題的動(dòng)約束同倫方法(簡(jiǎn)稱CSCH方法),通過(guò)構(gòu)造動(dòng)約束組合同倫方程,在弱條件下證明了CSCH方法的全局收斂性,并運(yùn)用算例表明了CSCH方法的有效性和可行性。文獻(xiàn)[2-6]將CSCH方法應(yīng)用到解無(wú)界非凸域上多目標(biāo)規(guī)劃問(wèn)題、變分不等式問(wèn)題、不動(dòng)點(diǎn)問(wèn)題上;文獻(xiàn)[7]利用凝聚光滑化方法,給出了求解非凸優(yōu)化問(wèn)題的凝聚CSCH方法。在利用CSCH方法求解非凸規(guī)劃問(wèn)題時(shí),如何構(gòu)造動(dòng)約束函數(shù)成為關(guān)鍵點(diǎn)。

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

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

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

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

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

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

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

(3)

假設(shè)條件2:

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

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

其中符號(hào)說(shuō)明如下:

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

(4)

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

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

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

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

定義2設(shè)

(5)

i=1,2,…,n,

若

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

為含原點(diǎn)的連通有界閉區(qū)域,則稱該區(qū)域?yàn)槎嗉夥峭褂?其中aij,bi(i=1，2，…,n,j=1，2，…,n)均為正值常數(shù)。

當(dāng)n=2時(shí)，

(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)

有解。

因?yàn)?0,且

即

易知式(10)有解

證畢。

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

(11)

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

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

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

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

(12)

由x1>0可知，

xg1(x,t)≠0,

(13)

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

若#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時(shí),有

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時(shí),若vi≠0,則必有

故滿足正獨(dú)立性。

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

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

成立,則必有

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

證明

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

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

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

證畢。

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

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

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

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

3 結(jié) 語(yǔ)

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