同倫內點法求解多目標規劃問題

趙 雪,楊月婷,張樹功

(1.北華大學 數學與統計學院,吉林 吉林 132013； 2.吉林大學 數學學院,長春 130012)

0 引言與預備知識

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

考慮多目標規劃問題:

(1)

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

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

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

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

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

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

假設條件：

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

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

構造如下組合同倫方程:

(2)

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

(3)

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

證明：令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.

當k→∞時,有下列幾種情形發生:

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

(4)

當t*=1時,式(4)可改寫為

令k→∞,有

從而

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

當t*∈[0,1)時,有

2 數值算例

例1

(6)

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

例2

(7)

由約束函數(7)構成的可行域滿足擬法錐條件.取t0=1,初始點為(-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] 張筑生.微分拓撲新講 [M].北京：北京大學出版社,2002.