馬素霞 ,高岳林 ,楊麗麗 ,柳迎春

(1.寧夏大學(xué)數(shù)學(xué)統(tǒng)計(jì)學(xué)院,寧夏 銀川 750021;2.北方民族大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,寧夏 銀川 750021;3.寧夏科學(xué)計(jì)算與智能信息處理協(xié)同創(chuàng)新中心,寧夏 銀川 750021)

1.引言

科學(xué)和工程中的大量決策問題都可歸結(jié)為求解全局優(yōu)化問題,而這類問題的求解方法是當(dāng)今社會(huì)的一個(gè)重要研究熱點(diǎn).現(xiàn)有的全局優(yōu)化算法大體可分為兩大類,即,確定性算法[1-4]和隨機(jī)性算法[5-7].其中,填充函數(shù)法是一種經(jīng)典的全局優(yōu)化確定性方法,由西安交通大學(xué)的葛仁溥教授[2]最早提出,該方法主要通過循環(huán)迭代不斷跳出當(dāng)前已知的最好局部極小點(diǎn)以便找到另一個(gè)更好的局部極小點(diǎn),直到找到全局極小點(diǎn)為止,從而能夠克服一般優(yōu)化算法容易陷入“早熟”的缺陷.在文[1]中,葛仁溥教授率先給出了填充函數(shù)的初步概念,并將其應(yīng)用于無約束全局優(yōu)化問題的求解,該方法因內(nèi)部只需要調(diào)用現(xiàn)有的局部?jī)?yōu)化方法而深受廣大學(xué)者的歡迎.然而,文[1]中的第一代填充函數(shù)包含指數(shù)項(xiàng)和兩個(gè)參數(shù),由于參數(shù)調(diào)節(jié)上的困難使得實(shí)際應(yīng)用中的計(jì)算量變大以及指數(shù)項(xiàng)的存在容易遺失問題的最優(yōu)點(diǎn),從而導(dǎo)致了該填充函數(shù)的不適用性.因此,諸多國(guó)內(nèi)外學(xué)者都對(duì)葛教授的填充函數(shù)的不足之處做出了相關(guān)改進(jìn)并提出了各種能夠被應(yīng)用到實(shí)際問題中的填充函數(shù).例如,文[8-11]中所出現(xiàn)的四種雙參數(shù)填充函數(shù)、文[12-16]中所提出的五個(gè)單參數(shù)填充函數(shù)以及文[17-22]中所給出的六種無參數(shù)填充函數(shù)等等,這些填充函數(shù)的提出使得全局優(yōu)化理論更為豐富.值得一提的是,文[16]中的填充函數(shù)僅在部分可行域內(nèi)有定義,使得該填充函數(shù)的填充效率大為降低;文[21]中是一個(gè)很有前景的無參數(shù)填充函數(shù),它具有連續(xù)可微的性質(zhì),但仍然包含指數(shù)項(xiàng)從而降低了填充效果,文[22]的填充函數(shù)卻避免了這一缺點(diǎn),但其函數(shù)圖像在某些情況下是平坦的,使得填充函數(shù)在跳出局部極小點(diǎn)時(shí)的效率降低,該填充函數(shù)中也包含不連續(xù)可微的符號(hào)函數(shù),這大大限制了極小化填充函數(shù)所需下降方法的選取范圍.上述填充函數(shù)方法僅能被用于求解無約束全局優(yōu)化問題或盒子約束全局優(yōu)化問題.目前,只有少數(shù)填充函數(shù)可以解決約束全局優(yōu)化問題,如文[23-27]中的方法.此外,現(xiàn)有的填充函數(shù)雖然各有優(yōu)點(diǎn),但也存在一些缺點(diǎn),如填充函數(shù)包含多個(gè)參數(shù),導(dǎo)致調(diào)整困難,降低了算法的效率,若某些填充函數(shù)是非光滑函數(shù),這也是傳統(tǒng)局部?jī)?yōu)化方法無法實(shí)現(xiàn)的.

為了求解有約束的全局優(yōu)化問題,本文提出了一種新的填充函數(shù),它是一個(gè)連續(xù)可微的單參數(shù)函數(shù).如果參數(shù)的取值盡可能小且大于0,那么該填充函數(shù)將保證不可行區(qū)域不存在駐點(diǎn).另外，如果某個(gè)可行點(diǎn)的目標(biāo)函數(shù)值大于當(dāng)前局部極小值,則該點(diǎn)也不是所提填充函數(shù)的駐點(diǎn).如果存在另一個(gè)優(yōu)于目標(biāo)函數(shù)當(dāng)前極小值的局部極小點(diǎn),那么此填充函數(shù)的極小點(diǎn)就會(huì)落在目標(biāo)函數(shù)值較優(yōu)的極小點(diǎn)附近.

本文的其余部分組織如下.第二節(jié)中給出了填充函數(shù)方法的相關(guān)預(yù)備知識(shí).第三節(jié)提出了一種連續(xù)可微的單參數(shù)填充函數(shù).并對(duì)其解析性質(zhì)做出了分析.第四節(jié)是所設(shè)計(jì)的填充函數(shù)全局優(yōu)化算法的具體步驟.第五節(jié)給出一些測(cè)試問題的數(shù)值實(shí)驗(yàn)結(jié)果.第六節(jié)是結(jié)論.

2.預(yù)備知識(shí)

本文研究以下約束全局優(yōu)化問題:

其中f:R,gi(x) :R,i1,2,···,m,均為二次連續(xù)可微函數(shù),?是一個(gè)盒子,S{x|gi(x)≤0,i1,2,···,m}是有界集且滿足cl(int(S))S,這里int(A)表示集合A的內(nèi)部,cl(A)表示集合A的閉包.在S的限制上,存在?滿足S ??和??∩S?(??表示集合?的界).

為確保問題(OP)的全局最優(yōu)解存在以及所提出的填充函數(shù)方法能夠順利實(shí)現(xiàn),預(yù)先給出關(guān)于該問題的一些假設(shè)條件和定義是有必要的.

假設(shè)2.1問題(OP)中的目標(biāo)函數(shù)是連續(xù)可微的.

假設(shè)2.2集合τ是由問題(OP)在S中的所有局部極小點(diǎn)組成的,且L?{F(x)|是有限的.

注2.1假設(shè)2.2表明問題(OP)可能有無限個(gè)局部極小點(diǎn),但是局部極小值的數(shù)量總是有限的.

定義2.1如果存在ε>0,使得(x0,ε)∩S,有F(x)≥(≤)F(x0),則x0被稱為F(x)在集合S上的一個(gè)局部極小點(diǎn)(極大點(diǎn)).如果等式不成立,則x0被稱為F(x)在集合S上的一個(gè)嚴(yán)格局部極小點(diǎn)(極大點(diǎn));如果,有F(x)≥(≤)F(x0)成立,則x0被稱為F(x)在集合S上的一個(gè)全局極小點(diǎn)(極大點(diǎn)).如果等式不成立,則x0被稱為F(x)在集合S上的一個(gè)嚴(yán)格全局極小點(diǎn)(極大點(diǎn)).

注2.2B(x0,ε)表示x0的以ε為半徑的鄰域.

注2.3 定義2.2的前兩個(gè)填充性質(zhì)保證了填充過程得以實(shí)現(xiàn),而第三個(gè)填充性質(zhì)則確保了填充函數(shù)極小點(diǎn)x′的存在性.另外定義2.2也可概括為: 1)填充函數(shù)在上是一個(gè)減函數(shù)并且沒有駐點(diǎn);2) 填充函數(shù)的極小點(diǎn)在上.

3.新的填充函數(shù)及其解析性質(zhì)

基于定義2.2所要求的三個(gè)填充性質(zhì)并且考慮到多參數(shù)填充函數(shù)的不足之處,提出了下面的單參數(shù)填充函數(shù):

式中r>0為參數(shù),∥·∥表示是·的歐氏范數(shù),F(x)是目標(biāo)函數(shù),是問題(OP)的一個(gè)局部極小點(diǎn),h(t),g(t)和fr(t)是R上連續(xù)可微的一元函數(shù).m是問題(OP)中不等式約束的個(gè)數(shù).容易驗(yàn)證,填充函數(shù)(3.1)是連續(xù)可微的.

下面驗(yàn)證,當(dāng)r>0且r足夠小時(shí),MF(x,,r)滿足第二部分所定義的填充函數(shù).

再利用函數(shù)fr(t)的定義不難斷定

4.填充函數(shù)算法

本節(jié)將利用構(gòu)造的填充函數(shù)設(shè)計(jì)出相應(yīng)的單參數(shù)填充函數(shù)算法(PFFA: Parameter Filled Function Algorithm).填充函數(shù)算法總是涉及到極小化過程,包括極小化目標(biāo)函數(shù)或者極小化填充函數(shù)本身.本文將采用SQP方法極小化目標(biāo)函數(shù),采用BFGS方法極小化填充函數(shù).

步0 選擇參數(shù)r的一個(gè)下界Lr(例如,取Lr10-9)和一個(gè)常數(shù)ρ<1(例如,取ρ10-3);給出r的初始值(例如,取r1);選擇一個(gè)初始點(diǎn)x0;令方向集D{eiRn|i1,2,···,2n}(其中ei(0,···,1,···,0)T,i1,2,···,n,ei的第i個(gè)元素取1,ei?ei-n,in+1,···,2n,n是函數(shù)F(x)的變量個(gè)數(shù));σ0>0(本文取σ00.01);ε>0(本文取ε10-6);置k1.

步1 以x0作為初始點(diǎn)極小化F(x)得到,置i1.

步2 構(gòu)造函數(shù)

5.數(shù)值實(shí)驗(yàn)

本文使用Matlab(2016a)對(duì)PFFA算法進(jìn)行編碼并執(zhí)行.通過使用6種測(cè)試函數(shù)對(duì)該算法進(jìn)行測(cè)試,所有這些計(jì)算過程均在Intel(R) Core(TM)i5-8500 3.00 GHz power處理器8.00 GB內(nèi)存,Win10操作系統(tǒng)的臺(tái)式電腦上進(jìn)行.

下面給出6種測(cè)試函數(shù),其中F(x)表示目標(biāo)函數(shù),x0表示初始點(diǎn),x?和F(x?)分別表示全局極小點(diǎn)和全局極小值.

例1[28]

例1的全局最優(yōu)解為x?(2.3295,3.1783)T,F(x?)?5.5079.實(shí)驗(yàn)中,采用初始點(diǎn)x0(0,0)T和x0(0.6,0.8)T,其計(jì)算結(jié)果見表5.2.

例2[29]

在例2中,x?(0.7255,0.3993)T,F(x?)?1.8376.本文使用初始點(diǎn)x0(1,1)T,x0(0.5,0.5)T,x0(1.5,1.5)T,x0(2,2)T和x0(2,1)T對(duì)該問題進(jìn)行數(shù)值測(cè)試,其計(jì)算結(jié)果見表5.2.

例3[29]

例3在可行域內(nèi)的全局最優(yōu)解為x?(5,1,5,0,5,10)T,F(x?)?310.本文使用初始點(diǎn)x0(3,3,3,3,3,3)T,x0(4,4,4,4,4,4)T,x0(3,3,4,4,3,5)T,x0(4,4,4,4,4,4)T和x0(2,2,3,2,3,2)T對(duì)該問題進(jìn)行數(shù)值測(cè)試,其數(shù)值計(jì)算結(jié)果見表5.2.

例4[28]

例4在可行域內(nèi)的全局最優(yōu)解為x?(78,33,29.9953,45,36.7758)T,F(x?)?30665.5387.本文使用了初始點(diǎn)x0(90,33,35,35,40)T來測(cè)試這個(gè)問題,其計(jì)算結(jié)果見表5.2.

例5[10]

在例5中,x?(0.1093,?0.6234)T,F(x?)?0.9711.本文使用初始點(diǎn)x0(?1,?1)T,x0(0,0)T和x0(1,1)T對(duì)該問題進(jìn)行數(shù)值測(cè)試,其計(jì)算結(jié)果見表5.2.

例6[26]

例6的全局最優(yōu)解為x?(0,0)T,F(x?)?2.7183.實(shí)驗(yàn)中,采用初始點(diǎn)x0(30,30)T,其計(jì)算結(jié)果見表5.2.

后面這部分對(duì)PFFA算法進(jìn)行了數(shù)值實(shí)驗(yàn)測(cè)試.為了證明該算法的有效性,我們對(duì)PFFA算法計(jì)算所得到的迭代次數(shù)和填充函數(shù)的評(píng)估次數(shù)的數(shù)值結(jié)果與文[10,23,26]中相應(yīng)的數(shù)值結(jié)果進(jìn)行了比較.在此之前,對(duì)這部分所使用的一些符號(hào)約定如表5.1所示.

表5.1 符號(hào)說明

從表5.2的數(shù)值結(jié)果可以看出,本文算法能夠在有限的迭代內(nèi)對(duì)這6種類型共19個(gè)測(cè)試?yán)舆M(jìn)行全局尋優(yōu),且算法的每一步都是下降的,這說明該算法是可行的.

表5.2 例1-4的計(jì)算結(jié)果

表5.3-5.5分別是本文算與文[23]、[10]和[26]中算法對(duì)這6種類型的測(cè)試問題的數(shù)值計(jì)算結(jié)果對(duì)比.從表5.3-5.5可以觀測(cè)到,算法PFFA與三個(gè)對(duì)比文獻(xiàn)中算法的迭代次數(shù)相當(dāng).而在函數(shù)評(píng)估次數(shù)上,表5.3表明了算法PFFA在13個(gè)測(cè)試?yán)又杏?1個(gè)測(cè)試?yán)泳鶅?yōu)于文[23]中算法,表5.4表明了算法PFFA在10個(gè)測(cè)試?yán)又杏?個(gè)測(cè)試?yán)泳鶅?yōu)于文[10]中算法.表5.5中算法PFFA與[26]中算法所得全局最優(yōu)解相一致.因此,本文算法也是有效的,并且比文[23]和[10]中的算法計(jì)算能力更強(qiáng).

表5.3 本文與文[23]的數(shù)值計(jì)算結(jié)果對(duì)比

表5.4 本文與文[10]的數(shù)值計(jì)算結(jié)果對(duì)比

表5.5 本文與文[26]的數(shù)值計(jì)算結(jié)果對(duì)比

綜上所述,本文所設(shè)計(jì)的填充函數(shù)算法是有效可行的,適合求解約束全局優(yōu)化問題.

6.結(jié)論

為更好地求解約束全局優(yōu)化問題,本文提出了一個(gè)具有連續(xù)可微性質(zhì)且無指數(shù)項(xiàng)和對(duì)數(shù)項(xiàng)的新型填充函數(shù),并證明了該填充函數(shù)滿足填充性質(zhì).最后利用6種共19個(gè)測(cè)試?yán)訉⒈疚乃惴ǚ謩e與文[23]、[10]和[26]中的算法進(jìn)行了數(shù)值計(jì)算結(jié)果對(duì)比,驗(yàn)證了本文算法的可行性和有效性.未來的研究中,將著重為約束優(yōu)化問題構(gòu)造無約束填充函數(shù)及其對(duì)應(yīng)的全局優(yōu)化算法,以避免參數(shù)調(diào)節(jié)上的限制.