一個新的求解線性互補問題的罰函數(shù)方法

李 園,韓海山,楊丹丹

(內(nèi)蒙古民族大學 數(shù)學學院,內(nèi)蒙古 通遼 028043)

一個新的求解線性互補問題的罰函數(shù)方法

李 園,韓海山,楊丹丹

(內(nèi)蒙古民族大學 數(shù)學學院,內(nèi)蒙古 通遼 028043)

線性互補問題LCP(A;b)中矩陣A的結構無論對線性互補問題解的存在性、唯一性,還是對算法的收斂性，都有著非常密切的關系.進一步將P-矩陣線性互補問題的非線性罰方程進行推廣,證明了線性互補問題的矩陣A在一定假設的基礎上,下對角元素均大于等于零時非線性罰方程的解指數(shù)次收斂到線性互補問題的解.

運籌學；線性互補問題；P-矩陣；非線性罰方程；收斂

線性互補問題是運籌學的一個重要分支,廣泛應用在自然科學、交通控制、管理科學、經(jīng)濟均衡和工程計算等諸多領域,正因為如此，線性互補問題成為數(shù)學規(guī)劃和計算數(shù)學中的一個十分熱門的研究領域.許多學者對求解線性互補問題的算法進行了深入的研究,提出了許多算法,可歸納為:投影算法、內(nèi)點法、光滑牛頓法、不動點算法、近似點算法、非光滑牛頓法、矩陣分裂法等[1-4].進一步研究和提出線性互補問題的新型算法不僅具有理論意義,而且也具有重要的實際價值.

本文考慮如下線性互補問題(簡記作LCP(A;b)):求向量x=(x1,x2,…,xn)T∈Rn,使得:

Ax-b≤0;x≤0;(Ax-b)Tx=0,

(1)

其中A∈Rn×n;b∈Rn.

令K={y∈Rn|y≤0},則線性互補問題(1)等價于如下的變分不等式問題:求向量x∈K,使得對任意的y∈K,滿足:

(y-x)TAx≥(y-x)Tb.

(2)

文獻[6]構造了如下關于線性互補問題(1)的非線性罰方程：求xλ∈Rn,使得:

(3)

關于線性互補問題(1)的相對應的非線性罰方程(3)的研究,已經(jīng)取得了如下成果：1984年,Glowinski[4]研究了Rn中變分不等式(2)的形如(3)式的非線性罰方程,證明了在矩陣A對稱正定的情況下罰方程的收斂性.2006年,Wang等人[5]將美國期權問題轉化成一線性互補問題,利用非線性罰方程(3)對其進行了求解,證明了線性互補問題的矩陣為正定時罰方程的解收斂到互補問題的解.2008年,Yang等人[6]在線性互補問題(1)的矩陣為正定，主對角元素大于零,其余元素均小于等于零的條件下證明了當懲罰因子趨向于無窮大時非線性罰方程(3)的解指數(shù)次收斂到線性互補問題的解.同年,Wang等人[7]提出了一個帶有擾動項的求解非線性拋物型互補問題的非線性罰方程,但是罰方程的解收斂到互補問題的解仍需正定性假設.鑒于上述罰函數(shù)方法的收斂性均依賴于線性互補問題的矩陣的正定性假設.李園等人[8-9]將上述罰函數(shù)方法進行了推廣,在線性互補問題的矩陣為嚴格行對角占優(yōu)的上三角形P-矩陣的條件下證明了非線性罰方程(3)的解指數(shù)次收斂到線性互補問題(1)的解.本文進一步將李園等人[9]的P-矩陣線性互補問題的非線性罰方程進行推廣,證明了線性互補問題(1)的矩陣A在文獻[9]的假設基礎上,下對角元素均大于等于零時非線性罰方程(3)的解收斂到線性互補問題(1)的解,并且收斂速率是指數(shù)次.

1 預備知識

定義1[1]矩陣A=(aij)∈Rn×n是P-矩陣的充要條件是A的所有主子式均大于零.

關于P-矩陣的性質(zhì),有如下結論：

引理1[3]A∈Rn×n是P-矩陣的充要條件是:存在一常數(shù)c>0,使得對于任意的向量x∈Rn,存在一下標k=k(x),1≤k≤n,滿足:

xk(Ax)k≥c‖x‖2.

其中xk表示x的第k個分量,(Ax)k表示Ax的第k個分量.

關于矩陣的F-范數(shù)‖·‖F(xiàn)與向量的歐式范數(shù)‖·‖的相容性,有如下結論：

引理2[10]設A∈∈Rn×n，x∈∈Rn,則：‖Ax‖≤‖A‖F(xiàn)·‖x‖.

2 非線性罰方程(3)解的性質(zhì)

本節(jié)將討論非線性罰方程(3)的解的性質(zhì),給出非線性罰方程(3)的解收斂于線性互補問題(1)的解的充分條件.首先對線性互補問題(1)中的矩陣A作如下假設:

(A1)A是P-矩陣;

(A3)矩陣A的奇異值均大于1.

在假設(A1)的條件下,線性互補問題(1)有唯一解.根據(jù)上面的假設,首先建立下面的定理.

定理1 設x=(u1,u2,…,un)T∈Rn是非線性罰方程(3)的解,若x滿足下面條件之一:

(i)xλ的分量均小于等于零;

(ii)xλ僅有一個正分量,其余分量均小于等于零;

(iii)xλ有m(2≤m

(4)

(5)

證明(i):若xλ的分量均小于等于零,此時[xλ]+=(0,0,…,0)T于是‖[xλ]+‖p=0;‖[xλ]+‖=0,所以式(4)和(5)顯然成立;下面僅證明情況(iii)，對于情況(ii)可類似證明.

(6)

A11=I1+L1+U1=L1+(I1+U1)=L1+K1,

其中I1,L1和U1分別是A11的對角、下三角和上三角矩陣,K1=L1+U1,則:

(7)

對式(7)應用H?lder不等式,得到:

‖[xλ]+‖2,

于是:

c1‖[xλ]+‖2≤[xλ

即:

不等式兩端同時開方后，得:

證畢.

由定理1,可以得到下面的收斂性定理.

定理2 設x∈Rn和x∈Rn分別是線性互補問題(1)和非線性罰方程(3)的解,其中x滿足定理1的條件.如果rλ=x+[xλ]-=(r1,r2,…,rn)T≤0且對其任意兩個不為零的分量ri和rj均有|ri|≥|rj|,則存在一個與n,x,xλ和λ均無關的正數(shù)C,使得:

(8)

其中[xλ]-=-min{xλ,0},λ和k是式(3)中定義的參數(shù).

證明由前面[xλ]+和[xλ]-的定義,有xλ=[xλ]+-[xλ]+,于是:

隨著網(wǎng)絡的發(fā)達，電子商務漸漸火熱起來，這一節(jié)日就被商家所利用，以光棍為嚎頭制造單身人士要在這一天購物的氣氛。2009年淘寶商城的管理層首次將11月11日選用為淘寶購物狂歡節(jié)，造就了高達0.5億元的銷售額，從此，“雙十一”被越來越多的消費者銘記，“雙十一”所產(chǎn)生的銷售額逐年攀升。這種從節(jié)日到節(jié)日的文化轉型為“雙十一”的成功塑造解決了尤為關鍵的一步，讓眾多消費者尤其是作為新世紀知識分子的大學生一代以最快的速度接受并記住。

x-xλ=x+[xλ]--[xλ]+=rλ-[xλ]+,

(9)

其中rλ=x+[xλ]-.令υ=x-rλ,由rλ的定義知υ=x-rλ=-[xλ]-≤0,于是υ∈K,在式(2)中令y=υ后,得:

(10)

(11)

將式(11)和式(12)相加后,有:

(12)

而:

(13)

將式(9)代入式(13)中,得:

(14)

設A=I+L+U=L+(I+U)=L+K,其中I;L和U分別是矩陣A的對角、下三角和上三角矩陣,K=I+U.于是:

(15)

根據(jù)引理2,不等式(15)的右端:

‖rλ‖·‖A[xλ]+‖≤‖rλ‖·‖A‖F(xiàn)·‖[xλ]+‖

(16)

又由引理1,有:

‖rλ‖2,

(17)

其中c2是常數(shù).

由式(15)～(17),得到:

c2‖rλ‖2≤‖rλ‖·‖A‖F(xiàn)·‖[xλ]+‖,

所以:

(18)

綜合式(5),(9),(18)和三角不等式,得:

證畢.

3 結語

本文進一步將李園等人[9]的P-矩陣線性互補問題的非線性罰方程進行推廣,證明了線性互補問題(1)的矩陣A在文獻[9]的假設基礎上,下對角元素均大于等于零時非線性罰方程(3)的解收斂到線性互補問題(1)的解,并且任然具有指數(shù)次的收斂速率,進一步改進了罰函數(shù)方法.

[1] Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problems[M].Aca-demic Press,San Diego,CA,1992.

[2] Facchinei F, Pang J S. Finite-dimensional variational inequalities and complementar-ity problems[M].New York: Springer,2003.

[3] 韓繼業(yè),修乃華,戚厚鐸.非線性互補理論與算法[M].上海:上?？茖W技術出版社,2006.

[4] Glowinski R. Numerical methods for nonlinear variational problems[M].New York:Springer-Verlag,1984.

[5] Wang S,Yang X Q,Teo K L.Power penalty method for a linear complementarity problems arising from American option valuation[J].Journal of Optimization Theory and Applications,2006,129(2):227-254.

[6] Wang S,Yang X Q.Power penalty method for linear complementarity problems[J].Operations Research Letters,2008,36(2):211-214.

[7] Wang S,Huang C S.A power penalty method for solving a nonlinear parabolic complementarity problem[J].Nonlinear Analysis,2008,69(4):1125-1137.

[8] Li Y,Han H S,Li Y M,et al.Convergence analysis of power penalty method for three dimensional linear complementarity problems[J].Intelligent Information Management Systems and Technologies,2009,5(3):191-198.

[9] 李園,楊丹丹,韓海山.線性互補問題罰函數(shù)方法的收斂性分析[J].運籌與管理,2012,21(5):129-134.

[10] 張賢達.矩陣分析與應用[M].北京:清華大學出版社,2004.

聲明

本刊已許可中國學術期刊(光盤版)電子雜志社在中國知網(wǎng)及其系列數(shù)據(jù)庫產(chǎn)品中，以數(shù)字化方式復制、匯編、發(fā)行、信息網(wǎng)絡傳播本刊全文。該著作使用費及相關稿酬，本刊均用作為作者文章發(fā)表、出版、推廣交流(含信息網(wǎng)絡)以及贈送樣刊之用途，即不再另行向作者支付。凡作者向本刊提交文章發(fā)表之行為即視為同意我刊上述聲明。

湖北民族學院學報編輯部

ANewPenalizedMethodforSolvingLinearComplementarityProblems

LI Yuan,HAN Hai-shan,YANG Dan-dan

(College of Mathematics,Inner Mongolia University for Nationalities,Tongliao 028043,China)

The structure of matrix A in the linear complementarity problem LCP(A;b) plays an important role in both the existence, uniqueness of the solution and the convergence of algorithms. In this paper,we further generalize the nonlinear penalized equation for solvingP-matrix LCP(A;b) and prove that the nonlinear penalized equation converges to that of the LCP(A;b) at an exponential rate under the condition that the lower diagonal elements of matrixAare greater than or equal to zero based on Li′s hypothesis.

operations research;linear complementarity problem;P-matrix;nonlinear penalized equation;convergence

2013-07-29.

內(nèi)蒙古自然科學基金項目(2011MS0114).

李園(1985- ),男,講師,主要從事變分不等式與互補問題的研究.

O221.2

A

1008-8423(2013)03-0262-05