楊 蓮, 姚奕榮

非線性優(yōu)化問題廣泛存在于工程設(shè)計、經(jīng)濟管理、軍事科研等應(yīng)用領(lǐng)域.許多學者開始把一些成熟的、有效的算法拓展到求解非線性優(yōu)化問題中,其中罰函數(shù)算法較為引人注目.罰函數(shù)算法是求解約束優(yōu)化問題的一類重要方法,也是一類比較有效的方法.

罰函數(shù)算法的基本思想是借助罰函數(shù)把約束問題轉(zhuǎn)化為無約束問題,進而利用無約束最優(yōu)化方法來求解約束問題.Courant[1]首先提出外點罰函數(shù)算法,有效地將帶有約束的非線性優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題.針對非線性不等式約束優(yōu)化問題,Carroll等[2]提出了內(nèi)點罰函數(shù)算法.精確罰函數(shù)的概念由Eremin[3]和Zangwill[4]在20世紀60年代末分別提出.精確罰函數(shù)包括非光滑精確罰函數(shù)[5-6]和光滑精確罰函數(shù)[7].1967年,Zangwill[4]對凸優(yōu)化問題提出了l1精確罰函數(shù).自此,精確罰函數(shù)算法成為解決非線性優(yōu)化問題的重要方法,人們對該算法開展了許多研究.Rosenberg[8]和Lasserre[9]分別研究了一個精確罰函數(shù)算法的全局收斂性.Pinar等[10]提出了一個一次連續(xù)可微的罰函數(shù).K¨omer[11]研究了二次規(guī)劃問題的精確罰函數(shù)的數(shù)值算法.文獻[12]給出了精確罰函數(shù)的一個充要條件.在文獻[13]中,對于單值標量約束優(yōu)化問題,Lucidi提出并證明了低階精確罰函數(shù)與原約束優(yōu)化問題的等價性.對于變分不等式的約束優(yōu)化問題,文獻[14]通過正則間隙函數(shù)提出了一個新的精確罰函數(shù).對含有目標約束的優(yōu)化問題,文獻[15]研究了罰函數(shù)的精確性并提出了相應(yīng)的算法.由于表達式中含有目標函數(shù)或約束函數(shù)的梯度,在實際計算工作中會顯得過于復(fù)雜,大大制約了這類可微精確罰函數(shù)算法的實際應(yīng)用.因此,非線性精確罰函數(shù)算法和低階罰函數(shù)算法得到了廣泛的關(guān)注,在許多新領(lǐng)域不斷有研究成果出現(xiàn).針對箱子約束的等式優(yōu)化問題,文獻[16]通過增加一個變量,給出了一個新的精確罰函數(shù).

受文獻[16]的啟發(fā),本工作主要通過增加一個變量,針對非線性不等式約束優(yōu)化問題構(gòu)造了一個新的指數(shù)型光滑精確罰函數(shù),并證明了該罰函數(shù)在集合{(x,ε)|ε=0,x∈S或0＜ε＜ε}上具有二次連續(xù)可微性和精確性質(zhì).最后,基于牛頓法設(shè)計了一種新的指數(shù)型精確罰函數(shù)算法,并通過數(shù)值計算驗證了算法的可行性.

1 指數(shù)型光滑精確罰函數(shù)

1.1 罰函數(shù)的構(gòu)造

考慮非線性不等式的約束優(yōu)化問題:

式中,函數(shù)f,gl:Rn→R是二次連續(xù)可微函數(shù).另記S={x∈Rn:gl(x)≤0,l∈I}.

通過增加一個變量ε,問題(P)等價于

式中,ωl∈ R+為給定的實數(shù).另記 Sε={(x,ε):gl(x)≤ εγωl,l∈ I}.構(gòu)造相應(yīng)的罰函數(shù)

考慮問題(P)的罰問題

式中,ε＞0是一固定的實數(shù).顯然,問題(Pσ)是一個無約束優(yōu)化問題.事實上,當罰參數(shù)足夠大時,問題(Pσ)的任何局部極小點都是問題(P)的局部極小點.下面對問題(P)做出一些假設(shè):(1)f(x)在可行域S上是下有界的,其中S是一個緊集或是一個無界閉集;(2)x?∈L(P)是孤立的點,L(P)的數(shù)量是有限的,其中L(P)表示問題(P)的局部極小點的集合.

若x∈/S且 ε＞0,Δ(x,ε)＜+∞,fσ(x,ε)=f(x)+(eΔ(x,ε)? 1)+ σεβ＞ f(x),則當 Sn是一個無界閉集合且f(x)在S上是下有界時,顯然fσ(x,ε)在集合{(x,ε)∈R×[0,ε]:ε =0,x∈S或者ε＞0,Δ(x,ε)＜+∞}中是下有界的.當S是一個緊集,則對于ε＞ 0,fσ(x,ε)在集合{(x,ε)∈Rn×[0,ε]:ε=0,x∈S或者ε＞0,Δ(x,ε)＜+∞}上是下有界的.因此,fσ(x,ε)在集合 Rn× [0,ε]上是有下界的,這表明 fσ(x,ε)在 Rn×[0,ε]上存在局部極小值.

1.2 罰函數(shù)的光滑性

設(shè){σk}是一遞增的罰參數(shù)序列,σk→+∞.對固定罰參數(shù)σk,記對應(yīng)的罰問題(Pσk)的最優(yōu)解為(xk,εk).為了證明罰函數(shù)的光滑性和精確性,作如下假設(shè).

(1)函數(shù)f,gl,l=1,2,···,m在Rn上是二次連續(xù)可微的.

(2)M-F約束品性在x?處成立,即如果存在h∈Rn使得對所有的j∈J(x?),有?gi(x?)Th＜0,其中J(x?)={j∈ I|gj(x?)=0},x?是問題(P)的局部極小點.

(3)max{0,gl(x(k))}=o((ε(k))σ),σ ＞ 1,l=1,2,···,m.

定理1 若(xk,εk)滿足假設(shè)(1)～(3),γ,β,N 滿足2N+γ?3＞0,N?2＞0,Nγ?3＞0,β ? 2＞ 0,則當 (x,ε)∈ {(x,ε)∈ Rn×[0,ε]:ε＞ 0,Δ(x,ε)＜ +∞},且 ε→ 0,x→ x?∈ S時,有

成立,其中

證明 (1)當 ε=0 時,由 fσ(x,ε)的定義可知 fσ(x,ε)=f(x).因此,

(2)當 ε/=0,(x,ε)∈ {(x,ε)∈ Rn×[0,ε]:ε＞ 0,Δ(x,ε)＜ +∞},由 fσ(x,ε)的定義可知

因此,有

由式(9)和(10)可得,

下面證明當ε→0,x→x?∈S時,

成立.

當ε/=0,ε→0,x→x?∈S時,由假設(shè)(3)可得

由式(7),(8),(9)和(10)可知,若令γ,β,N 分別滿足

則有

因此,有

定理得證.定理1表明本工作構(gòu)造的罰函數(shù)是二次連續(xù)可微函數(shù).

1.3 罰函數(shù)的精確性

下面證明罰問題(Pσ)的局部極小點序列(xk,εk)將會收斂到問題(P)的局部極小點.

引理1 令(xk,εk)是問題(Pσk)的一個局部極小點,且函數(shù)值fσk(xk,εk)有限,εk＞0.則(xk,εk)/∈Sε={(x,ε):gl(x)≤εγωl,l∈I}.

證明 若 (xk,εk)∈ Sε,由于 (xk,εk)是罰問題 (Pσk)的一個局部極小點且函數(shù)值fσk(xk,εk)為有限值,εk＞ 0,從而有

顯然,上式矛盾.因此有(xk,εk)/∈Sε.

定理2 設(shè)(xk,εk)是罰問題(Pσk)的局部極小點,函數(shù)值fσk(xk,εk)有限,εk＞0.如果k → +∞,(xk,εk)→ (x?,ε?)滿足假設(shè)條件(1)～ (3),那么有 ε?=0,x?∈ S.

證明由引理1可知,(xk,εk)/∈Sε,于是有?(x,ε)fσk(xk,εk)=0.因此,有

如果ε?/=0,則當σk→+∞,εk→ε?,xk→x?時,式(14)的第一項和第二項均為有限值,第三項則趨于無窮大,等式不可能成立,因此,εk→ε?=0.此外,由式(12)可知,當εk＞0時,

當σk→+∞,εk→ε?=0時,可以得到

下面證明I+=I0.假設(shè)I+/=I0,則存在l0∈I+I0,使得gl0(x?)＞0.由于在x?處滿足假設(shè)條件(2),因此存在p∈Rn,p/=0,使得?Tgl0(x?)p＜0,l0∈I+I0,由此可得

顯然上式與式(15)矛盾.因此,I+=I0,且x?∈S.

引理1和定理2表明局部極小點的序列{(xk,εk)}將收斂到問題(P)的可行解且具有有限的目標函數(shù)值,且這個可行解是問題(P)的局部極小點.

下面證明所構(gòu)造的罰函數(shù)fσ(x,e)是精確的.

定理3 假設(shè)定理2和條件(式(11))成立,則存在k0＞0,使得對任意的k≥k0＞0,都有εk→0,xk∈L(P)成立.

證明 假設(shè)結(jié)論不成立,則存在序列{(xk,εk)}的子序列{(xnk,εnk)},使得對任何k0＞0,都存在k′＞k0,且滿足εk/=0.根據(jù)定理2,有

簡化上式,可得

當k→+∞,由定理2可知,εk→ε?=0,xk→x?∈S.因為式(17)的第一項和第二項為有限值,而式(17)的第三項趨于∞,所以式(17)矛盾,因此子序列{(xnk,εnk)}不存在.故定理為真.

定理1和定理3表明所構(gòu)造的罰函數(shù)是光滑的和精確的.

2 罰函數(shù)算法及數(shù)值計算

2.1 罰函數(shù)算法

第1步 選擇適當?shù)?x0,ε0)∈Rn×[0,ε],ε＞0使得Δ(x0,ε0)＞0,σ0＞1足夠大,δ＞0足夠小,H0是一正定矩陣.令k:=0.

Hk是一正定矩陣.再令ασk滿足

第 4 步 令 (xk+1,εk+1)=(xk,εk)+ασkdk,σk+1=cσk,其中c＞1 為常數(shù).

第5步 令k:=k+1,返回第2步.

2.2 數(shù)值計算

此問題的最優(yōu)解和最優(yōu)值分別為=(0,1,2,?1)和f(x?)=?44.在本算例中,取x0=(0.5,1.5,1.5,?1.5),ε0=2.0,N=8,α=6,β=4,ω=0.05.運用Matlab 7.11軟件計算,結(jié)果如表1所示.

表1 算例1的數(shù)值計算結(jié)果Table 1 Numberical calculation results of Example 1

此問題的最優(yōu)解和最優(yōu)值分別為x?=(0.50,0.25)和f(x?)=0.25.在本算例中,取x0=(?1,0),ε0=1.0,N=4,α=4,β=4,ω=0.05.運用Matlab 7.11軟件計算,結(jié)果如表2所示.

表2 算例2的數(shù)值計算結(jié)果Table 2 Numberical calculation results of Example 2

算例1和算例2表明,通過選擇合適的參數(shù)可以得到原問題的近似最優(yōu)解,從而說明所設(shè)計的罰函數(shù)算法是可行的.

3 結(jié)束語

本工作針對非線性不等式約束優(yōu)化問題,通過加入一個變量構(gòu)造了一種新的指數(shù)型光滑精確罰函數(shù),并對罰函數(shù)的光滑性和精確性進行了討論.另外,還設(shè)計了求解原問題的精確罰函數(shù)算法.對于大規(guī)模的優(yōu)化問題,如何提出一種更好的算法,需要進一步的研究和討論.

[1]COURANT R.Variational methods for the solution of problems of equilibrium and vibrations[J].Bulletin of the American Mathematical Society,1943,49:1-23.

[2]CARROLL C W,FIACCO A V.The created response surface technique for optimizing nonlinear restrained systems[J].Operations Research,1961,9(2):169-184.

[3]EREMIN I I.The penalty method in convex programming[J].Cybernetics and Systems Analysis,1967,3(4):53-56.

[4]ZANGWILL W I.Nonlinear programming via penalty function[J].Management Science,1967,13(5):344-358.

[5]ANTCZAk T.Exact penalty function method for mathematical programming problem involving invex function[J].European Journal of Operational Research,2009,198(1):29-36.

[6]ZASLAVSkI A J.Existence of exact penalty for constrained optimization problems in Metric spaces[J].Set-Valued Analysis,2007,15(3):223-237.

[7]ZHENG F Y,ZHANG L S.New simple exact penalty function for constrained minimization[J].Applied Mathematics and Mechanics(English Edition),2012,33(7):951-962.

[8]ROSEBERG E.Globally convergent algorithms for convex programming with applications to geometric programming[J].Mathematics of Operations Research,1981,6(3):437-443.

[9]LASSERRE J B.A globally convergent algorithm for exact penalty functions[J].European Journal of Operational,1981,7(4):389-395.

[10]PINAR M C,ZENIOS S A.On smoothing exact penalty functions for convex constrained optimization[J].SIAM Journal on Optimization,1994,4(3):486-511.

[11]K¨OMER F.On the numerical realization of the exact penalty method for quadratic programming algorithm[J].European Journal of Operational Research,1990,46(3):404-409.

[12]張連生.全局精確罰函數(shù)的一個充要條件[J].數(shù)學年刊(A輯),1997,18(5):579-586.

[13]LUCIDI S.New results on a continuously diあerentiable exact penalty function[J].SIAM Journal on Optimization,1992,2(4):558-574.

[14]LI W,PENG J.Exact penalty functions for constrained minimization problems via regularized gap function for variational inequalities[J].Journal of Global Optimization,2007,37(1):85-94.

[15]MENG Z Q,DANG C Y,JIANG M,et al.Exactness and algorithm of an objective penalty function[J].Journal of Global Optimization,2013,56(2):691-711.

[16]HUYER W,NEUMAIER A.A new exact penalty function[J].SIAM Journal on Optimization,2003,13(4):1141-1158.