楊丹丹，韓海山，李 園

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

基于極大熵理論求解線性互補(bǔ)問題

楊丹丹，韓海山，李 園

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

給出了線性互補(bǔ)問題的一種解法，在假設(shè)A的特征值大于1時(shí)，線性互補(bǔ)問題等價(jià)轉(zhuǎn)化為絕對值方程問題，利用極大熵函數(shù)給出了求解此類絕對值問題的光滑滑迭代算法，并證明了算法是收斂的，數(shù)值實(shí)驗(yàn)表明此方法的有效性.

線性互補(bǔ)問題；絕對值方程；極大熵；不動(dòng)點(diǎn)迭代

線性互補(bǔ)問題是運(yùn)籌學(xué)與計(jì)算數(shù)學(xué)的一個(gè)交叉研究領(lǐng)域,已經(jīng)廣泛應(yīng)用于力學(xué)、交通、經(jīng)濟(jì)、金融、控制等領(lǐng)域中出現(xiàn)的許多數(shù)學(xué)模型.在20世紀(jì)90年代，研究線性互補(bǔ)問題的求解方法已達(dá)到了高潮.通過近幾十年的發(fā)展，人們不僅改進(jìn)和豐富了線性互補(bǔ)問題的理論和方法的研究，而且還提出了許多有效的算法[1-4]，例如: 多重分裂法、投影法、光滑牛頓法、非光滑牛頓法、松弛法、內(nèi)點(diǎn)法、非光滑方程法等. 進(jìn)一步掌握和研究互補(bǔ)問題的各類算法不僅具有理論意義, 而且具有實(shí)際意義.

設(shè)A∈Rn×n,q∈Rn,線性互補(bǔ)問題是指:求z=(z1,z2,…,zn)∈Rn, 使得:

(1)

簡記作LCP(A,q).

1 問題轉(zhuǎn)換

線性互補(bǔ)問題可以等價(jià)轉(zhuǎn)化為絕對值方程，即LCP(A,q)?AVE,引進(jìn)變量ω=Az+q將式(1)等價(jià)的改寫為:

(2)

令ω=|x|-x,z=|x|+x，由于A的特征值大于1，故(A+I)-1存在，從而：

ω=Az+q?x=(A+I)-1(I-A)|x|-(A+I)-1q

顯然求解LCP(A,q)問題等價(jià)于求x∈Rn滿足絕對值方程:

x=(A+I)-1(I-A)|x|-(A+I)-1q

(3)

由文獻(xiàn)[5]已知φp(xi)具有如下兩個(gè)性質(zhì):

性質(zhì)1：當(dāng)p>q時(shí)，φp(xi)>φq(xi) ，且當(dāng)p→0 時(shí)，φp(xi)以φ(xi) 為極限；

性質(zhì)2：?p>0,0≤φp(xi)-φ(xi)≤pln2.

則公式(3)可以轉(zhuǎn)換為:

x=(A+I)-1(I-A)φp(x)-(A+I)-1q

(4)

其中φp(x)=(φp(x1),φp(x2),…,φp(xn))T.

2 算法及收斂性分析

問題(4)是一個(gè)典型的不動(dòng)點(diǎn)問題，下面給出求解問題(4)的迭代算法.算法步驟如下：

a)任意選取一個(gè)初始點(diǎn)x0∈Rn,允許誤差ε>0及參數(shù)p>0,k:=0;

b)計(jì)算xk+1=f(xk)=(A+I)-1(I-A)φp(xk)-(A+I)-1q；

c)若‖xk+1-xk‖≤ε，則停止，得到解x*=xk+1；否則轉(zhuǎn)入步驟b).

迭代公式(4)的Jacobi矩陣為Mk=(A+I)-1(I-A)Λk，其中:

引理1 由算法所產(chǎn)生的序列{x1,x2,x3,…}收斂，且其極限就是問題(4)的解.

3 數(shù)值試驗(yàn)

數(shù)值試驗(yàn)運(yùn)用Matlab 7.0進(jìn)行編程計(jì)算，下面的計(jì)算中參數(shù)選取如下：ε=1.0e-6，p=0.1或者p=0.01.

例1 求解線性互補(bǔ)問題LCP(A,q)，其中:

調(diào)用本文的算法，其中選取n=4,p=0.01，T/s代表迭代時(shí)間，單位為秒，選用不同的初值x的結(jié)果見表1.

表1 不同初值x0的計(jì)算結(jié)果

通過上表可以看出本文的迭代法解線性互補(bǔ)問題是十分快速且有效的.

4 結(jié)語

本文提出了求解線性互補(bǔ)問題的一種光滑化不動(dòng)點(diǎn)迭代法，并且證明了該迭代法是收斂的，本算法具有格式簡單，存儲(chǔ)量小和易于在計(jì)算機(jī)上實(shí)現(xiàn)等優(yōu)點(diǎn)，為此本文給出的迭代.

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

[2] Facchinei F,Pang J S.Finite-dimensional variational inequalities and complementarity problems[M].New York:Vol. I and II. Springer,2003.

[3] 韓繼業(yè),修乃華,戚厚鐸.非線性互補(bǔ)理論與算法[M].上海:上海科學(xué)技術(shù)出版社,2006.

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

[5] LI X S.An efficient method for non-differentiable optimization problem[J].Science in China-Series,1994,24(4):371-377.

[6] 李慶陽，莫孜中，祁力群.非線性方程組的數(shù)值解法[M].北京：科學(xué)出版社，1999.

SolutionofLinearComplementarityBasedonMaximumEntropyTheory

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

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

In this paper,a method of solution for linear complementary problem is given, under the assumption that the characteristic of the value is greater than 1, the equivalent linear complementary problem into absolute value equation, using the maximum entropy function gives smooth iterative algorithm for solving this kind of absolute value problems ,and proves that the algorithm is convergent and numerical experiments show that the method is effective.

linear complementarity problem; absolute value equation；maximum entropy； fixed point Iterative method

2013-07-29.

內(nèi)蒙古自然科學(xué)基金項(xiàng)目(2011MS0114).

楊丹丹(1984- ),女,碩士生,講師,主要從事變分不等式與互補(bǔ)問題的研究.

O221.2

A

1008-8423(2013)03-0260-02