劉美玲

(上海電機(jī)學(xué)院 數(shù)理教學(xué)部, 上海 201306)

Fletcher等[1]在2002年提出了濾子方法。該方法中的濾子可代替?zhèn)鹘y(tǒng)求解非線性規(guī)劃問題方法中的價(jià)值函數(shù)。由于其良好的數(shù)值計(jì)算結(jié)果使得近幾年涌現(xiàn)了很多對(duì)濾子方法的研究[2-13]。

本文在文獻(xiàn)[7]的基礎(chǔ)上提出了一類新的線搜索濾子方法，結(jié)合Armijo線搜索方法用來求解非線性規(guī)劃問題?；谛刨囉蚣夹g(shù)的算法必須要滿足所有約束條件的相容性，而基于線搜索技術(shù)的迭代方法則不需要。與文獻(xiàn)[7]的一個(gè)重要不同在于，本文將Lagrangian函數(shù)的梯度范數(shù)包含在約束違反度函數(shù)中，使得常規(guī)的濾子接受準(zhǔn)則時(shí)有一個(gè)不同的不可行測(cè)度。類似文獻(xiàn)[7]，本文的測(cè)度函數(shù)在不同的充分下降準(zhǔn)則間設(shè)置了一個(gè)新的轉(zhuǎn)換條件。

1 新的線搜索濾子方法結(jié)構(gòu)

1.1 算法機(jī)制

本文算法用于求解如下的非線性規(guī)劃問題:

(1)

式中，目標(biāo)函數(shù)f:Rn→R和約束函數(shù)c:Rn→Rm假設(shè)為連續(xù)可微的；E={i|i=1,2，…,m}。c(x)=(c1(x),c2(x),…,cm(x))，將f(x)、c(x)縮寫為f、c。

相應(yīng)于問題式(1)的Lagrangian函數(shù)為

L(x,λ)=f(x)+λTc(x)

(2)

式中，向量λ為Lagrange乘子。問題(1)的Karush-Kuhn-Tucker(KKT)條件為

(3)

對(duì)于一個(gè)給定的初始估計(jì)值x0，線搜索算法由迭代公式

xk+1=xk+αkdk

產(chǎn)生一系列迭代點(diǎn)xk作為問題(1)最優(yōu)解的估計(jì)值。其中，αk為步長；k為迭代指標(biāo)；搜索方向dk由迭代點(diǎn)xk對(duì)應(yīng)的KKT條件

(4)

計(jì)算一個(gè)搜索方向dk后，步長αk∈(0,1]由一個(gè)回溯線搜索程序計(jì)算得到。然后，用濾子方法作為新試探點(diǎn)的接受準(zhǔn)則。

定義1一個(gè)點(diǎn)對(duì)(Vk,fk)支配另一個(gè)點(diǎn)對(duì)(Vl,fl)，當(dāng)且僅當(dāng)條件Vk≤Vl和fk≤fl成立，其中，l為迭代次數(shù)。

定義2一個(gè)濾子是指一列互相不能支配的點(diǎn)對(duì)序列(Vl,fl)。

由定義2可知，如果一個(gè)試探點(diǎn)不被濾子中任何點(diǎn)支配，則其可被濾子接受。

然而，簡單的濾子準(zhǔn)則不能完全保證算法的全局收斂。因此，類似文獻(xiàn)[2]，本文對(duì)濾子設(shè)置如下斜邊界:

V(xk+1)≤βV(xk)

(5)

或

f(xk+1)≤f(xk)-γV(xk)

(6)

式中，β，γ為定常數(shù)，滿足β,γ∈(0,1)。在實(shí)際的算法執(zhí)行中，常數(shù)β趨近1，γ趨近0。但是，若接受準(zhǔn)則式(5)，可能總是使得試探點(diǎn)處的約束違反度充分下降，而目標(biāo)函數(shù)卻沒有足夠的下降量。為防止這種情況發(fā)生，引用文獻(xiàn)[7]中提到的下降技術(shù)作為另一個(gè)充分下降準(zhǔn)則，

(7)

式中,常數(shù)δ>0；e1≥1；e2>1。如果式(6)成立，用Armijo類條件

(8)

如果一個(gè)試探點(diǎn)xk在某個(gè)步長能被式(8)接受，稱xk為一個(gè)f-型迭代步，相應(yīng)的步長αk稱作f-型步長。如果一個(gè)試探點(diǎn)xk能被式(5)接受，稱xk為一個(gè)V-型迭代點(diǎn)。

1.2 算法分析

本文定義濾子為一個(gè)集合Fk，包含所有被式(5)、(6)接受的迭代點(diǎn)。

如果線性系統(tǒng)式(4)是不相容的，算法轉(zhuǎn)到一個(gè)可行恢復(fù)項(xiàng)。在可行恢復(fù)項(xiàng)中，減少約束違反度直至找到一個(gè)新的迭代點(diǎn)xk+1滿足式(4)且可被當(dāng)前濾子接受。為探測(cè)可行恢復(fù)項(xiàng)的轉(zhuǎn)換條件，考慮減少α，并定義最小步長為

αk,min=

如果試探點(diǎn)步長αk<αk,min，則算法轉(zhuǎn)向可行恢復(fù)項(xiàng)。

一旦找到一個(gè)可行方向，算法則繼續(xù)執(zhí)行標(biāo)準(zhǔn)算法。

可行恢復(fù)項(xiàng)可能收斂到約束違反度的一個(gè)非零局部最小點(diǎn)，此時(shí)，說明算法失敗。本文不特別指定可行恢復(fù)算法，任何可以處理帶等式和不等式約束的非線性代數(shù)系統(tǒng)的算法都可以用來執(zhí)行可行恢復(fù)項(xiàng)。

1.3 算法

整體算法結(jié)構(gòu)如下:

步驟1給定初始點(diǎn)x0，常數(shù)Vmax=max{104,1.2V(x0)}，β,γ∈(0,1)，δ>0，e1≥1,e2>1，τ∈(0,1)。

步驟2初始化F0={(Vmax,f(x0))}，迭代數(shù)k←0。

步驟3對(duì)k=0,1,2,…，若xk滿足式(3),算法停止。

步驟4根據(jù)式(4)計(jì)算搜索方向dk。若線性系統(tǒng)式(4)是不相容的，轉(zhuǎn)至步驟7。

步驟5設(shè)置α0=1，計(jì)算αk,min。

(1) 若αk<αk，min，轉(zhuǎn)至步驟7；否則，計(jì)算新的試探點(diǎn)xk+1=xk+αkdk。

(2) 若式(8)成立，接受當(dāng)前試探步，轉(zhuǎn)至步驟6；否則，設(shè)置xk=xk+1，轉(zhuǎn)至(4)。

(3) 若沒有合適的αk使式(8)成立，若xk+1能被當(dāng)前濾子接受，增廣濾子Fk+1=Fk∪{(V(xk+1),f(xk+1))}，轉(zhuǎn)至步驟6；否則，設(shè)置xk=xk+1，返回至(1)。

(4) 計(jì)算αk+1=ταk，返回至(1)。

步驟6更新迭代數(shù)k←k+1，返回至步驟4。

步驟7可行恢復(fù)項(xiàng)。若找到一個(gè)新的迭代點(diǎn)xk+1可被當(dāng)前濾子接受，增廣濾子Fk+1=Fk∪{(V(xk+1),f(xk+1))}，返回至步驟6，繼續(xù)執(zhí)行標(biāo)準(zhǔn)算法；否則，算法停止。

另外，為了防止算法產(chǎn)生一系列f-型迭代步，且Vk→∞，給約束違反度V設(shè)置一個(gè)上界Vmax。

2 全局收斂

首先陳述必要的假設(shè)。

假設(shè)1所有迭代點(diǎn)都屬于Rn中的一個(gè)非空有界閉集S。

假設(shè)2函數(shù)f,c在一個(gè)包含S的開集上兩次連續(xù)可微。

為陳述方便，定義集合J={i|xk可被濾子接受}。另外，有時(shí)需要用某種修正方法修正Wk以保持其正定，如用阻尼BFGS公式。

由假設(shè)1～3，不失一般性，可以得到

(9)

式中，Md，Mm，MW，mW均為常數(shù)。

證明由式(4)和(9)可得

(10)

引理2若假設(shè)1～3成立，則

證明考慮兩種情況。

(1) 濾子被增廣了有限次。假設(shè)對(duì)于所有的迭代{xk}k>K濾子都未被增廣。對(duì)于k>K，其中，K為充分大的整數(shù)，若f-型迭代步條件成立，由式(8)得到

(11)

對(duì)k

(12)

式中，c1=max{-γ,-ηδ1/e1α-1/e1}；t為整數(shù)。

既然當(dāng)k→∞時(shí)，f(xK+t)是下有界的，則式(12)不等式右邊的級(jí)數(shù)是有界的，即引理結(jié)論成立。

(2) 濾子被增廣了無限次。既然濾子被增廣了無限次，則對(duì)于k∈J，若V(xk+1)≤βV(xk)，則V(xk)→0；若

f(xk+1)≤f(xk)-γV(xk)

則由第1種情況證明也可得V(xk)→0。

(13)

式中，y1為線段xks到xks+αdks上的某點(diǎn)。即引理結(jié)論成立。

引理4若假設(shè)1～3成立，濾子被增廣了有限次，則

V(xks)≤ε

及

(14)

(V(xks+1),f(xks+1))?Fks

(15)

或

(16)

設(shè)Vmin=min{Vk|(Vk,fk)∈Fk}，由Lagrange定理可得,對(duì)某個(gè)常數(shù)cV有

V(xks)+cVαksMd

(17)

證明算法機(jī)制確保了第1個(gè)迭代點(diǎn)可被濾子接受。然后，假設(shè)(V(xk),f(xk))可被當(dāng)前濾子接受，即

(V(xl),f(xl))∈Fk,l

若

其中，cf為類似于引理4中常數(shù)cV的某個(gè)常數(shù)，有

(18)

即

故由式(13)得

f(xks+αdks)≤f(xks)

(19)

類似地，若

則

(20)

f(xks+1)=f(xks+αdks)≤
f(xks)≤f(xl)-γV(xl)

(21)

及

V(xks+1)=

V(xks+αdks)≤V(xks)≤βV(xl)

(22)

由式(21)、(22)可推得結(jié)論。

證明由引理1、2，存在常數(shù)ε2>0，使得

對(duì)所有的ks>K成立。

若V(xks)=0，必存在f-型迭代步。對(duì)非f-型迭代步且滿足V(xks)>0，若

則式(7)、(8)成立，則由引理3、5的證明可得既然由αk,min的定義知α>ταk>ταk,min，算法在這些試探步不會(huì)轉(zhuǎn)換到可行恢復(fù)項(xiàng)。即引理結(jié)論成立。

(23)

基于以上引理結(jié)論，可以給出主要的全局收斂結(jié)果。

定理7若假設(shè)1～3成立，則

(24)

(25)

即存在一個(gè){xk}的極限點(diǎn)x*是問題(1)的KKT點(diǎn)。

證明式(24)直接由引理2可得。

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

本文給出本文算法的數(shù)值計(jì)算結(jié)果。算例均取自CUTE問題集[14],可在NEOS網(wǎng)站免費(fèi)獲取。程序代碼由Matlab編成。算法執(zhí)行中設(shè)置如下:

(1) 參數(shù)設(shè)置β=0.99,γ=10-4，終止精度ε=10-6，η=0.4；

(2) 最優(yōu)冗余定義為

即當(dāng)r<ε時(shí)，算法終止。

數(shù)值試驗(yàn)的結(jié)果如表1所示。為了比較，也給出三維濾子線搜索算法[15]的計(jì)算結(jié)果。其中，“問題”為所求解的CUTE問題名稱；N1為求解問題的變量個(gè)數(shù)；N2為所有約束的個(gè)數(shù)；N2_N1為非線性約束的個(gè)數(shù)；k為算法的迭代次數(shù)；NIT2為三維濾子算法的迭代次數(shù)。

表1 算例計(jì)算結(jié)果

由表1可知，本文所提算法的計(jì)算效果良好。從數(shù)值計(jì)算結(jié)果看，該算法比較穩(wěn)定；且在有限的計(jì)算試驗(yàn)下，該算法的計(jì)算結(jié)果好于三維線搜索濾子算法。

4 結(jié) 語

本文介紹了一類線搜索濾子算法求解一般的非線性規(guī)劃問題。算法有很多較好的性質(zhì)。新構(gòu)造的不可行測(cè)度函數(shù)，使濾子方法在不可行性測(cè)度方面更加靈活，并改善了收斂速度。數(shù)值試驗(yàn)也顯示了算法的有效性。濾子方法已用于大規(guī)模問題[1,11]，如何提高在大規(guī)模問題中的效率是今后研究的方向之一。

參考文獻(xiàn):

[1] Fletcher R，Leyffer S.Nonlinear programming without a penalty function[J].Mathematical Programming，2002，91(2): 239-269.

[2] Fletcher R，Gould N I M，Leyffer 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.

[3] Fletcher R，Leyffer S，Toint Ph L.On the global convergence of a filter-SQP algorithm[J].SIAM Journal on Optimization，2002，13(1): 44-59.

[4] Ulbrich S.On the superlinear local convergence of a filter-SQP method[J].Mathematical Programming，2004，100(1): 217-245.

[5] Yang Zhenghao，Sun Wenyu，Qi Liqun.Global convergence of a filter-trust-region algorithm for solving nonsmooth equations[J].International Journal of Computer Mathematics，2010，87(4): 788-796.

[6] Wang Zhujun，Zhu Detong.A reduced Hessian algorithm with line search filter method for nonlinear programming[J].Applied Mathematics and Computation，2011，217(19): 7679-7691.

[7] Gomez W，Ramirez H.A filter algorithm for nonlinear semidefinite programming[J].Computational and Applied Mathematics，2010，29(2): 297-328.

[8] Liu Xinwei，Yuan Yaxiang.A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization[J].SIAM Journal on Optimization，2011，21(2): 545-571.

[9] W?chter A，Biegler L T.Line search filter methods for nonlinear programming: Local convergence[J].SIAM Journal on Optimization，2005，16(1): 32-48.

[10] W?chter A，Biegler L T. Line search filter methods for nonlinear programming: Motivation and global convergence[J].SIAM Journal on Optimization，2005，16(1): 1-31.

[11] W?chter A，Biegler L T.On the implementation of an interiorpoint filter line-search algorithm for large-scale nonlinear programming[J].Mathematical Programming，2006，106(1)： 25-57.

[12] Gould N I M，Sainvitu C，Toint Ph L.A filter-trust-region method for unconstrained optimization[J].SIAM Journal on Optimization，2006，16(2): 341-357.

[13] Su Ke，Pu Dingguo.A nonmonotone filter trust region method for nonlinear constrained optimization[J].Journal of Computational and Applied Mathematics，2009，223(1): 230-239.

[14] Bongartz I，Conn A R，Gould N I M，et al.CUTE: Constrained and unconstrained testing environment[J].ACM Transactions on Mathematical Software，1995，21(1): 123-160.

[15] Shen Chungen，Xue Wenjuan，Pu Dingguo.Global convergence of a tri-dimensional filter SQP algorithm based on the line search method[J].Applied Numerical Mathematics，2009，59(2): 235-250.