帶分片光滑約束函數(shù)優(yōu)化問題的區(qū)域分割方法

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

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

0 引 言

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

1 預(yù)備知識

考慮非凸非光滑優(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)化問題。

文中設(shè)

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}為嚴(yán)格可行域，?Ω=ΩΩ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。

假設(shè)條件1:

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

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

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

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

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

圖1 R2上的可行域

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

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

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∈Ω處達(dá)到局部極小，則

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

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

1)當(dāng)I(x)≠?時，則

2)當(dāng)I(x)=?時，則

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

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

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

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

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

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

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

(3)

或

(4)

2 主要結(jié)論

引理3

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

令

證畢。

由于問題(1)是一類帶洞非凸非光滑優(yōu)化問題，因此根據(jù)文獻(xiàn)[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)正線性獨立。

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

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

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

下面證明第一種情況。

由已知得

?g1(x)=a1，

?gm+1(x)=2x，

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

a1+2λx=0,

那么

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

即

下面證明第二種情況。

由假設(shè)條件2中|B|≠0可知，

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

那么當(dāng)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設(shè)x∈S1，若x∈Ω2，x?S2且g1(x)=0，則x?S。

證明 假設(shè)x∈S，

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

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

證畢。

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

證明 假設(shè)x∈S，

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

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

證畢。

3 結(jié) 語

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