一類求解全局優(yōu)化問題的單參數(shù)填充函數(shù)算法

段曉輝，景書杰，牛海峰

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

1 引言

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

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

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

2 準(zhǔn)備工作

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

(P)

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

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

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

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

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

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

(1)在X上x*是F(x,x*,P)的一個(gè)嚴(yán)格局部極大點(diǎn)；

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

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

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

3 新的填充函數(shù)

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

ψ(f(x)-fx*))

(2.1)

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

定理3.1設(shè)x*是問題(P)的局部極小點(diǎn)，則當(dāng)A充分大時(shí)，x*是F(x,x*,A)的一個(gè)嚴(yán)格局部極大點(diǎn).

證明當(dāng)x=x*時(shí)，代入(3.1)可得：

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

?δ>0，對(duì)?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)有

綜上所述，當(dāng)A充分大時(shí)，x*是F(x,x*,A)的嚴(yán)格局部極大點(diǎn).

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

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

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

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

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)因?yàn)?S2為有界閉集，且F(x,x*,A)為連續(xù)可微函數(shù)，故?x′∈?S2為函數(shù)F(x,x*,A)在?S2上的全局極小點(diǎn)，因此

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

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

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

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

4 算法和數(shù)值實(shí)驗(yàn)結(jié)果

4.1 填充函數(shù)算法

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

步驟0 初始化階段

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

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

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

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

步驟5 若A

對(duì)上述算法做如下注解：

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

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

4.2 數(shù)值實(shí)驗(yàn)及結(jié)果

例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.對(duì)所有c全局極小值為f(x*)=0.具體迭代過程見表1.

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

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

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

表1 例1的數(shù)值實(shí)驗(yàn)結(jié)果(c=0.05)

表2 例2的數(shù)值實(shí)驗(yàn)結(jié)果

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

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

表3 例3的數(shù)值實(shí)驗(yàn)結(jié)果(n=10)

表4 數(shù)值實(shí)驗(yàn)結(jié)果對(duì)比

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

5 結(jié)語

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