王柳婷， 劉慶懷， 商玉鳳， 劉傲多

(1.長春工業(yè)大學 數(shù)學與統(tǒng)計學院， 吉林 長春 130012;2.長春財經(jīng)學院經(jīng)濟學院， 吉林 長春 130122；3.長春建筑學院 基礎教學部， 吉林 長春 130607)

0 引 言

許多實際問題中的優(yōu)化問題常常是非凸優(yōu)化問題，因此解決非凸優(yōu)化問題的理論和算法始終是優(yōu)化領域的熱點問題。近年來，文獻[1-5]給出了非凸優(yōu)化問題在滿足法錐條件、擬法錐條件或偽錐條件下的組合同倫方程。文獻[6]提出動約束組合同倫方法。文獻[7]給出了一類帶洞非凸域上函數(shù)極值的動約束同倫算法。對于非凸非光滑優(yōu)化問題學者們也提出了很多辦法，如凝聚同倫方法[8-10]、迫近束方法[11]、擬牛頓型束方法[12]、近似凸差分解方法[13]、不可行迫近束方法[14]、鄰近增量聚合梯度方法[15]、鄰近濾子束方法[16]等。文獻[17]針對單洞非凸優(yōu)化問題首次提出區(qū)域分割方法，在原問題的約束函數(shù)為光滑函數(shù)的條件下，證明了子問題與原問題KKT解的關系。文中將區(qū)域分割方法應用于求解非凸非光滑優(yōu)化問題，并且證明了子問題KKT解與原問題KKT解的關系。

1 預備知識

考慮非凸非光滑優(yōu)化問題

(1)

其中,f:Rn→R，gi:Rn→R(i=1,2,…,m+1)，f,gi(i=1,2,…,m+1)是連續(xù)可微的，x∈Rn。令

該函數(shù)是分片光滑函數(shù)，從而問題(1)也稱為帶分片光滑約束函數(shù)的優(yōu)化問題。

文中設

gm+1(x)=‖x‖2-r2，

其中,ai=(ai1,ai2,…,ain)T∈Rn，bi∈R，1≤i≤m，r∈R++，m>n(文中取m=n+1)。

記號如下：

Ω={x|h(x)≤0,gm+1(x)≤0}為可行域，Ω0={x|h(x)<0,gm+1(x)<0}為嚴格可行域，?Ω=ΩΩ0為可行域邊界，

D1={x|h(x)≥0}，

D2={x|gm+1(x)≤0}，

M={1,2,…,m}，

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

b=(b1,b2,…,bm)T∈Rm。

假設條件1:

1)D1有界，即存在一個常數(shù)d，對任意x∈D1滿足‖x‖≤d。

2)?Ω是正則的，即?x∈?Ω，?gi(x)(i∈I(x))正線性獨立，若I(x)=?，則?gm+1(x)≠0。

對問題(1)中的約束函數(shù)作如下假設。

假設條件2:

1)令B=(A,b)，滿足|B|≠0，其中A=(a1,a2,…,am)T。

2)A滿足ai×aj≠0，其中i,j=1,2,…,m，且i≠j。

3)對?x∈?D1，有

gi(x)>0,i∈MI(x)。

(2)

在上面假設條件下可行域如圖1所示(R2情形)。

圖1 R2上的可行域

由于問題(1)中的約束函數(shù)h(x)是非光滑函數(shù)，所以在討論最優(yōu)性一階必要條件時需要如下非光滑分析結(jié)論。

引理1[18]如果f:Rn→R在Ω上是局部Lipschitz連續(xù)的，且在x∈Ω處達到局部極小，則

0∈?f(x)+NΩ(x)，

這里?f(x)是f(x)在x處的Clarke廣義梯度，NΩ(x)是Ω在x∈Ω處的法錐。

引理2[18]如果f(x)在x處是連續(xù)可微函數(shù)，則

?f(x)={?f(x)}。

推論1[18]若f(x)是連續(xù)可微的，且在Ω上于x∈Ω處達到局部極小，則

-?f(x)∈NΩ(x)。

針對問題(1)，在滿足假設條件1和假設條件2的條件下，對?x∈?Ω，在x處的法錐分為如下兩種情況：

1)當I(x)≠?時，則

2)當I(x)=?時，則

NΩ(x)={ym+1?gm+1(x)|ym+1≥0}。

若問題(1)在x∈?Ω處達到局部極小時，由引理1和引理2可知，

-?f(x)∈NΩ(x)。

即當I(x)≠?時，存在yi≥0,i∈I(x)，使得

當I(x)=?時，存在ym+1≥0，使得

?f(x)+ym+1?gm+1(x)=0。

綜上，問題(1)在x∈?Ω處達到局部極小時，一階最優(yōu)性必要條件(也稱為KKT系統(tǒng))可寫成

(3)

或

(4)

2 主要結(jié)論

引理3

2)若r>d成立，則Ω0非空。

令

證畢。

由于問題(1)是一類帶洞非凸非光滑優(yōu)化問題，因此根據(jù)文獻[17]提出的區(qū)域分割方法，將可行域Ω用g1(x)=0分割成Ω1和Ω2兩個區(qū)域，記

Ω1={x|g1(x)≥0,h1(x)≤0,gm+1(x)≤0}，

Ω2={x|g1(x)≤0,gm+1(x)≤0}，

從而問題(1)被分解為如下兩個子問題。

(5)

s.t. minf(x),

g1(x)≤0,

gm+1(x)=‖x‖2-r2≤0。

(6)

I1(x)={i|gi(x)=0,i=1,2,…,m+1}，

I2(x)={i|gi(x)=0,i=1,m+1}，

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

引理4對?x∈?Ω1，有?gi(x)(i∈I(x)),?gm+1(x)正線性獨立。

證明 由假設條件1和2可知，只需證明以下兩種情況。

1)當I1(x)={1,m+1}時，{?gi(x)|i∈I1(x)}正線性獨立。

2)當1≤#I3(x)≤m-2時，?g1(x)，?gi(x)(i∈I3(x))正線性獨立。

下面證明第一種情況。

由已知得

?g1(x)=a1，

?gm+1(x)=2x，

假設?g1(x),?gm+1(x)正線性相關，則存在λ∈R+，使得

a1+2λx=0,

那么

由于λ≠0，將上式代入g1(x)=0，gm+1(x)=0聯(lián)立可得

即

下面證明第二種情況。

由假設條件2中|B|≠0可知，

所以(a1,a2,…,am-1)構(gòu)成一組基底，即向量組(a1,a2,…,am-1)線性無關，?g1(x),…,?gm-1(x)正線性獨立。

那么當1≤#I3(x)≤m-2時，?g1(x)，?gi(x)(i∈I3(x))正線性獨立。

證畢。

由引理1類似于問題(1)的KKT系統(tǒng)的討論，得問題(5)的KKT系統(tǒng)為

(7)

引理5對?x∈?Ω2，有?gi(x)(i∈I2(x))正線性獨立。

證明 由引理4即可得到。

問題(6)的KKT系統(tǒng)為

(8)

令S={x*∈Ω|x*為問題(1)的KKT解}，S1={x*∈Ω1|x*為問題(5)的KKT解}，S2={x*∈Ω2|x*為問題(6)的KKT解}。為求解該非光滑非凸域上優(yōu)化問題(1)的KKT解，給出以下定理。

定理1若x∈S1且g1(x)>0，則x∈S。

1)若m+1∈I1(x)，則式(9.1)可寫為

2)若m+1?I1(x)，則式(9.1)可寫為

綜上所述，若x∈S1且g1(x)>0，則x∈S。

證畢。

定理2若x∈S2，但x?Ω1，則x∈S。

1)若m+1∈I1(x)，x?Ω1，則式(10.1)可寫為

2)若m+1?I1(x)，x?Ω1，則式(10.1)可寫為

綜上所述，若x∈S2，但x?Ω1，則x∈S。

證畢。

定理3若S1∩S2≠?且x∈S1∩S2，則x∈S。

分兩種情況討論:

1)若m+1∈I1(x)，由式(11.1)和式(12.1)相減得

再由引理4和引理5可知，?Ω1,?Ω2是正則的,則

那么

又因為

所以

2)若m+1?I1(x)，由式(11.1)和式(12.1)相減得

則同1)可得

綜上所述，若S1∩S2≠?且x∈S1∩S2，則x∈S。

證畢。

為了證明下面定理，先給出引理6，且以下討論的S、S1和S2分別是問題(1)、問題(5)和問題(6)是局部極小解。

引理6若x∈S，則x∈S1且x∈S2。

定理4設x∈S1，若x∈Ω2，x?S2且g1(x)=0，則x?S。

證明 假設x∈S，

根據(jù)引理6可得x∈S1且x∈S2。

與x?S2矛盾，故x?S。

證畢。

定理5設x∈S2，若x∈Ω1，x?S1且g1(x)=0，則x?S。

證明 假設x∈S，

根據(jù)引理6可得x∈S1且x∈S2。

與x?S1矛盾，故x?S。

證畢。

3 結(jié) 語

討論的可行域為帶分片線性約束的非凸可行域，針對上述區(qū)域，給出一種區(qū)域分割方法，并證明了在一定條件下可以通過求子問題的解得到原問題的解。區(qū)域分割方法能夠解決更加復雜的非凸優(yōu)化問題。將區(qū)域分割方法應用于實際問題和更多復雜的可行域是接下來的研究工作。