非線性等式優(yōu)化的一種非單調(diào)SQP濾子算法

王 珺，王希云

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院 山西 太原 030024)

非線性等式優(yōu)化的一種非單調(diào)SQP濾子算法

王 珺，王希云

(太原科技大學(xué) 應(yīng)用科學(xué)學(xué)院 山西 太原 030024)

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

非線性等式約束； 信賴域； SQP； 濾子； 非單調(diào)

0 引言

非線性等式約束優(yōu)化問題如下

(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]提出濾子的概念并將其應(yīng)用于信賴域SQP方法后，信賴域SQP濾子方法就成為解決非線性規(guī)劃問題的一種重要方法.但是，信賴域SQP濾子方法也會(huì)遇到Maratos效應(yīng).為避免Marotos效應(yīng)，通常使用二階校正步技術(shù)及非單調(diào)技術(shù).

這種方法是有效的，但也存在不足，由于取當(dāng)前迭代點(diǎn)及其前m(k)個(gè)點(diǎn)中函數(shù)值最大的fl(k)作為參考函數(shù)值，可能會(huì)在某些步中丟失更優(yōu)點(diǎn).

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

1 算法

(1)

(2)

針對(duì)文[2，4-5]中算法的不足，本文采用非單調(diào)濾子形式：

(3)

(4)

當(dāng)且僅當(dāng)(3)式或(4)式成立時(shí)，當(dāng)前迭代點(diǎn)xk+1可被過濾接受.

此外，我們定義如下參數(shù)：

算法1如下：

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

(h0,f0)

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

Step3測(cè)試試探步是否被算法接受.

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

Step5取Δk∈[r0Δk,r1Δk]≥Δmin，轉(zhuǎn)step2.

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

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

說明Hk的調(diào)節(jié)見文獻(xiàn)[6]，Wk的計(jì)算見文獻(xiàn)[7].

本文假設(shè)如下：

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

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

A3對(duì)任意的k，Hk一致有界；

2 算法的適定性

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

定理1若假設(shè)成立，則算法是適定的.即算法中step1和step3、step5間的內(nèi)循環(huán)會(huì)有限終止.

證明假設(shè)在迭代點(diǎn)xk處算法1中step1和step3、step5間的內(nèi)循環(huán)不有限終止，則當(dāng)k→∞時(shí)，Δk→0.下面分兩種情況考慮.

(5)

由式(5)可得，當(dāng)Δk→0時(shí)有

(6)

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

3 算法的收斂性

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

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

證畢.

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

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

4 數(shù)值試驗(yàn)

試驗(yàn)使用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.

數(shù)值試驗(yàn)結(jié)果見表1.數(shù)值試驗(yàn)表明，本文算法是有效的.

表1 數(shù)值試驗(yàn)結(jié)果

[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ì)昌,汪壽陽,薛毅,等.等式約束的一種降維運(yùn)算的信賴域方法[J].中國管理科學(xué), 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

山西省自然科學(xué)基金資助項(xiàng)目，編號(hào)2008011013.

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