精確罰函數若干性質及算法

李 璞,尚有林

(河南科技大學數學與統計學院,河南洛陽 471003)

0 前言

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

1 精確罰函數

解集: X={x∈Rnhi=0,i∈Igj(x)≤0,j∈J},文獻[10]提出了如下的罰函數形式: 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*)。

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

2 精確罰函數的若干性質

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

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

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

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

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

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

3 算法

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

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

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

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

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

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

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

4 程序說明與計算實例

根據上面給出的算法,用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。

可見,用精確罰函數法求得最優點為(s,t)=(1.384 6,2.076 9)。

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

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

5 結論

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

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

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

[3] 陳寶林.最優化理論與算法[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] 汪壽陽.一種新的罰函數的精確罰定理[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] 江維瓊.一種新的精確罰函數[J].云南師范大學學報,2006,26(2):9-20.