蘇孟龍,呂顯瑞

(1.洛陽師范學(xué)院 數(shù)學(xué)學(xué)院,河南 洛陽 471934;2.吉林大學(xué) 數(shù)學(xué)學(xué)院,長(zhǎng)春 130012)

0 引 言

自文獻(xiàn)[1]提出用組合同倫內(nèi)點(diǎn)法求解一類凸規(guī)劃問題后,組合同倫內(nèi)點(diǎn)法作為一種新的、高效的內(nèi)路徑跟蹤算法,在求解各種非線性問題中被廣泛應(yīng)用[2-8]，目前已取得了豐富的成果：Song等[9]提出了一種新的組合同倫內(nèi)點(diǎn)法求解一類多目標(biāo)規(guī)劃問題,利用目標(biāo)函數(shù)的梯度,給出了一組無界性條件,從而在無界約束集上得到了算法的全局收斂性結(jié)果;Shang等[10]發(fā)現(xiàn)文獻(xiàn)[9]考慮的乘子向量λ∈p實(shí)質(zhì)上是常值向量,通過進(jìn)一步考慮當(dāng)λ為可變向量的情形,在新的無界性條件下給出了求解問題(1)的動(dòng)約束同倫方法.但文獻(xiàn)[9-10]給出的無界性條件在很多情形下并不容易驗(yàn)證,為了克服該困難,本文利用目標(biāo)函數(shù)的Hessian矩陣給出一組新的無界性條件,舉例說明該條件更容易驗(yàn)證,并在此基礎(chǔ)上給出連接給定初始點(diǎn)和多目標(biāo)規(guī)劃KKT(Karush-Kuhn-Tucker)點(diǎn)的內(nèi)路徑存在性的構(gòu)造性證明,從而得到了同倫內(nèi)點(diǎn)法的全局收斂性結(jié)果.

考慮如下多目標(biāo)規(guī)劃問題:

其中f:n→p,g:n→m,h:n→l是三次連續(xù)可微的.令Ω={x∈n:g(x)0,h(x)=0}為問題(1)的可行集,Ω0={x∈n:g(x)<0,h(x)=0}為問題(1)的嚴(yán)格可行集,B(x)={j∈{1,2,…,m}:gj(x)=0}為x∈Ω處的積極指標(biāo)集.給定x∈n,記‖x‖為x處的2-范數(shù).m的非負(fù)象限和正象限分別記為和

若x,y∈n,則有

1 主要結(jié)果

針對(duì)多目標(biāo)規(guī)劃問題(1),文獻(xiàn)[10]把乘子向量λ視為變量,考慮如下形式的規(guī)劃問題:

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

若x為多目標(biāo)規(guī)劃問題的Pareto最優(yōu)解,本文考慮規(guī)劃問題(2)對(duì)應(yīng)的KKT系統(tǒng):

為了求解系統(tǒng)(3),需要構(gòu)造如下組合同倫方程:

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

(4)

其中:

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

為了求解無界區(qū)域上的多目標(biāo)規(guī)劃問題,文獻(xiàn)[9-10]分別提出了如下兩個(gè)無界性條件：

在很多情形下,條件(H1)和(H2)不容易驗(yàn)證,為了克服這一困難,本文給出一個(gè)新的無界性條件:

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

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

下面舉例說明條件(H3)很容易驗(yàn)證,而條件(H1)和(H2)不易驗(yàn)證.

例1設(shè)目標(biāo)函數(shù)為

約束區(qū)域?yàn)?/p>

對(duì)任意給定的η∈Ω,記

引理1若假設(shè)(H3)成立,gj(x)(j=1,2,…,m)是凸函數(shù),hk(x)(k=1,2,…,l)是線性函數(shù),則對(duì)任意給定的η∈Ω,Ω-(η)是有界集.

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

fi(x)-fi(η)0.

(5)

根據(jù)Taylor展式,有

(6)

其中

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

從而由式(5)和假設(shè)(H3)得

(7)

進(jìn)而

(8)

即

(9)

若x=η,由η的有限性知x也是有限的.當(dāng)x≠η時(shí),由不等式(9)得

(10)

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

(11)

將式(4)的第一個(gè)等式兩邊同時(shí)乘以(x(k)-η)T,則有

根據(jù)引理1、式(12)、g(η)Tu(k)0及同倫方程(3)的第四個(gè)等式,則有

當(dāng)x(k)∈Ω+(η)時(shí),有

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

由式(13)得

如果‖x(k)‖→∞,因?yàn)椤瑇(0)-η‖2,g(x(0))T和u(0)都是常量,μk有界,則存在某個(gè)k,使得‖x(k)-η‖>M,此時(shí)式(14)的右邊嚴(yán)格大于0,而式(14)的左邊嚴(yán)格小于0,矛盾.當(dāng)x(k)∈Ω-(η)時(shí),由引理1知Ω-(η)有界.

綜上所述,w在同倫曲線Γw(0)上的x分量是有界的.證畢.

類似于文獻(xiàn)[10]的證明,可得如下同倫內(nèi)點(diǎn)方法的全局收斂性結(jié)果:

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

(15)