全局最優(yōu)化的一種新的擬全局下降法

劉呈軍

(重慶水利電力職業(yè)技術(shù)學(xué)院，重慶 永川 402160)

關(guān)于凸優(yōu)化問(wèn)題已有許多文獻(xiàn)對(duì)其做了研究，并有了一些很好的求解方法.然而，在自然世界中大多數(shù)的優(yōu)化問(wèn)題都是非凸的.當(dāng)目標(biāo)函數(shù)具有多個(gè)局部最小值時(shí)，這對(duì)求解全局最優(yōu)解是一個(gè)很大的挑戰(zhàn).輔助函數(shù)法［1］是求解全局優(yōu)化問(wèn)題的一種常用方法，通過(guò)對(duì)目標(biāo)函數(shù)做一些適當(dāng)?shù)男拚齺?lái)超越現(xiàn)有的局部最優(yōu)解.

函數(shù)修正法(即隧道效應(yīng)法)是由Levy 在1977年提出，并在1985年由Levy 和Montalvo 公開(kāi)發(fā)表［2］.1989年，Yao 推廣了這種隧道效應(yīng)算法［3］求解約束全局最優(yōu)化問(wèn)題，后面又有作者對(duì)其進(jìn)行的推廣［4］.1983年葛仁溥提出了填充函數(shù)法［1］，并在1990年被發(fā)表.而后文獻(xiàn)［5 -6］又將填充函數(shù)法進(jìn)行了推廣.

1 新的全局下降法

考慮無(wú)約束全局最優(yōu)化問(wèn)題:

其中，函數(shù)f 在Rn上連續(xù)可微，并且對(duì)問(wèn)題(P)作如下的假設(shè).

假設(shè)1:存在一個(gè)點(diǎn)x00∈Rn，f0＞0 和一個(gè)箱子集i = 1，2，…，n}?Rn，使得x00∈Ω 和對(duì)?x ∈Rnint Ω 有f(x)≥f(x00)+ f0．其中:int Ω 是Ω內(nèi)部點(diǎn)的集合.

注意到如果f 滿(mǎn)足強(qiáng)制條件，即當(dāng)‖x‖ →+ ∞時(shí)f(x)→+ ∞，那么f(x)滿(mǎn)足假設(shè)1．在假設(shè)1 的條件下問(wèn)題(P)等價(jià)于下面的問(wèn)題(PΩ)

本文提出一種新的輔助函數(shù)法即擬全局下降法來(lái)適應(yīng)函數(shù)修正法的第二階段.它具有如下一些性質(zhì):

1)在任意給出的一個(gè)可能不是問(wèn)題(P)的一個(gè)局部極小點(diǎn)x*處能夠構(gòu)造出全局下降函數(shù);

2)滿(mǎn)足f(x)≥f(x*)的任意點(diǎn)x (包含x*)不能是所構(gòu)造的全局下降函數(shù)的一個(gè)平穩(wěn)點(diǎn).在Rn中用任何傳統(tǒng)的局部搜索方法去極小化被構(gòu)造的全局下降函數(shù)將會(huì)在全局下降函數(shù)的一個(gè)極小點(diǎn)或平穩(wěn)點(diǎn)x＊＊(f(x＊＊)＜f(x*))處終止.

在后面討論中，假設(shè)x*是滿(mǎn)足f(x*)≤f(x00)的迭代算法中的當(dāng)前點(diǎn)，其中x00滿(mǎn)足假設(shè)1.

定義1 函數(shù)px*(x)稱(chēng)為問(wèn)題(PΩ)在點(diǎn)x*的一個(gè)全局下降函數(shù)，如果px*(x)滿(mǎn)足下面的條件:

1)函數(shù)px*(x)在Ω 上的任意平穩(wěn)點(diǎn)都有f()＜f(x*)成立;

2)函數(shù)px*(x)在Ω 上的任意局部極小點(diǎn)，除Ω 的(至多)一個(gè)頂點(diǎn)外都有f()＜f(x*)成立;

3)如果L(x*)≠φ，即x*不是問(wèn)題(P)的全局極小點(diǎn)，那么對(duì)任意的∈L(x*)是px*(x)在Ω 上的一個(gè)局部極小點(diǎn)和平穩(wěn)點(diǎn)，而且有px*()＜px*(x*);對(duì)任意的x ∈?Ω 有px*()＜px*(x)．

對(duì)一個(gè)給定的可變參數(shù)r ＞0 ，定義下面兩個(gè)函數(shù):

可以證明:gr(t)和fr(t)在R 上是可微的，且有

不失一般性，取點(diǎn)x0∈RnΩ 為

顯然，對(duì)任意的x ∈Ω 有‖x -x0‖≥1 .取Ω 中離x0最遠(yuǎn)的頂點(diǎn)為

設(shè)

注意到，x*不是函數(shù)φr，x*(x)的平穩(wěn)點(diǎn).規(guī)定

可以證明，函數(shù)φr，x*(x)是一個(gè)全局下降函數(shù)，在函數(shù)修正法的第二階段中采用上面所討論的全局下降會(huì)導(dǎo)出一個(gè)求解算法.但在全局下降法第二階段的數(shù)值計(jì)算時(shí)不太會(huì)令人滿(mǎn)意，因?yàn)檫@個(gè)算法通常會(huì)在頂點(diǎn)d = (d1，d2，…，dn)處停止.為了實(shí)現(xiàn)滿(mǎn)意的數(shù)值結(jié)果，對(duì)全局下降函數(shù)φr，x*(x)進(jìn)行修正得到一個(gè)新的擬全局下降函數(shù).

由假設(shè)1 可知，對(duì)任意的x ∈?Ω 有f(x)≥f(x00)+ f0，若當(dāng)前局部極小點(diǎn)或平穩(wěn)點(diǎn)x*滿(mǎn)足f(x*)≤f(x00)時(shí)，對(duì)任意的x ∈?Ω 有f(x)≥f(x00)+ f0≥f(x*)+ f0.

設(shè)

可以證明hr(t)在R 上是連續(xù)可微的，它的導(dǎo)數(shù)如下:

選擇一個(gè)給定點(diǎn)x0∈RnΩ，使得對(duì)任意的x ∈Ω 有‖x - x0‖≥1．設(shè)

其中r 是大于0 的參數(shù)，而q 為加速下降率可以調(diào)整的參數(shù).函數(shù)Qq，r，x*(x)具有下面的一些性質(zhì).

定理1 設(shè)假設(shè)1 成立，對(duì)?r ＞0 有下面的結(jié)論成立:

①滿(mǎn)足f(x)≥f(x*)+r 的任意x ∈Ω 不是Qq，r，x*(x)的平穩(wěn)點(diǎn).

②對(duì)滿(mǎn)足▽f(x)= 0，0 ≤f(x)-f(x*)＜r 的 任 何 x 不 是 Qq，r，x*(x)的 平 穩(wěn) 點(diǎn)，即▽Qq，r，x*(x)≠0．

有

對(duì)滿(mǎn)足f(x)≥f(x*)的任意x 都有:

①滿(mǎn)足f(x)≥f(x*)+ r 的任意x ∈Ω 有t= f(x)- f(x*)≥r，即有

②對(duì)滿(mǎn)足▽f(x)= 0，0 ≤f(x)-f(x*)＜r 的任何x 有

即▽Qq，r，x*(x)≠0．

定理2 假設(shè)

①假設(shè)1 成立，并且F 是一個(gè)有限集;

②L(x*)≠φ，即x*不是問(wèn)題(P)的一個(gè)全局極小點(diǎn).

證明 因?yàn)镕 是一個(gè)有限集且L(x*)≠φ，所以是有限集且β0(x*)＞0．對(duì)任意的∈L(x*)，因?yàn)閒(x*)- f()≥β0(x*)所以有f()- f(x*)≤- β0(x*)≤-2r ＜- r．由f(x)的 連 續(xù) 性 和L(x*)?int Ω，存在一個(gè)鄰域N(，δ0)使得f(x)-f(x*)＜-r 以及f(x)≥f()．因此對(duì)任意的x ∈N(，δ0)時(shí)，

且

和對(duì)?x ∈?Ω 有

證明 對(duì)任意的x ∈?Ω，r ≤f0有f(x)≥f(x*)+ f0≥f(x*)+ r．因此，

所以

因此，對(duì)任意的x ∈?Ω 和0 ＜r ≤f0有Qq，r，x*(x*)＜Qq，r，x*(x).又因?yàn)镼q，r，x*()≤Qq，r，x*(x*)，∈Ω，所以∈int Ω．

滿(mǎn)足▽f(x)≠0 和0 ≤f(x)-f(x*)＜r 的一 些 點(diǎn) 可 能 成 為 Qq，r，x*(x*) 的 平 穩(wěn) 點(diǎn)，Qq，r，x*(x*)不是前面定義的全局下降函數(shù)，但是函數(shù)Qq，r，x*(x*)具有全局下降函數(shù)的幾乎所有好的性質(zhì)，因此稱(chēng)Qq，r，x*(x*)為擬全局下降函數(shù).重要的是，采用擬全局下降函數(shù)防止了局部搜索過(guò)程跑到Ω 的邊界上，擬全局下降函數(shù)在Ω上的任何局部極小點(diǎn)都是Ω 的內(nèi)部點(diǎn).

根據(jù)前面提出的擬全局下降函數(shù)Qq，r，x*(x*)，下面給出具體的求解算法，稱(chēng)這種算法為擬全局下降算法(QGDA).

QGDA 算法:

步0 選取一個(gè)較小的數(shù)μ ＞0 作為問(wèn)題(P)極小化過(guò)程的參數(shù)r 的終止值，并且選取一個(gè)大的正數(shù)M ＞0 ，再選取一個(gè)點(diǎn)x0∈RnΩ 使得對(duì)任意的x ∈Ω 滿(mǎn)足‖x - x0‖≥1 ，最后選取一個(gè)初始點(diǎn)x00∈Ω 使得x00滿(mǎn)足假設(shè)1.

假設(shè)r0，q0分別是兩個(gè)參數(shù)r，q 的初值，令k:= 0

步1 從x0k出發(fā)，使用局部極小化方法來(lái)獲得問(wèn)題(1)的一個(gè)局部極小點(diǎn)x*k．

步2 設(shè)

其中g(shù)r(t)，hr(t)分別由(3)式和(11)式給定.局部極小化方法求解問(wèn)題(14):

步3 若q ＜M，設(shè)q:= 10q 增加q 的值，然后轉(zhuǎn)步2;否則，轉(zhuǎn)步4.

步4 若r ＞μ，設(shè)q = q0，再通過(guò)設(shè)來(lái)減小r，然后轉(zhuǎn)步2;否則停止.此時(shí)x*k即為極小化問(wèn)題(P)的一個(gè)近似全局極小點(diǎn).

注1 通常不需要驗(yàn)證假設(shè)1，因?yàn)楹苋菀撰@得一個(gè)大的箱子集Ω．

2 數(shù)值計(jì)算

下面用本文中的擬全局下降算法來(lái)求解幾個(gè)著名的檢驗(yàn)函數(shù).在下面的算例中，算法QGDA的步0 中，取

容易驗(yàn)證函數(shù)fG(x，y)是強(qiáng)制的，在本例中取并且取x0= (4，4)，x00= (1，1).利用本文中的擬全局下降函數(shù)法(QGDA)，在Matlab7.10 中最終求得Goldstein - Price 問(wèn)題的最優(yōu)解為x*=(0．0000，-1．0000)，最優(yōu)值為f(x*)= 3．0000．

例2 Six - Hump Camel - back(n = 2)min fs(x)= 4x21-2．1x41+x61/3 -x1x2-4x22+4x42

解:在本例中我們?nèi)?/p>

并且取x0= (4，4)，x00= (0，0).取初始點(diǎn)x00=(1，1)和x0= (4，4)，通過(guò)本文中提出的擬全局下降函數(shù)法(QGDA)，利用Matlab7.10 求得Six-Hump Camel-back 問(wèn)題的最優(yōu)解為x*= (-0．089 8，- 0．712 7)，最優(yōu)值為f(x*) =-1．031 6．

3 結(jié)論

針對(duì)全局最優(yōu)化問(wèn)題，本文介紹了一種新的擬全局下降法.這種算法只需用已有的局部搜索方法就可以求得原優(yōu)化問(wèn)題的全局最優(yōu)解.本文中的擬全局下降算法利用了Matlab7.10 中的最優(yōu)化工具箱里的最優(yōu)化子程序.從本文中的幾個(gè)算例結(jié)果來(lái)看，這種擬全局下降法是很有效的.

［1］Ge Renpu.A filled function method for finding a global minimizer of a function of several variables［J］.Mathematics Program，1990(46):191 -204.

［2］Levy A V，Montalvo A.The tunneling algorithm for the global minimization of functions［J］.SIAM Jouranal Sci.Stat.Comput.，1985，6(1):15 -29.

［3］Yao Y.Dynamic tunneling algorithm for global optimization［J］.IEEE Systems Man and Cybernetics Society，1989，19(5):1222 -1230.

［4］Chowdhury P R，Singh Y P，Chansarkar R A.Hybridization of gradient descent algorithms with dynamic tunneling methods for global optimization［J］.IEEE Systems Man and Cybernetics Society A，2000，30(3):384-390.

［5］Wu Z Y.A novel filled function method and quasi -filled function method for global optimization［J］.Computational Optimization and Applications，2006，34(2):249 -272.

［6］Zhang L S.A new filled function method for global optimization［J］.Global Optimization，2004(28):17-43.