線性互補問題測試算例的一個構(gòu)造方法

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

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

線性互補問題測試算例的一個構(gòu)造方法

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

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

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

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

線性互補問題就是求一個向量x∈Rn，使得：

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

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

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

1 一般線性互補問題

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

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

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

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

2 對稱半正定矩陣線性互補問題

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

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

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

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

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

3 反對稱矩陣線性互補問題

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

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

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

4 無解線性互補問題

算例4

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

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

[2]韓繼業(yè), 修乃華, 戚厚鐸. 非線性互補理論與算法[M]. 上海:上?？茖W技術(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]何尚錄. 求解互補問題的不可行內(nèi)點法及其計算復雜性[J]. 中國科學A輯, 2000,30(11):983-989.

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

[7]黃紅選, 梁治安. 全局優(yōu)化引論[M]. 北京:清華大學出版社, 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]. 北京:科學出版社, 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

陜西省教育廳自然科學研究項目(09JK381)。

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