非線性等式優化的一種非單調SQP濾子算法

王 珺，王希云

(太原科技大學 應用科學學院 山西 太原 030024)

非線性等式優化的一種非單調SQP濾子算法

王 珺，王希云

(太原科技大學 應用科學學院 山西 太原 030024)

SQP濾子方法是解非線性規劃的一種較為有效的方法，但是濾子方法也會遇到Maratos效應.采用非單調技術來避免Maratos效應，并采用降維的Byrd和Omojokun方法來計算試探步.在一定條件下，給出了全局收斂性證明，數值試驗表明該算法有效.

非線性等式約束； 信賴域； SQP； 濾子； 非單調

0 引言

非線性等式約束優化問題如下

(P)：minf(x) s.t.ci(x)=0,i∈I={1,2,…,m},

其中，x∈Rn,f：Rn→R,ci：Rn→R,c(x)=(c1(x),c2(x),…,cm(x))T.

文[1]提出濾子的概念并將其應用于信賴域SQP方法后，信賴域SQP濾子方法就成為解決非線性規劃問題的一種重要方法.但是，信賴域SQP濾子方法也會遇到Maratos效應.為避免Marotos效應，通常使用二階校正步技術及非單調技術.

這種方法是有效的，但也存在不足，由于取當前迭代點及其前m(k)個點中函數值最大的fl(k)作為參考函數值，可能會在某些步中丟失更優點.

本文對上述算法進行了改進，提出一種非單調格式，并給出了求解非線性等式約束問題的非單調信賴域SQP濾子算法.對算法的適定性和全局收斂性進行了論證，并通過數值試驗表明了算法的有效性.

1 算法

(1)

(2)

針對文[2，4-5]中算法的不足，本文采用非單調濾子形式：

(3)

(4)

當且僅當(3)式或(4)式成立時，當前迭代點xk+1可被過濾接受.

此外，我們定義如下參數：

算法1如下：

step0初始化.給出初始點x0∈Rn，初始信賴域半徑Δ0≥Δmin>0，初始對稱矩陣H0∈Rn×n.初始化濾子F={

(h0,f0)

}，令k=0，m(k)=0,0<γ<β<1，0<λ≤1，0

Step3測試試探步是否被算法接受.

計算h(xk+dk)，f(xk+dk)，如果xk+dk被濾子接受，轉step4,否則轉step5.

Step5取Δk∈[r0Δk,r1Δk]≥Δmin，轉step2.

Step6令xk+1=xk+dk，更新濾子.

令Δk+1∈[Δk,r2Δk]≥Δmin，更新Hk，m(k+1)=min{m(k)+1,M}，k=k+1，轉Step1.

說明Hk的調節見文獻[6]，Wk的計算見文獻[7].

本文假設如下：

A1對任意的k，xk和dk均屬于有界閉凸集子集S?Rn；

A2目標函數f(x)和約束函數c(x)(i∈I={1,2,…,m})在S內二次連續可微；

A3對任意的k，Hk一致有界；

2 算法的適定性

引理1[2]在假設條件成立時，存在不依賴于迭代的正常數α2，α3，使

定理1若假設成立，則算法是適定的.即算法中step1和step3、step5間的內循環會有限終止.

證明假設在迭代點xk處算法1中step1和step3、step5間的內循環不有限終止，則當k→∞時，Δk→0.下面分兩種情況考慮.

(5)

由式(5)可得，當Δk→0時有

(6)

由式(6)及過濾的定義可知，xk+dk被過濾接受.所以，當Δk→0時，算法1中step1和step3間的內循環終止.

3 算法的收斂性

證明若算法并不有限終止，則說明無窮的迭代點列{xk}被過濾接受.根據過濾的定義我們分以下兩個部分來證明：

下面僅證明第(i)部分,關于第(ii)部分的證明可參考文獻[2].記hk+1=h(xk+dk)，分2種情形證明.

證畢.

由引理2、引理3可得定理2.

定理2若算法1產生的點列{xk}是一個無窮點列，那么{xk}的任一聚點是問題(P)的一個KKT點.

4 數值試驗

試驗使用matlab軟件來求解.取誤差為10-4，并取各初值為：

H0=I∈Rn×n，β=0.98，γ=0.02，ρ=0.5，α=δ=0.1，r0=0.1，r1=0.5，r2=2，Δmin=10-6，Δ0=1.

數值試驗結果見表1.數值試驗表明，本文算法是有效的.

表1 數值試驗結果

[1] Fletcher R, Leyfer S.Nonlinear programming without a penalty function[J]. Mathematics and Statistics,2002,91(2):239-269.

[2] Ke S,Dingguo P.A nonmonotone filter trust region method for nonlinear constrained optimization[J]. Journal of Computational and Applied Mathematics,2009,223(1):230-239.

[3] 董紀昌,汪壽陽,薛毅,等.等式約束的一種降維運算的信賴域方法[J].中國管理科學, 2001, 9(6):26-30.

[4] Fletcher R, Leyfer S, Toint P L.On the global convergence of a trust-region SQP-filter algorithm[J]. SIAM Journal on Optimization,2002,13(1):44-59.

[5] Fletcher R, Gould N I M, Leyfer S, et al. Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming[J].SIAM Journal on Optimization,2002,13(3):635-659.

[6] Ulbrich S.On the superlinear local convergence of a filter-SQP method[J]. Math Program:Ser B, 2004,100(1):217-245.

[7] Ulbrich M, Ulbrich S. Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function[J].Math Program:Ser B, 2003, 95(1):103-135.

NonmonotoneSQPFilterMethodforNonlinearConstrainedEqualityOptimization

WANG Jun, WANG Xi-yun

(SchoolofAppliedSciences,TaiyuanUniversityofScienceandTechnology,Taiyuan030024,China)

Nonlinear constrained optimization was efficient and robust solved by the SQP filter approach.But,the so-called Maratos effect was suffered.A non-monotone trust region method was presented. The step was computed by the Byrd and Omojokun scheme.Global convergence was proved under certain conditions.

nonlinear equality constrained optimization; trust-region; SQP; filter; nonmonotone

O 221.2

A

1671-6841(2011)03-0062-04

2010-02-08

山西省自然科學基金資助項目，編號2008011013.

王珺(1984-)，女，碩士研究生，主要從事最優化理論研究，E-mail：simple_cloud@126.com.