劉呈軍

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

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

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

1 新的全局下降法

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

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

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

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

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

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

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

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

定義1 函數(shù)px*(x)稱為問題(PΩ)在點x*的一個全局下降函數(shù)，如果px*(x)滿足下面的條件:

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

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

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

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

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

不失一般性，取點x0∈RnΩ 為

顯然，對任意的x ∈Ω 有‖x -x0‖≥1 .取Ω 中離x0最遠的頂點為

設(shè)

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

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

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

設(shè)

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

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

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

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

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

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

有

對滿足f(x)≥f(x*)的任意x 都有:

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

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

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

定理2 假設(shè)

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

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

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

且

和對?x ∈?Ω 有

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

所以

因此，對任意的x ∈?Ω 和0 ＜r ≤f0有Qq，r，x*(x*)＜Qq，r，x*(x).又因為Qq，r，x*()≤Qq，r，x*(x*)，∈Ω，所以∈int Ω．

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

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

QGDA 算法:

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

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

步1 從x0k出發(fā)，使用局部極小化方法來獲得問題(1)的一個局部極小點x*k．

步2 設(shè)

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

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

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

注1 通常不需要驗證假設(shè)1，因為很容易獲得一個大的箱子集Ω．

2 數(shù)值計算

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

容易驗證函數(shù)fG(x，y)是強制的，在本例中取并且取x0= (4，4)，x00= (1，1).利用本文中的擬全局下降函數(shù)法(QGDA)，在Matlab7.10 中最終求得Goldstein - Price 問題的最優(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).取初始點x00=(1，1)和x0= (4，4)，通過本文中提出的擬全局下降函數(shù)法(QGDA)，利用Matlab7.10 求得Six-Hump Camel-back 問題的最優(yōu)解為x*= (-0．089 8，- 0．712 7)，最優(yōu)值為f(x*) =-1．031 6．

3 結(jié)論

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

［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.