非線(xiàn)性不等式約束優(yōu)化問(wèn)題的指數(shù)型精確罰函數(shù)算法

楊 蓮, 姚奕榮

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

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

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

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

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

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

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

通過(guò)增加一個(gè)變量ε,問(wèn)題(P)等價(jià)于

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

考慮問(wèn)題(P)的罰問(wèn)題

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

若x∈/S且 ε＞0,Δ(x,ε)＜+∞,fσ(x,ε)=f(x)+(eΔ(x,ε)? 1)+ σεβ＞ f(x),則當(dāng) Sn是一個(gè)無(wú)界閉集合且f(x)在S上是下有界時(shí),顯然fσ(x,ε)在集合{(x,ε)∈R×[0,ε]:ε =0,x∈S或者ε＞0,Δ(x,ε)＜+∞}中是下有界的.當(dāng)S是一個(gè)緊集,則對(duì)于ε＞ 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→+∞.對(duì)固定罰參數(shù)σk,記對(duì)應(yīng)的罰問(wèn)題(Pσk)的最優(yōu)解為(xk,εk).為了證明罰函數(shù)的光滑性和精確性,作如下假設(shè).

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

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

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

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

成立,其中

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

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

因此,有

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

下面證明當(dāng)ε→0,x→x?∈S時(shí),

成立.

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

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

則有

因此,有

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

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

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

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

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

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

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

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

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

當(dāng)σk→+∞,εk→ε?=0時(shí),可以得到

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

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

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

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

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

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

簡(jiǎn)化上式,可得

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

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

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

2.1 罰函數(shù)算法

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

Hk是一正定矩陣.再令ασk滿(mǎn)足

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

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

2.2 數(shù)值計(jì)算

此問(wèn)題的最優(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.運(yùn)用Matlab 7.11軟件計(jì)算,結(jié)果如表1所示.

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

此問(wèn)題的最優(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.運(yùn)用Matlab 7.11軟件計(jì)算,結(jié)果如表2所示.

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

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

3 結(jié)束語(yǔ)

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

[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ù)的一個(gè)充要條件[J].數(shù)學(xué)年刊(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.