總極值問題的幾種變差積分算法的實(shí)現(xiàn)比較

王筱莉， 梁澤亮， 姚奕榮， 鄭 權(quán)

(上海大學(xué)理學(xué)院，上海200444)

令X為一個(gè)拓?fù)淇臻g，f：X→R是一個(gè)實(shí)值函數(shù)，D?X，考慮如下總極小值問題：

積分水平集方法［1］形成2個(gè)序列：

其中序列{ck}和{Hck}是趨于總極小值和總極小值點(diǎn)的集合.

Phu等［2］提出采用均值變差積分來研究可求和函數(shù)的基本下確界;鄔冬華等［3］在此基礎(chǔ)上討論高階矩的變差積分;姚奕榮等［4］給出了一般形式變差積分;文獻(xiàn)［5］研究了變差積分的分析性質(zhì)及總極值問題的全局最優(yōu)性條件;文獻(xiàn)［6-7］對(duì)變差積分方法進(jìn)行了完善.而本研究在一般形式變差積分的基礎(chǔ)上，構(gòu)建了不同形式的變差積分并設(shè)計(jì)了算法，同時(shí)運(yùn)用Monte-Carlo模擬技術(shù)，對(duì)具有100個(gè)變量的總極值問題進(jìn)行了算法實(shí)現(xiàn)及數(shù)值試驗(yàn)結(jié)果的分析比較.數(shù)值試驗(yàn)結(jié)果表明，針對(duì)同一個(gè)問題利用不同類型的變差積分算法來計(jì)算，效果具有一定的差異性，但同時(shí)也有各自的優(yōu)勢(shì).

1 豐滿集、豐滿函數(shù)和Q-測(cè)度空間

下面總結(jié)關(guān)于積分型總極值問題的一些基本概念和性質(zhì)［8-10］.

1.1 豐滿集和豐滿函數(shù)

令X是一個(gè)拓?fù)淇臻g，若X的一個(gè)子集D滿足

則稱D為豐滿集，其中cl D表示D的閉包，int D表示D的內(nèi)部.

一個(gè)豐滿集合包含了這個(gè)集合的豐滿點(diǎn).若x∈D且對(duì)于 x的任意一個(gè)鄰域 N(x)，有 N(x)∩int D≠?，則稱x是D的豐滿點(diǎn).一個(gè)集合D是豐滿的當(dāng)且僅當(dāng)D中每一點(diǎn)都是豐滿點(diǎn).x∈D是集合D的豐滿點(diǎn)當(dāng)且僅當(dāng)存在一個(gè)序列{xλ}?int D，使得xλ→x.

非空豐滿集合的內(nèi)部是非空的，豐滿集合的并集是豐滿的，2個(gè)豐滿集合的交可能是非豐滿的，但是一個(gè)開集和一個(gè)豐滿集合的交是豐滿的.集合D是豐滿的當(dāng)且僅當(dāng)?D=?int D，其中?D=cl Dint D表示集合D的邊界.

若集合

對(duì)于每個(gè)實(shí)數(shù)c都是豐滿的，則稱函數(shù)f：X→R是上豐滿的.

2個(gè)上豐滿函數(shù)的和或乘積可能不是上豐滿的，但是一個(gè)上豐滿函數(shù)和一個(gè)上半連續(xù)函數(shù)的和是上豐滿的.一個(gè)函數(shù)f是上豐滿的當(dāng)且僅當(dāng)f在每一點(diǎn)x都是上豐滿的.若x∈Fc且f在x上是上豐滿的，則x是f的一個(gè)豐滿點(diǎn).

1.2 Q-測(cè)度空間以及一些相關(guān)假設(shè)

為了利用積分途徑研究總極值問題，需要引入一類特殊的測(cè)度空間，稱為Q-測(cè)度空間.

令X是一個(gè)拓?fù)淇臻g，Ω是X的子集的一個(gè)σ-域，μ是Ω上的測(cè)度，則稱(X，Ω，μ)為Q-測(cè)度空間，且滿足下列條件：①X中每個(gè)開集都是可測(cè)的;②X中非空開集G的測(cè)度μ(G)為正，即μ(G)＞0;③X中緊集K的測(cè)度μ(K)是有限的.

由于一個(gè)非空開集的內(nèi)部是非空的，包含非空豐滿集的可測(cè)集的Q-測(cè)度總是正的，這是在最小化的積分型途徑中所必需的性質(zhì)，因此，通常需要作以下假設(shè).

(A)：f是下半連續(xù)的(l.s.c.)，并且X是下緊的.

(M)：(X，Ω，μ)是一個(gè)Q-測(cè)度空間.

(R)：f是一個(gè)可測(cè)的上豐滿函數(shù).

2 變差積分及其性質(zhì)

定義1 令φ：R1→R1是一個(gè)嚴(yán)格遞增的連續(xù)函數(shù)，而且φ(0)=0.f的變差積分形式為

式中，Vφ(c)是關(guān)于x在Hc∩D上的積分.

性質(zhì)1 變差積分Vφ(c)有如下性質(zhì)：

(1)Vφ(c)＞0，?c＞c*;

(2)Vφ(c)=0，?c＜c*;

(3)Vφ(c)在(－∞，+∞)上是非遞減的，且在(c*，∞)上嚴(yán)格遞增;

(4)Vφ(c)是連續(xù)的.

定理1 假定φ在(－∞，+∞)上是可微的，而且φ'(0)=0，那么積分Vφ(c)在(－∞，+∞)上是可微的，而且

Vφ(c)是凸的.

定理2 在(A)，(M)和(R)的假設(shè)下，c*為總極小值當(dāng)且僅當(dāng)cn↓c*，

以上性質(zhì)和定理的具體證明可參見文獻(xiàn)［8］.

3 3種變差積分的構(gòu)造

3.1 雙曲變差積分

3.2 分式變差積分

3.3 三角變差積分

令φ3(x)=x－arctan x是一個(gè)嚴(yán)格遞增連續(xù)函數(shù)，而且φ3(0)=0.構(gòu)造f的三角變差積分如下：

注：可驗(yàn)證上述3種類型的變差積分滿足一般變差積分的性質(zhì)定理.

4 算法的實(shí)現(xiàn)

下面介紹變差積分型總極值算法的實(shí)現(xiàn)過程.

4.1 Monte-Carlo實(shí)現(xiàn)

假設(shè)約束集D是在Rn上的一個(gè)投點(diǎn)區(qū)域，

f是一個(gè)下半連續(xù)且上豐滿的目標(biāo)函數(shù)，并且有唯一的總極小值點(diǎn)x*∈D.換言之，對(duì)于一個(gè)遞減的收斂到總極值c*的數(shù)列{ck}，水平集的大小滿足

有

式中，Dk是包含水平集Hck∩D的最小圖投點(diǎn)區(qū)域.

這樣，就是計(jì)算Vφ(ck;Dk)和V'φ(ck;Dk)而不是計(jì)算Vφ(ck;D)和V'φ(ck;D).

在每次迭代中，試圖找到Dk來替代水平集Hck，其中

為了執(zhí)行算法，需要計(jì)算積分Vφ(ck)和V'e(ck).下面用Monte-Carlo技術(shù)來具體實(shí)現(xiàn).

(1)c0和Hc0的逼近.設(shè)ξ=(ξ1，ξ2，…，ξn)是一個(gè)均勻分布在區(qū)間［0，1］n上的n維隨機(jī)數(shù).設(shè)

則x=(x1，x2，…，xn)均勻分布在D上.

取km個(gè)子樣本，并在樣本點(diǎn)上計(jì)算函數(shù)值f(xj)，j=1，2，…，km.比較這些點(diǎn)上的函數(shù)值，得到一個(gè)樣本點(diǎn)的集合W，其中包括對(duì)應(yīng)的t個(gè)最小函數(shù)值點(diǎn)FV［j］，j=1，2，…，t.將其按函數(shù)值大小排序，即為

稱集合W為接受集，并將其看作是水平集Hc0的逼近，其中c0=FV［1］是{FV［j］}中最大的一個(gè)，稱正整數(shù)t為統(tǒng)計(jì)指標(biāo).可以看出，對(duì)于任意點(diǎn) x∈W，f(x)≤c0.

此外，f在水平集Hc0上的Vφ(c0)和V'φ(c0)可以由以下方式來逼近，即

設(shè)

(2)由W產(chǎn)生一個(gè)新的投區(qū)域.用統(tǒng)計(jì)方法產(chǎn)生的投點(diǎn)n維區(qū)域?yàn)?/p>

假設(shè)在W中的隨機(jī)樣本為τ1，τ2，…，τt.令

其中

將

作為估計(jì)來產(chǎn)生ai和bi，i=1，2，…，n.

(3)繼續(xù)迭代過程.從新的區(qū)域D1中去樣本點(diǎn).取一隨機(jī)子樣本x=(x1，x2，…，xn)∈D1，其中

計(jì)算f(x)，如果f(x)≥ck，則丟棄樣本點(diǎn);否則，更新集合FV［j］和W，最后使得FV［j］是最小的點(diǎn).對(duì)接受集W作相應(yīng)的更新.重復(fù)這個(gè)過程直到FV［1］≤c1，得到新的FV和W.

(4)迭代解.每次迭代，都可將集合FV［j］中的最小FV［t］及W中對(duì)應(yīng)的點(diǎn)看作是迭代解.

(5)收斂辨別.每次迭代，用Monte-Carlo方法來計(jì)算變差積分Vk和V'k.令

如果λk小于給定的精度ε，則迭代終止.可將步驟(4)中的迭代解作為總極小值和總極小值點(diǎn)的逼近.

5 數(shù)值試驗(yàn)

下面主要考慮一類無約束或盒箱約束的總極小值問題.分別結(jié)合上述3類變差積分，運(yùn)用Monte-Carlo技術(shù)可得以下數(shù)值結(jié)果.

當(dāng)n=20，40，60，80，100時(shí)，采用分式變差積分算法和三角變差積分算法求解問題1得到的計(jì)算結(jié)果如表1和表2所示.采用雙曲變差積分算法求解問題1的一些數(shù)值結(jié)果是數(shù)據(jù)溢出.

表1 分式變差積分算法求解問題1的一些數(shù)值結(jié)果Table 1 Numerical results of the problem 1 with fraction deviation integral method

表2 三角變差積分算法求解問題1的一些數(shù)值結(jié)果Table 2 Numerical results of the problem 1 with trigonometry deviation integral method

表1和表2的數(shù)據(jù)表明：①采用分式變差積分算法解決問題1時(shí)，迭代次數(shù)較少;② 采用雙曲變差積分算法解決問題1時(shí)，一旦數(shù)值過大就會(huì)遇到指數(shù)數(shù)據(jù)溢出的情況，所以在選用時(shí)要慎重;③數(shù)據(jù)較多時(shí)，采用三角變差積分算法計(jì)算累積量較小.

問題2

D={(x1，x2，…，xn)∈Rn：－10.0≤xi≤10.0，i=1，2，…，n}.解x*=(0，…，0)，f*=0.

當(dāng)n=20，40，60，80，100時(shí)，采用3種類型變差積分算法求解問題2得到的計(jì)算結(jié)果如表3～表5所示.

表3 雙曲變差積分算法求解問題2的一些數(shù)值結(jié)果Table 3 Numerical results of the problem 2 with hyperbolic deviation integral method

表4 分式變差積分算法求解問題2的一些數(shù)值結(jié)果Table 4 Numerical results of the problem 2 with fraction deviation integral method

表5 三角變差積分算法求解問題2的一些數(shù)值結(jié)果Table 5 Numerical results of the problem 2 with trigonometry deviation integral method

表3～表5的數(shù)據(jù)表明：①采用雙曲變差積分算法解決問題2時(shí)迭代次數(shù)最少，但計(jì)算結(jié)果的精度不高;②采用分式變差積分算法時(shí)迭代次數(shù)要少于三角變差積分算法;③ 數(shù)據(jù)較多時(shí)，采用三角變差積分算法計(jì)算累積量較少.

6 結(jié)束語

以上算例說明了本研究給出的3類變差積分算法是可行且有效的，但是各算法之間也存在差異.具體地說：①對(duì)于雙曲變差積分算法，其計(jì)算的迭代次數(shù)較少，當(dāng)數(shù)據(jù)量較大時(shí)，函數(shù)值的計(jì)算累積量并不大，但是當(dāng)數(shù)據(jù)值比較大時(shí)可能容易造成數(shù)據(jù)溢出，且計(jì)算精度不夠高;②對(duì)于分式變差積分算法，其計(jì)算的迭代次數(shù)較少，但是當(dāng)數(shù)據(jù)量較大時(shí)，其函數(shù)計(jì)算累積量是三種算法中最大的，所以當(dāng)計(jì)算數(shù)據(jù)規(guī)模較大時(shí)，其消耗時(shí)間也較多;③對(duì)于三角變差積分算法，其計(jì)算的迭代次數(shù)適中，當(dāng)數(shù)據(jù)量較大時(shí)，函數(shù)值的計(jì)算累積量比分式變差積分算法要小，且計(jì)算耗時(shí)相對(duì)適中.

由于上述各類變差積分算法的差異性和優(yōu)劣性，因此，在利用變差積分算法時(shí)應(yīng)該注意針對(duì)不同的問題選擇不同的算法.本研究就是通過設(shè)計(jì)變差積分算法來求解不連續(xù)、無約束總極值問題的.而對(duì)于約束的，特別是離散的總極值問題還需作進(jìn)一步研究.

［1］ CHEWS H，ZHENGQ.Integral global optimization：theory，implementation and applications［M］.Berlin：Springer-Verlag，1988.

［2］ PHUH X，HOFFMANNA.Essential supremum and supremum of summable functions［J］.Numer Funct Anal and Optimiz，1996，17(1/2)：167-180.

［3］ WUD H，WUW Y，ZHENGQ.A sufficient and necessary condition for global optimization［J］.Applied Mathematics Letters，2010，23(1)：17-21.

［4］ YAOY R，CHENL，ZHENGQ.Optimality condition and algorithm with deviation integral for global optimization［J］.Journal Mathematical Analysis and Applications，2009，357：371-384.

［5］ PARDALOSP M，ROMEIJNH E，TUYH.Recent developments and trends in global optimization［J］.J Comp and Appl Maths，2000，124：209-228.

［6］ TIANW W，WUD H，ZHANGL S，et al.Modified integral-level set method forthe constrained global optimization［J］.Applied Mathematics and Mechanics，2004，25(2)：202-210.

［7］ 鄔冬華，田蔚文，張連生，等.一種修正的求總極值的積分-水平集方法的實(shí)現(xiàn)算法收斂性［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，2001，24(1)：100-110.

［8］ SHIS Z，ZHENGQ，ZHUANGD M.Discontinuous robust mapping are approximatable［J］.Trans Amer Math Soc，1995，347：4943-4957.

［9］ ZHENGQ.Robust analysis and global minimization of a class of discontinuous functions(Ⅰ)and(Ⅱ)［J］.Acta Mathematicae Applicatae Sinica：English Ser，1990，6(3)：205-223，317-337.

［10］ ZHENGQ.Robust analysis and global optimization［J］.International J Computers and Mathematics with Applications，1991，21(6/7)：17-24.