基于積極集識別技術的半無限minimax問題非單調有限記憶SQP算法

楊永亮,王福勝,甄 娜

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

1 引言

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

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

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

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

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

2 算法描述

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

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

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

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

構造如下的QP子問題

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

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

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

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

(2)zk=0?dk=0;

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

(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提出了新的非單調搜索技術,受文獻[13]啟發,本文對其進行了改進,具體形式如下

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

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

步1初始化.取適當大正整數q,將區間[0,1]離散成有限集 Ωk選取參數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)的一個穩定點,停止.否則進入步3.

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

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

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

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

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

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

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

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

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

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

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

步4令轉步2.

3 收斂性分析

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

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

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

假設3.2問題(1.1)在點時有線性無關.

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

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

證先證

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

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

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

定理3.1若假設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 數值實驗

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

將算法與文獻[7]中的算法C(文獻[7]第二章2.6節的算法)進行對比.參數選取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為迭代次數,x0為初始點,x*為算法終止時近似的最優解,F(x*)為相應的最優值.P為所有迭代求解問題使用的約束個數,數值結果見表1.

表1 數值結果

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