基于極大熵理論求解線性互補問題

楊丹丹，韓海山，李 園

(內蒙古民族大學 數(shù)學學院，內蒙古 通遼 028043)

基于極大熵理論求解線性互補問題

楊丹丹，韓海山，李 園

(內蒙古民族大學 數(shù)學學院，內蒙古 通遼 028043)

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

線性互補問題；絕對值方程；極大熵；不動點迭代

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

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

(1)

簡記作LCP(A,q).

1 問題轉換

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

(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)問題等價于求x∈Rn滿足絕對值方程:

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

(3)

由文獻[5]已知φp(xi)具有如下兩個性質:

性質1：當p>q時，φp(xi)>φq(xi) ，且當p→0 時，φp(xi)以φ(xi) 為極限；

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

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

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

(4)

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

2 算法及收斂性分析

問題(4)是一個典型的不動點問題，下面給出求解問題(4)的迭代算法.算法步驟如下：

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

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

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

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

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

3 數(shù)值試驗

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

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

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

表1 不同初值x0的計算結果

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

4 結語

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

[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è),修乃華,戚厚鐸.非線性互補理論與算法[M].上海:上?？茖W技術出版社,2006.

[4] 李園,楊丹丹,韓海山.線性互補問題罰函數(shù)方法的收斂性分析[J].運籌與管理,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].北京：科學出版社，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.

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

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

O221.2

A

1008-8423(2013)03-0260-02