求解互补问题的New ton-K rylov-Schwarz算法*

何霞辉,李庆国 ,杨海建

(1.湖南大学机械与运载工程学院,湖南长沙 410082;2.湖南大学 数学与计量经济学院,湖南 长沙 410082)

求解互补问题的New ton-K rylov-Schwarz算法*

何霞辉1,李庆国2†,杨海建2

(1.湖南大学机械与运载工程学院,湖南长沙 410082;2.湖南大学 数学与计量经济学院,湖南 长沙 410082)

提出一类并行的半光滑New ton-K ry lov-Schw arz算法来解决互补问题.利用半光滑函数,通过解大规模稀疏非线性代数方程组,得到此类优化问题的数值解.计算结果表明此算法的可行性.

并行算法;互补问题;半光滑函数;New ton-K rylov-Schwarz;Schwarz预处理

互补问题在最优控制、机械工程、物理、经济管理等领域有着十分广泛的应用[1-5],该类问题非线性程度高,光滑程度低;计算规模大,精度要求高,需要并行计算,尤其是大规模并行计算.因此,对其在大规模并行计算下的数值解的研究是一个难度大的工作,也是工程人员和计算数学工作者的研究热点之一.近年来,由于各种新的数值解法的出现,使得互补问题得到很大的发展,其中,半光滑方法发挥了重要作用.半光滑方法是先通过把互补问题转化为半光滑方程组,然后采用广义牛顿法来解决这个方程组.本文将继续这方面的工作,通过一类并行半光滑New ton-K ry lov-Schw arz算法用来解决由互补问题所生成的非线性方程组的数值解.这类算法包括3部分:非精确半光滑牛顿法,K ry lov子空间法和Schwarz预处理技术.数值结果表明了这类算法的优越性.

1 预备知识

本文考虑如下互补问题:

式中:F=(F1,…,Fn)T∶Rn→Rn为一连续可导的函数,φ∈Rn为一给定向量.

半光滑算法是建立在互补问题的另一种表达方式

显然,一向量u*∈Rn是问题(1)的解且仅当它是问题(2)的解.若运用牛顿法来解式(2),则导致了一类半光滑算法.

接下来,考虑两类不同的 φ函数.一类是Fischer-Burmeister函数

用半光滑牛顿法解问题(2)是一个迭代的过程.假设u0是一个初始点,那么在第k步,uk是下面问题的解

式中:J k为F(uk)的一个广义雅可比矩阵.对于Fischer-Burmeister函数和M inimum函数.广义雅可比矩阵Jk有如下格式:

类似的,用M inim um 函数,有

式中:ηr∈[0,1)为相对误差,ηa∈ [0,1)为绝对误差.牛顿法的非精确是反映在不精确地计算雅可比系统.在牛顿法中最费时的步骤就是解问题(7).整个算法的可扩展性主要取决于如何取雅可比矩阵的预处理.代替解问题(7),解如下的右预处理问题:

令 Ω为一有界的开区域,为了定义Schwarz预处理算子,需要获得Ω的一个重叠划分.首先区域Ω被分成Ns个小的非重叠的子区域Ω1,1,…,Ns,然后扩张每个子区域到 Ωδi,也就是 Ωi⊂Ωδi⊂Ω.δ＞0定义为 ∂Ωδ

i和∂Ωi之间的最小距离.令 N和N i分别表示相对于Ω和Ωδi的网格点数.令J是如下雅可比系统的雅可比矩阵:

式中:B-1i是J i的逆矩阵.

2 数值实验

考虑如下障碍问题[6-7]:求u(x)使得

式中:λ≥0和边界条件是u(x)=0.在本文中 Φ =-4,λ=1.在一致网格上用2阶5点有限差分法来离散上述障碍问题.牛顿迭代法的初始点是障碍Φ.停止牛顿迭代当且仅当满足以下条件:

用GMRES(30)来解雅可比系统(8),并且停止迭代当且仅当满足以下条件:

每个子问题是用LU分解来解的.在这节中,“np”表示处理器的个数;“INB”表示牛顿步的迭代次数;“RAS”表示平均每个牛顿步的线性迭代次数;t表示总的计算时间.

在表1中,比较了两个不同的半光滑函数.从表中可以看到:相对于Fischer-Burmeister函数, M inimum函数是一个更好的选择,因为它的牛顿迭代次数和时间更少.在文[8]中,Kanzow计算了同一问题并且ILU预处理算子和CG来解相应的线性系统,其平均线性迭代次数非常多.因此,对于问题(9)来说,用限制加性 Schwarz预处理算子和GMRES来解相应的线性系统是一个更好的选择.

表1 问题(9)的计算结果Tab.1 The numerica l resu lt of problem(9)

[1] COTTLE R,PANG JS,STONE R.The linear complementarity p roblem[M].Boston:Academ ic Press,1992:168-320.

[2] FERRISM C,PANG JS.Engineering and econom ic applications of com plementarity problems[J].SIAM Review,1997 (39):669-713.

[3] HARKER P T,PANG JS.Finite-dimensionalvariational inequality and nonlinear com plem en tarity problems:a su rvey of theory,algorithm s and ap plications[J].M athematical Programming,1990(48):161-220.

[4] YANG H J,LIQ G,XU H R.A multiplicative schw arz iteration scheme for solving the linear com plem entarity problem w ith an H-m atrix[J].Linear A lgeb ra and its Applications, 2009(430):1058-1098.

[5] BERTSEKASD P.Constrained op tim ization and lag rangemultipliermethods[M].New York:Academ ic Press,1982:415-600.

[6] FACCHINEI F,KANZOW C.A nonsm ooth inexact new ton method for the solution of large-scale nonlinear complementarity problems[J].M athematical Prog ramm ing,1997(76):493-512.

[7] SM ITH B,BJORSTAD P,GROPP W.Domain decomposition:parallelmu ltilevelmethods for elliptic partial differential equations[M].Camb ridge:Cam bridge University Press, 1996:388-460.

[8] KANZOW C.Inexact sem ismooty new ton methods for largescale complemen tarity problem s[J].Optim ization M ethods and Softw are,2004(19):309-325.

New ton-Krylov-Schwarz Algorithm for Complementarity Problems

H E Xia-hui1,LIQing-guo2†,YANG Hai-jian2

(1.College of Mechanical and Vehicle Engineering,Hunan Univ,Changsha,Hunan 410082,China; 2.Co llege of Mathcmatics and Econom ctrics,H unan Univ,Changsha,H unan 410082,China)

We presented some parallel New ton-K ry lov-Schwarz(NKS)algorithm to solving the comp lementarity problems.Using semismooth function,the so lution of the optim ization p rob lem can be obtained by solving a large sparse non linear system of algebraic equations.Numerical results show that the efficiency can be achieved by the proposedmethod.

parallel algorithm s;comp lementatity problem;sem ismooth function;New ton-K ry lov-Schw arz;Schwarz p reconditioners

O241.82

A

1674-2974(2010)12-0090-03 *

2010-02-15

国家自然科学基金资助项目(10771056)

何霞辉(1981-),女,湖南益阳人,湖南大学博士研究生

†通讯联系人,E-mail:liqingguoli@yahoo.com.cn