同倫內(nèi)點(diǎn)法求解多目標(biāo)規(guī)劃問(wèn)題

趙 雪,楊月婷,張樹(shù)功

(1.北華大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,吉林 吉林 132013； 2.吉林大學(xué) 數(shù)學(xué)學(xué)院,長(zhǎng)春 130012)

0 引言與預(yù)備知識(shí)

同倫方法是一種大范圍收斂方法[1-2],其作為一種全局收斂方法目前已引起人們廣泛關(guān)注,并成為數(shù)值解決互補(bǔ)問(wèn)題、 變分不等式和不動(dòng)點(diǎn)等問(wèn)題的重要工具[3-6].文獻(xiàn)[7]定義了正獨(dú)立映射的概念,給出了比法錐條件更弱的擬法錐條件,并給出了修正的組合同倫方程.本文把同倫內(nèi)點(diǎn)方法運(yùn)用到多目標(biāo)規(guī)劃問(wèn)題中,通過(guò)引入擬法錐條件,削弱了對(duì)約束區(qū)域非凸性條件的限制,從而擴(kuò)大了組合同倫內(nèi)點(diǎn)法的求解范圍.

考慮多目標(biāo)規(guī)劃問(wèn)題:

(1)

其中f=(f1,f2,…,fp)T:n→p和g=(g1,g2,…,gm)T:n→m均為二次連續(xù)可微函數(shù).

令Ω={x∈n|gi(x)≤0,i=1,2,…,m}表示可行域,Ω0={x∈n|gi(x)<0}表示嚴(yán)格可行域,?Ω=ΩΩ0表示可行解集的邊界.記

定義2令U?n是一個(gè)開(kāi)集,φ:U→p是Cα(α>max{0,n-p})映射.如果Range[?φ(x)/?x]=p,?x∈φ-1(y),則稱y∈n是φ的一個(gè)正則值.

引理1(參數(shù)化Sard定理)[8]令V?n,U?m是開(kāi)集,且φ:V×U→k是一個(gè)Cα映射,其中α>max{0,m-k}.如果0∈k是φ的一個(gè)正則值,則對(duì)于幾乎所有的a∈V,0是φa=φ(a,·)的一個(gè)正則值.

引理2(逆映像定理)[8]令φ:U?n→p是一個(gè)Cα(α>max{0,n-p})映射.如果0是φ的一個(gè)正則值,則φ-1(0)由一些(n-p)-維Cα流形構(gòu)成.

引理3(一維光滑流形的分類定理)[8]一個(gè)一維光滑流形同胚于一個(gè)單位圓或一個(gè)單位區(qū)間.

假設(shè)條件：

(H1)Ω是非空連通的有界閉集合,Ω0非空；

1 同倫路徑的存在性及全局收斂性

構(gòu)造如下組合同倫方程:

(2)

證明: 由同倫方程(2),得

(3)

由于tk→t*∈[0,1],λk>0,故當(dāng)k→∞時(shí),式(3)左邊的第二部分趨于無(wú)窮,而其余兩部分是有界的,矛盾.從而λ的分量有界.

證明：令DH(w,w0,t)表示H(w,w0,t)的Jacobi矩陣,

其中:I是單位矩陣;U0=diag(u0).

(1-tk)(f(x)(xk)λk+g(x)(xk)uk+tkη(xk)(uk)2)+tk(xk-x0)=0,

Ukg(x)(xk)-tkU0g(x)(x0)=0.

當(dāng)k→∞時(shí),有下列幾種情形發(fā)生:

(1-tk)(f(x)(xk)λk+g(xk)uk+tkη(xk)(uk)2)+tk(xk-x0)=0.

(4)

當(dāng)t*=1時(shí),式(4)可改寫(xiě)為

令k→∞,有

從而

其中αi∈+,得這與擬法錐條件矛盾.

當(dāng)t*∈[0,1)時(shí),有

2 數(shù)值算例

例1

(6)

由約束函數(shù)(6)構(gòu)成的可行域滿足擬法錐條件.取t0=1,初始點(diǎn)為(3.000 0,0.000 0),可得x*=(3.755 2,-0.869 0)T.

例2

(7)

由約束函數(shù)(7)構(gòu)成的可行域滿足擬法錐條件.取t0=1,初始點(diǎn)為(-0.500 0,-0.100 0),可得x*=(-1.000 0,-0.006 2)T.

[1] Kellogg R B,Li T Y,Yorke J A.A Constructive Proof the Brouwer Fixed-Point Theorem and Computational Results [J].SIAM J Numer Analysis,1976,13(4): 473-483.

[2] Chow S N,Mallet-Paret J,York J A.Finding Zeroes of Maps: Homotopy Methods That Are Constructive with Probability One [J].Math Comput,1978,32: 887-899.

[3] Gowda M S.On the Extended Linear Complementarity Problem [J].Mathematical Programming,1996,72: 33-50.

[4] ZHAO Xue,ZHANG Shu-gong,LIU Qing-huai.A Combined Homotopy Interior Point Method for the Linear Complementarity Problem [J].Journal of Information and Computational Science,2010,7(7): 1589-1594.

[5] FAN Xiao-na,YU Bo.A Smoothing Homotopy Method for Solving Variational Inequalities [J].Nonlinear Analysis: Theory,Methods &Applications,2009,10(1): 211-219.

[6] SU Meng-long,LIU Zhen-xin.Modified Homotopy Method to Solve Fixed Points of Sel-Mapping in a Broader Class of Nonconvex Sets [J].Applied Numerical Mathematics,2008,58(3): 236-248.

[7] LIU Qing-huai,YU Bo,FENG Guo-chen.An Interior Point Path-Following Method for Non-convex Programming with Quasi-normal Cone Condition [J].Advances in Mathematics,2000,19(4): 281-282.

[8] 張筑生.微分拓?fù)湫轮v [M].北京：北京大學(xué)出版社,2002.