求解互補問題的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