總極值問題的幾種變差積分算法的實現比較

王筱莉， 梁澤亮， 姚奕榮， 鄭 權

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

令X為一個拓撲空間，f：X→R是一個實值函數，D?X，考慮如下總極小值問題：

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

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

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

1 豐滿集、豐滿函數和Q-測度空間

下面總結關于積分型總極值問題的一些基本概念和性質［8-10］.

1.1 豐滿集和豐滿函數

令X是一個拓撲空間，若X的一個子集D滿足

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

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

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

若集合

對于每個實數c都是豐滿的，則稱函數f：X→R是上豐滿的.

2個上豐滿函數的和或乘積可能不是上豐滿的，但是一個上豐滿函數和一個上半連續函數的和是上豐滿的.一個函數f是上豐滿的當且僅當f在每一點x都是上豐滿的.若x∈Fc且f在x上是上豐滿的，則x是f的一個豐滿點.

1.2 Q-測度空間以及一些相關假設

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

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

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

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

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

(R)：f是一個可測的上豐滿函數.

2 變差積分及其性質

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

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

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

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

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

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

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

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

Vφ(c)是凸的.

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

以上性質和定理的具體證明可參見文獻［8］.

3 3種變差積分的構造

3.1 雙曲變差積分

3.2 分式變差積分

3.3 三角變差積分

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

注：可驗證上述3種類型的變差積分滿足一般變差積分的性質定理.

4 算法的實現

下面介紹變差積分型總極值算法的實現過程.

4.1 Monte-Carlo實現

假設約束集D是在Rn上的一個投點區域，

f是一個下半連續且上豐滿的目標函數，并且有唯一的總極小值點x*∈D.換言之，對于一個遞減的收斂到總極值c*的數列{ck}，水平集的大小滿足

有

式中，Dk是包含水平集Hck∩D的最小圖投點區域.

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

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

為了執行算法，需要計算積分Vφ(ck)和V'e(ck).下面用Monte-Carlo技術來具體實現.

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

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

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

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

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

設

(2)由W產生一個新的投區域.用統計方法產生的投點n維區域為

假設在W中的隨機樣本為τ1，τ2，…，τt.令

其中

將

作為估計來產生ai和bi，i=1，2，…，n.

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

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

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

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

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

5 數值試驗

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

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

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

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

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

問題2

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

當n=20，40，60，80，100時，采用3種類型變差積分算法求解問題2得到的計算結果如表3～表5所示.

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

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

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

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

6 結束語

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

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

［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］ 鄔冬華，田蔚文，張連生，等.一種修正的求總極值的積分-水平集方法的實現算法收斂性［J］.應用數學學報，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.