非内点同伦方法求解双层规划问题

范晓娜,陈 燕,闫庆伦

(南京邮电大学理学院,江苏南京 210023)

§1 引言

双层规划问题(BLPP)是一种优化问题,它受到另一层优化问题的约束.其通用形式如下:

其中(x,y)∈Rn+m和f,F:Rn+m →R,

双层规划也称为双层优化,是指模型约束中包含子目标函数和子约束条件的数学规划.Bracken和McGill[1]在研究不平衡经济市场竞争中首次提出的.Cander和Norton[2]在科学报告中正式提出了双层规划.自1980年以来,双层规划在理论和算法上得到了广泛的关注和迅速的发展,并逐渐形成了一个新的运筹学分支.目前,双层规划问题在工程设计,生态,经济等领域有着广泛的应用,例如农业信贷分配[3],经济规划[4],交通运输[5],优化交通信号[6-7]等.

自20世纪70年代以来,研究人员提出了许多求解双层规划的算法.算法主要有几种类型:(1)极点算法.它主要用于求解线性双层规划问题.其基本思想是:线性双层规划问题的最优解必须在约束域的极点处得到.实际上,这是顶点枚举法,可以用单纯形法[8]解决;(2)分枝定界算法.它主要用于求解凸和线性双层规划问题.其基本思想是用问题的KKT条件代替底层问题,构造一个等价于双层规划问题的KKT模型,然后利用分枝定界技术处理KKT问题的互补项,从而将该问题转化为求解一个含有等式和不等式约束的一般优化问题[9-14];(3)罚函数算法.该算法主要将惩罚函数原理应用到非线性规划理论中,通过使用不同的惩罚项将下层问题转化为无约束的数学规划问题,然后在上层目标函数中加入惩罚项,将问题转化为具有惩罚参数的单层问题[15-17];(4)K-T方法.该算法的基本思想是用其Kuhn-Tucker条件代替低层规划问题,并将双层规划问题转化为单层的非线性规划问题.这个想法可以参考[18],这是解决BLPP的同伦方法.同伦方法的显著优点是它生成的算法在一定的较弱条件下具有全局收敛性.本文仍然考虑用同伦方法求解双层规划问题.主要任务是放宽对初始点的要求,并在无界集合上求解BLPP.

本文的其余部分安排如下:§2构造了BLPP的同伦方程以及得到一些基本结果;§3在适当条件下,证明了同伦曲线的有界性以及同伦路径的点全局收敛于BLPP的KKT点;§4使用Euler-Newton算法[19]对同伦路径进行了数值跟踪,给出一些数值结果,验证了所论方法的有效性.

§2 BLPP的同伦方程和一些基本结果

考虑BLPP的f,g,F,Gi,i=1,2,……,m2为三次连续可微的凸函数,从而G也是凸函数.首先,考虑下层最优化问题:

假设对于给定的x ∈Rn,集合{y ∈Rm:G(x,y)＜0}/=∅,下层优化问题相应地转化为以下的KKT系统[18].

其中w=(x,y,u)T,e=(1,……,1)T∈Rm2,t ∈(0,1].设～f(w)=f(x,y),～g(w)=g(x,y).符号定义如下:

在文献[18]中,构造的组合同伦方程如下:

假设1(C1)∀t ∈[0,1],Ω1(t)是非空有界的;

在[18]中,要求起始点w(0)∈Ω1(1)满足h(w,1)=0,这导致找到该点非常困难.为了克服这个困难,根据公式(1)构造一个新的同伦方程:

为方便起见,将H(θ,θ(0),t),表示为Hθ(0),同伦方程的解集用下式表示

下面来介绍几种适用于同伦方法的引理.

定义1设U ∈Rn为开集,φ:U →Rp为Cα(α ＞max{0,n-p})映射.若值域=Rp,∀x ∈φ-1(y),则y ∈Rp是φ的一个正则值.

引理1[19](参数化Sard定理) 设⊂Rn,⊂Rm为开集,φ:×→Rk为Cα(α ＞max{0,n-k})映射;若0∈Rk是φ的一个正则值,则对于几乎所有的a ∈～V,0是φa=φ(a,·)的一个正则值.

引理2[20](逆像定理) 设φ:U ∈Rn →Rp是Cα(α ＞max{0,n-p})映射,若0是φ的正则值,则φ-1(0)包含若干(n-p)-维的光滑流形.

引理3[20](一维光滑流形分类定理) 一维光滑流形与单位圆或单位区间同胚.

假设2(A1)∀t ∈[0,1],Ω0是非空的,∇yF(x,y)和∇yG(x,y)是凸函数;

备注1对于(A1),由于G是凸函数以及U=diag(u),u ≥0,故若∇yF(x,y)和∇yG(x,y)是凸函数,则h(w,t)必须是凸函数.(A1)和(A6)可以保证BLPP的同伦方法在无界集上的收敛性.如果集合Ω是有界的,则可以忽略条件(A1)和(A6).并且(A5)可以确保BLPP的下层问题具有唯一的解.

备注2假设2(A6)是文献中的常见条件,它比以下强制性条件弱.

定义2[22]令C为Rn的圆锥,F:C →Rn为连续映射.如果存在u ∈C使得

那么称F满足C中的强制性条件.假设2(A6)与以下条件一致.

证当t=1时,同伦方程(2)变形为如下形式:

§3 主要结果

引理5Hθ(0)定义如(2)式,假设2(A1),(A6)成立,则对于几乎所有

上式的第一个方程两边同乘上(w(k)-z),有

其中第一个不等式是通过g是凸函数和假设2(A1)或参考备注1得出的.根据(4)式,得到第二个不等式.最后一个不等式成立是由于k →∞,有(1-tk)(w(0))Tv(0)+(w(k)-z)T(w(k)-w(0))＞0,上面所得结论与假设2(A6)相矛盾.因此,θ的分量w是有界的.

引理7(同伦曲线的有界性) 若假设2成立,则对几乎所有,v(0),λ(0)T∈Ω01,0是Hθ(0)的正则值,则Γθ(0)在Ω1×(0,1]上是一条有界曲线.

将两边同除以‖(v(k),λ(k))‖且令k →∞,得到{∇～gi(w),i ∈I(w*),∇wh(w,t)}是线性相关的,与假设2中的(A3) 相矛盾,所以{λ(k)}是有界序列.

与假设2(A3)相矛盾,所以{v(k)}是有界序列.

根据上述等式,若极限(1-tk)v(k)i趋于无穷大,则它与假设2(A3)相矛盾.若极限(1-tk)v(k)i存在,则与假设2(A4)相反.因此序列{v(k)}也有界.

是非奇异的,因此θ(0)=(w(0),v(0),λ(0))是Hθ(0)(θ(0),1)=0的唯一解.所以Γθ(0)不可能返回点(θ(0),1).根据引理3,Γθ(0)只微分同胚于(0,1].

令(θ*,t*)为Γθ(0)的一个收敛点,则对于点(θ*,t*)有下面三种情况可能成立:

§4 数值例子

本文用非内点同伦方法求解双层规划问题时,主要用Euler-Newton算法[19]对同伦路径进行数值追踪并得出最终解.Euler-Newton算法主要追踪的是由同伦方程Hθ(0)(θ,t)=0确定的一条从(θ(0),1)出发的光滑曲线.对下面所有的数值例子,选取的精确度参数为:ε3=10-6,并且下面例题的约束区域的选择都是非空闭凸集:Ω={(x,y)∈Rn+m:g(x,y)≤0,G(x,y)≤0}.结果如表所示,其中A1表示本文提出的新的同伦方程所产生的BLPP的同伦方法,A2代表文献[18]中的BLPP的同伦方法,IT代表迭代次数,CPU表示程序运行的时间,x(0),y(0)表示初始点,列表中所示前两个点是选取所研究问题的内点即Ω(t) 中的点,第三个点选取的是仅满足不等式约束中的点即Ω0中的点,在以下示例中表明,对于方法A1,可以采用仅满足不等式约束的初始点进行测试,但是对于方法A2,必须采用初始内部点进行测试.(x*,y*)表示问题的近似解,t*表示算法终止时对应的同伦参数的值.实验结果见下表,数值结果表明了该方法的有效性.

例4.1[18]

表1 例4.1的两种同伦方法结果比较

例4.2[24]

表2 例4.2的两种同伦方法结果比较

例4.3[24]

表3 例4.3的两种同伦方法结果比较

例4.4[25]

表4 例4.4的两种同伦方法结果比较

例4.5[25]

表5 例4.5的两种同伦方法结果比较

例4.6[25]例4.5中的r=0.1改为r=0.

表6 例4.6的两种同伦方法结果比较

从上面的数值结果可以看出,本文所给出解BLPP的同伦方法不仅扩大了初始点的选取范围,而且计算效率也较原来的内点同伦方法有很大的提高.