求解無約束優化問題的新填充函數算法

摘 要：填充函數法是求解全局優化問題的一種重要的方法，本文構造一個新的形式簡單且便于計算的單參數填充函數，編寫算法，并通過數值計算驗證了該算法的有效性和可行性。

關鍵詞：填充函數；全局優化；單參數；數值計算

Abstract：The filled function method is an important way to solve global optimization problem. A novel single parameter filled function with simple form and easy to calculate is constructed in the paper. And also its validity and feasibility is validated by numerical calculation.

Keywords：filled function；global optimization；single parameter；numerical calculation

1引言

填充函數法由兩個階段組成：極小化階段和填充階段，兩個階段交替循環著進行，直到找到問題的全局極小點。其中極小化階段就是用我們學過的無約束極小化算法極小化問題，得到局部極小點，當該點不是全局極小點時，就進入填充階段，構造填充函數，回到極小化階段，找到更小的極小點，重復這個過程，就可以找到全局極小點。填充函數法的核心就是構造填充函數，填充函數的形式與性質決定著相應算法的效率，因此本文力求構造出形式簡單，含參數盡量少，且性質良好的填充函數。

2基本概念

考慮無約束極小化問題

■f（■） （p）

對問題（P）作如下假設：

● 函數f（■）是強制性質的，即■f（■）=+∞；

該假設的目的是保證存在一個緊集X？奐Rn，X包含了f（■）的所有全局極小點和函數值較小的局部極小點，于是，問題（p）等價于■f（■）。

● 函數f（■）在X上是連續可微的，問題（p）的局部極小點可以是無限多個，但不同的局部極小值是有限的。

下面給出問題（p）所滿足的填充函數的定義：

函數p（■，■，A）稱為f（■）在局部極小點處■的填充函數，如果它滿足以下條件：

（1）在X上■是p（■，■，A）的嚴格局部極大點；

（2）對任意■∈S1有，？塄p（■，■，A）≠■，其中S1={■|f（■）≥f（■），■∈X＼{■}}，即p（■，■，A）在S1上沒有極小點或鞍點；

（3）若■不是全局極小點，那么p（■，■，A）一定在S2={■|f（■）

3填充函數及其性質

針對本文問題（p），構造單參數填充函數如下：

p（■，■，A）=-Aexp[f（■）-f（■）]-||■-■||2，其中A>0是參數。

當A>0充分大時，下面幾個定理表明函數p（■，■，A）是滿足定義的一個填充函數。

定理1：■是f（■）的局部極小解，則■是p（■，■，A）的一個嚴格局部極大解。

證明：由■是f（■）的局部極小解及f（■）的連續性，可知，？堝N（■，？啄），？啄>0，？坌■∈N（■，？啄），且■≠■，有f（■）≥f（■），則？坌■∈N（■，？啄），且■≠■有p（■，■，A）=-Aexp[f（■）-f（■）]-||■-■||2≤0=p（■，■，A）。

定理2：若■是f（■）的局部極小解，則？坌■∈S1={■|f（■）≥f（■），■∈X＼{■}}都有？塄p（■，■，A）≠■。

證明：由f（■）的連續性，計算得

？塄p（■，■A）=Aexp[f（■）-f（■）]·？塄f（■）-2（■-■），則？坌■∈S1，有

（i）若？塄f（■）=■，或f（■）=f（■），則由■≠■可得？塄p（■，■，A）=-2（■-■）≠■。

（ii）若？塄f（■）≠■且f（■）>f（■），則當A充分大時，可得？塄p（■，■，A）≠■。

定理3：若■是f（■）的局部極小解，但不是全局極小解，則在S2={■|f（■）

證明：因為■是f（■）的局部極小解，但不是全局極小解，所以S2≠？準，則存在f（■）的另一個局部極小解■，使得f（■）p（■，■，A），計算得p（■，■，A）-p（■，■，A）

=A{exp[f（■）-f（■）]-exp[f（■）-f（■）-？著]}+[||■-■||2-||■-■||2]>0（*）

（當A充分大時）

記I={■∈X|f（■）≤f（■）+？著}，因為p（■，■，A）是有界閉集I上的連續函數，故一定能在I上取得最小值，不妨記■p（■，■，A）=p（■，■，A），由于■∈I，故p（■，■，A）≤p（■，■，A），由（*）有■p（■，■，A）=p（■，■，A）=■p（■，■，A），

又因為I＼H為開集■，因此■∈I＼H？奐intX，由？著的取值范圍有

f（■）≤f（■）+？著

4算法與算例

4.1算法

（1）令k=1，表示迭代次數，選取方向ei，i=1，2，…，k0，其中k0≥2n（k0為內循環的初始搜索方向個數上限），n為變量的維數，令H=0，并且任意選擇J≥1（用來判斷A是否充分大），選取合適的步長？啄（可取0.4）；

（2）選取初始點■∈X；

（3）以■為初始點，通過任一局部極小化算法極小化目標函數f（■）得到一局部極小解■；

（4）選取充分大的A（可取10）；

（5）構造填充函數

p（■，■，A）=-Aexp[f（■）-f（■）]-||■-■||2

令i=1，轉到內循環，

①若i≥k0，則令■=■+？啄ei，轉②，否則轉⑤；

②以■為初始點，用任意局部極小化算法極小化填充函數p（■，■，A），得到p（■，■，A）的一個局部極小點■；

③若■？埸X，則令i=i+1，轉①，否則轉④；

④若f（■）>f（■），轉⑤，否則轉⑥；

⑤若H

⑥令■=■，k=k+1，轉（3）。

4.2算例

例1：Treccani Function

minf（■）=x14+4x13+4x12+x22，

s.t. -3≤x1≤3，-3≤x2≤3。

取初始點■=（-1，2），算法找到全局最優點及最優值

■=（-2.0000，0.0000），f*=4.7731e-035。

例2：Six-hump camel-back Function

minf（■）=4x12-2.1x14+■x16-x1x2-4x22+4x24，

s.t. -3≤x1≤3，-3≤x2≤3。

取初始點■=（-2，1），算法找到全局最優點及最優值■=（0.0891，0.7098），f*=-1.0316。

例3：Two-dimendional Function

minf（■）=[1-2x2+csin（4？仔x2）-x1]2+[x2-0.5sin（2？仔x1）]2

s.t. 0≤x1≤10，-10≤x2≤0。

當c=0.2時，取初始點■=（4，-4），算法找到全局最優點及最優值

■=（1.87843103703609-0.34584998088019），

f*=2.018165391829496e-023；

當c=0.5時，取初始點■=[4，-2]，得最優解及最優值

■=（0.99999999999996-0.00000000000001），

f*=1.741754200684004e-026。

5結論

本文給出求解無約束全局優化問題的一個單參數填充函數算法，由數值算例的結論可以看出，本文給出的填充函數算法是可行有效的，并且計算精度也很高。

參考文獻：

[1]GE Ren-pu.A Filled Function Method for Finding a Global Minimizerofa

Function of Several Variables [J].Mathematical Programming， 1990， 46

（02）： 191-204.

[2]GE Ren-pu.The Theory of Filled Function Methods for Finding

Global Minimizers of Nonlinearly Constrained Minimization Problems

[J]. Journal of Computational Mathematics，1987，5（01）：1-9.

[3]SHANG Y L， PU D G， JIANG A P.Finding global minimizer with one-pa-

rameter filled function on unconstrained global optimization[J].Applied

Mathematicsand Computation， 2007， 191： 176-182.

[4]WANG Wei，YANG Yong-jian， ZHANG Lian-sheng. Unification of Filled

Function and Tunnelling Function in Global Optimization [J]. Acta Math-

ematicae Applicatae Sinica： English Series， 2007， 23（01）： 59-66.

[5]YangY J， ShangY L.A new filled function method for unconstrained global

optimization[J].Applied Mathematics and Computation，2006，173： 501-5

12.

[6]LIU Xian. Several filled functions with mitigators[J]. Applied Mathematics

and Computation， 2002， 133： 375-385.

[7]Lucidi S， Piccialli V.New Classes of Globally Convexized Filled

Functions for Global Optimization[J]. Journal of Global Optimization，

2002， 24（02）： 219-236.

注：本文為遼寧省自然科學基金項目，項目編號：201102070。