基于积极集识别技术的半无限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采用的积极约束集识别技术和非单调技术可以降低求解计算量和迭代次数,因而本文所提出的算法是有效的.