楊永亮,王福勝,甄 娜

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

1 引言

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

其中指標集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ù),將求解半無限規(guī)劃問題轉(zhuǎn)化為求解其離散后的一系列有限約束優(yōu)化問題.將Ω離散成有限集：其中q反映了離散水平,q越大離散水平越好.定義Ω和ΩE之間的Hausdorff 距離為其中集列滿足條件

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

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

2 算法描述

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

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

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

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

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

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

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

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

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

(2)zk=0?dk=0;

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

(4)如果xkX則zk＜0;

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

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

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

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

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

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

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

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

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

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

對于半無限minimax問題的離散化方法,由文獻[7]可知,若下面的假設(shè)2.3成立,且存在x0∈X,使得緊,那么離散化問題(1.3)解序列的某個子列,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如果則算法停止,否則,取更為精細的離散集使得和且滿足

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

3 收斂性分析

本節(jié)對算法B進行收斂性分析,首先給出如下的記號

對于算法B,定義如下的水平集

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

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

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

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

證先證

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

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

證明可參考文獻[7]的引理6.1.4.

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

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

4 數(shù)值實驗

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

將算法與文獻[7]中的算法C(文獻[7]第二章2.6節(jié)的算法)進行對比.參數(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.算法的終止準則為|zk|＜≤10-4,其中Ni為迭代次數(shù),x0為初始點,x*為算法終止時近似的最優(yōu)解,F(x*)為相應(yīng)的最優(yōu)值.P為所有迭代求解問題使用的約束個數(shù),數(shù)值結(jié)果見表1.

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

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