同伦内点方法求解一类无界区域上的多目标规划问题

苏孟龙,吕显瑞

(1.洛阳师范学院 数学学院,河南 洛阳 471934;2.吉林大学 数学学院,长春 130012)

0 引 言

自文献[1]提出用组合同伦内点法求解一类凸规划问题后,组合同伦内点法作为一种新的、高效的内路径跟踪算法,在求解各种非线性问题中被广泛应用[2-8]，目前已取得了丰富的成果：Song等[9]提出了一种新的组合同伦内点法求解一类多目标规划问题,利用目标函数的梯度,给出了一组无界性条件,从而在无界约束集上得到了算法的全局收敛性结果;Shang等[10]发现文献[9]考虑的乘子向量λ∈p实质上是常值向量,通过进一步考虑当λ为可变向量的情形,在新的无界性条件下给出了求解问题(1)的动约束同伦方法.但文献[9-10]给出的无界性条件在很多情形下并不容易验证,为了克服该困难,本文利用目标函数的Hessian矩阵给出一组新的无界性条件,举例说明该条件更容易验证,并在此基础上给出连接给定初始点和多目标规划KKT(Karush-Kuhn-Tucker)点的内路径存在性的构造性证明,从而得到了同伦内点法的全局收敛性结果.

考虑如下多目标规划问题:

其中f:n→p,g:n→m,h:n→l是三次连续可微的.令Ω={x∈n:g(x)0,h(x)=0}为问题(1)的可行集,Ω0={x∈n:g(x)<0,h(x)=0}为问题(1)的严格可行集,B(x)={j∈{1,2,…,m}:gj(x)=0}为x∈Ω处的积极指标集.给定x∈n,记‖x‖为x处的2-范数.m的非负象限和正象限分别记为和

若x,y∈n,则有

1 主要结果

针对多目标规划问题(1),文献[10]把乘子向量λ视为变量,考虑如下形式的规划问题:

其中λ-p=(λ1,…,λp-1)T,f-p(x)=(f1(x),…,fp-1(x))T.

若x为多目标规划问题的Pareto最优解,本文考虑规划问题(2)对应的KKT系统:

为了求解系统(3),需要构造如下组合同伦方程:

H(P,P(0),μ)=

(4)

其中:

P=(x,u,v,w,λ-p)∈n+m+l+p×Λ+;

为了求解无界区域上的多目标规划问题,文献[9-10]分别提出了如下两个无界性条件：

在很多情形下,条件(H1)和(H2)不容易验证,为了克服这一困难,本文给出一个新的无界性条件:

(H3)Ω0非空;存在ρi>0(i=1,2,…,p),使得对任意的x∈n和d∈n,均有

dT2fi(x)dρi‖d‖2,i=1,2,…,p.

下面举例说明条件(H3)很容易验证,而条件(H1)和(H2)不易验证.

例1设目标函数为

约束区域为

对任意给定的η∈Ω,记

引理1若假设(H3)成立,gj(x)(j=1,2,…,m)是凸函数,hk(x)(k=1,2,…,l)是线性函数,则对任意给定的η∈Ω,Ω-(η)是有界集.

证明: ∀x∈Ω-(η),存在i∈{1,2,…,p},使得

fi(x)-fi(η)0.

(5)

根据Taylor展式,有

(6)

其中

ζi=η+θi(x-η)=θix+(1-θi)η, 0<θi<1.

从而由式(5)和假设(H3)得

(7)

进而

(8)

即

(9)

若x=η,由η的有限性知x也是有限的.当x≠η时,由不等式(9)得

(10)

‖x(k)-η‖2-‖x(0)-η‖22(x(k)-η)T(x(k)-x(0)).

(11)

将式(4)的第一个等式两边同时乘以(x(k)-η)T,则有

根据引理1、式(12)、g(η)Tu(k)0及同伦方程(3)的第四个等式,则有

当x(k)∈Ω+(η)时,有

fi(η)-fi(x(k))<0, ∀i=1,2,…,p.

由式(13)得

如果‖x(k)‖→∞,因为‖x(0)-η‖2,g(x(0))T和u(0)都是常量,μk有界,则存在某个k,使得‖x(k)-η‖>M,此时式(14)的右边严格大于0,而式(14)的左边严格小于0,矛盾.当x(k)∈Ω-(η)时,由引理1知Ω-(η)有界.

综上所述,w在同伦曲线Γw(0)上的x分量是有界的.证毕.

类似于文献[10]的证明,可得如下同伦内点方法的全局收敛性结果:

H(P(s),P(0),μ(s))=0, (P(0),μ(0))=(P(0),1),

(15)