楊永亮，王福勝

(太原師范學(xué)院 數(shù)學(xué)系，山西 晉中 030619)

0 引言

半無限Minmax問題是一類重要的優(yōu)化問題,離散化方法是解決這類型問題的重要方法之一,基于離散化方法求解半無限Minmax問題可歸結(jié)為求解一系列具有如下形式的半無限Minimax離散化問題：

(1)

本文考慮固定離散水平q的問題(1),文獻(xiàn)[1]中提出一種求解Minmax問題的非單調(diào)SQP算法該算法采用文獻(xiàn)[2]提出的非單調(diào)技術(shù),但在求解步長過程中由于每次迭代都需要更新參數(shù)，隨著計(jì)算量的增加在求解過程中成為一種負(fù)擔(dān).Gu和Mo[3]克服這一缺陷提出了一種新的非單調(diào)搜索方式,其中的Ck是Ck-1和f(xk)的簡單凸組合而數(shù)值實(shí)驗(yàn)表明該算法具有高效性、魯棒性. Shi Z J和Shen J[4]提出一種新的大步長非精確線搜索技術(shù),有利于算法的快速收斂.受文獻(xiàn)[1-5]的啟發(fā),本文提出一種新的大步長非單調(diào)搜索準(zhǔn)則結(jié)合模松弛SQP算法的思想,提出一個(gè)求解問題(1)的大步長非單調(diào)SQP算法.

1 算法描述

Ω-(x)={ω∈Ω|g(x,ω)≤0},Ω+(x)={ω∈Ω|g(x,ω)>0},

構(gòu)造如下的QP子問題：

(2)

假設(shè)1.1 對于任意的y∈Y,ω∈Ω，函數(shù)f(·,y)和g(·,ω)均二階連續(xù)可微.

假設(shè)1.2 對于任意的x∈Rn，Mangasarian-Fromovitz約束規(guī)格成立(簡稱MFCQ成立),即存在d∈Rn使得xg(x,ω)Td<0，對于所有的ω∈Ω成立.

受文獻(xiàn)[2][4]的啟發(fā)，本文所用到的大步長非單調(diào)線性搜索準(zhǔn)則具體形式如下：

(3)

(4)

算法A

(H1)初始化.取適當(dāng)大正整數(shù)q,將區(qū)間[0,1]離散成有限集ω，選取參數(shù)r0,r,rω,θ∈(0,1),σk,η∈(0,1)選取初始點(diǎn)x0∈Rn，對稱正定矩陣H0∈Rn×n，并令k:=0.

(H3)求步長.由新的大步長非單調(diào)線搜索準(zhǔn)則(3)獲得步長αk.

2 收斂性分析

本節(jié)將分析算法A的全局收斂性,設(shè){xk}是算法產(chǎn)生的無窮點(diǎn)列,將證明{xk}的任一極限點(diǎn)x*都是問題(1)的一個(gè)穩(wěn)定點(diǎn),為此做如下假設(shè):

定理2.1假設(shè)2.1成立，αk由大步長非單調(diào)線搜索(3)產(chǎn)生，算法A生成一個(gè)無窮序列{xk}，且0

(5)

證明：K1={k|αk=sk},K2={k|αk

因此，

(6)

(7)

如果k∈K2,則αk

對上式的左端等式由中值定理可知，存在一個(gè)θk∈[0,1]，有

因此，

(8)

由假設(shè)2.1和式(8)根據(jù)Cauchy-Schawarz不等式可得：

αkL‖dk‖2/t≥‖xf(xk+θkαkdk/t)-xf(xk)‖.‖dk‖>

因此，αkL‖dk‖2/t>-(1-δ)xf(xk,y)Tdk,這表明

αk≥-[t(1-δ)/t]xf(xk,y)Tdk/‖dk‖2,k∈K2.

(9)

(10)

由式(3)和式(10)可得

-[δt(1-δ)(1-(1/2)γ)/L](xf(xk,y)Tdk/‖dk‖)2.

令ρ''=δt(1-δ)(1-(1/2)γ)/L,則有：

(11)

令ρ0=min(ρ′,ρ″),由式(7)和(11)可得

(12)

推論2.1如果假設(shè)1.1,1.2,2.1成立且滿足定理2.1中的條件,則有

(13)

進(jìn)而序列{xk}的任一極限點(diǎn)是問題(1)的穩(wěn)定點(diǎn),即算法A是全局收斂的.

證明：類似于定理3.1證明，如果k∈K1,式(7)可知

(14)

如果k∈K2,由式(3)可得

由假設(shè)2.1可得

(15)

如果存在一個(gè)常數(shù)β0≥0,和一個(gè)無限子集K3?K2則有：

-xf(xk,y)Tdk/‖dk‖≥β0,?k∈K3,

(16)

由式(15)和式(16)可得：

(17)

由式(8)可得

xf(xk+θkαkdk/t,y)Tdk≥δxf(x,y)Tdk,k∈K3,

(18)

其中θk∈[0,1]在定理2.1的證明中已經(jīng)定義，由Cauchy-Schawarz不等式和式(18)得

‖xf(xk+θkαkdk/t)-xf(xk)‖≥

≥-(1-δ)xf(xk,y)Tdk/‖dk‖,k∈K3.

(19)

由式(14)和式(19)且K1∪K2={1,2,3,…},可得式(14)成立.故算法A是全局收斂的.

3 數(shù)值實(shí)驗(yàn)

本節(jié)將對算法A的有效性進(jìn)行數(shù)值實(shí)驗(yàn)，在MATLAB2016a上編程序進(jìn)行數(shù)值實(shí)驗(yàn)，結(jié)果見表1.

其中P1,P2,P3三個(gè)算例來源于文獻(xiàn)[5],將算法與文獻(xiàn)[6]中的算法B進(jìn)行對比.參數(shù)如下：

q=100,r0=5,r=1,rω=0.01,θ=0.1,γ=1,δ=0.38,

該算法的終止準(zhǔn)則為|zk|≤10-4.

表1 數(shù)值結(jié)果

通過比較算法A和B,數(shù)值實(shí)驗(yàn)表明算法A的迭代次數(shù)較算法B有明顯減少,近似最優(yōu)值略有差距,在精度要求不太高的情況下大步長非單調(diào)技術(shù)對迭代次數(shù)的減少有一定的作用,可以認(rèn)為該算法是有效的.