雍龍泉

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

互補(bǔ)問題算例分析

雍龍泉

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

給出了互補(bǔ)問題的測試算例，研究了這些算例的特征，為互補(bǔ)問題算法的研究提供了測試平臺(tái)。

線性互補(bǔ)；非線性互補(bǔ)；正定矩陣；唯一解；多個(gè)解

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

1 線性互補(bǔ)問題常用的算例

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

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

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

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

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

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

1.1 矩陣M正定且對(duì)稱的線性互補(bǔ)問題的算例

算例1：考慮線性互補(bǔ)問題，其中

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

算例2：考慮線性互補(bǔ)問題，其中

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

算例3：考慮線性互補(bǔ)問題，其中

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

算例4：考慮線性互補(bǔ)問題，其中

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

1.2 矩陣M正定且非對(duì)稱的線性互補(bǔ)問題的算例

算例5：考慮線性互補(bǔ)問題，其中

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

算例6：考慮線性互補(bǔ)問題，其中

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

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

算例7：考慮線性互補(bǔ)問題，其中

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

算例8：考慮線性互補(bǔ)問題，其中

經(jīng)過計(jì)算可知，矩陣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é)成分，廣泛存在于動(dòng)植物和礦物中，以蒽醌類居多，萘醌和苯醌類次之，且大多具有重要的生物活性。

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

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

算例9：考慮線性互補(bǔ)問題，其中

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

算例10：考慮線性互補(bǔ)問題，其中

經(jīng)過計(jì)算可知，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的正定性。

對(duì)于任意的 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)過計(jì)算可知，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)于線性互補(bǔ)問題，常見的求解方法是針對(duì)單調(diào)線性互補(bǔ)問題的，而非單調(diào)的線性互補(bǔ)問題（即矩陣M非半正定）方面的研究較少，算例9～11可以用來測試算法的適用范圍，即對(duì)非單調(diào)的線性互補(bǔ)問題，算法是否適用。

表1 線性互補(bǔ)算例特征分析

1.4 無解的線性互補(bǔ)問題的算例

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

算例12：考慮線性互補(bǔ)問題，其中

算例13：考慮線性互補(bǔ)問題，其中

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

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

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

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

算例14：考慮線性互補(bǔ)問題，其中

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

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

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

算例16：考慮線性互補(bǔ)問題，其中

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

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

2 非線性互補(bǔ)問題常用的算例

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

2.1 有唯一解的非線性互補(bǔ)問題的算例

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

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

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

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

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

2.2 有多個(gè)解的非線性互補(bǔ)問題的算例

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

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

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

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

3 結(jié)束語

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

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

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

［3］ 雍龍泉，鄧方安.線性互補(bǔ)問題中矩陣正定性判別的兩點(diǎn)注記［J］.吉首大學(xué)學(xué)報(bào)（自然科學(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］ 屈彪，王長玨，張樹霞.一種求解非線性互補(bǔ)問題的方法及其收斂性［J］.計(jì)算數(shù)學(xué)，2006（3）：247-258.

［10］雍龍泉.基于多目標(biāo)優(yōu)化算法求解非線性互補(bǔ)問題［J］.中南大學(xué)學(xué)報(bào)（自然科學(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é)基金項(xiàng)目（11401357）；陜西理工學(xué)院教學(xué)改革研究項(xiàng)目（SLGYJG1416）

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