李 璞,尚有林

(河南科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,河南洛陽(yáng) 471003)

0 前言

罰函數(shù)法是將有約束的優(yōu)化問(wèn)題轉(zhuǎn)化成無(wú)約束的優(yōu)化問(wèn)題來(lái)求解的方法。經(jīng)典的罰函數(shù)理論,是通過(guò)添加罰函數(shù)項(xiàng)后,研究一系列無(wú)約束優(yōu)化問(wèn)題,并使懲罰參數(shù)趨于無(wú)限大來(lái)獲得原規(guī)劃的最優(yōu)解。而精確罰函數(shù)理論是通過(guò)求解單個(gè)無(wú)約束優(yōu)化問(wèn)題來(lái)求原規(guī)劃的最優(yōu)解。如文獻(xiàn)[1]所述,罰函數(shù)法的主要缺點(diǎn)是目標(biāo)函數(shù)的病態(tài)性質(zhì),這種病態(tài)性質(zhì)是由罰因子的無(wú)限增大或減小而引起的[2-3],為了改進(jìn)罰函數(shù)法而提出的各類(lèi)方法中,精確罰函數(shù)方法是一類(lèi)重要的算法。一般精確罰函數(shù)并不光滑[4-5],可以將非光滑的精確罰函數(shù)光滑化[6],但罰函數(shù)的形式會(huì)變的更加復(fù)雜,在實(shí)際計(jì)算中,由于不知道罰參數(shù)具體有多大,需要不斷的增大,這樣就影響了常用的一些有效的算法,如 Newton算法。因此,精確性和可微性是罰函數(shù)的關(guān)鍵性問(wèn)題。文獻(xiàn)[8-9]給出了最小精確罰參數(shù)的估計(jì)。文獻(xiàn)[7]也提出了同時(shí)具有光滑性和精確性的一類(lèi)罰函數(shù)形式。本文在一種精確罰函數(shù)形式下[10],討論了相關(guān)的一些性質(zhì)定理,根據(jù)此罰函數(shù)的形式設(shè)計(jì)了相應(yīng)的算法,并通過(guò)編程給予實(shí)現(xiàn)。

1 精確罰函數(shù)

解集: X={x∈Rnhi=0,i∈Igj(x)≤0,j∈J},文獻(xiàn)[10]提出了如下的罰函數(shù)形式: P(x,M)=φ(f(x)-M)+F(x)。其中φ(t)=max2(0,t),F(x)=[hi(x)]2+φ(gj(x)),顯然F(x)≥0,所以P(x,M)≥0,F(x)=0的充要條件是hi(x)=0,i∈Igj(x)≤0,j∈J。

于是問(wèn)題(I)的解x*滿足F(x*)=0,并且對(duì)于任意的滿足F(x)=0的點(diǎn)x都有f(x)≥f(x*)。

考慮新的無(wú)約束優(yōu)化問(wèn)題:(Ⅱ)minP(x,M),s.t x∈Rn。

2 精確罰函數(shù)的若干性質(zhì)

針對(duì)上述精確罰函數(shù)的形式,文獻(xiàn)[7]與文獻(xiàn)[10]分別介紹了若干性質(zhì)定理如下:

性質(zhì)1【7】如果x*是問(wèn)題(I)的最優(yōu)解且M=f*=f(x*),則x*是罰問(wèn)題(Ⅱ)的最優(yōu)解且P(x*,f*)=0。

性質(zhì)2【7】設(shè)x*是問(wèn)題(I)的最優(yōu)解,對(duì)某個(gè)M,是罰問(wèn)題(Ⅱ)的最優(yōu)解和問(wèn)題(I)的可行解,并且P(x*,M)≠0。如果M≤f(x*),那么是問(wèn)題(I)的最優(yōu)解。

性質(zhì)3【10】設(shè)X是連通緊集,f(x)是X上的連續(xù)函數(shù),令α=f(x),β=f(x),對(duì)某個(gè)M,是罰問(wèn)題(Ⅱ)的最優(yōu)解,則:

上述 3個(gè)性質(zhì)雖然指出了給定的精確罰函數(shù)的若干性質(zhì),但是并未涉及到罰參數(shù)和最優(yōu)值之間的具體聯(lián)系,本文在已有文獻(xiàn)基礎(chǔ)上,給出兩個(gè)有關(guān)罰函數(shù)的罰參數(shù)與原問(wèn)題最優(yōu)解以及罰問(wèn)題最優(yōu)解之間關(guān)系的性質(zhì)定理,具體如下:

該定理說(shuō)明了當(dāng)罰參數(shù)取值大于原問(wèn)題最優(yōu)值的時(shí)候,罰問(wèn)題最優(yōu)解x*M滿足P(x*M,M)=0,并且當(dāng)P(,M)=0時(shí),罰參數(shù)的取值一定是大于原問(wèn)題最優(yōu)值的。

3 算法

已有文獻(xiàn)在給出精確罰函數(shù)的形式之后,選擇適當(dāng)?shù)牧P參數(shù),將各個(gè)變量直接代入罰函數(shù)形式中進(jìn)行計(jì)算,驗(yàn)證這樣的精確罰函數(shù)是確實(shí)存在的,但并沒(méi)有提出有效算法。根據(jù)精確罰函數(shù)性質(zhì)以及P(x,M)連續(xù)性,若知道f*的近似值,則能通過(guò)求解問(wèn)題(II)得到約束問(wèn)題(I)的最優(yōu)解,基于這個(gè)思想,本文在已有罰函數(shù)形式基礎(chǔ)上,設(shè)計(jì)了相關(guān)算法,并通過(guò)編程給予實(shí)現(xiàn),在計(jì)算上減少直接代入的不便性,提高了效率。具體算法如下:

(1)輸入f*的下界初值α0≤f*(α0可根據(jù)目標(biāo)函數(shù)與可行域適當(dāng)選取),取得問(wèn)題(I)的可行點(diǎn)x0,顯然F(x0)=0。令β0=f(x0)為f*的上界初值,即f*≤β0(x0也可以通過(guò)求解min F(x)得到)。

(2)令Mk=(1-θ)αk+θβk(θ為參數(shù),取值范圍 0＜θ＜0.5,程序中取了θ=0.4),求解min P(x,M)=P(,Mk)=

(4)重復(fù)(2)、(3)直到βk-αk≤ε,這時(shí)令最優(yōu)解為x*=k。

定理 1和定理 2給出 f*確定的取值范圍,并且 f*下界不宜選取過(guò)小,這就可避免產(chǎn)生溢出而導(dǎo)致算法失敗。

收斂性定理 上述精確罰函數(shù)的算法是收斂的。

由上述算法產(chǎn)生的 αk,βk滿足αk≤f*≤βk,并且由于βk-αk→0,所以,上面給出的算法是收斂的。

4 程序說(shuō)明與計(jì)算實(shí)例

根據(jù)上面給出的算法,用MATLAB編寫(xiě)程序,列出部分主程序如下:

以上程序中涉及到的無(wú)約束問(wèn)題的求解采用的是擬牛頓法。

對(duì)上述程序給出算例(以?xún)蓚€(gè)變量為例)如下:

其中初始點(diǎn)選取(s,t)=(2,3)。

解 在MATLAB的命令窗口中輸入:syms s t。

f=s^2-s*t+t-s+1;g=[——t^2-s^2+6;-s;-t];h=[2*s+3*t-9];[x,minf]=minLP(f, [2 3],g,h,0,0.4,[s t])。

運(yùn)行結(jié)果為:x=1.384 6; 2.076 9。

min f=0.733 7。

可見(jiàn),用精確罰函數(shù)法求得最優(yōu)點(diǎn)為(s,t)=(1.384 6,2.076 9)。

例2 m in f(s,t)=0.5t2+0.25s2,s.t t+s=1。

這是僅有等式約束的優(yōu)化問(wèn)題,初始點(diǎn)取(s,t)=(0,0),運(yùn)行結(jié)果為(s,t)=(0.500 0,0.500 0), min f=0.187 5。因此,也可以用精確罰函數(shù)法求解僅含有等式約束的優(yōu)化問(wèn)題。

5 結(jié)論

在文獻(xiàn)[10]的基礎(chǔ)上討論了罰函數(shù)的罰參數(shù)與原問(wèn)題最優(yōu)解以及罰問(wèn)題最優(yōu)解之間具體關(guān)系,指出精確罰函數(shù)P(x,M)的精確性以及f(x*)的取值范圍,并且給出了具體罰函數(shù)形式下相應(yīng)的算法,最后通過(guò)計(jì)算機(jī)編寫(xiě)程序給予實(shí)現(xiàn)。

[1] 胡毓達(dá).非線性規(guī)劃[M].北京:高等教育出版社,1990.

[2] 《運(yùn)籌學(xué)》教材編寫(xiě)組.運(yùn)籌學(xué)[M].3版.北京:清華大學(xué)出版社,2005.

[3] 陳寶林.最優(yōu)化理論與算法[M].2版.北京:清華大學(xué)出版社,2005.

[4] Han S P,Mngasarian O L.Exact Penalty Functions in Nonlinear Programm ing[J].Math Programming,1979,17:251-269.

[5] ZangwillW I.Non linear Programm ing Via Penalty Function[J].Management Science,1967,13:344-358.

[6] Zenio S A.A Smooth Penalty Function Algorithm for Network Structured Prob lems[J].European Journal of Operational Research,1993,64:258.

[7] 汪壽陽(yáng).一種新的罰函數(shù)的精確罰定理[J].自然科學(xué)進(jìn)展,2003,13(3):328-329.

[8] Wu Z Y,Bai F S,Yang X Q.An Exact Lowei Order Penalty Function and Its Smoothing in Nonlinear Programming[J].Optim ization,2004,53(1):51-68.

[9] Rubinov A M,Yang X Q.Langrange-type Functions in Corrstrained Non-Convex Optimization[M].Boston,London:Kluwer Academ ic Publishers,2003.

[10] 江維瓊.一種新的精確罰函數(shù)[J].云南師范大學(xué)學(xué)報(bào),2006,26(2):9-20.