精確罰函數(shù)若干性質及算法

李 璞,尚有林

(河南科技大學數(shù)學與統(tǒng)計學院,河南洛陽 471003)

0 前言

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

1 精確罰函數(shù)

解集: X={x∈Rnhi=0,i∈Igj(x)≤0,j∈J},文獻[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。

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

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

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

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

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

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

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

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

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

3 算法

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

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

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

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

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

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

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

4 程序說明與計算實例

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

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

對上述程序給出算例(以兩個變量為例)如下:

其中初始點選取(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])。

運行結果為:x=1.384 6; 2.076 9。

min f=0.733 7。

可見,用精確罰函數(shù)法求得最優(yōu)點為(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)化問題,初始點取(s,t)=(0,0),運行結果為(s,t)=(0.500 0,0.500 0), min f=0.187 5。因此,也可以用精確罰函數(shù)法求解僅含有等式約束的優(yōu)化問題。

5 結論

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

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

[2] 《運籌學》教材編寫組.運籌學[M].3版.北京:清華大學出版社,2005.

[3] 陳寶林.最優(yōu)化理論與算法[M].2版.北京:清華大學出版社,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] 汪壽陽.一種新的罰函數(shù)的精確罰定理[J].自然科學進展,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].云南師范大學學報,2006,26(2):9-20.