求解互補(bǔ)問(wèn)題的New ton-K rylov-Schwarz算法*

何霞輝,李慶國(guó) ,楊海建

(1.湖南大學(xué)機(jī)械與運(yùn)載工程學(xué)院,湖南長(zhǎng)沙 410082;2.湖南大學(xué) 數(shù)學(xué)與計(jì)量經(jīng)濟(jì)學(xué)院,湖南 長(zhǎng)沙 410082)

求解互補(bǔ)問(wèn)題的New ton-K rylov-Schwarz算法*

何霞輝1,李慶國(guó)2?,楊海建2

(1.湖南大學(xué)機(jī)械與運(yùn)載工程學(xué)院,湖南長(zhǎng)沙 410082;2.湖南大學(xué) 數(shù)學(xué)與計(jì)量經(jīng)濟(jì)學(xué)院,湖南 長(zhǎng)沙 410082)

提出一類并行的半光滑New ton-K ry lov-Schw arz算法來(lái)解決互補(bǔ)問(wèn)題.利用半光滑函數(shù),通過(guò)解大規(guī)模稀疏非線性代數(shù)方程組,得到此類優(yōu)化問(wèn)題的數(shù)值解.計(jì)算結(jié)果表明此算法的可行性.

并行算法;互補(bǔ)問(wèn)題;半光滑函數(shù);New ton-K rylov-Schwarz;Schwarz預(yù)處理

互補(bǔ)問(wèn)題在最優(yōu)控制、機(jī)械工程、物理、經(jīng)濟(jì)管理等領(lǐng)域有著十分廣泛的應(yīng)用[1-5],該類問(wèn)題非線性程度高,光滑程度低;計(jì)算規(guī)模大,精度要求高,需要并行計(jì)算,尤其是大規(guī)模并行計(jì)算.因此,對(duì)其在大規(guī)模并行計(jì)算下的數(shù)值解的研究是一個(gè)難度大的工作,也是工程人員和計(jì)算數(shù)學(xué)工作者的研究熱點(diǎn)之一.近年來(lái),由于各種新的數(shù)值解法的出現(xiàn),使得互補(bǔ)問(wèn)題得到很大的發(fā)展,其中,半光滑方法發(fā)揮了重要作用.半光滑方法是先通過(guò)把互補(bǔ)問(wèn)題轉(zhuǎn)化為半光滑方程組,然后采用廣義牛頓法來(lái)解決這個(gè)方程組.本文將繼續(xù)這方面的工作,通過(guò)一類并行半光滑New ton-K ry lov-Schw arz算法用來(lái)解決由互補(bǔ)問(wèn)題所生成的非線性方程組的數(shù)值解.這類算法包括3部分:非精確半光滑牛頓法,K ry lov子空間法和Schwarz預(yù)處理技術(shù).數(shù)值結(jié)果表明了這類算法的優(yōu)越性.

1 預(yù)備知識(shí)

本文考慮如下互補(bǔ)問(wèn)題:

式中:F=(F1,…,Fn)T∶Rn→Rn為一連續(xù)可導(dǎo)的函數(shù),φ∈Rn為一給定向量.

半光滑算法是建立在互補(bǔ)問(wèn)題的另一種表達(dá)方式

顯然,一向量u*∈Rn是問(wèn)題(1)的解且僅當(dāng)它是問(wèn)題(2)的解.若運(yùn)用牛頓法來(lái)解式(2),則導(dǎo)致了一類半光滑算法.

接下來(lái),考慮兩類不同的 φ函數(shù).一類是Fischer-Burmeister函數(shù)

用半光滑牛頓法解問(wèn)題(2)是一個(gè)迭代的過(guò)程.假設(shè)u0是一個(gè)初始點(diǎn),那么在第k步,uk是下面問(wèn)題的解

式中:J k為F(uk)的一個(gè)廣義雅可比矩陣.對(duì)于Fischer-Burmeister函數(shù)和M inimum函數(shù).廣義雅可比矩陣Jk有如下格式:

類似的,用M inim um 函數(shù),有

式中:ηr∈[0,1)為相對(duì)誤差,ηa∈ [0,1)為絕對(duì)誤差.牛頓法的非精確是反映在不精確地計(jì)算雅可比系統(tǒng).在牛頓法中最費(fèi)時(shí)的步驟就是解問(wèn)題(7).整個(gè)算法的可擴(kuò)展性主要取決于如何取雅可比矩陣的預(yù)處理.代替解問(wèn)題(7),解如下的右預(yù)處理問(wèn)題:

令 Ω為一有界的開(kāi)區(qū)域,為了定義Schwarz預(yù)處理算子,需要獲得Ω的一個(gè)重疊劃分.首先區(qū)域Ω被分成Ns個(gè)小的非重疊的子區(qū)域Ω1,1,…,Ns,然后擴(kuò)張每個(gè)子區(qū)域到 Ωδi,也就是 Ωi?Ωδi?Ω.δ＞0定義為 ?Ωδ

i和?Ωi之間的最小距離.令 N和N i分別表示相對(duì)于Ω和Ωδi的網(wǎng)格點(diǎn)數(shù).令J是如下雅可比系統(tǒng)的雅可比矩陣:

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

2 數(shù)值實(shí)驗(yàn)

考慮如下障礙問(wèn)題[6-7]:求u(x)使得

式中:λ≥0和邊界條件是u(x)=0.在本文中 Φ =-4,λ=1.在一致網(wǎng)格上用2階5點(diǎn)有限差分法來(lái)離散上述障礙問(wèn)題.牛頓迭代法的初始點(diǎn)是障礙Φ.停止牛頓迭代當(dāng)且僅當(dāng)滿足以下條件:

用GMRES(30)來(lái)解雅可比系統(tǒng)(8),并且停止迭代當(dāng)且僅當(dāng)滿足以下條件:

每個(gè)子問(wèn)題是用LU分解來(lái)解的.在這節(jié)中,“np”表示處理器的個(gè)數(shù);“INB”表示牛頓步的迭代次數(shù);“RAS”表示平均每個(gè)牛頓步的線性迭代次數(shù);t表示總的計(jì)算時(shí)間.

在表1中,比較了兩個(gè)不同的半光滑函數(shù).從表中可以看到:相對(duì)于Fischer-Burmeister函數(shù), M inimum函數(shù)是一個(gè)更好的選擇,因?yàn)樗呐ｎD迭代次數(shù)和時(shí)間更少.在文[8]中,Kanzow計(jì)算了同一問(wèn)題并且ILU預(yù)處理算子和CG來(lái)解相應(yīng)的線性系統(tǒng),其平均線性迭代次數(shù)非常多.因此,對(duì)于問(wèn)題(9)來(lái)說(shuō),用限制加性 Schwarz預(yù)處理算子和GMRES來(lái)解相應(yīng)的線性系統(tǒng)是一個(gè)更好的選擇.

表1 問(wèn)題(9)的計(jì)算結(jié)果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

國(guó)家自然科學(xué)基金資助項(xiàng)目(10771056)

何霞輝(1981-),女,湖南益陽(yáng)人,湖南大學(xué)博士研究生

?通訊聯(lián)系人,E-mail:liqingguoli@yahoo.com.cn