一個求解無約束優(yōu)化的單參數(shù)填充函數(shù)算法

張玉琴，馮向東，張建亮

(成都理工大學(xué) 工程技術(shù)學(xué)院，四川 樂山 614000)

0 引 言

全局優(yōu)化問題是解決實際問題的重要理論之一，在日常生活中，有著非常廣泛的應(yīng)用，尤其在管理決策、工程計算和控制理論等領(lǐng)域。從算法的結(jié)構(gòu)分類，全局最優(yōu)化算法被分為兩類：確定性算法和隨機性算法。然而填充函數(shù)法被稱為確定性算法。

西安交通大學(xué)葛仁溥教授最初提出填充函數(shù)法[1]。此方法是求解非線性全局優(yōu)化問題的方法之一；填充函數(shù)法是解決怎樣從原問題的一個局部極小解開始，找到更小的局部極小解的方法。填充函數(shù)法主要有兩個過程：極小化過程與填充過程。這兩個過程循環(huán)使用直到找不到更好的局部極小解。為了消除已有的經(jīng)典極小化算法存在早熟的弊端，找到更好的局部極小解，眾多理論和實際工作者更加熱衷于研究填充函數(shù)法[2-7]。

填充函數(shù)法的核心工作是填充函數(shù)，其性質(zhì)與形式?jīng)Q定它的算法效率；填充函數(shù)應(yīng)構(gòu)建為目標(biāo)函數(shù)的復(fù)合函數(shù)，且含有一個參數(shù)[4，8-10]或兩個參數(shù)[1，3，5，11]，由于參數(shù)的選取比較困難，或由于填充函數(shù)是分段函數(shù)[3，5，11]，使得填充函數(shù)算法的效率降低。為此，科研工作者竭力地構(gòu)建參數(shù)盡量少、形式足夠簡單及呈現(xiàn)優(yōu)良性質(zhì)的填充函數(shù)。仔細研究文獻[4，8]，筆者構(gòu)建了一個形式簡易、容易計算的連續(xù)的單參數(shù)的填充函數(shù)。

1 基本知識

文中僅研究無約束最優(yōu)化問題

(1)

對于無約束最優(yōu)化問題(P0)，目標(biāo)函數(shù)f(x)滿足以下假設(shè)：

假設(shè)Ⅰ：(P0)的函數(shù)f(x)是強制的。即當(dāng)‖x‖→時，f(x)→。

由假設(shè)Ⅰ可以得出，必定存在一個有界閉集X?Rn，使得f(x)的全局極小解都包含在X內(nèi)；也可以這樣解釋f(x)的極小值在X的內(nèi)部取得。因此，問題(P0)就轉(zhuǎn)化為求解如下問題：

(P1) minf(x) s.t.x∈X

(2)

假設(shè)Ⅱ：在Rn上，函數(shù)f(x)連續(xù)而且可微。

假設(shè)Ⅲ：問題中可有無窮個相異的局部極小解，但只有可數(shù)個相異的局部極小值。

文中填充函數(shù)的定義參考文獻[4]。

(2)對所有x∈S1,有這里即在S1上沒有極小解或鞍點；

2 填充函數(shù)與性質(zhì)

鑒于問題(P0)，假若(P0)的局部極小解為x*，單參數(shù)填充函數(shù)構(gòu)建如下：

P(x,x*,ρ)=-ρ[f(x)-f(x*)]2-arctan(‖x-x*‖2)

(3)

其中，ρ>0為參數(shù)，以下定理說明函數(shù)P(x,x*,ρ)滿足填充函數(shù)定義，而且有一些較好的性質(zhì)。

定理1：若x*是函數(shù)f(x)的局部極小解，則x*是P(x,x*,ρ)的一個嚴格的局部極大解。

證明：因為在Rn上，目標(biāo)函數(shù)f(x)連續(xù)；又因為x*為函數(shù)f(x)的局部極小解，所以存在點x*的某個鄰域U(x*)，使得對于每個x∈U(x*)，且x≠x*，滿足f(x)≥f(x*)且

P(x,x*,ρ)=-ρ[f(x)-f(x*)]2-arctan(‖x-x*‖2)<0=P(x*,x*,ρ)

即證：x*是P(x,x*,ρ)的一個嚴格的局部極大解。

定理2：假若x*是函數(shù)f(x)的局部極小解，對每個x∈S1，則P(x,x*,ρ)≠0。

證明：因為f(x)連續(xù)可微，因此

對任意x∈S1，滿足

下面證明對任意x∈Y,都有P(x,x*,ρ)>P(x1*,x*,ρ)。

P(x,x*,ρ)-P(x1*,x*,ρ)=

ρ{[f(x1*)-f(x*)]2-[f(x)-f(x*)]2}+

ρ{[f(x*)-f(x1*)]2-[f(x*)-f(x1*)-

arctan(‖x-x*‖2)

因為ε>0，因此

ρ{[f(x*)-f(x1*)]2-[f(x*)-f(x1*)-ε]2}>0

因此，對任意x∈Y，當(dāng)ρ充分大時，P(x,x*,ρ)>P(x1*,x*,ρ)。(*)

由上述證明可得，當(dāng)取足夠大的ρ時，使得在S2上存在P(x,x*,ρ)的一個局部極小解x0*。

定理4：如果x*是函數(shù)f(x)的全局極小解，則對于任意的x∈X,x≠x*，有P(x,x*,ρ)<0。

證明：因為x*是目標(biāo)函數(shù)f(x)的全局極小解，因此對任意x∈X，f(x)≥f(x*)。

由定理1知：對于任意x∈X,x≠x*，有P(x,x*,ρ)<0。

定理5：如果x*是目標(biāo)函數(shù)f(x)的局部極小解，對于任意x∈S1，且當(dāng)ρ充分大時，則方向d=f(x)T是P(x,x*,ρ)在x處的下降方向；其中f(x)T≠0。

-2ρ[f(x)-f(x*)]所以f(x)TP(x,x*,ρ)=-2ρ[f(x)-f(x*)]f(x)Tf(x)-

對于任意x∈S1，當(dāng)ρ充分大時，f(x)TP(x,x*,ρ)<0。因此結(jié)論成立。

3 填充函數(shù)算法與算例實驗

3.1 填充函數(shù)算法

假設(shè)調(diào)節(jié)步長δ>0，ε>1，參數(shù)k是外循環(huán)的運算次數(shù)，且存在一個足夠大的正整數(shù)N，使得k≤N；參數(shù)i是內(nèi)循環(huán)迭代次數(shù)，且存在一個足夠大的正整數(shù)M，使得i≤M;一般選取M>2n，其中n是決策變量的維數(shù)。參數(shù)ρ≤ρ0

Step1：令k:=1，i:=1，ρ:=1。

Step2：選擇初始點x0∈X,從x0開始，利用成熟的最優(yōu)化方法，解出局部極小解x1*和對應(yīng)的局部極小值f(x1*)。

Step3：在極小解x1*處構(gòu)建填充函數(shù)：

P(x,x*,ρ)=-ρ[f(x)-f(x*)]2-

arctan(‖x-x*‖2)

Step4：如果i≤M，選取x1=x1*+δdi∈X,其中di是隨機方向，‖di‖∞≤1，δ>0；從點x1開始，用成熟的優(yōu)化算法求解P(x,x*,ρ)的局部極小解x2，轉(zhuǎn)為Step5；否則，令k:=k+1，轉(zhuǎn)為Step6。

Step5：假若x2∈X,轉(zhuǎn)為Step6；否則令i:=i+1，轉(zhuǎn)為Step4。

Step7：如果k≤N,令ρ:=ρε，i:=1，如果ρ>ρ0，則取ρ=ρ0，轉(zhuǎn)為Step4。否則，結(jié)束計算；輸出x1*與函數(shù)值f(x1*)，把f(x1*)作為近似的全局極小值。

3.2 算例實驗

算例都在Matlab2014a運行環(huán)境下實現(xiàn)。

算例1：Rastrigin

s.t.x∈{(x1,x2)|-1≤x1,x2≤1}

文中迭代次數(shù)是1次，得到的全局極小解是x*=(-0.679 5e-9,0.555 2e-9)T，全局極小值f(x*)=-2；而文獻[4]的數(shù)值結(jié)果中迭代次數(shù)是4次，全局最小解是x*=(-0.200 0e-7,-0.200 0e-7)T，全局極小值是f(x*)=-1.999 999 99。

算例2：Three-hump camel-back Function

s.t.x∈{(x1,x2)|-3≤x1,x2≤3}

文中的迭代次數(shù)是2次，全局極小解是x*=(0.076 5e-6,0.161 8e-6)T，全局極小值是f(x*)=2.551 4e-14。文獻[4]的迭代次數(shù)是3次，全局極小解是x*=(-1.356e-5,0.492 0e-5)T，全局極小值是f(x*)=4.585e-10。

算例3：Treccani Function

s.t.x∈{(x1,x2)|-3≤x1,x2≤3}

文中的迭代次數(shù)是1，全局極小解是x*=(0.061 0×1.0e-6,-0.156 9×1.0e-6)T全局極小值是f(x*)=3.951 4e-14；文獻[4]的迭代次數(shù)是2，全局極小解是x*=(4.66e-6,0.000 0)T,全局極小值是f(x*)=8.677 1e-11。

算例4：Six-hump camel-back Function

s.t.x∈{(x1,x2)|-3≤x1,x2≤3}

文中迭代次數(shù)是2次。全局極小解是(0.089 8,0.712 7)T，全局極小值是f(x*)=-1.031 6。文獻[4]的迭代次數(shù)是3，全局極小解是x*=(0.089 837 22,0.712 694 68)T,全局極小值是f(x*)=-1.031 628 44。

算例5：Two-dimensional Function

minf(x)=[1-2x2+0.5sin(4πx2)-x1]2+[x2-0.5sin(2πx1)]2

s.t.x∈{(x1,x2)|0≤x1≤10,-10≤x2≤0}文中迭代次數(shù)是4次；全局極小解是x*=(0.934 2,-0.174 6)T，全局極小值是f(x*)=7.669 3e-14。文獻[4]的迭代次數(shù)是3，全局極小解是

x*=(0.999 999 99,0.000 000 17)T，全局極小值是f(x*)=5.907 849 04e-13。

小結(jié)：對比文獻[4，8]的數(shù)值結(jié)果，算法迭代次數(shù)較少，而且精度較高。

4 結(jié)束語

文中構(gòu)建的無約束的優(yōu)化問題的單參數(shù)填充函數(shù)，具有較好的性質(zhì)，而且形式簡單，便于計算。算例結(jié)果證明了該算法的可行性。在此基礎(chǔ)上，還可以構(gòu)建無參數(shù)填充函數(shù)，或引入濾子方法等[12-15]，研究求解優(yōu)化問題的填充函數(shù)仍是一個研究方向。