非凸最優(yōu)化問題可行解序列的有限終止性

張猛，趙文玲，郭希敏，張茜

(山東理工大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 山東 淄博 255049)

設(shè)x∈Rn，〈·，·〉表示Rn中的內(nèi)積。

x在閉集C上的投影定義為

x到C的距離定義為

如果C是閉集, 則有

dist(x,C)=‖PC(x)-x‖。

C的極錐定義為

C°={y∈Rn|〈y,x〉≤0,?x∈C}。

據(jù)文獻[1]命題6.5,本文有

TC(x)°=NC(x)。

當(dāng)C是凸集時,由文獻[1]定理6.9, 本文有

?x∈C}。

若?Sf(x)=PTS(x)(-?f(x))，稱之為f(·)在S上的投影梯度, 簡記作 ?Sf。

序列{xk}?Rn有限終止于C, 如果存在k0,當(dāng)k≥k0時，有xk∈C。

1 強非退化集與弱強極小集

考慮最優(yōu)化問題(NP):

當(dāng)f(x)是凸函數(shù)時, (NP)是凸最優(yōu)化問題；當(dāng)f(x)是非凸函數(shù)時, (NP)是非凸最優(yōu)化問題；當(dāng)f(x)的梯度?f連續(xù)時, (NP)是光滑最優(yōu)化問題。

對于最優(yōu)化問題(NP)的解集S*, Burke等[2]將強單一極小點的概念進行推廣, 建立了弱強極小(weak sharp minima)集的概念, 它包含了解集是非單點集的情況。 如果存在僅依賴于f,S和S*的常數(shù)α*>0, 使得對?x∈S與?x*∈S有

f(x)-f(x*)≥α*dist(x,S*)，

(1)

本文稱S*是弱強極小集,

(2)

關(guān)于最優(yōu)化問題由算法所產(chǎn)生的可行解序列的有限終止性問題,長期受到廣泛的關(guān)注與研究。解集強非退化性的概念在可行解序列有限終止性問題中也起到了重要的作用[5-8]。 目前已驗證最優(yōu)化問題在解集滿足弱強極小或(強)非退化的條件下能使某些逼近點算法[9-12]與其他類型算法[13-18]的可行解序列具有有限終止性。

對于凸最優(yōu)化問題(NP)解集的強非退化集與弱強極小集的概念,文獻[6，8]給出了如下定義。

定義1如果

(3)

定義2如果

(4)

Burke等[2]關(guān)于凸最優(yōu)化問題的可行解序列的有限終止性定理(簡化形式)如下。

定理1對非凸最優(yōu)化問題是不成立的。舉例如下。

例1非凸最優(yōu)化問題

s.t. 1-x≤0。

其最優(yōu)解集為

是弱強極小集也是非退化集。對于可行解序列{xk}={2,3,…,k,…}, 有(注意TS(xk)=R)

由此例知, 對非凸最優(yōu)化問題, 雖然它的解集既是弱強極小集又是強非退化集, 但定理1結(jié)論并不成立。 因此本文有必要對非凸最優(yōu)化問題解集的強非退化與弱強極小的概念進行推廣,進一步研究非凸最優(yōu)化問題可行解序列有限終止性的條件。

本文首先對非凸最優(yōu)化問題(NP)的解集, 給出廣義強非退化集和廣義弱強極小集的概念,它們分別是凸最優(yōu)化問題中強非退化集與弱強極小集概念的推廣。 然后在非凸最優(yōu)化問題(NP)的解集是廣義強非退化或廣義弱強極小的情況下, 分別給出了其可行解序列有限終止于解集的充分與必要條件， 這些結(jié)果分別包含了現(xiàn)有相關(guān)文獻([2,14,17,19]) 中相應(yīng)的結(jié)論。 最后討論了廣義強非退化和廣義弱強極小的簡單應(yīng)用。

2 廣義強非退化集與廣義弱強極小集

為了進一步研究非凸最優(yōu)化問題可行解序列的有限終止性的條件,給出廣義強非退化集與廣義弱強極小集的定義。

xk-PS(xk)〉≥0。

下面舉例說明, 解集的廣義強非退化與廣義弱強極小分別是強非退化與弱強極小的推廣。

例2對最優(yōu)化問題

是廣義強非退化集也是廣義弱強極小集。

并且

相反地，本文有下面的命題。

例2與命題1說明了廣義強非退化集與廣義弱強極小集是凸最優(yōu)化問題解集的強非退化集與弱強極小集的實際性推廣。

(5)

因此有

(6)

由式(3)與式(6)知存在常數(shù)α>0使得

所以

由上式即得

3 有限終止性條件

定理2設(shè)在非凸最優(yōu)化問題(NP)中,

(7)

因為S為閉凸集, 所以對?k∈K有

(8)

則?α>0使得

(9)

式中B為Rn中的單位球。 由式(8)與式 (9)可推出

由命題2與定理2即得下面推論。

注1推論1即是文獻[17]的定理5.3，后者是文獻[14] 推論3.5的推廣。

(10)

證明必要性顯然成立, 下面證明充分性。

(11)

(12)

由式(12)可知, ?α>0使得對所有充分大的k∈K有

(13)

式中B為Rn中的單位球。 由式(11)與式(13)可推出

這與式(10)矛盾, 所以定理3成立。

由命題1與定理3即得下面推論。

注2推論2即是文獻[19]的定理3.1， 后者推廣并改進了文獻[2]的定理4.7。

由命題3與定理3即得下面推論。

4 應(yīng)用

本節(jié)研究廣義強非退化集與廣義弱強極小集的應(yīng)用。

定理4設(shè)在最優(yōu)化問題(NP)中, {xk}?S,yk=PS(xk-?

(14)

(15)

由投影性質(zhì), 對?y∈S有

〈xk-?f(xk)-yk,y-yk〉≤0,

即

〈?f(yk),y-yk〉≤〈yk-xk,y-yk〉+

〈?f(xk)-?f(yk),y-yk〉。

(16)

對?d∈TS(yk),‖d‖≤1, 由切錐的定義與式(16)得

由文獻[20]的引理3.1得

(17)

(18)

將式(16)與式(17)相加得

因此有

由已知條件,根據(jù)上式可得

再由三角不等式有

再根據(jù)?f(·)在{xk}的一個δ鄰域B({xk},δ)上一致連續(xù)性,可知{xk}滿足定理4的條件, 因此得證。

注3在凸最優(yōu)化問題(NP)中, 強非退化集的概念是弱強極小集的特例,所以推論4對于凸優(yōu)化問題(NP)也成立, 因此,由推論4可以得到文獻[2]中定理4.7的充分條件。

定理5設(shè)在非凸最優(yōu)化問題(NP)中, {xk}?S,yk=PS(xk-?

將定理5應(yīng)用到凸最優(yōu)化問題,可以得到下面推論。

此推論可以用類似于推論4的方法證明。

注4推論5是文獻[2]中定理4.7可行解序列有限終止性的充分條件。

5 結(jié)束語

解集的強非退化或弱強極小性是逼近點算法以及許多最優(yōu)化算法具有有限終止性的充分條件, 但在許多情況下, 最優(yōu)化問題解集的強非退化和弱強極小性并不成立。 為了彌補這種缺陷, 本文給出了最優(yōu)化問題中廣義強非退化集和廣義弱強極小集的概念, 這為最優(yōu)化問題的可行解序列有限終止性提供了比強非退化和弱強極小性更弱的充分條件。