段曉輝，景書杰，牛海峰

(河南理工大學 數(shù)學與信息科學學院，河南 焦作 454000)

1 引言

全局優(yōu)化被廣泛地應用于工程、運輸、生產(chǎn)、經(jīng)濟等領域.全局優(yōu)化方法可分為隨機型方法和確定型方法兩大類.前者包括模擬退火法[1]、遺傳算法[2]、粒子群算法[3]等，后者包括打洞函數(shù)法[4]、填充函數(shù)法[5]等.本文主要討論確定型方法中的填充函數(shù)算法，該算法的主要步驟是從目標函數(shù)任一局部極小點出發(fā)，構建一個與之相關的復合函數(shù)，通過極小化上述復合函數(shù)找到一個更好的局部極小點.填充函數(shù)算法的關鍵是構建滿足條件的復合函數(shù)和選取有效的局部優(yōu)化算法.上面構建的填充函數(shù)是一個與目標函數(shù)有關的復合函數(shù)且需要滿足x′填充函數(shù)定義，局部優(yōu)化算法通常根據(jù)問題類型從前人提出的經(jīng)典局部優(yōu)化算法中選擇.構建有效可行的填充函數(shù)為該算法的關鍵.

1990年，葛仁普提出了求解無約束全局優(yōu)化問題的填充函數(shù)法，給出了第一代填充函數(shù)P-function，具體見文獻[6].上述填充函數(shù)存在許多不足，如：填充函數(shù)包含指數(shù)項，使得在計算中可能產(chǎn)生假的平穩(wěn)點.為了改善上述不足，后續(xù)研究者提出了新的填充函數(shù)及有效算法，如文獻[7].

同時葛仁普在文獻[6]中給出了原始填充函數(shù)定義.

2 準備工作

我們考慮如下優(yōu)化問題：

(P)

其中X為有界閉集且X?Rn.

為了解決問題(P)，首先假定目標函數(shù)滿足如下假設：

(1) 函數(shù)f(x)在Ω上是連續(xù)可微的.

(2) 函數(shù)f(x)是強制性的，即函數(shù)f(x)滿足

(3) 問題(P)的不同局部極小點的個數(shù)可以是無限的，但不同局部極小值只有有限個.

定義1.1[9]函數(shù)f(x,x*,P)稱為f(x)在局部極小點x*處的填充函數(shù)，如果它滿足下列條件：

(1)在X上x*是F(x,x*,P)的一個嚴格局部極大點；

(2)對于任意的x∈S1，有▽F(x,x*,P)≠0.即F(x,x*,P)在S1上沒有極小點或鞍點，其中

S1={x∣f(x)≥f(x*),x∈X{x*}}；

(3)如果x*不是f(x)的全局極小點，那么F(x,x*,P)在S2上一定存在局部極小點，其中S2={x∣f(x)

3 新的填充函數(shù)

本文構造問題(P)的一類填充函數(shù)：

ψ(f(x)-fx*))

(2.1)

下面證明當參數(shù)A充分大時，函數(shù)F(x,x*,A)為滿足定義2.1的填充函數(shù).

定理3.1設x*是問題(P)的局部極小點，則當A充分大時，x*是F(x,x*,A)的一個嚴格局部極大點.

證明當x=x*時，代入(3.1)可得：

由于x*是問題(P)的局部極小點，從而

?δ>0，對?x∈N(x*,δ)且x≠x*，有

f(x)≥f(x*)，即f(x)-f(x*)≥0.

φ(A·(f(x)-f(x*)))=2,ψ(f(x)-f(x*))=0代入(3.1)有

綜上所述，當A充分大時，x*是F(x,x*,A)的嚴格局部極大點.

定理3.2設x*是問題(P)的局部極小點，則當A充分大時，對于任意的x∈S1，有▽F(x,x*,P)≠0，其中S1={x∣f(x)≥f(x*),x∈X{x*}}.

證明對?x∈S1={x∣f(x)≥f(x*),

x∈X{x*}}有f(x)-f(x*)≥0且x≠x*，取

定理3.3若x*不是問題(P)的全局極小點，則函數(shù)F(x,x*,A)在S2上存在局部極小點，這里

S2={x∣f(x)

證明令S3={x∣f(x)≤f(x*),x∈X}，記?S2={x∣f(x)=f(x*),x∈X}，則S3=S2∪?S2，且S3及?S2均為有界閉集.

(1)因為?S2為有界閉集，且F(x,x*,A)為連續(xù)可微函數(shù)，故?x′∈?S2為函數(shù)F(x,x*,A)在?S2上的全局極小點，因此

F(x′,x*,A)=minx∈?S2F(x,x*,A)=0.

(2)對?x″∈S2，φ(A·(f(x)-f(x*)))=0，代入(3.1)可得

f(x*))=-(f(x″)-f(x*))2+(fx″)-f(x*))3<0.

綜上所述，若x*不是問題(P)的全局極小點，函數(shù)F(x,x*,A)在S2上存在局部極小點.

4 算法和數(shù)值實驗結果

4.1 填充函數(shù)算法

本節(jié)中，結合上面構建的填充函數(shù)給出下述算法.

步驟0 初始化階段

選擇Up作為A的上確界(本文中取UA=109)；

選擇常數(shù)ρ>1(本文中取ρ=103)；選擇初始值A=1；選擇初始值A=1；提前給出方向向量記為di,i=1, 2, …，2n.任取點x0∈X作為極小化問題(P)的初始點；令k=1，轉步驟1.

步驟2 構建填充函數(shù)如下：

ψ(f(x)-f(x*)).

步驟5 若A

對上述算法做如下注解：

(1)本文在數(shù)值計算中步驟1中選擇用FMINCON函數(shù)極小化目標函數(shù)；步驟4中選擇BFGS擬牛頓算法極小化填充函數(shù).

(2)初始化中方向向量di如下：

4.2 數(shù)值實驗及結果

例1 (二維函數(shù))

minf(x)=[1-2x2+csin(4πx2)]2+[x2-

0.5sin(2πx1)]2

s.t.0≤x1≤10, -10≤x2≤0.

其中c=0.2, 0.5, 0.05.對所有c全局極小值為f(x*)=0.具體迭代過程見表1.

例2 (三駝峰函數(shù))

s.t.-3≤x1≤3, -3≤x2≤3.

全局極小點為x*=(0, 0)T.具體迭代過程見表2.

表1 例1的數(shù)值實驗結果(c=0.05)

表2 例2的數(shù)值實驗結果

例3 (n維正弦平方Ⅱ函數(shù))

s.t.-10≤xi≤10,i=1, 2，…，n.

表3 例3的數(shù)值實驗結果(n=10)

表4 數(shù)值實驗結果對比

上述表1—表3中的數(shù)值結果，證明本文中構建的填充函數(shù)及算法是有效可行的.表4的數(shù)據(jù)說明在初始點相同的情況下，與文獻[10]結果比較本文算法迭代次數(shù)更少或結果更精確.

5 結語

本文在不含有不等式約束條件下構建了新的只含有一個參數(shù)連續(xù)可微的填充函數(shù)，且在適當條件下該填充函數(shù)與目標函數(shù)含有相同的局部極小點，因此可以減少極小化目標函數(shù)的次數(shù)，在一定程度上加快了計算速度.從理論上證明提出的函數(shù)滿足填充函數(shù)定義，設計相應的填充函數(shù)算法，結合MATLAB軟件通過數(shù)值實驗證明算法是可行的.