線性互補問題測試算例的一個構造方法

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

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

線性互補問題測試算例的一個構造方法

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

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

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

線性互補問題; 測試算例; 單調線性互補; 混合整數線性規劃

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

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

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

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

1 一般線性互補問題

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

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

根據構造過程可知該問題的一個解是x=(9.7975,2.7145,2.5233,8.7574,7.3731)T，接下來驗證其正確性。現將線性互補問題轉換成相伴的混合整數線性規劃[6]：

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

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

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

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

根據構造過程可知該問題的一個解是x=(8.7437,0.1501,7.6795,9.7084,9.9008)T，接下來驗證其正確性。現將線性互補問題轉換成相應的混合整數線性規劃(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個結果是一致的，這說明筆者構造的線性互補問題算例是有效的。

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

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

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

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

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

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

4 無解線性互補問題

算例4

由文獻[10]可知該LCP(q,M)問題可行域非空，但是無解。 現將線性互補問題轉換成相應的混合整數線性規劃(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]韓繼業, 修乃華, 戚厚鐸. 非線性互補理論與算法[M]. 上海:上海科學技術出版社, 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]何尚錄. 求解互補問題的不可行內點法及其計算復雜性[J]. 中國科學A輯, 2000,30(11):983-989.

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

[7]黃紅選, 梁治安. 全局優化引論[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]申培萍. 全局優化引論[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)。

楊春艷，女，助教，現主要從事最優化理論與算法方面的教學與研究工作。