楊春艷 (銀川大學(xué)數(shù)學(xué)系,寧夏 銀川 750105)

雍龍泉 (陜西理工學(xué)院數(shù)學(xué)系,陜西 漢中 723001)

線性互補(bǔ)問(wèn)題測(cè)試算例的一個(gè)構(gòu)造方法

楊春艷 (銀川大學(xué)數(shù)學(xué)系,寧夏 銀川 750105)

雍龍泉 (陜西理工學(xué)院數(shù)學(xué)系,陜西 漢中 723001)

建立了線性互補(bǔ)問(wèn)題測(cè)試函數(shù)的一個(gè)構(gòu)造方法。給出了一般線性互補(bǔ)問(wèn)題、單調(diào)線性互補(bǔ)問(wèn)題以及反對(duì)稱矩陣線性互補(bǔ)問(wèn)題測(cè)試算例的構(gòu)造方法。結(jié)果表明，建立的構(gòu)造方法是有效的。這些結(jié)果對(duì)線性互補(bǔ)問(wèn)題的研究具有重要的意義，進(jìn)而可以利用該方法來(lái)構(gòu)造一系列的線性互補(bǔ)做測(cè)試算例，這在很大程度上豐富了線性互補(bǔ)問(wèn)題的數(shù)值試驗(yàn)。

線性互補(bǔ)問(wèn)題; 測(cè)試算例; 單調(diào)線性互補(bǔ); 混合整數(shù)線性規(guī)劃

線性互補(bǔ)問(wèn)題就是求一個(gè)向量x∈Rn，使得：

x≥0Mx+q≥0xT(Mx+q)=0

線性互補(bǔ)問(wèn)題簡(jiǎn)記為L(zhǎng)CP(q,M)。求解線性互補(bǔ)問(wèn)題的算法有很多，經(jīng)典的有Lemke算法。近年來(lái)出現(xiàn)的一些具有多項(xiàng)式復(fù)雜性的算法，諸如投影法、內(nèi)點(diǎn)法、非光滑牛頓法、光滑牛頓法等已成為目前研究的熱點(diǎn)[1-5]。文獻(xiàn)[6]中把線性互補(bǔ)問(wèn)題轉(zhuǎn)化為一個(gè)混合整數(shù)線性規(guī)劃，通過(guò)求解混合整數(shù)線性規(guī)劃得到原問(wèn)題的最優(yōu)解，該方法更實(shí)用，且更容易上機(jī)操作，因此也可以作為求解線性互補(bǔ)問(wèn)題的一個(gè)實(shí)用方法。

下面，筆者就線性互補(bǔ)問(wèn)題測(cè)試算例的一個(gè)構(gòu)造方法做了研究，給出了一般線性互補(bǔ)問(wèn)題、單調(diào)線性互補(bǔ)問(wèn)題以及反對(duì)稱矩陣線性互補(bǔ)問(wèn)題測(cè)試算例的構(gòu)造方法。

1 一般線性互補(bǔ)問(wèn)題

隨機(jī)產(chǎn)生矩陣M∈Rn×n,隨機(jī)生成非負(fù)向量x∈Rn×1,令q=-Mx,因此就得到矩陣M和向量q,由于x≥0,Mx+q=0，故xT(Mx+q)=0,因此相應(yīng)的線性互補(bǔ)問(wèn)題LCP(q,M)的解就是x。

算例1隨機(jī)生成5階方陣M，隨機(jī)生成非負(fù)向量x∈R5×1；從而得到M和q如下:

根據(jù)構(gòu)造過(guò)程可知該問(wèn)題的一個(gè)解是x=(9.7975,2.7145,2.5233,8.7574,7.3731)T，接下來(lái)驗(yàn)證其正確性?，F(xiàn)將線性互補(bǔ)問(wèn)題轉(zhuǎn)換成相伴的混合整數(shù)線性規(guī)劃[6]：

其中e=(1,1,…,1)T∈R5,y∈R5,z∈{0,1}5,稱(MILP)為L(zhǎng)CP(q,M)問(wèn)題的伴隨混合整數(shù)線性規(guī)劃[6-7]，求解(MILP)問(wèn)題[6]得到a*=0.102067,y*=(1,0.277071,0.257538,0.893844,0.752553)T，由于a*gt;0,故根據(jù)文獻(xiàn)[6]可知x*=y*/a*=(9.79748,2.7146,2.52322,8.75742,7.37313)T就是原線性互補(bǔ)問(wèn)題的一個(gè)解，由此可見(jiàn),2個(gè)結(jié)果是一致的，這說(shuō)明筆者構(gòu)造的線性互補(bǔ)問(wèn)題算例是正確的。

2 對(duì)稱半正定矩陣線性互補(bǔ)問(wèn)題

隨機(jī)產(chǎn)生矩陣A∈Rn×n令M=ATA+kI(其中I是單位矩陣,k≥0)；隨機(jī)生成非負(fù)向量x∈Rn×1,令q=-Mx，因此就得到半正定矩陣M和向量q,同理可知,相應(yīng)的線性互補(bǔ)問(wèn)題LCP(q,M)的解就是x。

算例2隨機(jī)生成5階方陣A，隨機(jī)生成非負(fù)向量x∈R5×1；進(jìn)而得到M和q如下:

根據(jù)構(gòu)造過(guò)程可知該問(wèn)題的一個(gè)解是x=(8.7437,0.1501,7.6795,9.7084,9.9008)T，接下來(lái)驗(yàn)證其正確性?，F(xiàn)將線性互補(bǔ)問(wèn)題轉(zhuǎn)換成相應(yīng)的混合整數(shù)線性規(guī)劃(MILP)問(wèn)題，求解(MILP)問(wèn)題得到a*=0.06513，y*=(0.569522,0.009833,0.5,0.632387,0.644824)T，因?yàn)閍*gt;0，從而x*=y*/a*=(8.744,0.151,7.677,9.71,9.901)T就是原線性互補(bǔ)問(wèn)題的一個(gè)解，由此可見(jiàn),2個(gè)結(jié)果是一致的，這說(shuō)明筆者構(gòu)造的線性互補(bǔ)問(wèn)題算例是有效的。

對(duì)稱半正定矩陣線性互補(bǔ)問(wèn)題通常被稱為單調(diào)線性互補(bǔ)問(wèn)題，因此調(diào)用單調(diào)線性互補(bǔ)問(wèn)題的勢(shì)下降內(nèi)點(diǎn)算法[8-9]，得到x*=(8.7444,0.1510,7.6769,9.7096,9.9005)T，可見(jiàn),2個(gè)結(jié)果是一致的，這就充分說(shuō)明筆者構(gòu)造的線性互補(bǔ)問(wèn)題算例是正確的。

鑒于M類型的多樣性，可以構(gòu)造更多類型的線性互補(bǔ)問(wèn)題，比如隨機(jī)產(chǎn)生矩陣A∈Rn×n，令M=A±AT,這樣就可以構(gòu)造矩陣M為(反)對(duì)稱的線性互補(bǔ)問(wèn)題。

3 反對(duì)稱矩陣線性互補(bǔ)問(wèn)題

隨機(jī)產(chǎn)生矩陣A∈Rn×n,令M=A-AT,隨機(jī)生成非負(fù)向量x∈Rn×1,令q=-Mx，因此就得到反對(duì)稱矩陣M和向量q,由于x≥0,Mx+q=0，故xT(Mx+q)=0,因此相應(yīng)的線性互補(bǔ)問(wèn)題LCP(q,M)的解就是x。

算例3隨機(jī)生成2階方陣A，隨機(jī)生成非負(fù)向量x∈R2×1，進(jìn)而得到M和q如下:

根據(jù)構(gòu)造過(guò)程可知該問(wèn)題的一個(gè)解是x=(6.4491,8.1797)T。接下來(lái)驗(yàn)證其正確性?，F(xiàn)將線性互補(bǔ)問(wèn)題轉(zhuǎn)換成相應(yīng)的混合整數(shù)線性規(guī)劃(MILP)問(wèn)題，求解(MILP)問(wèn)題得到a*=0.122254,y*=(0.788425,1)T,由于a*gt;0,所以根據(jù)文獻(xiàn)[6]知x*=y*/a*=(6.449073,8.179691)T就是原問(wèn)題的一個(gè)解。由此可見(jiàn),2個(gè)結(jié)果基本上一致的。

4 無(wú)解線性互補(bǔ)問(wèn)題

算例4

由文獻(xiàn)[10]可知該LCP(q,M)問(wèn)題可行域非空，但是無(wú)解。 現(xiàn)將線性互補(bǔ)問(wèn)題轉(zhuǎn)換成相應(yīng)的混合整數(shù)線性規(guī)劃(MILP)問(wèn)題，求解(MILP)問(wèn)題得到a*=0,y*=(0,0)T,由于a*=0,所以原LCP(q,M)問(wèn)題無(wú)解。

[1]Cottle R W, Pang J S, Stone R E.The Linear Complementarity Problems[M]. Academic Press, 1992.

[2]韓繼業(yè), 修乃華, 戚厚鐸. 非線性互補(bǔ)理論與算法[M]. 上海:上海科學(xué)技術(shù)出版社, 2006.

[3]Kojima M, Megiddo N, Yoshise A. A unified approach to interior point algorithms for linear complementary problem[A]. Lecture Notes in computer science[C]. Berlin: Springer-Verlag,1991:538.

[4] Stephen J. Wright. An infeasible-interior-point algorithm for linear complementarity problems[J]. Mathematical Programming, 1994,64:29-51.

[5]何尚錄. 求解互補(bǔ)問(wèn)題的不可行內(nèi)點(diǎn)法及其計(jì)算復(fù)雜性[J]. 中國(guó)科學(xué)A輯, 2000,30(11):983-989.

[6]雍龍泉, 鄧方安, 趙景服. 線性互補(bǔ)問(wèn)題的一種混合整數(shù)規(guī)劃解法[J]. 陜西理工學(xué)院學(xué)報(bào), 2007,23(4):80-82.

[7]黃紅選, 梁治安. 全局優(yōu)化引論[M]. 北京:清華大學(xué)出版社, 2003.

[8] YOANG Long-quan.Potential-reduction interior point algorithm for monotone linear complementarity problem[A]. Proceedings of First International Conference of Modelling and Simulation[C]. UK: World Academic Press, 2008:437-441.

[9]申培萍. 全局優(yōu)化引論[M]. 北京:科學(xué)出版社, 2006.

[10] Kostreva M M, Yang X Q. Unified approaches for solvable and unsolvable linear complementarity problems [J]. European Journal of Operational Research,2004,158: 409-417.

[編輯] 洪云飛

10.3969/j.issn.1673-1409.2011.07.003

O224

A

1673-1409(2011)07-0008-02

2011-05-10

陜西省教育廳自然科學(xué)研究項(xiàng)目(09JK381)。

楊春艷，女，助教，現(xiàn)主要從事最優(yōu)化理論與算法方面的教學(xué)與研究工作。