同倫內點方法求解一類無界區域上的多目標規劃問題

蘇孟龍,呂顯瑞

(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)