全局優(yōu)化問題的最優(yōu)性條件及其實(shí)現(xiàn)算法

丁 譯， 程建強(qiáng)， 鄔冬華

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

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

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

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

以及水平集

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

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

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

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

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

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

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

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

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

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

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

則

并且

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

則

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

及均值

并且

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

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

再由引理3可知，

那么

則

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

又因?yàn)閏*≥cm，(c*－cm)·μ(O(x—，δ))≥0，所以

移項(xiàng)可得

則

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

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

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

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

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

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

矛盾.

定理3 若有某下標(biāo)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ù)性，存在測(cè)度為正的小鄰域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é)為計(jì)算數(shù)列{ck}和水平集序列{Hk}，概括算法步驟如下：

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

(2)若μ(Hk)=0，則ck為總極大值，Hk為總極大值點(diǎn)集，轉(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中的近似總極大值點(diǎn)集，算法終止.

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

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

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

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

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

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

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

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

具體用這2種方法得到的2個(gè)序列是否收斂，以及用這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］ 俞武揚(yáng)，鄔冬華，呂瑜佩.一種求有約束總極值的新途徑［J］.上海大學(xué)學(xué)報(bào)：自然科學(xué)版，2002，8(6)：590-597.

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

［8］ 鄔冬華，俞武揚(yáng)，田蔚文，等.一種求約束總極值的水平值估計(jì)方法［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.