Báo cáo nghiên cứu khoa học: "Kết hợp phương pháp chiếu và hàm phạt giải bài toán bất đẳng thức biến phân đơn điệu"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

122
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo luận văn - đề án 'báo cáo nghiên cứu khoa học: "kết hợp phương pháp chiếu và hàm phạt giải bài toán bất đẳng thức biến phân đơn điệu"', luận văn - báo cáo phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "Kết hợp phương pháp chiếu và hàm phạt giải bài toán bất đẳng thức biến phân đơn điệu"

KÕt hîp ph¬ng ph¸p chiÕu vµ hµm ph¹t gi¶i bµi to¸n bÊt ®¼ng thøc biÕn ph©n ®¬n ®iÖu §Ëu Xu©n L¬ng (a) Tãm t¾t. Trong bµi b¸o nµy, chóng t«i kÕt hîp ph¬ng ph¸p hµm ph¹t ([2]) vµ ph¬ng (D, F ), ph¸p chiÕu ®Ó gi¶i mét líp c¸c bµi to¸n bÊt ®¼ng thøc biÕn ph©n, kÝ hiÖu VIP D lµ mét tËp con låi ®ãng kh¸c rçng cña Rn , F : K → Rn lµ mét hµm ®¬n ®iÖu trong ®ã vµ liªn tôc Lipschitz trªn miÒn K chøa D . Tríc tiªn, bµi to¸n ban ®Çu ®îc ®a vÒ mét d·y c¸c bµi to¸n bÊt ®¼ng thøc biÕn ph©n trªn miÒn K chøa D , trong ®ã K tháa m·n tÝnh chÊt h×nh chiÕu Euclid cña mét ®iÓm bÊt kú lªn K cã c«ng thøc tÝnh ®¬n gi¶n. TiÕp ®ã, sö dông ph¬ng ph¸p chiÕu ®Ó gi¶i d·y c¸c bµi to¸n nµy. Khi ®ã, nÕu miÒn D tháa m·n mét vµi gi¶ thiÕt nhÊt ®Þnh, th× ®iÓm giíi h¹n bÊt kú cña d·y nghiÖm cña c¸c bµi to¸n nµy lµ mét nghiÖm cña bµi to¸n ban ®Çu. B»ng c¸ch nµy, ta lo¹i bá ®îc khã kh¨n khi tÝnh to¸n h×nh chiÕu trong c¸c thuËt to¸n chiÕu gi¶i bÊt ®¼ng thøc biÕn ph©n. Chóng t«i còng ®a ra mét vµi vÝ dô ®Ó minh häa ph¬ng ph¸p nµy. Giíi thiÖu 1. D ⊂ Rn F : Rn → Rn . Cho lµ mét tËp låi ®ãng kh¸c rçng vµ mét ¸nh x¹ XÐt bµi to¸n bÊt ®¼ng thøc biÕn ph©n sau: x∗ ∈ D, sao cho F (x∗ ), x − x∗ 0 ; ∀x ∈ D. (V IP (D, F )) T×m TËp nghiÖm cña VIP(D, F ) ®îc kÝ hiÖu lµ SOL-VIP(D, F ). F f , th× bµi to¸n VIP(D, F ) t¬ng ®¬ng víi NÕu lµ ®¹o hµm cña mét hµm låi bµi to¸n t×m cùc tiÓu cña f trªn D . Tuy nhiªn kh«ng ph¶i mäi bµi to¸n bÊt ®¼ng thøc biÕn ph©n VIP(D, F ) ®Òu t¬ng ®¬ng víi bµi to¸n quy ho¹ch låi. BÊt ®¼ng thøc biÕn ph©n cã nhiÒu øng dông réng r·i trong thùc tÕ: c¸c bµi to¸n c©n b»ng m¹ng giao th«ng ([5]), c¸c bµi to¸n c©n b»ng kinh tÕ ([6]), c¸c bµi to¸n c©n b»ng di c ([7]), c¸c bµi to¸n c©n b»ng tµi chÝnh, m¹ng kiÕn thøc ([8]), v.v. ®Òu cã thÓ m« t¶ díi d¹ng mét bÊt ®¼ng thøc biÕn ph©n. Ph¬ng ph¸p chiÕu ([1]) lµ mét ph¬ng ph¸p c¬ b¶n vµ kh¸ hiÖu qu¶ ®Ó gi¶i c¸c F bµi to¸n bÊt ®¼ng thøc biÕn ph©n víi gi¶ thiÕt gi¶ ®¬n ®iÖu vµ liªn tôc. Trë ng¹i chÝnh trong ph¬ng ph¸p nµy lµ viÖc tÝnh to¸n h×nh chiÕu lªn mét tËp låi bÊt kú kh«ng D hÒ ®¬n gi¶n. §ã lµ mét bµi to¸n quy ho¹ch toµn ph¬ng víi miÒn x¸c ®Þnh låi. NÕu D kh«ng cã h×nh d¹ng ®Æc biÖt th× viÖc x¸c ®Þnh h×nh chiÕu lªn sÏ gÆp khã kh¨n. Mét c¸ch tiÕp cËn ®Ó gi¶i quyÕt khã kh¨n nµy lµ kü thuËt hµm ph¹t cho phÐp ®a bµi to¸n bÊt ®¼ng thøc biÕn ph©n trªn miÒn låi ®ãng bÊt kú vÒ c¸c bµi to¸n bÊt K ®¼ng thøc trªn mét miÒn chøa miÒn låi ban ®Çu. ý tëng cña chóng t«i lµ ®èi víi VIP(D, F ) trong ®ã D lµ mét miÒn låi ®ãng bÊt 1 NhËn bµi ngµy 08/8/2008. Söa ch÷a xong 30/9/2008.
kú, tríc tiªn dïng ph¬ng ph¸p hµm ph¹t ®Ó ®a nã vÒ mét d·y c¸c bµi to¸n trªn mét K D, sau ®ã dïng ph¬ng ph¸p chiÕu ®Ó gi¶i mçi bµi to¸n trªn K . MiÒn K miÒn chøa ®îc x¸c ®Þnh sao cho viÖc tÝnh to¸n h×nh chiÕu cña mét ®iÓm lªn K lµ dÔ dµng. Trong trêng hîp K lµ h×nh hép, h×nh cÇu hay kh«ng gian con, v× phÐp chiÕu cña mét ®iÓm lªn K cã c«ng thøc hiÓn ®¬n gi¶n nªn trë ng¹i chÝnh cña ph¬ng ph¸p ®îc kh¾c phôc. KiÕn thøc chuÈn bÞ 2. 2.1. C¸c kÕt qu¶ vÒ sù tån t¹i vµ tÝnh duy nhÊt nghiÖm cña bµi to¸n VIP(D,F) §Þnh lý 1.([1]) (i). NÕu D lµ tËp låi comp¨c kh¸c rçng vµ F liªn tôc trªn D th× VIP(D, F) cã Ýt nhÊt mét nghiÖm. F (x) − F (x), x − x =∞ F lim (ii). NÕu tho¶ m·n ®iÒu kiÖn bøc ||x − x|| x∈D;||x||→∞ x∈D nµo ®ã, th× bµi to¸n VIP(D, F ) lu«n cã nghiÖm. víi F : D → Rn , F §Þnh nghÜa 1.([1]) (i). Cho D ®îc gäi lµ ®¬n ®iÖu trªn nÕu F (x) − F (y ), x − y 0 ; ∀x, y ∈ D. F D (ii). ®îc gäi lµ ®¬n ®iÖu ngÆt trªn nÕu F (x) − F (y ), x − y > 0 ; ∀x, y ∈ D; x = y. F D α > 0 sao cho (iii). ®îc gäi lµ ®¬n ®iÖu m¹nh trªn nÕu tån t¹i α||x − y ||2 ; ∀x, y ∈ D. F (x) − F (y ), x − y F D L > 0 sao cho (iv). ®îc gäi lµ liªn tôc Lipschitz trªn nÕu tån t¹i ||F (x) − F (y )|| L.||x − y || ; ∀x, y ∈ D. F ) nÕu SOL-VIP(D, F ) = ∅ F ®îc gäi lµ gi¶ ®¬n ®iÖu trªn D øng víi SOL-VIP(D, (v). vµ ∀x∗ ∈ SOL − V IP (D, F ) tho¶ F (x), x − x∗ 0; ∀x ∈ D. ∗ trong ®ã x lµ nghiÖm cña bµi to¸n VIP(D, F ). §Þnh lý 2.([1]) (i). Gi¶ sö F D. Khi ®ã nghiÖm cña VIP(D, F ) nÕu ®¬n ®iÖu ngÆt trªn cã lµ duy nhÊt. F D. Khi ®ã VIP(D, F ) cã ®óng mét nghiÖm. (ii). Gi¶ sö ®¬n ®iÖu m¹nh trªn 2.2. PhÐp chiÕu vµ mèi quan hÖ víi VIP Rn , x ∈ Rn §Þnh nghÜa 2.([1]) Cho D lµ tËp con låi ®ãng, kh¸c rçng cña víi ta ®Æt d(D, x) = inf ||x − y ||. Hµm d(D, .) ®îc gäi lµ hµm kho¶ng c¸ch theo chuÈn Euclid tõ y ∈D
Rn y∈D d(D, x) = ||y − x|| th× y ®îc gäi lµ D. ®iÓm trong ®Õn NÕu tån t¹i sao cho Euclid cña x trªn D vµ ®îc kÝ hiÖu h×nh chiÕu vu«ng gãc hay h×nh chiÕu theo chuÈn PD (x). lµ D lµ tËp låi ®ãng, kh¸c rçng th× h×nh chiÕu vu«ng gãc bao giê Nh ta ®· biÕt nÕu còng tån t¹i duy nhÊt. K Trong trêng hîp lµ h×nh hép, víi chuÈn Euclid, vÊn ®Ò tÝnh to¸n h×nh chiÕu K K cña mét ®iÓm lªn trë lªn ®¬n gi¶n. ThËt vËy, gi¶ sö lµ h×nh hép sau T n K = {x = (x1 , x2 , ..., xn ) ∈ R |ai bi ; i = 1, 2, ..., n}, xi a = (a1 , a2 , ..., an ) ; b = (b1 , b2 , ..., bn )T ∈ Rn . T Khi ®ã h×nh chiÕu cña x lªn K ®îc x¸c ®Þnh nh sau  ai , xi < ai  (PK (x))i = xi , xi ∈ [ai ; bi ]  bi , xi > bi .  I (a1 , a2 , ..., an ) ∈ Rn , b¸n kÝnh R, cã ph¬ng tr×nh C Gi¶ sö lµ h×nh cÇu t©m n C = {x ∈ R n | (xi − ai )2 R2 } i=1 b = (b1 , b2 , ..., bn )T ∈ Rn . CÇn t×m h×nh chiÕu vu«ng gãc PC (b) cña b lªn C . NÕu b ∈ C vµ th× PC (b) ≡ b. NÕu b n»m ngoµi C , h×nh chiÕu cña b lªn C lµ giao ®iÓm cña ®êng th¼ng n S = {x ∈ Rn | (xi − ai )2 = R2 }. I C nèi b vµ t©m cña víi mÆt cÇu i=1 Ph¬ng tr×nh tham sè cña ®êng th¼ng nµy nh sau: ∆ = {x ∈ Rn |xi = ai + t(bi − ai ) ; i = 1, 2, ..., n ; t ∈ R}. n xi = ai + t(bi − ai ) vµo ph¬ng tr×nh S , ta cã t2 (bi − ai )2 = R2 . Thay i=1 Do ®ã R t= . n (bi − ai )2 i=1 PC (b) cña b lªn C cã to¹ ®é VËy h×nh chiÕu R xi = ai + (bi − ai ) . n (bi − ai )2 i=1 L ⊂ Rn B = {η1 , η2 , ..., ηk }. Gi¶ sö b ∈ Rn Khi lµ kh«ng gian con k chiÒu víi c¬ së lµ mét k cj ηj ∈ L ; cj f = b − a tho¶ f , ηj = 0, a= ®iÓm bÊt k×, lµ c¸c h»ng sè thùc, sao cho j =1
j = 1, 2, ..., k . Khi ®ã a lµ h×nh chiÕu vu«ng gãc cña b lªn L. víi mäi c ∈ L, v× f vu«ng gãc víi mäi vÐct¬ trong c¬ L, ThËt vËy, gi¶ sö së cña nªn nã vu«ng gãc víi mäi vÐct¬ thuéc L. Do ®ã ||b − c||2 = b − a + a − c, b − a + a − c = b − a, b − a + a − c, a − c + 2 b − a, a − c = ||b − a||2 + ||a − c||2 ||b − a||2 . L. Do ®ã a lµ h×nh chiÕu vu«ng gãc cña b lªn i = 1, . . . , k , ta cã: f , ηi = 0, Giê ta t×m a; víi mäi k b− cj ηj , ηi = 0, j =1 k ηi , ηj cj = b, ηi . j =1 Aij = ηi , ηj ; Di = b, ηi ; i = 1, 2, ..., k ; j = 1, 2, ..., k . §Æt Khi ®ã ta thu ®îc mét hÖ ph¬ng tr×nh tuyÕn tÝnh k ph¬ng tr×nh, k Èn Ac = D , trong ®ã A = (Aij ), c = (c1 , c2 , ..., ck )T ; D = (D1 , D2 , ..., Dk )T . A, det(A) = 0, H¬n n÷a, do c¸ch x¸c ®Þnh ®©y lµ mét ma trËn x¸c ®Þnh d¬ng, suy ra k a= cj ηj , sau khi tÝnh ®îc ci , ta tÝnh nghÜa lµ hÖ trªn lu«n cho nghiÖm duy nhÊt. V× j =1 ®îc a. NÕu chän B lµ c¬ së trùc chuÈn nghÜa lµ ηi , ηj = 0 nÕu i = j ; =1 nÕu i = j , th× A lµ ma trËn ®¬n vÞ, do ®ã cã thÓ tÝnh ngay ®îc nghiÖm ci = Di = b, ηi . Liªn quan ®Õn h×nh chiÕu vµ bÊt ®¼ng thøc biÕn ph©n ta cã ®Þnh lý sau. D ⊂ Rn lµ mét tËp låi ®ãng vµ F : Rn → Rn lµ mét ¸nh x¹. Khi MÖnh ®Ò 1.([1]) Gi¶ sö ∗ ∈ SOL − V IP (D, F ) ⇔ FD (x∗ ) = 0, trong ®ã FD (x∗ ) ≡ x − PD (x − ξF (x)) nat nat ®ã ta cã x ξ > 0 nµo ®ã. víi Ph¬ng ph¸p kÕt hîp ph¬ng ph¸p hµm ph¹t vµ ph¬ng ph¸p chiÕu 3. 3.1. Ph¬ng ph¸p chiÕu ë ®©y ta chØ ®Ò cËp ®Õn ph¬ng ph¸p chiÕu hai lÇn (extragradient method) v× ph¬ng ph¸p nµy tuy cÇn hai lÇn chiÕu trong mçi bíc lÆp nhng cã thÓ ¸p dông cho VIP(D, F) F víi gi¶ ®¬n ®iÖu vµ liªn tôc Lipschitz. Trong khi ®ã ph¬ng ph¸p chiÕu
F mét lÇn ®ßi hái ®¬n ®iÖu m¹nh, liªn tôc Lipschitz; ph¬ng ph¸p chiÕu ba lÇn (hyper- plane projection method) tuy ¸p dông ®îc cho VIP(D, F ) víi F gi¶ ®¬n ®iÖu vµ liªn tôc (thay v× liªn tôc Lipschitz nh hai ph¬ng ph¸p ®Çu), nhng khèi lîng tÝnh to¸n trong mçi bíc lÆp l¹i t¨ng lªn ®¸ng kÓ do ph¶i sö dông thªm thuËt to¸n t×m kiÕm. ViÖc ph©n lo¹i c¸c ph¬ng ph¸p chiÕu cã thÓ tham kh¶o trong ([1]). NÕu ta sö dông ph¬ng ph¸p chiÕu hai lÇn cho VIP víi rµng buéc hép hoÆc h×nh cÇu, hoÆc kh«ng gian con, th× khèi lîng tÝnh to¸n trong mçi vßng lÆp t¨ng lªn kh«ng ®¸ng kÓ so víi ph¬ng ph¸p chiÕu mét lÇn, v× h×nh chiÕu cña mét ®iÓm lªn c¸c tËp kiÓu nµy cã c«ng thøc hiÓn nh trªn ®· thÊy. Trong khi ®ã, ph¬ng ph¸p chiÕu mét lÇn cßn ®ßi hái viÖc tÝnh to¸n α cña hµm F . §ång thêi, ®Ó thuËt to¸n héi tô, c¸c hÖ sè bíc tk ph¶i c¸c hÖ sè ®¬n ®iÖu α/L2 , L lµ h»ng sè Lipschitz cña F (xem [1]). Trong nhiÒu trêng nhá h¬n trong ®ã 2 L kh¸ lín khi sè chiÒu cña bµi to¸n t¨ng lªn, mÉu sè L lín sÏ lµm bíc hîp, trë lªn tk trë nªn rÊt nhá. §iÒu nµy thêng ¶nh hëng tíi tèc ®é héi tô vµ ®é chÝnh x¸c cña thuËt to¸n chiÕu. x0 ∈ K ThuËt to¸n 1. ([1]) LÊy η > 0. vµ chän Bíc 0: §Æt k = 0. xk = PD (xk − ηF (xk )), th× xk ∈ SOL − V IP (D, F ) : dõng thuËt to¸n víi Bíc 1: NÕu k nghiÖm thu ®îc lµ x . k = P (xk − ηF (xk )) th× tÝnh Bíc 2: NÕu x D 1 xk+ 2 = PD (xk − ηF (xk )), 1 xk+1 = PD (xk − ηF (xk+ 2 )). k := k + 1 vµ quay l¹i bíc 1. Cho Sù héi tô cña thuËt to¸n nµy ®îc b¶o ®¶m bëi ®Þnh lý sau. D ⊂ Rn F : D → Rn §Þnh lý 3.([1]) (i). Gi¶ sö låi ®ãng vµ lµ mét ¸nh x¹ gi¶ ®¬n x∗ ∈ D t¬ng øng víi SOL-VIP(D, F ) vµ L-Lipschitz liªn tôc trªn D. ®iÖu trªn Gi¶ sö SOL − V IP (D, F ). Khi ®ã, víi mäi k ∈ N 1 ||xk+1 − x∗ ||2 ||xk − x∗ ||2 − (1 − η 2 L2 )||xk+ 2 − xk ||2 . F : D → Rn gi¶ ®¬n ®iÖu trªn D t¬ng øng víi SOL-VIP(D, F) L- (ii). Gi¶ sö vµ k Lipschitz trªn D . NÕu 0 < η < 1/L th× d·y {x } sinh bëi thuËt to¸n 1 héi tô vÒ mét nghiÖm cña VIP(D, F ). 3.2. Ph¬ng ph¸p hµm ph¹t Ph¬ng ph¸p hµm ph¹t tr×nh bµy sau ®©y ®îc ®Ò xuÊt trong ([2]). 3.2.1. X©y dùng hµm ph¹t kh¶ vi XÐt bµi to¸n bÊt ®¼ng thøc biÕn ph©n sau:
x∗ ∈ D T×m sao cho F (x∗ ), x − x∗ 0 , ∀x ∈ D. (1) Gi¶ sö D låi, ®ãng, bÞ chÆn; K lµ mét h×nh hép (hay mét h×nh D. cÇu ®ãng) chøa X©y dùng mét hµm låi kh¶ vi P : K → R tho¶ m·n 0 ⇔ x ∈ D. P (x) (2) D = {x ∈ Rn |gi (x) 0 , i = 1, 2, ..., m}, trong ®ã gi : Rn → R lµ c¸c hµm låi Chó ý lµ khi kh¶ vi, hµm ph¹t P cã thÓ lÊy nh sau: m [max(0, gi (x))]2 . P (x) := (3) i=1 P P DÔ thÊy tho¶ m·n (2), h¬n n÷a kh¶ vi. ThËt vËy, xÐt hi (x) = [max(0, gi (x))]2 = (α ◦ g )(x), x2 , x > 0 α(x) := [max(0, x)]2 = trong ®ã 0, x 0. 2 ; víi x < 0, α (x) = 0. T¹i x = 0, ®¹o hµm bªn ph¶i b»ng 0 DÔ thÊy víi x > 0, α (x) = x (∆x)2 α(0 + ∆x) − α(0) lim = lim = 0. ∆x ∆x→0+ ∆x ∆x→0+ α(x) kh¶ vi. V× gi kh¶ vi, do ®ã hi vµ b»ng ®¹o hµm bªn tr¸i. Do ®ã, lµ hîp cña hai hµm kh¶ vi, còng kh¶ vi, nghÜa lµ P (x) kh¶ vi; hoÆc cã thÓ lÊy P (x) = max (gi (x)). (4) 1im m = 1, khi ®ã P ≡ g1 g1 P Chó ý r»ng trong nhiÒu trêng hîp, vµ do ®ã nÕu kh¶ vi th× còng kh¶ vi. 3.2.2. Dïng hµm ph¹t ®Ó chuyÓn bµi to¸n ban ®Çu vÒ mét d·y c¸c bµi to¸n víi rµng buéc ®¬n gi¶n t > 0 xÐt bµi to¸n ph¹t VIP(K, tF + P ) sau Víi mçi xt ∈ K T×m sao cho P (xt ), x − xt 0 , ∀x ∈ K, tF (xt ) + (1t ) K ⊃ D lµ mét tËp låi, ®ãng ®¬n gi¶n (h×nh hép, qu¶ cÇu) sao cho h×nh chiÕu trong ®ã K cã thÓ tÝnh ®îc mét c¸ch dÔ dµng, thËm chÝ cã thÓ tÝnh ®îc theo mét vu«ng gãc lªn P (xt ) lµ ®¹o hµm cña P t¹i xt . KÝ hiÖu S (t) lµ tËp nghiÖm cña (1t ) vµ c«ng thøc hiÓn; ®Æt t∗ = sup{t 0 : S (t) ⊂ D}. Bæ ®Ò 1.([2]) Gi¶ sö F P lµ hµm ®¬n ®iÖu, lµ hµm låi, kh¶ vi, tho¶ m·n (2) vµ bÞ chÆn díi. Khi ®ã S (t) ∩ D = ∅ nÕu t > t∗ ; (i).
S (t) ⊂ D 0 < t < t∗ ; (ii). nÕu (iii). S (t∗ ) n»m trong tËp nghiÖm cña bµi to¸n ban ®Çu (1) nÕu 0 < t∗ < ∞ vµ ¸nh x¹ S (.) nöa liªn tôc díi t¹i t∗ ; {xn } xn ∈ S (tn ) =∞ → t∗ (iv). NÕu t∗ vµ tn th× bÊt k× d·y nµo ®ã víi cã mét ®iÓm tô n vµ bÊt k× ®iÓm tô nµo cña {x } ®Òu lµ mét nghiÖm cña (1). NhËn xÐt: Hµm P lÊy nh (3) bÞ chÆn díi bëi 0 nªn hiÓn nhiªn tho¶ ®iÒu kiÖn trong bæ ®Ò trªn. ThuËt to¸n 2.([2]) X©y dùng hµm låi P tho¶ m·n ®iÒu kiÖn cña bæ ®Ò 1. a = 0; b = ∞ vµ chuyÓn sang bíc k víi k = 0. LÊy t0 lµ mét sè d¬ng tuú ý. LÊy Bíc k (k = 0, 1, ...). (1tk ) thu ®îc nghiÖm xk . Gi¶i bµi to¸n xk ∈ D, ®Æt a := tk a) NÕu vµ  a + b , b
F ) víi D lµ tËp låi ®ãng, bÞ chÆn cña Rn . Gi¶ sö F lµ mét ¸nh x¹ liªn XÐt VIP(D, tôc, x¸c ®Þnh trªn mét tËp låi, comp¨c K chøa D , trong ®ã K lµ mét qu¶ cÇu ®ãng hoÆc lµ mét h×nh hép comp¨c. ý tëng chÝnh cña ph¬ng ph¸p kÕt hîp nh sau: Tríc tiªn, ta dïng ph¬ng ph¸p D vÒ mét d·y c¸c bµi to¸n ph¹t hµm ph¹t ®Ó ®a bµi to¸n trªn miÒn låi ®ãng bÊt kú K D. Mçi bµi to¸n ph¹t sÏ ®îc gi¶i mét c¸ch xÊp xØ b»ng ph¬ng ph¸p trªn miÒn chøa chiÕu. ThuËt to¸n kÕt hîp gåm 2 bíc chÝnh sau: Bíc 1: Dïng ph¬ng ph¸p hµm ph¹t chuyÓn VIP(D, F ) vÒ mét d·y c¸c bµi to¸n trªn K chøa D, V IP (K, tF + P ) trong ®ã P lµ mét hµm låi x¸c ®Þnh, kh¶ vi liªn tôc miÒn khi vµ chØ khi x ∈ D. trªn K vµ tho¶ m·n P (x) 0 Bíc 2: Gi¶i bµi to¸n VIP(K, tF + P ) b»ng mét trong c¸c ph¬ng ph¸p chiÕu trong ([1]). P Theo tÝnh chÊt cña hµm låi, kh¶ vi liªn tôc vµ Lipschitz (xem hÖ qu¶ 25.5.1, [4]). KÕt F Ft := tF + P hîp víi gi¶ thiÕt liªn tôc, ta suy ra liªn tôc. Dïng ph¬ng ph¸p chiÕu hai lÇn ®Ó gi¶i bµi to¸n V IP (K, tF + P ). ThuËt to¸n cô thÓ ®îc m« t¶ nh sau: ThuËt to¸n 3 (KÕt hîp ph¹t vµ chiÕu hai lÇn) X©y dùng mét siªu hép (hoÆc mét h×nh K D P cÇu ®ãng) chøa vµ mét hµm låi tho¶ m·n ®iÒu kiÖn cña bæ ®Ò 1. → 0 khi k → ∞. LÊy t0 lµ mét sè d¬ng tuú ý. Chän > 0, sao cho k k a = 0 , b = ∞ vµ chuyÓn sang bíc k víi k = 0. LÊy k0 : Chän c¸c h»ng sè λ > 0 , η ∈ (0; 1/Ltk ), trong ®ã Ltk lµ h»ng sè Lipschitz Bíc Fk := tk F + P . cña 0 Khëi t¹o j := 0, chän ®iÓm xuÊt ph¸t y ∈ K . j − P (y j − λ.F (y j ))|| k j Bíc k1 : a) NÕu ||y k , th× dõng, ®Æt x := y . T¨ng k thªm K k 1 vµ trë l¹i bíc k . j j j b) NÕu ||y − PK (y − λ.Fk (y ))|| > k , th× qua bíc k2 Bíc k2 : TÝnh 1 y j + 2 := PK (y j − ηFk (y j )), 1 y j +1 := PK (y j − ηFk (y j + 2 )), j := j + 1 k1 , PK (x) x K. ®Æt vµ quay l¹i bíc ë ®©y lµ h×nh chiÕu vu«ng gãc cña lªn K H×nh chiÕu nµy ®îc tÝnh dÔ dµng theo c«ng thøc hiÓn, khi lµ siªu hép hoÆc lµ mét qu¶ cÇu ®ãng.
xk j Sau c¸c vßng lÆp trªn cña ph¬ng ph¸p chiÕu, ta thu ®îc nghiÖm xÊp xØ cña (1tk ). XÐt hai trêng hîp bµi to¸n xk ∈ D, ®Æt a := tk a) NÕu vµ  a + b , b 0, nªn trong vßng lÆp j , víi mçi k §Þnh lý 3, ta cã y ∗ ∗ cè ®Þnh, bíc k1 sÏ ph¶i x¶y ra sau mét sè h÷u h¹n bíc lÆp j . Gäi x lµ nghiÖm cña bÊt ®¼ng thøc biÕn ph©n VIP(D, F ). Khi ®ã ta cã ||xk − x∗ || ||xk − xk || + ||xk − x∗ ||. ∗ ∗ → 0, xk → x∗ , nªn suy ra ||xk − x∗ || → 0 xk = y j , nªn ||xk − xk || Do k . Tõ ®Êy vµ do k ∗ ∗ khi k → +∞. C¸c vÝ dô 4. D = {x ∈ Rn |g (x) 0} ∩ K, trong ®ã VÝ dô 1. MiÒn D lÊy nh sau n K = {x = (x1 , x2 , ..., xn ) ∈ R |0 ai , i = 1, 2, ..., n}, xi e5 +n−1 i 1 ; g (x) := 2 i exi − ai = 5 + . trong ®ã n2 3i − 1 n n n DÔ thÊy g (x) lµ mét hµm låi trªn R . Chän hµm ph¹t P (x) ≡ g (x) trªn R . Khi ®ã, 0, x ∈ D P (x) = > 0, x ∈ K \ D. D K P D. H¬n n÷a, Ta sÏ bao bëi nªn tho¶ m·n ®iÒu kiÖn cña hµm ph¹t trªn 1 · (ex1 , ex2 , ..., exn )T . P (x) = n2 P (x) liªn tôc Lipschitz trªn D víi h»ng sè Lipschitz e6 /n2 . Ngoµi ra, dÔ thÊy Do ®ã, P (x) cßn ®¬n ®iÖu m¹nh víi h»ng sè ®¬n ®iÖu 1/n2 . Nh vËy, chØ cÇn F ®¬n ®iÖu th×
tF + P sÏ ®¬n ®iÖu m¹nh. F ®îc lÊy theo m« h×nh Nash (xem [3], trang 129). Hµm F (x) = H (x) − p(σx )e − p (σx )x, trong ®ã e = (1, ..., 1)T ∈ Rn , σx = x, e = xj , j H (x) = (α1 x1 + β1 , . . . , αn xn + βn )T , αi , βi trong ®ã lÊy ngÉu nhiªn trong kho¶ng [0; 10]. γ p(t) = , t+1 γ trong ®ã lÊy ngÉu nhiªn trong [0; 15]. F Khi ®ã, lÊy nh trªn lµ mét hµm ®¬n ®iÖu (xem, ch¼ng h¹n [3]). Ngoµi ra ta cã thÓ 2(α2 + 4n2 γ 2 ). F Ln = chøng minh r»ng liªn tôc Lipschitz víi h»ng sè Lipschitz Nh vËy, vÝ dô nµy tho¶ m·n c¸c gi¶ thiÕt cña ®Þnh lý 5, do ®ã, ¸p dông thuËt to¸n 3 cho ta mét d·y sè trong ®ã bÊt kú ®iÓm tô nµo cña d·y ®ã ®Òu lµ mét nghiÖm cña bµi to¸n. ε = 10−6 . Sau ®©y lµ kÕt qu¶ ch¹y ch¬ng tr×nh. Sai sè cho phÐp cña thuËt to¸n chiÕu lµ B¶ng 1 γ \n 5 10 20 5 [15 - 18] - 1s [15 - 28] - 1s [13 - 24] - 8s 10 [17 - 25] - 1s [15 - 25] - 3s [10 - 24] - 9s 15 [19 - 25] - 2s [14 - 24] - 5s [14 - 22] - 12s B¶ng 2 γ \n 30 40 50 5 [13 - 15] - 10s [15 - 25] - 28s [10 - 24] - 70s 10 [15 - 22] - 50s [12 - 22] - 60s [13 - 21] - 210s 15 [17 - 22] - 90s [13 - 21] - 225s [13 - 20] - 420s D÷ liÖu trong hai b¶ng trªn ®îc ®äc nh sau: Ch¼ng h¹n, lÊy « n»m ë hµng 3, cét 3, γ = 10: ThuËt to¸n ch¹y mÊt 3 gi©y ®Ó ®Õn ®îc vßng b¶ng 1, t¬ng øng víi n = 10 vµ lÆp thø 25 ( gi¶i hÕt bµi to¸n ph¹t thø 25), trong ®ã, c¸c vßng lÆp tõ 15 ®Õn 25 cho cïng xk mét nghiÖm (tÝnh ®Õn 6 ch÷ sè thËp ph©n). P sÏ ®îc lÊy theo c«ng thøc (??). Ta xÐt 2 vÝ dô tiÕp theo, trong ®ã hµm ph¹t D = {x = (x1 , x2 )T ∈ R2 |g1 (x) 0 , g2 (x) 0}, XÐt 2 2 trong ®ã g1 (x) = x2 − x1 , g2 (x) = −x2 + x1 − 1 lµ c¸c hµm låi trªn R . Ta xÐt hai vÝ dô øng víi hai hµm F kh¸c nhau. x1 + x2 VÝ dô 2. F (x) = . x2 x2 + e 4 − 1
ë ®©y, D lµ miÒn n»m díi ®êng th¼ng x2 = x1 +1 vµ n»m trªn ®êng cong x2 = x2 − 1, 1 (I) lµ miÒn n»m trªn c¶ ®êng th¼ng vµ ®êng cong, (II) n»m trªn ®êng th¼ng vµ díi ®êng cong, (III) n»m díi c¶ ®êng th¼ng vµ ®êng cong. F Cã thÓ nhËn thÊy (0; 0) lµ mét nghiÖm cña bµi to¸n trªn vµ lµ nghiÖm duy nhÊt, do P ®¬n ®iÖu m¹nh. Ta lÊy theo c«ng thøc (3). P (x1 , x2 ) = [max(0, x2 − x1 − 1)]2 + [max(0, −x2 + x2 − 1)]2 1  (x1 , x2 ) ∈ D 0,  (x − x − 1)2 ,  (x1 , x2 ) ∈ (I ) 2 1 = (x2 − x1 − 1)2 + (−x2 + x2 − 1)2 , (x1 , x2 ) ∈ (II ) 1   (−x2 + x2 − 1)2 , (x1 , x2 ) ∈ (III ).  1 D Hai giao ®iÓm cña ®êng th¼ng vµ ®êng cong lµ (-1; 0) vµ (2; 3). Do ®ã cã thÓ bao K = {x = (x1 ; x2 )| − 1 x1 2 ; −1 x2 √ }. 3 bëi h×nh hép F liªn tôc Lipschitz trªn K víi h»ng sè Lipschitz l = 4.4, do ®ã tF (t > 0) liªn tôc √ Lipschitz víi h»ng sè Lipschitz lt = t. 4.4. H¬n n÷a, F ®¬n ®iÖu m¹nh trªn K víi h»ng 1 sè ®¬n ®iÖu m¹nh α = . 2 t Do ®ã tF (t > 0) cã h»ng sè ®¬n ®iÖu m¹nh αt = . 2 Ta cã  0 (x1 , x2 ) ∈ D    0      −2(x − x − 1) 2 1  (x1 , x2 ) ∈ (I )    2(x − x − 1)  2 1 P (x1 , x2 ) =  −2(x2 − x1 − 1) + 4x1 (−x2 + x2 − 1) 1 (x1 , x2 ) ∈ (II )   2(x2 − x1 − 1) − 2(−x2 + x2 − 1)   1     4x (−x + x2 − 1)  1 2 1  (x1 , x2 ) ∈ (III )    −2(−x + x2 − 1)  2 1 K Ft := tF + ∆P liªn tôc Lipschitz trªn víi h»ng sè Lipschitz 69. Do ®ã liªn tôc √ K Lt = 69 + t 4.4 Lipschitz trªn víi h»ng sè Lipschitz vµ cã h»ng sè ®¬n ®iÖu m¹nh αt = t/2. Tríc hÕt, ta dïng ph¬ng ph¸p hµm ph¹t ®a bµi to¸n trªn vÒ d·y c¸c VIP(K, tF + ∆P ). t > 0, ¸p dông ph¬ng ph¸p chiÕu mét lÇn, ta chän ®é dµi bíc ηk := η lµ h»ng Víi mçi αt t √ tho¶ 0 < η < 2 · 2= . (69 + t 4.4)2 Lt 0.9t √ Do ®ã cã thÓ lÊy ηk = η = . (69 + t 4.4)
¸p dông ph¬ng ph¸p chiÕu hai lÇn, ta chän ®é dµi bíc η tho¶ 1 1 √. 0 0 nªn theo bæ ®Ò 1, S (t0 ) ⊂ D, do ®ã, nghiÖm cña bµi to¸n ph¹t øng víi t0 còng chÝnh lµ nghiÖm cña bµi to¸n ban ®Çu. §iÒu ®ã gi¶i thÝch t¹i sao nghiÖm cña bµi to¸n ban ®Çu l¹i ®îc t×m ra ngay sau bíc lÆp ®Çu tiªn. x1 + x2 + 10 VÝ dô 3. Hµm F F (x) = . cho bëi c«ng thøc sau x2 + ex2 + 10 Cã thÓ thÊy hµm F kh«ng cã nghiÖm trªn miÒn D gièng nh ë vÝ dô 1 n÷a. Tuy vËy, F vÉn ®¬n ®iÖu m¹nh vµ liªn tôc Lipschitz víi cïng h»ng sè nh ë vÝ dô 1. KÕt qu¶ ch¹y ch¬ng tr×nh 10−10 , t0 = 1 , x0 = (1; 1), Dïng thuËt to¸n 3, víi ®é chÝnh x¸c (cña thuËt to¸n chiÕu) sau ®©y lµ kÕt qu¶ cña vßng lÆp 24 ®Õn vßng lÆp 28: B¶ng 3 xk tk Sè bíc lÆp k 889881606 24 (-0.437337405102318 - 0.808736590634006) 0.0000001192 1779680342 25 (-0.437337404356388 - 0.808736293018647) 0.0000000596 3560253327 26 (-0.437337403855591 - 0.808736144322769 ) 0.0000000298 14205655551 28 (-0.437337403325762 - 0.808736032935760) 0.0000000075 Cét ®Çu tiªn cho biÕt sè vßng lÆp mµ thuËt to¸n chiÕu thùc hiÖn ®Ó gi¶i bµi to¸n ph¹t. tk → 0, nghÜa lµ t∗ = 0. Trong trêng hîp t∗ = 0, tõ bæ ®Ò 1, nghiÖm Cã thÓ thÊy lµ k cña bµi to¸n ph¹t øng víi t lu«n n»m ngoµi miÒn D , vµ mét ®iÓm tô bÊt kú cña x k k k mét d·y {x } bÊt kú víi x ∈ S (tk ) vµ tk → t∗ lµ nghiÖm cña (1). Cã thÓ nhËn thÊy lµ −8 , nhng nghiÖm cña nh÷ng bíc cuèi cïng xÊp xØ thuéc miÒn D víi sai sè kho¶ng 10
D. vÉn n»m ngoµi §iÒu nµy phï hîp víi kÕt luËn cña bæ ®Ò 1. ThuËt to¸n ch¹y trong nhiÒu giê ®ång hå ®Ó tíi ®îc vßng lÆp thø 28. Tµi liÖu tham kh¶o [1] F. Facchinei, and J. S. Pang, Finite - Dimensional Variational Inequalities and Complemen- tarity Problems, Springer series in Operations Research, 2003. [2] D. M. Le, An Augmented Penalty Function Method for Solving a Class of Variational in- 2 (1986), 1788 - 1796. equalities, Soviet Computational Mathematical Physics, [3] I. Konnov, Combined relaxation methods for variational inequalities, Lecture notes in eco- 495, Springer, 2001. nomics and mathematical systems, [4] R. T. Rockafellar, Convex Analysis, Princeton University Press, 1970. 14 [5] S. C. Dafermos, Traffic Equilibria and Variational Inequalities, Transportation Science, (1980), 42-54. [6] S. C. Dafermos and S. C. McKelvey, Partitionable variational inequalities with applications 73 (2) to network and economic equilibria, Journal of Optimization Theory and Applications, (1992), 243-268. [7] A. Nagurney, Migration equilibrium and variational inequalities, Springer series in Ad- vance in Computational, 1989. [8] A. Nagurney, Network economics: A variational approach, Kluwer Academic Publishers, Dordrecht, The Netherlands, 1999. SUMMARY COMBINING THE PROJECTION METHOD AND THE PENALTY FUNCTION TO SOLVE THE VARIATIONAL INEQUALITIES WITH MONOTONE MAPPINGS In this paper, we combine the augmented penalty function method ([2]) and the well- (D, F ), known projection methods to solve a class of variational inequality problems, denoted VIP Rn , F : K → Rn is monotone and Lipschitz D where is a nonempty closed convex subset of n continuous on K ⊃ D . More specifically, the original problem on D ⊂ R is first transformed into a sequence of variational inequality problems on K ⊃ D , where K is a simpler set, in the n sense that the Euclidean projection of any point of R onto K can be calculated easily. Then the projection methods are employed to solve each of these problems. In this way, we over- come the main disadvantage of the projection methods, which is the difficulty in computing the projection of a point onto a convex set. Under some assumptions, any cluster point of the sequence of solutions of these problems is a solution of the original problem. We also provide some examples to illustrate our method. (a) Khoa Tù nhiªn, Trêng Cao ®¼ng S ph¹m Qu¶ng Ninh.