基于積極集識(shí)別技術(shù)的半無(wú)限minimax問題非單調(diào)有限記憶SQP算法

楊永亮,王福勝,甄 娜

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

1 引言

半無(wú)限minimax優(yōu)化問題是一類非常重要的優(yōu)化問題,有著廣泛的應(yīng)用背景,例如工程設(shè)計(jì)、最優(yōu)控制、金融工程等領(lǐng)域的很多問題可以歸結(jié)為求解這類優(yōu)化問題,很多學(xué)者對(duì)此進(jìn)行了研究,獲得了豐富的研究成果(如文獻(xiàn)[1–12]).由于其特殊的結(jié)構(gòu),大多數(shù)傳統(tǒng)的方法不再適用,離散化方法是求解這類型問題的重要數(shù)值方法之一(如文獻(xiàn)[1–8]).半無(wú)限minimax問題具有如下形式

其中指標(biāo)集Y=[1,2,···m],f:Rn×Y→R,關(guān)于x,y都連續(xù)可微關(guān)于x連續(xù)可微g:Rn×[0,1]→R.為了方便起見,記問題(1.1)的可行集X和水平集l(x0,Ω)：

離散化方法的主要思想通過不斷離散連續(xù)變量的連續(xù)區(qū)間來逼近約束函數(shù),將求解半無(wú)限規(guī)劃問題轉(zhuǎn)化為求解其離散后的一系列有限約束優(yōu)化問題.將Ω離散成有限集：其中q反映了離散水平,q越大離散水平越好.定義Ω和ΩE之間的Hausdorff 距離為其中集列滿足條件

基于離散化方法求解原問題(1.1)可歸結(jié)為求解一系列具有如下形式的minimax離散化問題:

在一定的條件下,當(dāng)dist(ΩE,Ω)→0時(shí)式(1.3)的最優(yōu)解趨向于原問題(1.1)的最優(yōu)解.當(dāng)q非常大的時(shí)候,問題(1.3)的約束個(gè)數(shù)非常多,求解的成本也會(huì)很高,如何設(shè)計(jì)高效的算法求解問題(1.3)是解決半無(wú)限minimax問題的一個(gè)關(guān)鍵.文獻(xiàn)[5]提出了一種求解半無(wú)限規(guī)劃問題的超線性收斂的模松弛SQP算法,每次迭代只需要求解一個(gè)QP子問題就可以獲得搜索方向,遺憾的是上述算法要求初始點(diǎn)可行,而通常求解可行點(diǎn)的計(jì)算量很大.為了克服這一問題,文獻(xiàn)[6]提出了一種初始點(diǎn)任意的模松弛強(qiáng)次可行SQP算法.另外,在模松弛強(qiáng)次可行方向法中常利用線搜索來確定步長(zhǎng),傳統(tǒng)的線搜索方法都要求目標(biāo)函數(shù)值嚴(yán)格下降,其缺點(diǎn)是當(dāng)?shù)c(diǎn)“陷入很窄的峽谷時(shí)”,常常會(huì)導(dǎo)致小步長(zhǎng)或出現(xiàn)鋸齒現(xiàn)象,而采用非單調(diào)線搜索技術(shù)可以克服這些缺點(diǎn)(如文獻(xiàn)[13–15]).文獻(xiàn)[9]提出一種約束積極集識(shí)別技術(shù),可以對(duì)積極集進(jìn)行精確識(shí)別和估計(jì)來減少計(jì)算量.文獻(xiàn)[16]提出了一種求解無(wú)約束優(yōu)化問題的有限記憶BFGS修正規(guī)則(簡(jiǎn)稱L-BFGS),L-BFGS修正方法無(wú)需存貯近似海森矩陣Hk,從而大大減少了計(jì)算機(jī)存儲(chǔ)量,提高運(yùn)行效率,對(duì)大規(guī)模的優(yōu)化問題更有效.受文獻(xiàn)[5–9]啟發(fā),本文結(jié)合離散化方法和模松弛強(qiáng)次可行SQP方法,基于新型約束積極集識(shí)別技術(shù),采用非單調(diào)搜索和有限記憶L-BFGS修正方法更新Hk,提出了一種新的求解半無(wú)限minimax問題的非單調(diào)SQP算法.

2 算法描述

定義2.1點(diǎn)x稱為QP子問題(2.1)的穩(wěn)定點(diǎn)(KKT點(diǎn)),如果存在乘子向量λω,(ω∈ΩE);γy,(y∈Y)使得

以下給出了式(1.3)的拉格朗日函數(shù)L(x,λ,y),可行集XE和有效集Y(x)和ΩE(x):

由式(2.1),(2.2),定義如下的約束積極集識(shí)別函數(shù)

其中e=(1,1,···,1)T∈Rn,0＜δ＜1,由文[5]可得到問題(1.3)的兩個(gè)積極約束識(shí)別集

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

其中參數(shù)r0,r,rω(ω∈ΩE),θ都是正的常數(shù),σk是隨迭代調(diào)整的正參數(shù),Hk是的近似矩陣.我們引入一個(gè)重要的項(xiàng)-εkz2是為了確保當(dāng)dk→0有zk→0.以下引理說明QP子問題具有良好的性質(zhì).

假設(shè)2.1對(duì)于任意的y∈Y,ω∈Ω,函數(shù)f(·,y)和g(·,ω)在可行集上至少一階連續(xù)可微.

假設(shè)2.2對(duì)于任意的x∈XE,弱MFCQ成立,即存在d∈Rn使得?xg(x,ω)Td＜0,對(duì)于所有的ω∈Ω(x)成立.

引理2.1設(shè)假設(shè)2.1和假設(shè)2.2成立,xk∈X,Hk是對(duì)稱正定,若(zk,dk)是子問題(2.5)的最優(yōu)解,則

(2)zk=0?dk=0;

(3)zk=0?xk是問題(1.3)的一個(gè)穩(wěn)定點(diǎn);

(4)如果xkX則zk＜0;

(5)若dk0,則zk＜0,dk為問題(1.3)在xk處的可行下降方向.

證(1),(2)的證明類似于文獻(xiàn)[9](引理2.2,2.3)其余證明可參考文獻(xiàn)[7](引理2.1).

在文獻(xiàn)[13]中Zhang和Hager提出了新的非單調(diào)搜索技術(shù),受文獻(xiàn)[13]啟發(fā),本文對(duì)其進(jìn)行了改進(jìn),具體形式如下

由于采用離散化技術(shù)后,問題(1.3)的約束個(gè)數(shù)較多,導(dǎo)致算法求解的計(jì)算量增加,效率降低,如何降低計(jì)算量成為本文的關(guān)鍵.在SQP算法中通常用BFGS公式更新Hk,文[16]提出一種新的有限記憶L-BFGS更新規(guī)則,它最顯著的特點(diǎn)是不需要存儲(chǔ)Hk,對(duì)給定的Hk和非負(fù)整數(shù)m,利用前m步的信息對(duì)H0進(jìn)行修正m次得到Hk,僅存貯m+1個(gè)向量組就能計(jì)算Hk+1,從而降低了算法對(duì)計(jì)算量和存儲(chǔ)量的要求,本文將其應(yīng)用到算法設(shè)計(jì)中更新Hk.

算法A(求解離散化問題(1.3))

步1初始化.取適當(dāng)大正整數(shù)q,將區(qū)間[0,1]離散成有限集 Ωk選取參數(shù)r0,r,rω,θ∈(0,1),σk,η∈(0,1). 選取初始可行點(diǎn)x0∈XE,初始對(duì)稱正定矩陣H0,(λ0,γ0)T=(1,1,···,1)T∈Rm+q+1,并令k:=0.

步 2由 (2.3)式計(jì)算由 (2.4)式生成積極約束識(shí)別集和如果則xk是問題 (1.3)的一個(gè)穩(wěn)定點(diǎn),停止.否則進(jìn)入步3.

步3計(jì)算搜索方向.對(duì)當(dāng)前迭代點(diǎn)xk求解QP子問題(2.5)得到一個(gè)KKT點(diǎn)對(duì)(zk,dk).如果dk=0,則xk是問題(1.3)的一個(gè)穩(wěn)定點(diǎn),停止.否則進(jìn)入步4.

步4求搜索步長(zhǎng).由新的非單調(diào)搜索(2.6)獲得步長(zhǎng)αk.

步5令xk+1=xk+αdk,對(duì)稱正定矩陣kk+1可按文獻(xiàn)[16]中L-BFGS更新規(guī)則得到,σk+1由,?k≥1獲得,其中均為正常數(shù).置k=k+1,1返回步2.

對(duì)于半無(wú)限minimax問題的離散化方法,由文獻(xiàn)[7]可知,若下面的假設(shè)2.3成立,且存在x0∈X,使得緊,那么離散化問題(1.3)解序列的某個(gè)子列,Nk?N,k∈R收斂于原問題(1.1)的解.

假設(shè)2.3集列滿足條件(1.2),且成立.

下面給出求解原問題(1.1)的算法

算法Bq0∈N+{0},ε=10-4以及算法A的初始化參數(shù).

初始步給定參數(shù):{πi}i∈N+滿足 0＜ε＜πi+1＜πi,?i∈N+和

步1選取x0∈X離散集滿足令i=0.

步2利用算法A求解離散化問題(1.3),其最優(yōu)解記為.

步3如果則算法停止,否則,取更為精細(xì)的離散集使得和且滿足

步4令轉(zhuǎn)步2.

3 收斂性分析

本節(jié)對(duì)算法B進(jìn)行收斂性分析,首先給出如下的記號(hào)

對(duì)于算法B,定義如下的水平集

假設(shè)3.1水平集有界,且存在Lipschitz常數(shù)lgx和常數(shù)lgw使得下式成立.

假設(shè)3.2問題(1.1)在點(diǎn)時(shí)有線性無(wú)關(guān).

引理3.1[7]若為算法B生成的迭代點(diǎn)列,則序列存在聚點(diǎn).

引理3.2令是算法B生成的序列存在聚點(diǎn)x? 的一個(gè)收斂于的子列,則收斂,且

證先證

若Φ(x)=0,則以上的關(guān)系式顯然成立.若Φ(x)＞0,取ω∈X,則存在,滿足因而有

引理3.3令是算法B生成的序列的一個(gè)足.

證明可參考文獻(xiàn)[7]的引理6.1.4.

定理3.1若假設(shè)3.1,3.2成立,如果是由算法B生成的迭代點(diǎn)列,則存在的一個(gè)聚點(diǎn)是半無(wú)限minimax問題(1.1)的KKT點(diǎn),即算法B是收斂的.

證類似于文獻(xiàn)[8]中定理2.1的證明過程,由引理3.1可知序列存在聚點(diǎn),取其收斂于的子列,由算法B可知是問題(1.3)的KKT點(diǎn).因此,由Caratheodory定理,對(duì)于m=n+1,i∈Nk和有

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

本節(jié)將對(duì)算法B在MATLAB2016a上編程序進(jìn)行數(shù)值實(shí)驗(yàn).其中P1,P2,P3三個(gè)算例來源于文獻(xiàn)[4],三個(gè)問題如下

將算法與文獻(xiàn)[7]中的算法C(文獻(xiàn)[7]第二章2.6節(jié)的算法)進(jìn)行對(duì)比.參數(shù)選取q=100,r0=5,r=1,rω=0.01,θ=0.1,γ=1,δ=0.38,Lk=1,t=0.87,Lk=1,=0.01,σ1=100,ζ=0.5,H0=I.算法的終止準(zhǔn)則為|zk|＜≤10-4,其中Ni為迭代次數(shù),x0為初始點(diǎn),x*為算法終止時(shí)近似的最優(yōu)解,F(x*)為相應(yīng)的最優(yōu)值.P為所有迭代求解問題使用的約束個(gè)數(shù),數(shù)值結(jié)果見表1.

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

數(shù)值實(shí)驗(yàn)表明,算法B的迭代次數(shù)較算法C有明顯減少,近似最優(yōu)值略有差距,求解問題所使用的約束個(gè)數(shù)也有所減少.在精度要求不太高的情況下,算法B采用的積極約束集識(shí)別技術(shù)和非單調(diào)技術(shù)可以降低求解計(jì)算量和迭代次數(shù),因而本文所提出的算法是有效的.