丁 譯， 程建強， 鄔冬華

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

最優(yōu)化問題存在于現(xiàn)實生活中的許多領(lǐng)域，而最優(yōu)化方法是人們對實際問題進行建模和分析的重要手段.在分析問題的過程中所抽象出來的優(yōu)化模型，許多都可以歸結(jié)為求全局最優(yōu)解的問題.現(xiàn)有的求解全局優(yōu)化問題的方法依據(jù)收斂性質(zhì)分為兩大類［1］：確定型方法和隨機型方法.確定型方法包括區(qū)間方法、分支定界方法、填充函數(shù)方法、積分水平集算法等;隨機型方法包括純粹隨機搜索算法、純粹更新搜索算法和現(xiàn)代啟發(fā)式算法(如遺傳算法、模擬退火算法)等.

一個全局優(yōu)化問題可表述如下：

式中，G是Rn上的有界閉區(qū)域，f：Rn→R上的連續(xù)函數(shù)，f*為f(x)在G中的總極小值.20世紀七八十年代，鄭權(quán)等［2-4］提出了求總極小值的積分水平集算法，并給出了相應(yīng)的收斂準則.隨后，鄔冬華等［5-10］對此算法進行了多次修正.該算法的主要思想是在第k步構(gòu)造一個均值函數(shù)

以及水平集

從而得到2個收斂序列{ck}和{Hk}，算法終止條件為水平集上的均方差趨近于0.

本研究受到求總極小值的積分水平集算法及權(quán)重思想的啟發(fā)，考慮n維歐式空間Rn中區(qū)域D上的連續(xù)函數(shù)f(x)的總極大值，建立了一種新的求總極大值的積分水平集算法，并給出了相應(yīng)的收斂性法則.

對于連續(xù)函數(shù)f(x)，若有一點x*∈D，對于一切x∈D，滿足不等式

則稱x*是函數(shù)在D上的總極大值點，f(x*)是總極大值.D中所有總極大值點的全體，構(gòu)成了總極大值點集.

另外，假設(shè)對任意x∈D，f(x)≥0;若f(x)＜0，則認為可以通過給f(x)加上一個足夠大的常數(shù)m＞0，使得f(x)+m≥0.那么，總極大值的問題可表示為

式中，D為Rn中的有界閉集，f：Rn→R上的連續(xù)函數(shù)，且對任意x∈D，f(x)≥0，f*為f(x)在D中的總極大值.

1 求總極大值的積分水平集算法

給定一個常數(shù)c0≥0，使水平集

非空，式(6)的右端表示在D中滿足關(guān)系式f(x)≥c0的點的全體.設(shè)D是有界閉集，若H0是有界閉集，則H0是Rn中的緊集，f(x)在H0上達到極大值.由于對D－H0上的點x，f(x)＜c0，故這個極大值必是總極大值.于是，只需在H0上討論f(x)在D中的總極大值問題.

引理1 若μ(H0)=0，且H0≠?，其中μ(H0)表示集合H0的勒貝格測度，則c0就是f(x)的總極大值，H0就是f(x)的總極大值點集.

于是，設(shè)μ(H0)＞0，依據(jù)求總極小值的積分水平集算法，構(gòu)造f(x)在H0上的均值

則

并且

在本研究中，因為f(x)≥0，那么，若對任意點的函數(shù)值f(x)賦予權(quán)重fn－1(x)(n為不小于1的整數(shù))，則函數(shù)值越大的f(x)，其權(quán)重也越大，函數(shù)值上升的速度越快.于是，對f(x)在H0上的均值函數(shù)進行如下修正：

則

一般地，由ck構(gòu)造水平集

及均值

并且

k=1，2，….從而得到一個新的單調(diào)上升數(shù)列{ck}及一個單調(diào)的集序列{Hk}，它們的上升速度均比數(shù)列{}和序列{}快.由于ck≤f(x*)(設(shè)x*是f(x)在D上的總極大值點，k=1，2，…)，故{ck}有上界，設(shè)

定理1 若f(x)是區(qū)域D上的連續(xù)函數(shù)，則式(15)中數(shù)列{ck}的極限c*一定是f(x)在D上的總極大值，水平集序列{Hk}的極限H*是f(x)的總極大值點集.

再由引理3可知，

那么

則

由上述可知，在Hm－O(，δ)上，f(x)≥ck;在O，δ)上，f(x)＞c*+η，所以

又因為c*≥cm，(c*－cm)·μ(O(x—，δ))≥0，所以

移項可得

則

又由于0＜μ(Hm)＜μ(H0)，那么

是總極大值點集(非空).

證明 必要性.設(shè)c是總極大值，則

充分性.設(shè)方差序列條件成立時，c不是總極大值.令Hc={x|f(x)≥c，x∈D}，那么μ(Hc)＞0，且

已知Hk→Hc(k→∞)，故μ(Hk)→μ(Hc)(k→∞)(已假設(shè)H0有界)，那么上式右端被積函數(shù)一致有界.當(dāng)k→∞時，2個積分→0，

設(shè)f(x)在D上的總極值為c*=f(x*)，那么c*＞c，故存在η＞0以及x*的鄰域O(x*，δ)，對x∈O(x*，δ)，f(x)＞c+η，這時

矛盾.

定理3 若有某下標k，使得ck=ck+1或μ(Hk)= μ(Hk+1)，則f(x)≡常數(shù).

由定義可知，ΔHk={x|ck－1≤f(x)＜ck，x∈D}，ΔHk必為空集，也就證明了μ(Hk－1)=μ(Hk).

再證，若μ(Hk)=μ(Hk+1)，則ck=ck+1，ck+1=ck+2，其中ck+1=ck+2顯然成立.然后，證明ck=ck+1.設(shè)ck＜ck+1，由f(x)的連續(xù)性，存在測度為正的小鄰域O(x，δ)?ΔHk={x|f(x)＞ck，f(x)≤ck+1}，這與μ(Hk)=μ(Hk+1)矛盾.

利用上面的結(jié)果，若ck=ck+1，可推得μ(Hk－1)= μ(Hk)，μ(Hk)=μ(Hk+1)，從而可得ck－1=ck，ck+1= ck+2.依此類推，可知 f(x)≡常數(shù).若 μ(Hk)= μ(Hk+1)，則ck=ck+1，也可推得f(x)≡常數(shù).

2 算法步驟

將上述迭代模型歸結(jié)為計算數(shù)列{ck}和水平集序列{Hk}，概括算法步驟如下：

(1)取x0∈D，給定一個正數(shù)ε，令c0=f(x0)，H0={x|f(x)≥c0，x∈D}，k=0;

(2)若μ(Hk)=0，則ck為總極大值，Hk為總極大值點集，轉(zhuǎn)步驟(6);

(5)若V≥ε，令k=k+1，轉(zhuǎn)步驟(2)，否則，轉(zhuǎn)步驟(6);

(6)令f*=ck+1，且H=Hk+1，H為f(x)在D中的近似總極大值點集，算法終止.

3 數(shù)值試驗及算法討論

本研究基于積分水平集算法，提出了對函數(shù)值恒大于0的函數(shù)求總極大值的概念性積分水平集算法;并根據(jù)權(quán)重的概念，修正了均值函數(shù)，理論上可使得函數(shù)值上升的速度更快，運算效率得到提高.

在實際計算過程中，本研究引入重要樣本(important sample)和相對熵(cross entropy，CE)方法，在相對熵方法中，采用指數(shù)分布更新參數(shù).

為了驗證該算法的有效性，對具有代表性的全局最優(yōu)化問題Rastrigin函數(shù)進行改進，分別運用一般的相對熵方法和改進的相對熵方法求其極大值，并進行了簡單的比較.改進后的Rastrigin函數(shù)可表示為

試驗結(jié)果如表1所示.

數(shù)值試驗的結(jié)果顯示，當(dāng)全局最優(yōu)化問題的維數(shù)較低(如d≤10)，n取到足夠大(如n≥100)時，運算時間明顯縮短，表明改進后的相對熵算法具有較好的收斂性和較高的效率，與理論推測結(jié)果一致，因此本算法有效.然而，當(dāng)全局最優(yōu)化問題的維數(shù)d越高時，n越大，運算時間越長，效率偏低，算法有待改進.

表1 CE算法與改進的CE算法的數(shù)值試驗結(jié)果Table 1 Numerical results of CE method and modified CE method

另外，本研究賦予函數(shù)的權(quán)重是fn－1(x)，理論上也可以使用同樣具有單調(diào)性的指數(shù)函數(shù)或者對數(shù)函數(shù)替代，那么對應(yīng)的{ck}可以分別表示為

具體用這2種方法得到的2個序列是否收斂，以及用這2種方法求極值的最優(yōu)性條件將另文給出.

［1］ PARDALOSP P，ROMEIJNH E，HOANGT.Recent developments and trends in global optimization［J］.Journal of Computational and Applied Mathematics，2000，124：209-228.

［2］ ZHENGQ，JIANGB C，ZHUANGS L.A method for finding globalextrema［J］. Acta Mathematicae Applicatae Sinica，1978，2(1)：161-174.

［3］ ZHENGQ.Optimality conditions of global optimization (Ⅰ) ［J］.Acta Mathematicae Applicatae Sinica：English Series，1985，1(2)：66-78.

［4］ ZHENGQ.Optimality conditions of global optimization (Ⅱ) ［J］.Acta Mathematicae Applicatae Sinica：English Series，1985，1(3)：118-132.

［5］ WUD H，TIANW W，ZHANGL S，et al.An algorithm of modified integral-level set method for solving global optimization［J］.Acta Mathematicae Applicatae Sinica，2001，24：100-110.

［6］ 俞武揚，鄔冬華，呂瑜佩.一種求有約束總極值的新途徑［J］.上海大學(xué)學(xué)報：自然科學(xué)版，2002，8(6)：590-597.

［7］ 田蔚文，鄔冬華，張連生，等.一種修正的求約束總極值的積分水平集方法［J］.應(yīng)用數(shù)學(xué)和力學(xué)，2004，25：202-209.

［8］ 鄔冬華，俞武揚，田蔚文，等.一種求約束總極值的水平值估計方法［J］.應(yīng)用數(shù)學(xué)和力學(xué)，2006(7)：165-178.

［9］ PENGZ，WUD H，TIANW W.A level-value estimation method for solving constrained global optimization［J］.Mathematica Numerica Sinica，2007，29(3)：271-282.

［10］ WUD H，YUW Y，ZHENGQ.A sufficient and necessary condition for global optimization［J］.Applied Mathematics Letters，2010，23：17-21.