APPLICATION OF AN ITERATIVE METHOD TO A CLASS OF SEMILINEAR COMPLEMENTARITY PROBLEMS

TRU Mathematics 23−1〔1987）

APPLI CATION OF AN ITERATIVE METH⊃D TO A CLASS OF

       α〕MPLEMENTARITY PROBLEMS

SEMILINEAR

Hideho OGASMARA and Kenj i

HAYASHI

（Recevied APri1 11，1987） 1． Introduct ion     There are several iterative Inethods of successive overrelaxation （SOR） type for solving the line ar comp lementarity problem （LCP） of finding a vector xsuch that       ’ x ≧ 0， Mx ≠q ≧ 0， 0フ2d

ノ侮oc≠qノニ0，

where M・i・agiv・n… m・t・i・， q i・agi・・n。−vect。。 and、。T d。mt。、 the transpose ofコc．      Some general sufficient conditions fbr the corrvergence of．abroad class of iteration schemes， under symmetry assumption on M， have been given by Mangasarian［3L  Fbr nonsymmetric cases， certain sufficient conditions fbr the comvergence o f a紋）ve s chemes have been discussed in ［1，4，5】．     This paper is concerned with an iterative method f6r so lving the nonlinear co町〕lement arity problem o f the fbrm

x≧0，

Frx）＝Mx≠q （x） ≧0， αnd oo『Fω＝0， where M is a 9iv・n・・n symm・t・i・m・t・ix・nd gパηパηi・agiv・n m・pPing．      Since M is a linear operator， the nonlinear mapping F＝M≠（7 may be called semilinear in accordance with the classification of differential equat ions． There fbre， we shall re fer here to this problem as the serniline ar cornp lement arity problem 〔SLCP）． In part i cular， we de al with the case when q is the gradient mapping of a real−valued function φ， i．e．， q ＝ ▽φ．      弓1㎝ing［51 in the lin・ar case・w・int・・duce t｝…1gQ・it㎞i・mapPing・A・ Rn ・ 2R d・fi・・d by

〔1．1〕 A （x）

ニ｛yεRnl

_{uニBy ＋Ox＋q（x） ≧ O， 召 ≧．Dx，}

uT （y−Dりc）＝0｝，

162

H．eGASMARA AND K． HAIYASHI where B and 6「are a splitting of M， i．e．，M＝B≠C， and Z）is a diagPnal matrix with O≦D．．＜ヱ． It is clear that x solves the SLCP if and only if x       z．T is a fi｝ed point of A， i．e．，xεA（x）． Thisユeads to an a1．gprit㎞fbr the SI．CP as fo llows： St。，ti。g f，。＿y。。m。9。ti。。 vect。r。°， the sequence｛xk｝i・9・n・rat・d iterative ly by       ’ 〔1．2〕 。，k＋1，Arみf。r 。ll k≧0．        k＋2        is produced by solving the fbllowing I・CP_{Actually， the successor oc}

subprob16m

（1．3〕  u＝by≠Cxk≠q Cxk）≧0， y≧Dxk，”T（y−D⑳たノニ0．

     In Section 2， it is sI℃m that t｝re algprit㎞臼．2〕generates the sequen㏄   k    ｝ such that each o f its accumulation poinヒs so lves the SLCP and it also｛⑳        k        ｝which converges to the unique solution o f the SLCP_{generates the sequence ｛x} lmder sUital〕1e conditions． A computaヒional algt）rit㎞fbr solving the SLCP is proposed in Section 3． Particularly， the modification of Mangasarian，s scheme is used in order to so lve the LCP su1堀）robユem （1．3〕． Finally， in Section 4， some numerical e）∼periments on the obstacle problem， which is one o f free boundary problems fbr differential equations， are reported． 2．〔bnvergence Properties of the Algρrit㎞ic Mapping      In this se（tion， we shall discuss the convergence properties o f the a1即rit㎞〔1．2）to the solution of the SLCP． We assume througbOut this paper that the matrix M is s）㎜etric and qごRn今Rn is a gradient mapping． The functionφis always used fc）r the mapping such that ▽φ＝q． Also， f and F are

…dfb・．

￨・。，％。，／2・φr。，元and F・▽了， respecti・・1y．1、et・AC・）be as defired in（1．1）． In what fbllows， A （x）will be assuned ru）ne呵）ty’fbr any mmegative vector x． Fbr ensuring this， it suffi ces that the matrix B， one part of the splitting of〃， be a Q−matrix．      ’   ・      Be fbre stat ing convergβnce properties，we begin by preparing the fb llowing le㎜a． 〔2．1〕 Mpmth 2．1． ip（a）

  5叩ρose thatψごRn→1隅deffned痴

＝ノrB一σノ。／2一岨

i…ntinu…姻苛・…ti・カZ・・πRηα㎡翻碗α・π・・…埠・

METHOD TO SEMILINEAR．〔）CM）IEN旺愁『TARITY PROBI正到躍3 Then， f is劫θdesoent fμnotion sueh thαt

・ 了ω＜倒』⑳・・°≦x￠ s，・吻・臨ノ・

tuhe”e 5 is the soZution set of the SLO・P．     PROOF． First， note that by using 〔2．1） alx1〃ニB＋ C， we gβt          f（。） ・ 。TM。／2 ・ ￠（、）        ＝ノTMz ／2・。TrB−o〃2一ψr。ノ        ．ノrM．B．の、／2一姻        ・aTgz一ψω 噸e∫d。。。t。。 the、卿。t。i。 p館。f B， i．・．，；・rB・fノ／2．     Let O≦ec￠5and yεAω．皿鳩n clearly， y’≠x． Fr㎝the stri（尤 comrexity o fψ and the s）㎜metry o f M， it fb llows that

         細一了ω・ゾ励一ユ・ψでxノーw

      ・ry・調r“一。ノーrr∫−6ノ・−qωノ㌘ψ一・・ノ       ・⑱・荏・q、（。〃Try−。ノ       ・⑳醜・qω・ば一B）y／2 ・ （♂−c）・／2）T（y−x）       ．⑳・c。・4ωノ％一。）匂一x」Tcf−B〃“、一・・ノ／2       ・⑳・伽qωノTイy−xノ

      ・r助伽4ωん一Dx）・（By・既qωノ『rD一刀x

      ≦O wh∋re the last ine（luality holds beca］use yεA （x） and ↓Z）一∫ノx≦0． The proof is comPlete・      By・u・i・9・thi・1・㎜・・we・h・11 sbOw t！’e fO11°wi”g the°「㎝・

163

164

H60GASAWARA AND K．． HAIYASHI

     ㎜醐2・2・5・PP・s・力励輪…卿力鋤・f L・㎜・2・1 ip ld・・写， in

α漉力鋤，了ω→・・as l同1÷・・， x≧o， wh・re ll・］1 d・n・カ・s砺励αz砲・励eα。

・・nn，吻・th・・θq・θ・θθ｛♂｝de・θ・at・w吻αz卿力加r・．2ノ。・αrw醐

xa≧0， has at Zθαsカoηθαα拠Z砺gηpo伽and eVery euoh point so・Zves the． 5乙OP．       た      PROOF． If co       hal PPens to be in 5， then we have none to prove， so that we ・ay．as・m・th・t・x㌔・es n・t・b・…gt・S・f。r・a・・た≧・． The。．by．・emm。2．1，肥

have

      fr。k’12・fr．k）≦f（。らfO。・。11・k≧・． Nbte that the leve l set          ・〆・°・・｛・・ε弓1了ω・fr・°・｝ is c・叩・Ct b・6・ms・・f t垣・finity・…噂i・n． Th・refbre，．t．he・equen㏄｛k｝

蒜d、：’蕊｝1＝㌃・’：麟蕊遷㌧嚇、，

then by t aktng the limit as k → o。 in      Byk＋Cxk＋q （■k）≧o， yk≧Dxk， （Byk＋Cxk＋q r苫k〃Tryk＿D誇二〇， we obtain from the continuity．of q，      By＋鋤．チq rxノ≧0， y≧Dx， rβ〃＋Cx＋q rx〃T（y−Dttノ＝O so that          yεArxノ． Thus， it 丘）110ws by Zangwillls theorem．［6，p．91，Theore皿A］that the sequence ｛xk｝h・・ ・t・・…。・e acc㎝…ti・叩i㎡加。very。u。h．Pei。t。。1ve， th。・SLCP． This completes the proof．      Fr㎝Theore皿2．2，we have the fo llowing coro llary． Recall that l a matrix

〃is said t・be・t・i・tly・・PO・itiv・ifみ9・Owhen。ver O≠。，≧0．

     COROLLARY 2・：3． S・PP・9・th・tt th・as・卿励・・f ’Ldnh・2．1 h・・Zd・． lf， in

・硫軌臨⑭・・ぬ・t・・i・tZy・・声励一d・orxノ・・dlx ll2） as ll。・il−，

x≧ 0， カフz￠ηthe coneZusion of Theorθm 2．2 加Z∂s．

ME工HOD TO SEMILINEAR C（斑》LEMENTARITY PROBL［EIMS      PROOF． It suffices to verify that the infinity condition o f Theorem 2．2

bO・d・・te… 已・璋lll洲・・｝． Cb鵬ider t岳P・・b・㎝・mi・i・i・eみ“

sUbj ect to y ε σ． Since 〃is oompact， there exists a minimum point z4 inび． It・mi皿・u・uTMu・mi・PO・iti・・becaus・〃is st・i・tly・・P・siti・・． S・tti。g ・≦x・ll。・ll y f・…m・ y i・ひ・nd・・n・ideri・gφω・。r11。112ノ，。・・ee f（x） ﹀＝ ll。， ll㌦％・φω／1同12／ ll。 112 （m・φ（。〃11。 il2） 一… Thus， the conclusion of the        asl同卜・・，x≧0． coro llary fb llows i㎜ediately丘om Theorem 2．2． We conclude this section by sh⊃wing the unique ly convergent result．      THEOREM 2・4・ S障PPose that the αs8z碑）tion of Lenmia 2．ヱ hO Zds． lf， in

醐鋤，M・i・ ・ymmetri…Sゼ励・晒屹α両か・ヱi・・・・・・…η弓，

吻・鋤sθq・θ・・θ繭9・…t・d・by・・he吻・？itin7i （ヱ．2／st・鋤9甑

工0≧0，00nverges to the unique soZμ玩oηo∫the S五CP．’      PROOF．地first sl幻w that the infinity condition of Theorem 2．2 is satisfied． The convexity ofφmeans the monotonicity of q． Since M is positive de finite， it fb llows that F is uni f（）rmly morK）tone． Because Fニ▽了， this imp lies that f is mifbrmly convex． Hence， there exists a positive number o s’uch that

〔2．2〕 鋼一f（yノ・・rゾr・・−yノ・・II・・−Yll2允・a・…，…：・

It is immediate from the above inequality that’fsatisfies the infinity conユition． 〔bnsequent ly， it fb llows from Th∋orem 2．2 that at least one acc㎝。1、ti。。 POi。t。f｛ノ｝。泊・t・掘・very・u・h・POi・t・・lves th・ SLCP． We。e江，bO。 th。t・the。bO1。。eque。㏄｛。，k｝。。nverge・． Recall・h・t F i・ 1皿foimly monotone and｝rence the SLCP has a l血que solution as we11㎞om 〔see［2 D．世。fO。。， t』cc㎝。1。ti。n p。i。t。f的i・，・f・・ur・e，・nique． le・〆d。m・。 i・． Since｛xk｝i， b。u。d。d，。。血。creasi。g，equence｛fr。kノ｝i・ also tx）mded and so converges． From （2．2〕，we have       f品一鯉ノ≧F（xt／Tr。k−x・］・。II、。k一訓2       ．    ・。ll、，た一、，叶！2

165

166

H．OGASAWARA AND K． HAYASHI 噛e・the・。。t．i。。q。a・i・y fb・・。w，丘。m・th・ fac・th伽友≧・姐。，・s・・ve・the SLCP． By passing to the limit as た→。。 in the above inequality， we get       k       −・c当二〇，       励ll。c       k→。。

。垣。h．i。plies the、eque。ce｛k｝。。田erges t・t』血que・・1・ti…f・㎏SLCP．

This proves the theorem．

3．（bmputational Algorit㎞

     In this section， we propose a co町）utational a19ρrit㎞丑）r solving the SLCP which realizes the algρrit㎞described in Section 1．      In order jbr the alg）rit㎞〔1．2）to be practica1， the splitting of M should be chosen so that the subproblem 〔1．3） is numerically easy to solve as 。。11。、s。 th、t・r誇i，。。ne叩・y f。r 。ll 。k． lf・h…t・i・・i・t・k・n・・be aP−matrix， then the set A（x／ is a singleton fbr all x because the LCP with such a matrix has， as well known， a unique solution fbr any constant vector q and the subproblem 〔1．3） has also the same property． Hence， in this case， 。ach A r。k） d。t。㎝ine，皿iq。e・y。，k≠ヱ．      If， in addition， B is upper or lower triangular， then the subproblem beco限s trivial and can be solved directly without an imer iteration． This       た≠ヱ       can be written in the explicit fbrm． M）re specifically，

means that苫

setti・gβ・K・rλ岨一1 ・nd D・rヱーλノヱ， where X・r・』，… ， E i・a positive diagonal matrix and K is a strict ly urpper or lower triangular matrix， yields the fb llowing algorit㎞： S・arti。g。it已y。。m。9。ti。。 v。ct・r。，°，・h・ seque・ce｛・k｝i・g・n轍・d by

〔・．1〕xk’1・・［♂−t・E・r・・k・，r誇端・・純一xk川．・（・一・泌，

       k＝0，ヱ，2，．．．，        denotes the e lement−wise ma）⊂㎞um vector o f O aI冠x， the parameters where［⑳】        λ，ωand the matrices E， K are as mentioned above． Nbtice that the皿atrix B is a triangular皿atrix with positive diag〕nal entries and hence belongs to tたclasS P． The above a1即rit㎞〔3．1）is the modification of M angasarian，s one 五）r the LCP with a symmetrlc matrlx M．      Si。㏄正＋1 aPP。a，s i・the・・ight h・nd・id・・f（3．1），it・m・y・be・eemi・gly of implicit fb㎝． A（加ally， however， by virtue of the str1Ct triangularlty of K， it is computed bac㎞ard （resp． fbrward） in the order o f its e lements when K is upPer 〔10wer） triangular・

167

METHOD TO SEMILINEAR C（腿）1￡MENTARITY PROBLEMS      In the algprit㎞〔3．1），the matrix K is utilized fbr the use of the latest dat a in computing each e lement， as is done in SOR metb⊃ds fbr systems of linear equations． When K is the strictly lower triangular part of M or a zero matrix， the algorithm I皿ay be SOR−1ike or Jacobi−1i1（e， respectively． In both cases， the matrix E may be ta1くen as the inverse of the diagonal part of M if possible． Application of the algorit㎞（3．1）will be made with these two specific cases in the next section・ 4．Nu皿erical E）窪）erirnents      Wge present here some results of pre liminary comput ational tests in whidh the algOrit㎞ （3．1〕was applied to the discretization system of the one− dimens ional obstacle problem， a kind o f the free bOundary problems．      The obstacle problem can be stated as fb llows： Find a fm（tion uニu（x）such that （4．1a〕 ＝ 0 ノ σ 一 r ノ ク 一

μ2

♂ゐ

一 r ， θ ﹀＝ カ 0 ＞＝

P

一

∼血

2 onIニ（O，Zノ， 〔4．1b〕   u（O） ニα，  u（￡ノ ＝わ， ・he。。 P・P、r。，、u）、1・Rヱ・Rヱ，9・g敏1・Rl ar・gi・・n f・n・ti・田鋤・，力 are g1Ven COnStantS・      ．      Imposing on I a uni fb皿 subdivision， approximating the second derivative in〔4・1・〕by・th・㏄・tra1 diff・rence・・nd・etting・h ＝ヱ／・・苫ゲ仇 ％ニu「Xi）・Pi （・8・P「ち・Uiノ・9i ＝9「Xiノ・i＝1・…・・−1・mw giv・・t｝・・ fbllowing dis（：retized problem of 〔4．1〕：

（4．2） 吻肪2r。−pωノ≧・，。≧σ，伽・h2 re−pru川㌘ω一9）・・，

where

M＝

2ヱ

一29ロ  一  ヱ  一 ・ ● ● ・ ・ ●

ヱ2

 一

・21

  一 ゜ヱ  一 ● ， ↓也 二 uヱ  ：  ： 元．、 ，

168

H．OGASAWARA AND K． HAYASHI c ＝．

α0

．   ・ ゜0わ ， P （u） ノ ー° r ヱ ρ ●  ■  ● ノ  ー  一  η ◆r  ヱ  一  η ρ ， _θ＝

91

 ：  ：  ・ 9n＿ヱ ・ Although the symbols za，ρ and g are used here in a different sense， it will be always cleaエ in the context whether those stand fbr the functions or the vectors．      Furt．helmore， by setting v ＝u−g， problem 〔4．2） is immediately rewritten as fb llows：      ’

〔4．3） 励・qr・ノ≧0， v≧・，⑭・q励隅・・，      ．

・h・re qr・）・吻・h2（。一ρ恒9〃，

whi・h fin・11y・be・・mes th・ SLCP i・v becau・e p i・di・9…1・i・e・・P諺ω・ ρ〆㌢ノfOr a11ちand s・i・σ（in which cas・・it is e・・y・t・see t｝・e・・d・t・nce ofφ such that ▽φ ニ〈7）．      In order to motivate the nu皿erical experiments，we deal with the obstacle problem de fined by 1 ニ （O，ヱノ， P r⑳，u） ＝α／θ チuノ  〔α： grxノ ＝4xCl −x） −0．5，

α＝b＝0．

scalar parameter）， Especially， the two discrete obstacle proble皿s （4．3） （or equivalent ly 〔4．2）〕．

withα＝−2．0（Problem 1〕andα＝ヱ．0〔Problem 2〕were solved by the algorit㎞

〔3・1） proposed in the last section． Note first that the皿atrix M is sy㎜etric positive de finite． It can be verified that these test problems， Problem l and Problem 2， satisfy the assu町）tions of Cbrollary 2．3 and Theorem 2．4， respectively， under suitable choice of re laxation parameters．      正br the discretization， we chose the mesh size with h＝0．05 〔i．e．， n＝20）．      We investigated the influen㏄of parameters K， λandωin 〔3．1） fbr the solution of the problems・ Kwas taken to be a zero matrix 〔type I） and the      str1（尤1y lower triaiigular part o f M 〔type I）． λwas ch⊃sen as λ ＝0．5 and λニヱ．0． ωwas varied from O．2 to 4． O with stepsize O．2． Ewas fixed to be

169

METHOD TO SEMILINEAR（：（斑）1正MENTARITY PROBLEMS the inverse of the di agOnal part of M； in this case， E ＝ r1／2ノエ．      F・r ・ll・the・ases， t｝…t・・ting・P・int w、s 。O＝0． W。 used t｝、e

temlnat10n Crlteria

      l三㍗ケヱー咽・・a・nd。≒三ll穿陽・ヱ1…

・h・re・w・r・i） i・c・mP・…n・ary・a・i・b・…f・ ・nd・h・t・・er・nce・…−6． The maximum nunber of iterations that were a11σwed is ヱ，000．      The pro grams were coded in FORTRAN 77 us ing double precision arit㎞etic and run on the personal con唾）uter 1VEC PC−9801F2．      The numerical solutions of Problem l fbrωニ2．6 and Problem 2 fbrωニ 2．8are shom in Fig．4．1（a）and Fig．4．1〔b〕，respectively． In either case， type 丑 of K and λ ＝0．5were used． Figure 4．2 shows the variations o f the number of iterat ions required fbr convergence as a function ofω． From this figure， we can obsexve that the opt imal value ofωexists and the SOR−1ike algorit㎞〔t）ηpe I〕is less sensitive than the Jacobi−like algorit㎞〔type I〕 with respect to varying o fω・ The analys is of these phenomena is left as the neXt lnVeStlgat 10n． ω＝2．6 iter． 〔a〕 Problem 1

／

ω＝2．8

iter． 23

（b） Pi℃blem 2 1．0 Fig． 4．1． Numerical so lutions of the obstacle problems

170 H．OGASAWARA AND K． HAYASHI ・之メぷぷ謁2メ造謁ぷ之ユぷ謁ぷ2ぷ追ぷぷ 00001‘3−12222∼333334 1tεr・ ‘00   200   31ヨ   400   50｛   600   700   冊0   900  ！000 λ＝0．5

 2468024680246eO24660

・札輻立立LL仁LL乞乙LL乙入志志Σ乱軋 Ster・ 100    200    300    400    500    GOO    ；OO    醐    900   1000 λ＝1．0 （a） Probl6m 1

☆ぱ部ほ携袈詰謡芸粥“

＄Ltr・ ’eo 200    300   400   500   ‘i｛   700   800   900   1000 λ＝0．5 S2メぷ謁﹄2ぷ謁謁﹄之晶﹄ぷぷ之メ造ぷ浪

000011‘1122222333334

‘ter‘ 100   200   300    400   500   600   700   600   900   1000 λ＝1．0 〔b〕 Problem 2 Fig．4．2． Variations of the nLEnber of iterations as a function ofω

Ac㎞owled即ent

     The authors wQuld

comments

like to thank Mr． Satoru Takahashi fbr his he lpful and suggestions・

REFERENCES

［1］ B．H．Ahn：

iterative methods

175−185 ［2】 S．Karamardian： ［31 part 1， O．L．Mangasarian：  iterat ive methods 465−485 So lution of nons）㎜etric linear co町）1ement arity problems by          ，」ou？nαZ・f Optimigαtion Theory and，App Zieαtions，至， 〔1 981）．       The nonlinear complementarity problem with applications， Joitr・naZ o了Oρti栩ization Tアzeory and∠1クpZioation＄， 旦， 87−98 〔1969〕・         So lut ion of sym皿etric．1inear comp．1ementarity proble皿s ヒツ          ，」ourvzaZ of Optimization Theoryαπ∂App Zieαtions，』旦， （1977）．

METHOD TO SEMILINEAR COMP工正IMEN工ARITY PROBLIMS

171

［4］J．S．Pang：On the convergence of a basic iterative method fbr the implicit     oomp lement arity proble皿，」ヒ）urnαZ of’（）ptintzαtion Theo？y αnd App Zioations，     37， 149−162 〔1982）． 【5］Jτ百．Pang：Necessary and suffic‡ent conditions fbr the co刀Lvergence of     iterat ive metlx）ds fbr the linear complementarity prob1αn， Jouor，naZ of     Optimigation TheoTy and ApP Zications， 42， 1−17 （1984）． 16］W．1．Zangwi 11：MonZineαr・Pro≦7rcmmting： A莇Zβθ∂ApProaoh， Prentice−Ha11，     Englewood Cliffs， New Jersey （1969〕． Department of∠迦）lied Mathemat ics Science University of Tokyo 1−3 Kagurazaka， Shinj ukU− kU， 162 T（）kyo， Japan