劉呈軍，卓春英

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

已有許多文獻對全局最優(yōu)化問題中凸最優(yōu)化問題進行了研究，并得到了一些很有效的解法.但是，在自然世界中大多數(shù)的最優(yōu)化問題都是非凸的，目前已有文獻對非凸全局優(yōu)化問題進行凸化、凹化方面的研究［1］.如果一個通常的目標函數(shù)存在很多的局部最優(yōu)解，這對求解全局最優(yōu)是一個很大的挑戰(zhàn).

函數(shù)修正法［2］是一種針對一般全局最優(yōu)化問題的求解方法，通過對目標函數(shù)作一些適當?shù)男拚齺沓浆F(xiàn)有的局部最優(yōu)解.函數(shù)修正法(隧道效應法)［3］是1985年由Levy和Montalvo提出的.1989年，在文獻［4］中Yao將這種隧道效應算法用于求解約束全局最優(yōu)化問題.在1983年兩年一度的蘇格蘭敦提市第十屆數(shù)值分析研討會上，葛仁溥提出了填充函數(shù)法，并且他的文章［5］在1990年被發(fā)表.文獻［6，7］又將填充函數(shù)法進行了推廣.但是，現(xiàn)有的填充函數(shù)都具有以下的缺點:

(1)填充函數(shù)能夠在原目標函數(shù)f的一個局部極小點x*處被構造出來，但在實際計算中局部最優(yōu)化方法有時可能在一個不是局部極小點處終止，比如在函數(shù)f的一個平穩(wěn)點處終止.

(2)在當前局部極小點x*處構造填充函數(shù)，則點x*一定是被構造出的填充函數(shù)的一個局部極大點.因為x*是這個填充函數(shù)的一個平穩(wěn)點，所以不直接從點x*開始極小化這個填充函數(shù)，必須選取x*附近的點x來代替x*作為初始點去極小化填充函數(shù).

針對以上的兩個缺點，提出一種新的輔助函數(shù)法即全局下降法，這種全局下降法在函數(shù)修正法的第1，2階段都有松弛的要求，用局部最優(yōu)化方法產生的一個點x*可能不是一個局部極小點，比如是問題(P)的KKT點或平穩(wěn)點，并且全局下降函數(shù)的極小化可能在一個平穩(wěn)點處而不必是局部極小點處結束.

1 全局下降法

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

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

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

此處提出一種新的輔助函數(shù)法(全局下降法)，使得它具有如下性質:

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

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

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

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

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

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

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

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

定理1 如果假設1成立，那么對任意的r＞0(x)滿足下面的條件:

(1)如果x∈Ω滿足f(x)≥f(x*)，那么x不是函數(shù)(x)的平穩(wěn)點，且滿足‖▽(x)‖≥D.

①f()＜f(x*).

證明 1)由式(9)，有

因為f(x)≥f(x*)，即f(x)-f(x*)≥0，所以gr(f(x)-f(x*))=1，g'r(f(x)-f(x*))=0，f'r(f(x)-f(x*))=0.

設Y是問題(PΩ)的局部極小點的集合，并設

定理2 假設

1)假設1成立且F是一個有限集.

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

證明 因為x*不是問題(P)的全局極小點，且F是一個有限集，所以集合{f(x*)-f(x)|x∈L(x*)}既是非空的又是有限的，并且對任意∈L(x*)和r，滿足0＜r≤時，β0(x*)＞0和≤-2r＜-r.因為f(x)連續(xù)，且是問題(PΩ)的一個局部極小點，所以存在的一個領域)∩Ω，有)＜-r和f(x)≥).因此對任意的0，fr(f(x)-f(x*))=f(x)-f(x*)+r和f(x)≥)，即有).因此∈L(x*)是)在Ω上的一個局部極小點.因∈L(x*)?int Ω，故=0.由式(12)可知)=0，并且對任意x∈?Ω，f(x)≥f(x*)，有

定理3 對任意的x1，x2∈Ω，如果f(x1)≥f(x*)，f(x2)≥f(x*)，則‖x2-x0‖＞‖x1-x0‖當且僅當(x2)＜(x1).

證明 對任意的x1，x2∈Ω 滿足f(x1)≥f(x*)，f(x2)≥f(x*)，則有(x2)=

+1，所以‖x2-x0‖＞‖x1-x0‖當且僅當

1)滿足f(x)≥f(x*)的任意點x∈Ω(除點d外)既不是(x)在Ω上的局部極小點也不是平穩(wěn)點.

2)當參數(shù)r充分小時，滿足f)＜f(x*)的原問題(P)的任意局部極小點，或是在Ω上的一個局部極小點或是它的平穩(wěn)點.

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

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

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

①選取一個小的正數(shù) μ＞0作為參數(shù)r的終止值，選取一個點x0∈RnΩ，使得對任意的x∈Ω滿足‖x-x0‖≥1，選取一個初始點∈Ω，使得滿足假設1.設r0是參數(shù)r的初始值，令k:=0.

注1 通常情況下，假設1的驗證并不容易.但是，在許多情況下，不需要驗證，因為很容易得到一個大的箱子集Ω.

2 數(shù)值計算

此處將利用全局下降算法來求解一些著名的檢驗函數(shù)的全局極小點.在后面的算例中，取 μ=10-10，r0=1.

例1 Six-Hump Camel-back(n=2).

例2 Rastrigin(n=2).

3 結論

介紹了無約束全局優(yōu)化的一種全局下降法，只要調用現(xiàn)有的局部搜索方法就可以求得原問題的全局最優(yōu)解，這是因為此處提出的全局下降函數(shù)具有非常好的性質.此處全局下降算法利用了MATLAB7.10最優(yōu)化工具箱的最優(yōu)化子程序，從文中例子的計算結果來看，這種全局下降法是非常有效的.

［1］劉呈軍.非凸全局最優(yōu)化的一種凸化、凹化方法［J］.重慶工商大學學報:自然科學版，2012，29(3):22-26

［2］GE R P.A Filled Function Method for Finding a Global Minimizer of a Function of Several Variables［J］.Mathematics Program，1990(46):191-204

［3］LEVY A V，MONTALVO A.The Tunneling Algorithm for the Global Minimization of Functions［J］.SIAM J SciStat Comput，1985，6(1):15-29

［4］YAO Y.Dynamic Tunneling Algorithm for Global Optimization［J］.IEEE Trans SystMan Cybern，1989，19(5):1222-1230

［5］HANSEN E R.Global Optimization Using Interval Analysis［M］.New York:Dekker，1992

［6］WU Z Y，LEE H W J，ZHANG L S，et al.A Novel Villed Function Method and Quasi-filled Function Method for Global Optimization［J］.Comput Optim Appl，2006，34(2):249-272

［7］ZHANG L S，NG C K，LI D，et al.A New Filled Function Method for Global Optimization［J］.Glob Optim，2004(28):17-43