Tài liệu Phương pháp lặp banach cho bài toán bất đẳng thức biến phân

0 ®¹i häc th¸i nguyªn tr­êng ®¹i häc khoa häc ---------------------------- Phan ThÕ NghÜa ph­¬ng ph¸p lÆp Banach cho BµI TO¸N BÊT §¼NG THøC BIÕN PH¢N luËn v¨n th¹c sÜ to¸n häc øng dông Th¸i Nguyªn-2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 0 ®¹i häc th¸i nguyªn tr­êng ®¹i häc khoa häc ---------------------------- Phan ThÕ NghÜa ph­¬ng ph¸p lÆp Banach cho BµI TO¸N BÊT §¼NG THøC BIÕN PH¢N Chuyªn ngành: To¸n øng dông M· sè: 60.46.36 luËn v¨n th¹c sÜ to¸n häc øng dông NGUêI H­íNG DÉN KHOA HäC: TS. PH¹M NGäC ANH Th¸i Nguyªn-2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 0 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 2 Môc lôc Trang phô b×a Môc lôc 2 Lêi c¶m ¬n 3 Mét sè ký hiÖu vµ ch÷ viÕt t¾t 4 Lêi nãi ®Çu 5 Ch­¬ng 1. Bµi to¸n BÊt ®¼ng thøc biÕn ph©n 1.1. Mét sè kh¸i niÖm c¬ b¶n 7 1.2. Ph¸t biÓu bµi to¸n vµ vÝ dô 10 1.3. Sù tån t¹i nghiÖm cña bµi to¸n VI 18 Ch­¬ng 2. Ph­¬ng ph¸p lÆp Banach gi¶i bµi to¸n (VI) ®¬n ®iÖu m¹nh 2.1. TÝnh kh«ng gi·n cña ¸nh x¹ nghiÖm 23 2.2. M« t¶ thuËt to¸n vµ sù héi tô 27 Ch­¬ng 3. Ph­¬ng ph¸p lÆp Banach gi¶i bµi to¸n ®ång bøc 3.1. TÝnh kh«ng gi·n cña ¸nh x¹ nghiÖm 30 3.2. M« t¶ thuËt to¸n vµ sù héi tô 35 3.3. KÕt qu¶ tÝnh to¸n thö nghiÖm 3.3.1. M« h×nh c©n b»ng b¸n ®éc quyÒn 38 3.3.2. KÕt qu¶ tÝnh to¸n thö nghiÖm 43 Tµi liÖu tham kh¶o Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 http://www.Lrc-tnu.edu.vn 3 Lêi c¶m ¬n B¶n luËn v¨n nµy ®­îc hoµn thµnh t¹i tr­êng §¹i häc Khoa häc-§¹i häc Th¸i Nguyªn d­íi sù h­íng dÉn cña TS. Ph¹m Ngäc Anh. T¸c gi¶ xin bµy tá lßng kÝnh träng vµ biÕt ¬n s©u s¾c tíi thÇy vÒ sù tËn t×nh h­íng dÉn trong suèt thêi gian t¸c gi¶ lµm luËn v¨n. Trong qu¸ tr×nh häc tËp vµ lµm luËn v¨n, th«ng qua c¸c bµi gi¶ng vµ xªmina, t¸c gi¶ th­êng xuyªn nhËn ®­îc sù quan t©m gióp ®ì vµ ®ãng gãp nh÷ng ý kiÕn quý b¸u cña PGS. TS. Lª ThÞ Thanh Nhµn, TS. NguyÔn ThÞ Thu Thñy vµ c¸c thÇy c¸c c« trong tr­êng §¹i häc Khoa häc-§¹i häc Th¸i Nguyªn. Tõ ®¸y lßng m×nh, t¸c gi¶ xin bµy tá lßng biÕt ¬n s©u s¾c ®Õn c¸c thÇy c¸c c«. T¸c gi¶ xin bµy tá lßng biÕt ¬n tíi c¸c thÇy, c¸c c« khoa Khoa häc C¬ b¶n, Ban ChÊp Hµnh §oµn tr­êng Cao ®¼ng C«ng nghiÖp Th¸i Nguyªn ®· ®· t¹o ®iÒu kiÖn gióp ®ì t¸c gi¶ trong thêi gian lµm cao häc. Xin ch©n thµnh c¶m ¬n anh chÞ em häc viªn cao häc vµ b¹n bÌ ®ång nghiÖp gÇn xa ®· trao ®æi, ®éng viªn vµ khÝch lÖ t¸c gi¶ trong qu¸ tr×nh häc tËp, nghiªn cøu vµ lµm luËn v¨n. LuËn v¨n sÏ kh«ng hoµn thµnh ®­îc nÕu kh«ng cã sù th«ng c¶m, gióp ®ì cña nh÷ng ng­êi th©n trong gia ®×nh t¸c gi¶. §©y lµ mãn quµ tinh thÇn, t¸c gi¶ xin kÝnh tÆng gia ®×nh th©n yªu cña m×nh víi tÊm lßng biÕt ¬n ch©n thµnh vµ s©u s¾c. T¸c gi¶ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 4 Mét sè ký hiÖu vµ ch÷ viÕt t¾t Rn |β| kh«ng gian Euclide x := y ∀x ∃x x ®­îc ®Þnh nghÜa b»ng y víi mäi x tån t¹i x I A⊂B A⊆B ¸nh x¹ ®ång nhÊt A∪B A∩B A×B A hîp víi B A giao víi B tÝch §Ò-c¸c cña hai tËp convD bao låi cña tËp argmin{f (x) AT xk → x VI n-chiÒu trÞ tuyÖt ®èi cña sè thùc β tËp A lµ tËp con thùc sù cña tËp B tËp A lµ tËp con cña tËp B A vµ B D | x ∈ C} tËp c¸c ®iÓm cùc tiÓu cña hµm f trªn C ma trËn chuyÓn vÞ cña ma trËn A d·y {xk } héi tô m¹nh tíi x bµi to¸n bÊt ®¼ng thøc biÕn ph©n Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 5 Lêi nãi ®Çu Theo Harker vµ Pang, bµi to¸n bÊt ®¼ng thøc biÕn ph©n ®­îc giíi thiÖu lÇn ®Çu tiªn vµo n¨m 1966 bëi Hartman vµ Stampacchia. Nh÷ng nghiªn cøu ®Çu tiªn vÒ bÊt ®¼ng thøc biÕn ph©n liªn quan tíi viÖc gi¶i c¸c bµi to¸n biÕn ph©n, bµi to¸n ®iÒu khiÓn tèi ­u vµ c¸c bµi to¸n biªn cã d¹ng cña ph­¬ng tr×nh ®¹o hµm riªng. Bµi to¸n biÕn ph©n trong kh«ng gian v« h¹n chiÒu vµ c¸c øng dông cña nã ®­îc giíi thiÖu trong cuèn s¸ch "An introduction to variational inequalities and their application" cña Kinderlehrer vµ Stampacchia xuÊt b¶n n¨m 1980 vµ trong cuèn s¸ch "Variational and quasivariational inequalities: Application to free boundary problems" cña Baiocchi vµ Capelo xuÊt b¶n n¨m 1984. N¨m 1979 Michael J. Smith ®­a ra bµi to¸n c©n b»ng m¹ng giao th«ng vµ n¨m 1980 Defermos chØ ra r»ng: §iÓm cÇn b»ng cña bµi to¸n nµy lµ nghiÖm cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n. Tõ ®ã bµi to¸n bÊt ®¼ng thøc biÕn ph©n ®­îc ph¸t triÓn vµ trë thµnh mét c«ng cô h÷u hiÖu ®Ó nghiªn cøu vµ gi¶i c¸c bµi to¸n c©n b»ng trong kinh tÕ tµi chÝnh, vËn t¶i, lý thuyÕt trß ch¬i vµ nhiÒu bµi to¸n kh¸c (xem [7]). Bµi to¸n bÊt ®¼ng thøc biÕn ph©n cã quan hÖ mËt thiÕt víi c¸c bµi to¸n tèi ­u kh¸c. Bµi to¸n bï phi tuyÕn, xuÊt hiÖn vµo n¨m 1964 trong luËn ¸n tiÕn sÜ cña Cottle, lµ mét tr­êng hîp ®Æc biÖt cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n (xem [5]). GÇn ®©y, bµi to¸n bÊt ®¼ng thøc biÕn ph©n còng lµ mét ®Ò tµi ®­îc nhiÒu ng­êi quan t©m nghiªn cøu v× vai trß cña nã trong lý thuyÕt to¸n häc vµ trong c¸c øng dông thùc tÕ (xem [5, 7]). Mét trong c¸c h­íng nghiªn cøu quan träng cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n lµ viÖc x©y dùng c¸c ph­¬ng ph¸p gi¶i. Th«ng th­êng c¸c ph­¬ng ph¸p gi¶i ®­îc chia thµnh c¸c lo¹i sau: Lo¹i thø nhÊt lµ c¸c ph­¬ng ph¸p chuyÓn bµi to¸n vÒ hÖ ph­¬ng tr×nh vµ dïng c¸c ph­¬ng ph¸p th«ng dông nh­ ph­¬ng ph¸p Newton, ph­¬ng ph¸p ®iÓm trong ®Ó gi¶i hÖ ph­¬ng tr×nh nµy. Lo¹i thø hai lµ ph­¬ng ph¸p cã tÝnh chÊt kiÓu ®¬n ®iÖu. §iÓn h×nh cña ph­¬ng ph¸p nµy lµ c¸c ph­¬ng ph¸p gradient sau nµy ®­îc tæng qu¸t bëi Cohen thµnh nguyªn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 6 lý bµi to¸n phô (xem [5]), ph­¬ng ph¸p ®iÓm gÇn kÒ cña Rockafellar (xem [3]), ph­¬ng ph¸p hiÖu chØnh Tikhonov (xem [5]),.... C¸c ph­¬ng ph¸p nµy kh¸ hiÖu qu¶, dÔ thùc thi trªn m¸y tÝnh nh­ng c¸c ®iÒu kiÖn héi tô chØ ®­îc ®¶m b¶o d­íi c¸c gi¶ thiÕt kh¸c nhau vÒ tÝnh chÊt ®¬n ®iÖu. Lo¹i thø ba lµ c¸c ph­¬ng ph¸p ®­îc dùa trªn kü thuËt hµm ch¾n (xem [5]). Néi dung chÝnh cña ph­¬ng ph¸p nµy lµ chuyÓn bµi to¸n bÊt ®¼ng thøc biÕn ph©n vÒ cùc tiÓu cña hµm ch¾n vµ sau ®ã sö dông kü thuËt tèi ­u tr¬n hoÆc kh«ng tr¬n ®Ó t×m cùc tiÓu cña hµm ch¾n. Ph­¬ng ph¸p nµy cã thÓ gi¶i ®­îc c¸c bµi to¸n víi c¸c gi¶ thiÕt rÊt nhÑ. Tuy nhiªn, tèc ®é héi tô cña thuËt to¸n ®­îc ®Ò xuÊt lµ chËm (xem [5]). Lo¹i thø t­ lµ c¸c ph­¬ng ph¸p dùa trªn c¸ch tiÕp cËn ®iÓm bÊt ®éng. Néi dung chÝnh cña ph­¬ng ph¸p nµy lµ chuyÓn bµi to¸n bÊt ®¼ng thøc biÕn ph©n vÒ t×m ®iÓm bÊt ®éng cña ¸nh x¹ nghiÖm. LuËn v¨n nµy tr×nh bµy ph­¬ng ph¸p gi¶i bµi to¸n bÊt ®¼ng thøc biÕn ph©n th«ng qua t×m ®iÓm bÊt ®éng cña ¸nh x¹ nghiÖm ®­îc viÕt trong bµi b¸o "P. N. Anh, L. D. Muu, V. H. Nguyen and J. J. Strodiot (2005), On the contraction and nonexpansiveness properties of the marginal mapping in generalized variational inequalities involving cocoercive operators, in: Generalized Convexity and Generalized Monotonicity and Applications. Eds A. Eberhard, N. Hadjisavvas and D. T. Luc, Springer, pp. 89-111". Ngoµi lêi nãi ®Çu vµ phÇn tµi liÖu tham kh¶o, luËn v¨n ®­îc chia lµm ba ch­¬ng. Ch­¬ng 1 cã tiªu ®Ò lµ "bµi to¸n bÊt ®¼ng thøc biÕn ph©n". Ch­¬ng nµy nh¾c l¹i c¸c kiÕn thøc c¬ b¶n vÒ bµi to¸n bÊt ®¼ng thøc biÕn ph©n, c¸c vÝ dô, c¸c kiÕn thøc liªn quan vµ c¸c øng dông cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n. Ch­¬ng 2 gåm hai phÇn c¬ b¶n: PhÇn thø nhÊt tr×nh bµy mèi quan hÖ gi÷a nghiÖm cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n vµ ¸nh x¹ nghiÖm. PhÇn thø hai chØ ra ¸nh x¹ nghiÖm lµ co khi hµm gi¸ lµ ®¬n ®iÖu m¹nh vµ Lipschitz. Ch­¬ng 3 tr×nh bµy ph­¬ng ph¸p lÆp Banach cho ¸nh x¹ ®ång bøc vµ mét vài tÝnh to¸n øng dông cña thuËt to¸n ®­îc ®Ò xuÊt. Khi ®ã, ¸nh x¹ nghiÖm chØ lµ kh«ng gi·n vµ viÖc t×m ®iÓm bÊt ®éng cña ¸nh x¹ kh«ng gi·n ®­îc t×m theo kiÓu ®iÓm bÊt ®éng cña Nadler. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 7 CH¦¥NG I BµI TO¸N BÊT §¼NG THøC BIÕN PH¢N 1.1. Mét sè kh¸i niÖm c¬ b¶n Cho hai vÐc t¬ x := (x1, x2, ..., xn)T , y := (y1, y2, ..., yn)T ∈ Rn hx, yi = n X xiyi i=1 ®­îc gäi lµ tÝch v« h­íng cña hai vÐc t¬ x vµ y . ChuÈn Euclide vµ kho¶ng c¸ch ®­îc x¸c ®Þnh t­¬ng øng bëi ||x|| := p hx, xi, d(x, y) := ||x − y||. Ta nh¾c l¹i mét sè kiÕn thøc c¬ b¶n cña gi¶i tÝch låi sÏ ®­îc dïng cho c¸c ch­¬ng tiÕp theo. §Þnh nghÜa 1.1. • TËp con C ⊂ Rn ®­îc gäi lµ tËp låi, nÕu λx + (1 − λ)y ∈ C ∀x, y ∈ C, λ ∈ (0, 1). • TËp con C ⊂ Rn ®­îc gäi lµ nãn, nÕu λx ∈ C ∀x ∈ C, λ ≥ 0. • Cho C ⊂ Rn hiÖu lµ mét tËp låi vµ x ∈ C , nãn ph¸p tuyÕn ngoµi cña C t¹i x, ký NC (x), ®­îc x¸c ®Þnh bëi c«ng thøc NC (x) := {w ∈ Rn : hw, y − xi ≤ 0 ∀y ∈ C}. Cho C ⊂ Rn lµ mét tËp låi, ¸nh x¹ f : C → Rn . Khi ®ã, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 8 §Þnh nghÜa 1.2. • MiÒn h÷u hiÖu cña f , ký hiÖu dom f , ®­îc x¸c ®Þnh bëi domf := {x ∈ Rn : f (x) < +∞}. •f ®­îc gäi lµ chÝnh th­êng, nÕu domf 6= ∅, f (x) > −∞ ∀x ∈ C. •f ®­îc gäi lµ hµm låi trªn C , nÕu f (λx1 + (1 − λ)x2) ≤ λf (x1) + (1 − λ)f (x2) ∀x1, x2 ∈ C, λ ∈ [0, 1]. •f ®­îc gäi lµ hµm låi chÆt trªn C , nÕu f (λx1 + (1 − λ)x2) < λf (x1) + (1 − λ)f (x2) ∀x1 6= x2 ∈ C, λ ∈ (0, 1). • f ®­îc gäi lµ hµm låi m¹nh víi hÖ sè β > 0 trªn C , nÕu ∀x1 6= x2 ∈ C, λ ∈ (0, 1), ta cã f (λx1 + (1 − λ)x2) < λf (x1) + (1 − λ)f (x2) − λ(1 − λ)β||x1 − x2||2 . B©y giê ta gi¶ sö r»ng Khi ®ã, vÐc t¬ f lµ mét hµm låi trªn tËp låi C trong kh«ng gian Rn . w ∈ Rn ®­îc gäi lµ d­íi gradient cña hµm f t¹i x ∈ C , nÕu f (y) − f (x) ≥ hw, y − xi ∀y ∈ C. TËp tÊt c¶ c¸c d­íi gradient cña hµm ký hiÖu f t¹i x ®­îc gäi lµ d­íi vi ph©n cña f , ∂f (x), hay ∂f (x) := {w ∈ Rn : f (y) − f (x) ≥ hw, y − xi ∀y ∈ C}. Khi ®ã, f ®­îc gäi lµ kh¶ d­íi vi ph©n trªn C , nÕu ∂f (x) 6= ∅ ∀x ∈ C. VÝ dô 1.1. trªn tËp Khi ®ã C Cho C lµ mét tËp låi kh¸c rçng cña kh«ng gian  0 δ(x) := +∞ nÕu x ∈ C, nÕu x∈ / C. Rn . XÐt hµm chØ ∂δC (x) = NC (x). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 9 ThËt vËy, nÕu x ∈ C th× δC (x) = 0 vµ ∂δC (x) = {w ∈ Rn : δC (y) ≥ hw, y − xi ∀y ∈ C}. Hay ∂δC (x) = {w ∈ Rn : 0 ≥ hw, y − xi ∀y ∈ C} = NC (x). VÝ dô 1.2. Trong kh«ng gian Rn cho hµm chuÈn f (x) := ||x|| x ∈ Rn . Khi ®ã,  {w ∈ Rn : ||w|| = 1, hw, xi = ||x||} ∂f (x) := B̄(0, 1) trong ®ã nÕu x 6= 0, nÕu x = 0, B̄(0, 1) lµ h×nh cÇu ®ãng, t©m t¹i 0 vµ b¸n kÝnh 1. ThËt vËy, ta xÐt c¸c tr­êng hîp sau: Tr­êng hîp 1. Víi x 6= 0, ta cÇn chøng minh ∂f (x) = {w ∈ Rn : ||w|| = 1, hw, xi = ||x||}. NÕu w tháa m·n ||w|| = 1, hw, xi = ||x|| th× hw, xi ≤ ||w||.||x|| = ||x||. Do ®ã hw, x − yi ≤ ||x|| − ||y||. Hay w ∈ ∂f (x). Ng­îc l¹i, nÕu w ∈ ∂f (x), th× −||x|| = ||0|| − ||x|| ≥ hw, 0 − xi = −hw, xi, ||x|| = ||2x|| − ||x|| ≥ hw, 2x − xi = hw, xi suy ra ||x|| = hw, xi. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (∗) http://www.Lrc-tnu.edu.vn 10 MÆt kh¸c ||λz + x|| − ||x|| ≥ hw, λz + x − xi = hw, λzi ∀λ > 0, z ∈ Rn . Suy ra Cho x 1 ||z + || − ||x|| ≥ hw, xi. λ λ λ → ∞, ta nhËn ®­îc ||z|| ≥ hw, zi ∀z ∈ Rn . Do vËy ||w|| ≤ 1. H¬n n÷a nÕu thay z= ||w|| < 1 th× víi mäi z ∈ Rn , ||z|| = 1 ta cã |hw, zi| < 1. Khi ®ã, x ||x|| ta cã |hw, zi| = |hw, x i| < 1. ||x|| Do ®ã hw, xi < ||x||. §iÒu nµy m©u thuÉn víi Tr­êng hîp 2. Víi (∗). VËy ||w|| = 1. x = 0. Ta cã ∂f (x) = {w ∈ Rn : hw, yi ≤ ||y|| ∀y} = {w ∈ Rn : ||w|| ≤ 1} = B̄(0, 1). 1.2. Ph¸t biÓu bµi to¸n vµ vÝ dô "Bµi to¸n bÊt ®¼ng thøc biÕn ph©n" lµ mét trong nh÷ng bµi to¸n ®­îc quan t©m nhiÒu trong to¸n häc nãi chung vµ ®Æc biÖt trong ngµnh tèi ­u tÝnh to¸n nãi riªng. LuËn v¨n nµy sÏ tr×nh bµy mét ph­¬ng ph¸p gi¶i bµi to¸n bÊt ®¼ng thøc biÕn ph©n trong kh«ng gian h÷u h¹n chiÒu. Ch­¬ng nµy bao gåm viÖc nh¾c l¹i c¸c kiÕn thøc c¬ b¶n nhÊt vÒ bµi to¸n bÊt ®¼ng thøc biÕn ph©n sÏ ®­îc sö dông cho c¸c ch­¬ng sau. Bµi to¸n bÊt ®¼ng thøc biÕn ph©n trong kh«ng gian h÷u h¹n chiÒu cã thÓ ®­îc ph¸t biÓu nh­ sau: C lµ mét tËp con låi, ®ãng kh¸c rçng cña kh«ng gian Euclidean n-chiÒu Rn , F : C → Rn lµ ¸nh x¹ liªn tôc. Bµi to¸n bÊt ®¼ng thøc biÕn ph©n Cho Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 11 (viÕt t¾t lµ: VI) lµ bµi to¸n t×m ®iÓm x∗ ∈ C , sao cho: hF (x∗), x − x∗i ≥ 0 ∀x ∈ C. TËp nghiÖm cña VI ký hiÖu lµ §Þnh nghÜa 1.3. ¸nh x¹. Khi ®ã, F (a) ®¬n ®iÖu trªn C Cho (1.1) S ∗. lµ tËp låi, ®ãng trong Rn , vµ cho F : C → Rn lµ mét ®­îc gäi lµ: C , nÕu: hF (u) − F (v) , u − vi ≥ 0 ∀u, v ∈ C (b) ®¬n ®iÖu ngÆt trªn C , nÕu: hF (u) − F (v) , u − vi > 0 ∀u, v ∈ C, u 6= v. (c) ®¬n ®iÖu m¹nh trªn C víi h»ng sè τ > 0 (viÕt t¾t lµ:τ -®¬n ®iÖu m¹nh) nÕu: hF (u) − F (v) , u − vi ≥ τ ku − vk2 δ (d) ®ång bøc víi m« ®un ∀u, v ∈ C. (viÕt t¾t lµ:δ -®ång bøc) trªn C nÕu tån t¹i mét sè δ > 0 sao cho: hF (u) − F (v), u − vi ≥ δ||F (u) − F (v)||2 u, v ∈ C. Ta nh¾c l¹i kÕt qu¶ t­¬ng ®­¬ng sau: NhËn xÐt 1.1. Cho C tôc trªn tËp më chøa i) F ®¬n ®iÖu trªn C lµ mét tËp låi vµ F : C → Rn lµ mét ¸nh x¹ kh¶ vi liªn C . Khi ®ã, khi vµ chØ khi ∇F (x) lµ nöa x¸c ®Þnh d­¬ng trªn C hay hy, ∇F (x)yi ≥ 0 ∀y ∈ C. ii) F ®¬n ®iÖu chÆt trªn C khi vµ chØ khi ∇F (x) lµ x¸c ®Þnh d­¬ng trªn C hay hy, ∇F (x)yi > 0 ∀y ∈ C, y 6= 0. iii) C F ®¬n ®iÖu m¹nh trªn hay tån t¹i C khi vµ chØ khi ∇F (x) lµ x¸c ®Þnh d­¬ng ®Òu trªn β > 0 sao cho hy, ∇F (x)yi > β||y||2 ∀y ∈ C, y 6= 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 12 C¸c vÝ dô d­íi ®©y cho ta thÊy ®­îc c¸ch tiÕp cËn cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n VÝ dô 1.3. x0 ∈ C Cho f (x) lµ mét hµm thùc kh¶ vi trªn tËp më chøa C = [a, b]. T×m sao cho f (x0) = min f (x). x∈C x0 ∈ [a, b], suy ra cã 3 tr­êng hîp x¶y ra: x0 ∈ (a, b), theo ®Þnh lý Fermat, ta cã f 0 (x0) = 0. f (x)−f (x0 ) ≥ 0. TH2: NÕu x0 = a, f 0 (x0 ) = lim x−x0 0 TH1: NÕu x→x+ TH2: NÕu 0 0 0 x = b, f (x ) = lim0 KÕt hîp l¹i, ta cã thÓ viÕt: x→x− 0 f (x)−f (x0 ) x−x0 ≤ 0. x lµ nghiÖm cña bµi to¸n f 0 (x0).(x − x0) ≥ 0 ∀x ∈ C. Nh­ vËy x0 lµ nghiÖm cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n VI víi F = f 0 trªn C = [a, b]. B©y giê, ta xÐt vÝ dô tæng qu¸t h¬n VÝ dô 1.4. x0 ∈ C Cho f (x) lµ mét hµm thùc kh¶ vi trªn tËp më chøa C ⊆ IRn. T×m sao cho f (x0) = min f (x). x∈C MÖnh ®Ò 1.1. NÕu x0 lµ nghiÖm cña bµi to¸n trªn, th× to¸n bÊt ®¼ng thøc biÕn ph©n VI víi Chøng minh. Víi mäi x0 lµ nghiÖm cña bµi F (x) := ∇f (x). y ∈ C , do C låi nªn (1 − t)x0 + ty ∈ C ∀t ∈ [0, 1]. §Æt ϕ(t) := f (x0 + t(y − x0 )). Gi¶ thiÕt cho x0 lµ nghiÖm hay t = 0 lµ nghiÖm cña ϕ(t) trªn [0, 1]. Theo VÝ dô 1.3, ta cã ϕ0 (t0 ).(t − t0) ≥ 0 ∀t ∈ [0, 1]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 13 Hay h∇f (x0), x − x0i ≥ 0 ∀x ∈ C. 2 MÖnh ®Ò 1.2. Cho f lµ hµm låi kh¶ vi trªn tËp låi C ⊆ Rn . Khi ®ã, x0 ∈ C lµ nghiÖm cña bµi to¸n min f (x) x∈C khi vµ chØ khi x0 lµ nghiÖm cña bµi to¸n bÊt ®¼ng thøc VI víi F (x) := ∇f (x). Chøng minh. §iÒu kiÖn cÇn ®­îc suy ra tõ MÖnh ®Ò 1.1. Do trªn f lµ hµm låi C , nªn f (x) − f (x0) ≥ h∇f (x0), x − x0i ∀x ∈ C. Gi¶ thiÕt cho h∇f (x0), x − x0i ≥ 0 ∀x ∈ C. Do ®ã f (x) ≥ f (x0) ∀x ∈ C. Hay x0 lµ nghiÖm cña bµi to¸n min f (x). x∈C 2 VÝ dô 1.5. Cho (Bµi to¸n bï, ký hiÖu CP) C = Rn+ vµ F : C → Rn . Bµi to¸n ®­îc ®Æt ra lµ: T×m ®iÓm x0 ∈ C sao cho F (x0) ∈ C, MÖnh ®Ò 1.3. x0 ∈ C = Rn+ hF (x0), x0i = 0. lµ nghiÖm cña bµi to¸n bï CP khi vµ chØ khi lµ nghiÖm cña bµi to¸n VI hay hF (x0), x − x0i ≥ 0 ∀x ∈ C. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn x0 14 Chøng minh. (⇒) Gi¶ sö x0 lµ nghiÖm cña bµi to¸n bï CP hay F (x0) ∈ C, hF (x0), x0i = 0. Khi ®ã hF (x0), x − x0i = hF (x0), xi − hF (x0 ), x0i = hF (x0), xi ≥ 0 ∀x ∈ C. (⇐) Gi¶ sö x0 lµ nghiÖm cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n VI hay x0 ∈ C : hF (x0 ), x − x0i ≥ 0 ∀x ∈ C. Gäi ei Thay = (0, 0, ..., 0, 1, 0, ...0)T (1 ë vÞ trÝ thø i). Khi ®ã, x1 = x0 + ei ∈ C . x1 vµo bÊt ®¼ng thøc biÕn ph©n, ta cã hF (x0), x1 − x0i ≥ 0. Hay hF (x0), eii ≥ 0 ∀i = 1, 2, ...n. VËy F (x0) ∈ C . Tõ 0 ∈ C vµ hF (x0), x − x0i ≥ 0 ∀x ∈ C. suy ra −hF (x0), x0i ≥ 0. Do ®ã hF (x0), x0i = 0. 2 D­íi ®©y ta xÐt hai vÝ dô thùc tÕ cña bµi to¸n VI. VÝ dô 1.6. Bµi to¸n c©n b»ng m¹ng giao th«ng XÐt mét m¹ng giao th«ng ®­îc cho bëi mét m¹ng luång h÷u h¹n. Gäi •N : tËp hîp c¸c nót cña m¹ng. •A: lµ tËp hîp c¸c c¹nh (mçi c¹nh ®­îc gäi lµ mét ®o¹n ®­êng). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 15 Gi¶ sö O ⊆ N, D ⊆ N O ∩ D = ∅. Mçi phÇn tö cña O ®­îc gäi lµ cña D ®­îc gäi lµ ®iÓm ®Ých. Mçi ®iÓm nguån sao cho ®iÓm nguån, cßn mçi phÇn tö vµ ®iÓm ®Ých ®­îc nèi víi nhau bëi mét tËp hîp liªn tiÕp c¸c c¹nh (®­îc gäi lµ mét tuyÕn ®­êng). Ký hiÖu: •fai lµ mËt ®é giao th«ng cña ph­¬ng tiÖn vÐc t¬ cã c¸c thµnh phÇn lµ fai víi i∈I i vµ trªn ®o¹n ®­êng a ∈ A (I a ∈ A. f §Æt lµ lµ tËp hîp c¸c ph­¬ng tiÖn giao th«ng. •cia lµ chi phÝ khi sö dông ph­¬ng tiÖn giao th«ng i ∈ I, a ∈ A. ph­¬ng tiÖn i ∈ I trªn lµ vÐc t¬ cã c¸c thµnh phÇn lµ •diw lµ nhu cÇu sö dông víi O ∈ O, D ∈ D . lo¹i cia i trªn ®o¹n ®­êng A. c víi tuyÕn ®­êng w = (O, D) Gi¶ sö r»ng chi phÝ giao th«ng phô thuéc vµo l­u l­îng, tøc lµ mét hµm cña §Æt c = c(f ) lµ f. •λiw lµ møc ®é chi phÝ trªn tuyÕn ®­êng •xiw lµ mËt ®é giao th«ng cña ph­¬ng tiÖn w cña ph­¬ng tiÖn giao th«ng i. i∈I trªn tuyÕn w ∈ O × D. Gi¶ sö trong m¹ng trªn, ph­¬ng tr×nh c©n b»ng sau ®­îc tho¶ m·n diw = X xip ∀i ∈ I, w ∈ O × D, (1.2) p∈Pw Pw ký hiÖu tËp hîp c¸c tuyÕn ®­êng cña w = (O, D) (nèi ®iÓm nguån O vµ ®iÓm ®Ých D). Theo ph­¬ng tr×nh (2.18), th× nhu cÇu sö dông lo¹i ph­¬ng trong ®ã, tiÖn i trªn tuyÕn ®­êng w b»ng ®óng tæng mËt ®é giao th«ng cña ph­¬ng tiÖn ®ã trªn mäi tuyÕn ®­êng nèi ®iÓm nguån vµ ®iÓm ®Ých cña tuyÕn ®­êng ®ã. Khi ®ã ta cã fai = X xipδap ∀i ∈ I, w ∈ O × D, (1.3) p∈Pw trong ®ã δap :=  1 0 nÕu a ∈ p, nÕu a∈ / p. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 16 Víi mçi tuyÕn ®­êng p nèi mét ®iÓm nguån vµ mét ®iÓm ®Ých, ®Æt X cip = cia δap. (1.4) a∈A cip i trªn tuyÕn ®­êng p. §Æt d lµ vÐc t¬ cã c¸c thµnh phÇn lµ diw (i ∈ I, w ∈ O × D) vµ ®Æt f lµ vÐc t¬ cã i ∗ ∗ c¸c thµnh phÇn lµ da (i ∈ I, a ∈ O × D). Mét cÆp (d , f ) tho¶ m·n c¸c ®iÒu Nh­ vËy, lµ mét chi phÝ khi sö dông ph­¬ng tiÖn kiÖn (2.18) vµ (2.21) ®­îc gäi lµ ®iÓm c©n b»ng cña m¹ng giao th«ng nÕu  λi (d∗) w i ∗ cp (f ) = > λi (d∗) w i∈I víi mçi vµ mçi tuyÕn ®­êng p. khi xip > 0, khi xip = 0, Theo ®Þnh nghÜa nµy, t¹i ®iÓm c©n b»ng ®èi víi mäi lo¹i ph­¬ng tiÖn giao th«ng vµ mäi tuyÕn ®­êng, chi phÝ sÏ thÊp nhÊt khi cã l­u l­îng giao th«ng trªn tuyÕn ®ã. Tr¸i l¹i, chi phÝ sÏ kh«ng ph¶i thÊp nhÊt. §Æt K = {(f, d) | ∃ x ≥ 0 sao cho (2.18) vµ (2.21) ®óng}. Khi ®ã, ta cã ®Þnh lý sau. §Þnh lý 1.1. Mét cÆp vÐc t¬ (f ∗, d∗) ∈ K lµ mét ®iÓm c©n b»ng cña m¹ng giao th«ng khi vµ chØ khi nã lµ nghiÖm cña bÊt ®¼ng thøc biÕn ph©n sau: T×m (f ∗ , d∗ ) ∈ K sao cho
h c(f ∗)), λ(d∗) , (f, d)−(f ∗, d∗)i ≥ 0 ∀(f, d) ∈ K. VÝ dô 1.7. Bµi to¸n kinh tÕ b¸n ®éc quyÒn Gi¶ sö cã mçi c«ng ty σ := Pn i n c«ng ty pi cña phô thuéc vµo tæng sè l­îng s¶n phÈm cña tÊt c¶ c¸c c«ng ty i=1 xi . Ký hiÖu hµng ho¸ cïng s¶n xuÊt mét lo¹i s¶n phÈm vµ lîi nhuËn hi (xi) lµ chi phÝ cña c«ng ty i khi s¶n xuÊt ra l­îng xi. Gi¶ sö r»ng lîi nhuËn cña c«ng ty i ®­îc cho bëi fi (x1, ..., xn) = xipi ( n X xi) − hi (xi) (i = 1, ..., n), (1.5) i=1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 17 trong ®ã p( Pn j=1 xj ) lµ gi¸ cña mét ®¬n vÞ s¶n phÈm, phô thuéc vµo tæng s¶n phÈm, cßn hµm chi phÝ cña mçi c«ng ty i chØ phô thuéc vµo møc ®é s¶n xuÊt cña c«ng ty ®ã. §Æt Ui ⊂ IR, (i = 1, ..., n) lµ tËp chiÕn l­îc cña c«ng ty i. LÏ dÜ nhiªn, mçi c«ng ty cÇn x¸c ®Þnh cho m×nh mét møc ®é s¶n xuÊt ®Ó ®¹t ®­îc lîi nhuËn cao nhÊt. Tuy nhiªn, trong tr­êng hîp tæng qu¸t, viÖc tÊt c¶ c¸c c«ng ty ®Òu cã lîi nhuËn cùc ®¹i lµ khã cã thÓ ®­îc. V× vËy ng­êi ta dïng ®Õn kh¸i niÖm c©n b»ng: Mét ®iÓm x∗ = (x∗1, ..., x∗n) ∈ U := U1 × ... × Un ®­îc gäi lµ ®iÓm c©n b»ng Nash nÕu fi(x∗1, ..., x∗i−1, yi, x∗i+1, ..., x∗n) 6 fi(x∗1, ..., x∗n) ∀yi ∈ Ui, ∀i = 1, ..., n. Trong m« h×nh c©n b»ng Cournot cæ ®iÓn, hµm chi phÝ vµ hµm lîi nhuËn cña mçi c«ng ty lµ affine cã d¹ng pi (σ) ≡ p(σ) = α0 − βσ, α0 ≥ 0, β > 0, víi σ= hi (xi) = µi xi + ξi , µi ≥ 0, ξi ≥ 0 (i = 1, ..., n). Pn i=1 xi , Ta ®Æt  β  0 A= ...  0 vµ 0 β   0 ... 0 0    0 ... 0   , à =  β ... ... ... ... ...   0 0 0 β β  β β ... β  0 β ... β   ... ... ... ...  β β ... 0 αT = (α0 , ..., α0), µT = (µ1, ..., µn). §iÓm x∗ lµ ®iÓm c©n b»ng Nash khi vµ chØ khi x∗ lµ nghiÖm cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n:  T×m ®iÓm x ∈ U sao cho hÃx + µ − α, y − xi + y T Ay − xT Ax ≥ 0 ∀y ∈ U. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 18 1.3. Sù tån t¹i nghiÖm cña bµi to¸n VI Sù tån t¹i nghiÖm cña bµi to¸n VI phô thuéc vµo hµm gi¸ F vµ miÒn rµng buéc C . Trong môc nµy, ta chØ xÐt hµm F lµ liªn lôc trªn tËp më chøa C vµ miÒn rµng buéc C lµ mét tËp låi ®ãng trong kh«ng gian Rn . §Þnh lý 1.2. NÕu C ⊆ Rn lµ mét tËp låi, compact vµ F liªn tôc trªn C , th× bµi to¸n bÊt ®¼ng thøc biÕn ph©n VI cã nghiÖm. Chøng minh. §Æt ¸nh x¹ f = P rC (I − F ), trong ®ã P rC lµ phÐp chiÕu trªn C ®­îc x¸c ®Þnh bëi c«ng thøc P rC (x) = inf{||x − y|| : y ∈ C} vµ I lµ ¸nh x¹ ®ång nhÊt. Bæ ®Ò 1.1. (®Þnh lý Browder, xem [8]) C ⊆ Rn F :C→C tån t¹i Ýt nhÊt mét ®iÓm bÊt ®éng cña ¸nh x¹ F . Cho lµ mét tËp låi, compact vµ DÔ dµng thÊy r»ng liªn tôc trªn C. Khi ®ã, F liªn tôc trªn C nªn f còng liªn tôc trªn C . Theo Bæ f cã ®iÓm bÊt ®éng, hay tån t¹i x∗ ∈ C sao cho x∗ = f (x∗), hay x∗ = P rC (x∗ − F (x∗)). Theo ®Þnh nghÜa cña phÐp chiÕu P rC , ta cã ®Ò 1.1, ¸nh x¹ hx∗ , y − x∗ i ≥ h(I − F )(x∗), y − x∗ i ∀y ∈ C. Do vËy, hx∗ , y − x∗ i ≥ hx∗ − F (x∗), y − x∗i ∀y ∈ C. Hay x∗ lµ nghiÖm cña bµi to¸n VI hF (x∗ ), y − x∗i ∀y ∈ C. 2 B©y giê ta xÐt sù tån t¹i nghiÖm cña bµi to¸n VI trong tr­êng hîp miÒn chÊp nhËn ®­îc C kh«ng bÞ chÆn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn