一個低階濾子算法及收斂性

王學(xué)永

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

2002年，F(xiàn)letcher和Leyffer［1］提出了濾子方法來求解非線性約束優(yōu)化問題。該算法接受新的測試點的條件更加溫和，即一個測試點被濾子接受，當(dāng)且僅當(dāng)目標(biāo)函數(shù)值或者違反約束度有充分的下降。自此，許多學(xué)者進(jìn)行這方面的研究，并出現(xiàn)大量的成果［2－3］，但這種方法仍然會遇到馬洛托斯效應(yīng)。罰函數(shù)方法在適當(dāng)選取罰參數(shù)時會避免馬洛托斯效應(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)前迭代點是xk，定義一種低階罰函數(shù)c－(x)=(ci－(x))i∈I∪E，其中令

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

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

其中Bk是對稱矩陣。

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

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

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

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

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

定義3

算法A

步驟0 給定

步驟1 計算

步驟2 求解QPk得到步長dk。

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

步驟4 計算

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

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

步驟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 若，則取，停止計算。

步驟2 計算

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

2 全局收斂性

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

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

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

H3:矩陣序列Bk有界。

H4:在算法B中，有

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

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

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

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

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

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

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

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

若K2是無限集，則對任意 xk∈K2及 x0∈X，有若 K2是有限集，則存在 k0∈N，任意k＞k0，有

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

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

假設(shè)x0是非穩(wě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］陳純榮，孟開文，李聲杰.一個新的低階精確罰函數(shù)及其性質(zhì)［J］.重慶大學(xué)學(xué)報:自然科學(xué)版，2007，30:253－256.