王學(xué)永

(重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，重慶 401331)

2002年，F(xiàn)letcher和Leyffer［1］提出了濾子方法來(lái)求解非線性約束優(yōu)化問題。該算法接受新的測(cè)試點(diǎn)的條件更加溫和，即一個(gè)測(cè)試點(diǎn)被濾子接受，當(dāng)且僅當(dāng)目標(biāo)函數(shù)值或者違反約束度有充分的下降。自此，許多學(xué)者進(jìn)行這方面的研究，并出現(xiàn)大量的成果［2－3］，但這種方法仍然會(huì)遇到馬洛托斯效應(yīng)。罰函數(shù)方法在適當(dāng)選取罰參數(shù)時(shí)會(huì)避免馬洛托斯效應(yīng)。受這些思想的啟發(fā)，提出了一種低階罰函數(shù)濾子算法［4－5］，在溫和的條件下證明了算法的全局收斂性。

1 問題與算法描述

本文考慮如下非線性約束優(yōu)化問題:

其中 f(x):Rn→R，c(x)=(c(x)):Rn→Rm是連續(xù)可微函數(shù)。

ii∈I∪E

記當(dāng)前迭代點(diǎn)是xk，定義一種低階罰函數(shù)c－(x)=(ci－(x))i∈I∪E，其中令

顯然在xk處，若第i個(gè)約束函數(shù)滿足，則有ci－(x)=0。本研究利用這種低階罰函數(shù)定義違反約束度函數(shù)為h(x)=‖c(x)‖，同時(shí)定義p(x)=f(x)+δ‖c－(x)‖。

在信賴域方法中給定測(cè)試點(diǎn)xk，信賴域半徑ρ≥0，通過求解如下二次規(guī)劃問題得到步長(zhǎng)dk:

其中Bk是對(duì)稱矩陣。

在本文中若子問題QPk相容通過上述方法可求得下一迭代點(diǎn)xk+1;若子問題QPk不相容，則通過可行性恢復(fù)階段算法(算法B)得到新的迭代點(diǎn)xk+1。

定義1 數(shù)對(duì)(h(x1)，p(x1))控制(h(x2)，p(x2))，當(dāng)且僅當(dāng) h(x1)≤h(x2)，p(x1)≤p(x2)。

定義2 濾子是一列不能相互控制的數(shù)對(duì)。

注1:在濾子方法中，一個(gè)點(diǎn)x被接受當(dāng)且僅當(dāng)它被當(dāng)前迭代點(diǎn)xk和當(dāng)前濾子中任何其他迭代點(diǎn)接受。本文中給定α∈(0，1)，若p(x)≤p(y)－αh ( x)或h(x)≤(1－α)h(y)，則稱x能被 y接受。若x被濾子中所有數(shù)對(duì)接受，則稱x被濾子接受。

本文用如下方法調(diào)整濾子集:Fk+1=Fk∪{k+1}Dk+1。

定義3

算法A

步驟0 給定

步驟1 計(jì)算

步驟2 求解QPk得到步長(zhǎng)dk。

步驟3 若dk=0，則停;若QPk無(wú)解，進(jìn)入算法B得到dk，令xk+1=xk+dk，轉(zhuǎn)步驟1。

步驟4 計(jì)算

若 rk≤η，令，轉(zhuǎn)步驟 2;若 xk+dk∈Fk令轉(zhuǎn)步驟5;若 h( x )≥kmin{ η，ρk}，轉(zhuǎn)步驟6;否則用算法B得到新的迭代點(diǎn)xk+1∈Fk，轉(zhuǎn)步驟2。

步驟5 取xk+1=xk+dk，移除被(h(xk+1)，p(xk+1))控制的點(diǎn)。

步驟6 由BFGS公式調(diào)整Bk得到Bk+1。

步驟7 若h( xk)≤min{ η，ρk}，轉(zhuǎn)步驟1;否則應(yīng)用算法B產(chǎn)生xk+1被濾子接受，轉(zhuǎn)步驟2。

算法B 可行性恢復(fù)階段算法

步驟0 V取

步驟1 若，則取，停止計(jì)算。

步驟2 計(jì)算

步驟3 若，令，轉(zhuǎn)步驟2;否則，轉(zhuǎn)步驟 1。

2 全局收斂性

為了討論算法的全局收斂性，本文作如下假設(shè):

H1:f( x )，( ci(x ))i∈E∪I是二次連續(xù)可微函數(shù)。

H2:算法A產(chǎn)生的點(diǎn)列 { xk}?X，其中X?Rn是非空凸集。

H3:矩陣序列Bk有界。

H4:在算法B中，有

引理1 可行性恢復(fù)階段算法B有限步終止。

證明由算法B框架知，若算法B有限步終止，則有

假設(shè)命題不成立，則存在 ε ＞0，j0∈R，對(duì)任意 j＞j0，有

假設(shè)不成立，故原命題成立。

引理2 算法產(chǎn)生的任意迭代點(diǎn)xk+1( ≠ xk)被濾子集Fk接受。

引理3 假設(shè)有無(wú)限多個(gè)點(diǎn)進(jìn)入濾子集，則有

定理1 算法A產(chǎn)生的迭代點(diǎn)列 { xk}至少存在一個(gè)可行的穩(wěn)定點(diǎn)。

證明由引理1知存在k0，當(dāng)k＞k0時(shí)算法A不會(huì)進(jìn)入算法B，令

若K2是無(wú)限集，則對(duì)任意 xk∈K2及 x0∈X，有若 K2是有限集，則存在 k0∈N，任意k＞k0，有

即{ p ( xk)}是單調(diào)下降序列，故p( xk+1)－p( xk)→0。

由引理3知 { xk}至少存在一個(gè)可行的聚點(diǎn)，設(shè)為x0。

假設(shè)x0是非穩(wěn)定點(diǎn)，由 H3知存在 k＞0，k0∈N，使得任意 k＞k0，有

由h( xk)的定義知p( xk)－p( xk+dk)＞0。這與p( xk+1)－p( xk)→0矛盾，假設(shè)不成立。故原命題得證。

［1］FLETCHER R，LEYFFER S.Nonlinear programming without a penalty function［J］.Mathematical Programming，2002 ，91:239－269.

［2］NIE P Y，MA C F.A trust region filter method for general non-linear programming［J］.Applied Mathematics and Computation，2006，172:1000 －1017.

［3］Nie P Y.Sequential penalty quadratic programming filter methods for non-linear programming［J］.Nonlinear Analysis，2007，8:118－129.

［4］Meng K W，Li S J，Yang X Q.A robust SQP method based on a smoothing lower order penalty function［J］.Optimization，2009，58:23－38.

［5］陳純榮，孟開文，李聲杰.一個(gè)新的低階精確罰函數(shù)及其性質(zhì)［J］.重慶大學(xué)學(xué)報(bào):自然科學(xué)版，2007，30:253－256.