互補問題算例分析

雍龍泉

（陜西理工學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院，陜西漢中723001）

互補問題算例分析

雍龍泉

（陜西理工學(xué)院數(shù)學(xué)與計算機科學(xué)學(xué)院，陜西漢中723001）

給出了互補問題的測試算例，研究了這些算例的特征，為互補問題算法的研究提供了測試平臺。

線性互補；非線性互補；正定矩陣；唯一解；多個解

衡量求解互補問題算法的優(yōu)劣，需要根據(jù)相應(yīng)數(shù)值實驗的測試結(jié)果做出判斷。數(shù)值實驗要求所給互補問題的解是已知的，通過對比測試結(jié)果和已知解就能知道算法的優(yōu)劣，因此，設(shè)計一些能夠反映互補問題的測試算例是該領(lǐng)域的一個重要研究課題。在本文中，筆者給出了一些互補問題的測試算例，并分析了這些算例的特性，為互補問題的研究提供了測試平臺。

1 線性互補問題常用的算例

定義1［1］：若對任意的 x??n，都有 xΤMx ≥0，則矩陣 M??n×n稱為半正定矩陣；若對任意的 x??n，x≠ 0 ，都有 xΤM x＞0，則M稱為正定矩陣。

當(dāng)M是半正定矩陣時，稱相應(yīng)的LCP為單調(diào)線性互補問題。

引理1［1］：設(shè)矩陣 M??n×n是一個半正定矩陣，若對于任意 q??n，LCP是可行的，則LCP必有解，且解集為凸集。

引理2［1］：設(shè)矩陣 M??n×n是一個正定矩陣，則對于任意 q??n，LCP有唯一解。

上述判定線性互補問題解存在的條件是充分條件，而非必要條件。

下面給出一些常見的線性互補問題的測試算例［2-3］。

1.1 矩陣M正定且對稱的線性互補問題的算例

算例1：考慮線性互補問題，其中

通過計算可知，矩陣M的特征值分別為λ1= 0.308 0，λ2= 0.643 1， λ3=5.048 9。由于特征值全為正值，故矩陣M是正定矩陣。由引理2可知，該線性互補問題的解是唯一存在的，且該唯一解為 x*=(0,4,3)。Τ

算例2：考慮線性互補問題，其中

由于矩陣M是一個三對角矩陣，通過計算可知其特征值全大于零，矩陣M是正定矩陣。由引理2可知，該線性互補問題的解是唯一存在的。另外，該問題的解具有對稱性。

算例3：考慮線性互補問題，其中

通過計算可知，矩陣M的特征值全大于零，故矩陣M是正定矩陣。由引理2可知，該線性互補問題的解是唯一存在的，且唯一解為 x*=(1,0,… ,0)Τ。

算例4：考慮線性互補問題，其中

算例2、算例3和算例4可以用來測試算法求解的精度。

1.2 矩陣M正定且非對稱的線性互補問題的算例

算例5：考慮線性互補問題，其中

通過計算，可求得M的特征值為λ1=1.438 4，λ2= 5.561 6， λ3= λ4= 4。由于特征值全為正值，故矩陣M是正定矩陣。由引理2可知，該線性互補問題的解是唯一存在的，且唯一解為 x*=(1,0,1,0)Τ。

算例6：考慮線性互補問題，其中

容易驗證， M??n×n是正定矩陣。由引理2可知，該線性互補問題的解是唯一存在的，且唯一解為x*=(0,0,… ,0,1)Τ。該算例可以用來測試算法求解的精度。

下面的算例說明，矩陣的特征值為復(fù)數(shù)時，矩陣也可能是正定或半正定矩陣，因此特征值非負(fù)是M正定或半正定的充分而非必要條件［3］。

算例7：考慮線性互補問題，其中

經(jīng)過計算可得矩陣M的特征值分別為 λ2=1，λ2= 2.2225，λ3= 0.8888+ 1.8054i，λ4= 0.8888- 1.8054i。由于特征值中存在復(fù)數(shù)，故不能用特征值來判斷矩陣M的正定性。

算例8：考慮線性互補問題，其中

經(jīng)過計算可知，矩陣M的特征值為λ1= 0.264 0+ 5.298 0i， λ2= 0.264 0 - 5.298 0i ，λ3= 0.7487 +2.5437i，λ4= 0.748 7 - 2.543 7i，λ5= 0.174 3 +1.888 8i，λ6= 0.174 3 -1.888 8i，λ7=0.625 9。

醌類化合物是中藥中一類具有醌式結(jié)構(gòu)的化學(xué)成分，廣泛存在于動植物和礦物中，以蒽醌類居多，萘醌和苯醌類次之，且大多具有重要的生物活性。

由于特征值中存在復(fù)數(shù)，故不能用特征值來判斷正定性，下面用定義來判別矩陣M的正定性。

1.3 矩陣M非正定的線性互補問題的算例

算例9：考慮線性互補問題，其中

經(jīng)過計算可知，矩陣M的特征值為λ1= λ2= 0.5+ 0.866i，λ3= λ4= 0.5 -0.866i。由于特征值都是復(fù)數(shù)，故只能用定義來判別矩陣M的正定性。

算例10：考慮線性互補問題，其中

經(jīng)過計算可知，M的特征值為 λ1=17.326 9，λ2= 1.386 2，λ3= 3.758 9，λ4= 9.100 3，λ5= 0.2138+ +1.6091i；λ6= 0.2138 -1.6091i。由于特征值中存在復(fù)數(shù)，故只能用定義來判別矩陣M的正定性。

對于任意的 x=(x1, x2, x3, x4, x5, x6)Τ。由于若取=(0,0,0,0, -8,3)Τ，則有因此矩陣M不是正定矩陣，但是該問題具有唯一解x*=(0.7,0,0.3,0,0.6,0)Τ。

經(jīng)過計算可知，M的特征值為 λ1= 4.4665，λ2= -4.466 5，λ3= 0.223 9，λ4=-0 .2239， λ5=0。由于存在負(fù)特征值，故矩陣M是非半正定矩陣。

把上述算例的結(jié)果進(jìn)行歸納，可得表1。

關(guān)于線性互補問題，常見的求解方法是針對單調(diào)線性互補問題的，而非單調(diào)的線性互補問題（即矩陣M非半正定）方面的研究較少，算例9～11可以用來測試算法的適用范圍，即對非單調(diào)的線性互補問題，算法是否適用。

表1 線性互補算例特征分析

1.4 無解的線性互補問題的算例

下面給出無解的線性互補問題的算例［4–6］。

算例12：考慮線性互補問題，其中

算例13：考慮線性互補問題，其中

經(jīng)過計算可以發(fā)現(xiàn)以上線性互補問題無解。

能否在算法終止時判別有解或無解，可以用算例12和算例13進(jìn)行測試。

1.5 含參數(shù)的線性互補問題的算例

下面給出含參數(shù)的線性互補問題的算例［7］。

算例14：考慮線性互補問題，其中

經(jīng)過計算可得，該問題的唯一解為

算例15：考慮含參數(shù)的線性互補問題，其中

經(jīng)過計算可得，該問題的唯一解為

算例16：考慮線性互補問題，其中

經(jīng)過計算可得，該問題的唯一解為

算例14～16常用于算法的靈敏度分析。

2 非線性互補問題常用的算例

文獻(xiàn)［1］詳細(xì)地給出了非線性互補解存在的條件。下面僅給出常見的非線性互補算例，這些算例在有變分不等式的互補問題中經(jīng)常用到［8–10］。

2.1 有唯一解的非線性互補問題的算例

算例17：考慮非線性互補問題，其中

該非線性互補問題的唯一解為 x*=(1,1,0)Τ。算例18：考慮非線性互補問題，其中

該非線性互補問題的唯一解為 x*=(2,1,0)Τ。算例19：考慮非線性互補問題，其中

算例20：考慮非線性互補問題，其中

該非線性互補問題的唯一解為 x*=(0,3,1,0,0)Τ。

2.2 有多個解的非線性互補問題的算例

算例21：考慮非線性互補問題，其中

該問題的非退化解為 x*=(1,0,3,0)Τ，退化解為

算例22：考慮非線性互補問題，其中

該問題有無窮多個解 x*=(λ,0,0,0)Τ，其中λ?[0,3]。

3 結(jié)束語

在本文中，筆者詳細(xì)地給出了互補問題的一些測試算例，在驗證互補問題算法的有效性時，可以通過這些算例驗證算法的優(yōu)劣。

［1］ 韓繼業(yè)，修乃華，戚厚鐸.非線性互補理論與算法［M］.上海：上?？茖W(xué)技術(shù)出版社，2006：31-125.

［2］ 雍龍泉，鄧方安，陳濤.單調(diào)線性互補問題的一種內(nèi)點算法［J］.數(shù)學(xué)雜志，2009（5）：681-686.

［3］ 雍龍泉，鄧方安.線性互補問題中矩陣正定性判別的兩點注記［J］.吉首大學(xué)學(xué)報（自然科學(xué)版），2009（1）：33-35.

［4］KOSTREVAM M，WIECEKM M.Linear Complementarity Problems and Multiple Objective Programming［J］. Mathematical Programming，1993，60:349-359.

［5］ISAC G，KOSTREVA M M，WIECEK M M.Multiple Objective Approximation of Feasible but Unsolvable LinearComplementarityProblems［J］.JournalofOptimization Theory and Applications，1995，86:389-405.

［6］KOSTREVA M M，YANG X Q.Unified Approaches for Solvable and Unsolvable Linear Complementarity Problems［J］.European JournalofOperationalResearch，2004，158:409-417.

［7］ XIAO B C.The Linear Complementarity Problem with a Parametric Input［J］.European Journal of Operational Research，1995，81:420-429.

［8］ JIANG H Y，QI L Q.A New Nonsmooth Equations Approach to Nonlinear Complementarity Problems［J］. Siam Journal on Control and Optimization，1997，35: 178-193.

［9］ 屈彪，王長玨，張樹霞.一種求解非線性互補問題的方法及其收斂性［J］.計算數(shù)學(xué)，2006（3）：247-258.

［10］雍龍泉.基于多目標(biāo)優(yōu)化算法求解非線性互補問題［J］.中南大學(xué)學(xué)報（自然科學(xué)版），2011（增刊1）：596-599.

【責(zé)任編輯 王云鵬】

Examp le Analysis for Com p lementary Problem

YONG Longquan
（School ofMathematics and Computer Science，ShanxiUniversity of Technology，Hanzhong 723001，China）

Complementary problem test examples were given in the paper，and the characteristic of these examples were studied respectively，which provided a test platform on algorithm for complementary problem.

linear complementarity；nonlinear complementarity；positive definitematrix；unique solution；multiple solutions

O221

A

2095-7726（2015）06-0004-05

2015-02-10

國家自然科學(xué)基金項目（11401357）；陜西理工學(xué)院教學(xué)改革研究項目（SLGYJG1416）

雍龍泉（1980-），男，陜西洋縣人，副教授，博士，研究方向：最優(yōu)化理論與算法、智能優(yōu)化算法。