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

王學永

(重慶大學數學與統計學院，重慶 401331)

2002年，Fletcher和Leyffer［1］提出了濾子方法來求解非線性約束優化問題。該算法接受新的測試點的條件更加溫和，即一個測試點被濾子接受，當且僅當目標函數值或者違反約束度有充分的下降。自此，許多學者進行這方面的研究，并出現大量的成果［2－3］，但這種方法仍然會遇到馬洛托斯效應。罰函數方法在適當選取罰參數時會避免馬洛托斯效應。受這些思想的啟發，提出了一種低階罰函數濾子算法［4－5］，在溫和的條件下證明了算法的全局收斂性。

1 問題與算法描述

本文考慮如下非線性約束優化問題:

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

ii∈I∪E

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

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

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

其中Bk是對稱矩陣。

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

定義1 數對(h(x1)，p(x1))控制(h(x2)，p(x2))，當且僅當 h(x1)≤h(x2)，p(x1)≤p(x2)。

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

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

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

定義3

算法A

步驟0 給定

步驟1 計算

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

步驟3 若dk=0，則停;若QPk無解，進入算法B得到dk，令xk+1=xk+dk，轉步驟1。

步驟4 計算

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

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

步驟6 由BFGS公式調整Bk得到Bk+1。

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

算法B 可行性恢復階段算法

步驟0 V取

步驟1 若，則取，停止計算。

步驟2 計算

步驟3 若，令，轉步驟2;否則，轉步驟 1。

2 全局收斂性

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

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

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

H3:矩陣序列Bk有界。

H4:在算法B中，有

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

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

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

假設不成立，故原命題成立。

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

引理3 假設有無限多個點進入濾子集，則有

定理1 算法A產生的迭代點列 { xk}至少存在一個可行的穩定點。

證明由引理1知存在k0，當k＞k0時算法A不會進入算法B，令

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

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

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

假設x0是非穩定點，由 H3知存在 k＞0，k0∈N，使得任意 k＞k0，有

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

［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］陳純榮，孟開文，李聲杰.一個新的低階精確罰函數及其性質［J］.重慶大學學報:自然科學版，2007，30:253－256.