Tài liệu Nghiên cứu hiệu chỉnh hóa trong bài toán cân bằng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ KIM NGỌC NGHIÊN CỨU HIỆU CHỈNH HÓA TRONG BÀI TOÁN CÂN BẰNG LUẬN VĂN THẠC SĨ TOÁN HỌC 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.vn1 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ KIM NGỌC NGHIÊN CỨU HIỆU CHỈNH HÓA TRONG BÀI TOÁN CÂN BẰNG 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ười hướng dẫn khoa học: GS. TSKH LÊ DŨNG MƯU 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.vn2 Môc lôc Môc lôc 1 Më ®Çu 2 Ch­¬ng 1. Bµi to¸n c©n b»ng 4 1.1. C¸c kiÕn thøc chuÈn bÞ . . . . . . . . . . . . . . . . . . . . 4 1.2. Bµi to¸n c©n b»ng vµ c¸c tr­êng hîp riªng . . . . . . . . . . 9 Ch­¬ng 2. Ph­¬ng ph¸p chiÕu vµ ®¹o hµm t¨ng c­êng gi¶i bµi to¸n c©n b»ng 16 2.1. Ph­¬ng ph¸p chiÕu gi¶i bµi to¸n c©n b»ng . . . . . . . . . . 16 2.2. Ph­¬ng ph¸p ®¹o hµm t¨ng c­êng gi¶i bµi to¸n c©n b»ng . . 25 Ch­¬ng 3. Ph­¬ng ph¸p hµm ®¸nh gi¸ 40 3.1. Hµm ®¸nh gi¸ A.Auslender . . . . . . . . . . . . . . . . . . 42 3.2. Hµm ®¸nh gi¸ M.Fukushima . . . . . . . . . . . . . . . . . 48 KÕt luËn 53 Tµi liÖu tham kh¶o 54 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 http://www.Lrc-tnu.edu.vn3 Më ®Çu Bµi to¸n c©n b»ng cã nhiÒu øng dông trong khoa häc, kÜ thuËt vµ ®êi sèng nh­: vËt lÝ (®Æc biÖt lµ c¬ häc), ho¸ häc, sinh häc, qu©n sù, n«ng nghiÖp, kinh tÕ, viÔn th«ng... Bµi to¸n c©n b»ng lµ bµi to¸n tæng qu¸t, nã bao gåm c¸c tr­êng hîp riªng nh­: bµi to¸n tèi ­u, bµi to¸n bÊt ®¼ng thøc biÕn ph©n, bµi to¸n bï phi tuyÕn, bµi to¸n Nash trong trß ch¬i hîp t¸c... Do cã øng dông thùc tÕ réng r·i nªn viÖc quy vÒ bµi to¸n c©n b»ng vµ ®­a ra c¸c thuËt to¸n gi¶i bµi to¸n c©n b»ng lµ cÇn thiÕt. Ngµy nay víi sù ph¸t triÓn nhanh chãng cña kÜ thuËt tin häc nªn ph¹m vi vµ kh¶ n¨ng øng dông cña bµi to¸n c©n b»ng ngµy cµng më réng. LuËn v¨n nµy nh»m giíi thiÖu vÒ bµi to¸n c©n b»ng vµ mét sè ph­¬ng ph¸p hiÖu chØnh cho bµi to¸n c©n b»ng. LuËn v¨n gåm môc lôc, ba ch­¬ng, phÇn kÕt luËn vµ tµi liÖu tham kh¶o. Ch­¬ng 1 tr­íc hÕt nh¾c l¹i kh¸i niÖm vµ kÕt qu¶ c¬ b¶n nhÊt vÒ tËp låi vµ hµm låi sÏ ®­îc dïng ë c¸c ch­¬ng sau. TiÕp theo lµ giíi thiÖu vÒ bµi to¸n c©n b»ng vµ c¸c tr­êng hîp riªng cña nã. PhÇn nµy ®­îc coi lµ c¬ së lÝ thuyÕt cho c¸c ph­¬ng ph¸p sÏ dïng ®Õn ë c¸c ch­¬ng sau. Ch­¬ng 2 tr×nh bµy hai ph­¬ng ph¸p hiÖu chØnh bµi to¸n c©n b»ng, ®ã lµ ph­¬ng ph¸p chiÕu vµ ph­¬ng ph¸p ®¹o hµm t¨ng c­êng. Ch­¬ng 3 giíi thiÖu hai lo¹i hµm ®¸nh gi¸ lµ hµm ®¸nh gi¸ Auslender vµ hµm ®¸nh gi¸ Fukushima. C¸c thuËt to¸n t­¬ng øng víi hai lo¹i hµm ®¸nh gi¸ nµy ®­îc tr×nh bµy chi tiÕt trong ch­¬ng 3. §Ó hoµn thµnh luËn v¨n nµy, t¸c gi¶ ®· nhËn ®­îc sù gióp ®ì vµ h­íng dÉn tËn t×nh cña GS.TSKH. Lª Dòng M­u. T¸c gi¶ xin bµy tá lßng biÕt ¬n s©u s¾c ®Õn thµy cña m×nh. T¸c gi¶ xin ch©n thµnh c¶m ¬n c¸c thµy c« trong Bé m«n to¸n, Tr­êng §¹i häc Khoa häc- §¹i häc Th¸i Nguyªn, cïng c¸c b¹n häc viªn líp cao häc to¸n K1 ®· lu«n t¹o ®iÒu kiÖn thuËn lîi, ®éng viªn, khÝch lÖ ®Ó luËn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 http://www.Lrc-tnu.edu.vn4 v¨n ®­îc hoµn thµnh. MÆc dï t¸c gi¶ ®· cè g¾ng nh­ng luËn v¨n khã tr¸nh khái nh÷ng thiÕu sãt, h¹n chÕ. T¸c gi¶ mong nhËn ®­îc nh÷ng ý kiÕn ®ãng gãp cña c¸c thµy c« vµ b¹n ®äc ®Ó luËn v¨n ®­îc hoµn thiÖn h¬n. Th¸i Nguyªn, 10/2009 Häc viªn Hoµng ThÞ Kim Ngäc Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3 http://www.Lrc-tnu.edu.vn5 Ch­¬ng 1 Bµi to¸n c©n b»ng Ch­¬ng nµy nh»m giíi thiÖu mét sè kh¸i niÖm vµ kiÕn thøc c¬ b¶n vÒ bµi to¸n c©n b»ng vµ c¸c tr­êng hîp riªng cña nã. Tr­íc tiªn ta kh¸i qu¸t l¹i mét sè kiÕn thøc vÒ gi¶i tÝch låi sÏ dïng ®Õn trong c¸c phÇn cña luËn v¨n. 1.1. C¸c kiÕn thøc chuÈn bÞ Gi¶i tÝch låi ®ãng vai trß quan träng trong viÖc nghiªn cøu, ph©n tÝch vµ x©y dùng c¸c thuËt to¸n gi¶i bµi to¸n c©n b»ng. Môc ®Ých chÝnh cña phÇn nµy lµ nh¾c l¹i mét sè kiÕn thøc vÒ gi¶i tÝch låi, c¸c ®Þnh lý kh«ng ®­îc chøng minh cã thÓ xem trong KÝ hiÖu [4]. R lµ tËp sè thùc, Rn lµ kh«ng gian Euclid n chiÒu. §Þnh nghÜa 1.1.1. [4] Cho hai ®iÓm a, b trong kh«ng gian Euclid n-chiÒu Rn . §­êng th¼ng ®i qua hai ®iÓm a, b lµ tËp hîp c¸c ®iÓm x trong Rn cã d¹ng: x = λa + (1 − λ)b, ∀λ ∈ R. §o¹n th¼ng nèi a, b lµ tËp hîp tÊt c¶ c¸c ®iÓm x trong Rn cã d¹ng: x = λa + (1 − λ)b = λ(a − b) + b, 0 ≤ λ ≤ 1. §Þnh nghÜa 1.1.2. [4] TËp A ⊆ Rn gäi lµ , nÕu nã chøa trän ®o¹n tËp låi th¼ng nèi hai ®iÓm bÊt k× thuéc nã. VÝ dô 1.1.1. H×nh 1.1 cho ta vÝ dô ®¬n gi¶n vÒ tËp låi vµ tËp kh«ng låi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4 http://www.Lrc-tnu.edu.vn6 (b) (a) H×nh (c) (d) 1.1. (a), (c)- TËp låi; (b), (d)- TËp kh«ng låi §Þnh lý 1.1.1. [1] TËp låi lµ ®ãng víi phÐp giao, phÐp hîp, phÐp céng, phÐp nh©n víi mét sè vµ phÐp lÊy tæ hîp tuyÕn tÝnh. Tøc lµ, nÕu tËp låi trong Rn A vµ B lµ hai th× c¸c tËp sau còng lµ tËp låi: a, A ∩ B := {x : x ∈ A, x ∈ B}, b, αA + βB := {x = αa + βb : a ∈ A, b ∈ B}. §Þnh nghÜa 1.1.3. [1] TËp A ⊂ Rn ®­îc gäi lµ nãn nÕu: x ∈ A, λ ≥ 0 ⇒ λx ∈ A. Mét nãn lu«n chøa ®iÓm gèc 0 ∈ Rn . TËp A ⊂ Rn ®­îc gäi lµ nãn låi nÕu A võa lµ nãn võa lµ tËp låi, tøc lµ λ1 x + λ2 y ∈ A, ∀x, y ∈ A, ∀λ1 , λ2 ≥ 0. A ⊂ Rn vµ ®iÓm x0 ∈ clA. TËp    NC (x0 ) = t ∈ Rn : t, x − x0 ≤ 0, ∀x ∈ A §Þnh nghÜa 1.1.4. [4] lµ mét nãn låi ®ãng Cho tËp låi hay lµ nãn ph¸p tuyÕn ngoµi cña A t¹i x0 . A ⊆ Rn . Vecto d 6= 0 ®­îc gäi lµ ph­¬ng lïi xa cña A nÕu víi mçi x ∈ A cã: §Þnh nghÜa 1.1.5. [3] Cho tËp låi kh¸c rçng {x + λd | λ ≥ 0} ⊂ A. NhËn xÐt [3] ? Mäi nöa ®­êng th¼ng song song víi mét ph­¬ng lïi xa d xuÊt ph¸t tõ mét ®iÓm bÊt k× cña A ®Òu n»m trän trong A. Râ rµng, tËp A kh«ng bÞ chÆn khi Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5 http://www.Lrc-tnu.edu.vn7 vµ chØ khi A cã mét ph­¬ng lïi xa. ? TËp tÊt c¶ c¸c ph­¬ng lïi xa cña tËp låi A ⊆ Rn cïng vecto 0 t¹o thµnh nãn låi. Nãn låi ®­îc gäi lµ nãn lïi xa cña tËp A vµ kÝ hiÖu lµ recA. ? Ta nãi hai ph­¬ng d1 vµ d2 lµ kh¸c biÖt nÕu d1 6= αd2 , α > 0. Ph­¬ng lïi xa d cña tËp A ®­îc gäi lµ ph­¬ng cùc biªn cña A nÕu kh«ng tån t¹i c¸c ph­¬ng lïi xa kh¸c biÖt d1 vµ d2 cña A sao cho d §Þnh nghÜa 1.1.6. [1] Mét tËp hîp lµ giao cña mét sè h÷u h¹n c¸c nöa kh«ng gian ®ãng ®­îc gäi lµ §Þnh nghÜa 1.1.7. [1] = λ1 d1 +λ2 d2 , λ1 , λ2 > 0. tËp låi ®a diÖn TËp con hay gäi lµ . khóc låi B cña khóc låi A ®­îc gäi lµ mét diÖn cña A nÕu hÔ B chøa mét ®iÓm trong cña mét ®o¹n th¼ng nµo ®ã cña A th× B chøa c¶ ®o¹n th¼ng ®ã cña A. Tøc lµ, ∀a, b ∈ A nÕu x = λa + (1 − λ)b ∈ B, 0 < λ < 1 ⇒ a, b ∈ B . Mét diÖn cã thø nguyªn b»ng 0 ®­îc gäi lµ mét ®Ønh hay mét ®iÓm cùc biªn. C¹nh lµ diÖn cã thø nguyªn b»ng 1. §Þnh lý 1.1.2. [1] a, Mäi tËp låi ®a diÖn kh«ng chøa trän mét ®­êng th¼ng ®Òu cã Ýt nhÊt mét ®Ønh. b, Mäi tËp låi ®a diÖn A cã ®Ønh b»ng tËp hîp cña c¸c ®iÓm x cã d¹ng: X X x= λi v i + βj dj i∈I trong ®ã, P λi = 1, λi , βj ≥ 0 j∈J víi mäi i∈I ph­¬ng cña c¸c c¹nh v« h¹n cña i, j cßn vi lµ c¸c ®Ønh, dj lµ c¸c A. M, K lµ c¸c tËp låi kh¸c rçng cña Rn , M ⊆ K vµ f : K × K → R ∪ {+∞}. Khi ®ã: a, Hµm f ®¬n ®iÖu m¹nh trªn M víi h»ng sè τ > 0 nÕu víi mçi cÆp §Þnh nghÜa 1.1.8. [5] Cho x, y ∈ M ta cã: f (x, y) + f (y, x) ≤ −τ k x − y k2 . b, Hµm f ®¬n ®iÖu chÆt trªn M nÕu víi mäi x, y ∈ M ta cã: f (x, y) + f (y, x) < 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 6 http://www.Lrc-tnu.edu.vn8 c, Hµm f trªn ®¬n ®iÖu M nÕu víi mçi cÆp x, y ∈ M ta cã: f (x, y) + f (y, x) ≤ 0. d, Hµm f trªn gi¶ ®¬n ®iÖu M nÕu víi mçi cÆp x, y ∈ M th×: f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0. §Þnh nghÜa 1.1.9. [4] a, Hµm f lµ hµm låi x¸c ®Þnh trªn tËp låi X ⊆ Rn , nÕu:   f λx + (1 − λ)y ≤ λf (x) + (1 − λ)f (y), víi bÊt k× x, y ∈ X vµ sè thùc λ ∈ [0, 1]. b, Hµm f lµ hµm låi chÆt trªn tËp låi X , nÕu:   f λx + (1 − λ)y < λf (x) + (1 − λ)f (y), víi bÊt k× x, y ∈ X, x 6= y vµ λ ∈ (0, 1). c, Hµm f lµ hµm låi m¹nh víi hÖ sè β > 0 trªn tËp låi X nÕu:   f λx + (1 − λ)y ≤ λf (x) + (1 − λ)f (y) − β(1 − λ)λ k x − y k2 , víi bÊt k× x, y ∈ X vµ λ ∈ (0, 1). d, Hµm f ®­îc gäi lµ hµm tùa låi trªn tËp låi X , nÕu víi ∀α ∈ R, tËp møc d­íi Lα (f ) = {x ∈ X : f (x) ≤ α} lµ tËp låi. A vµ g lµ hµm låi trªn tËp låi B . Khi ®ã, c¸c hµm sau lµ hµm låi trªn tËp låi A ∩ B : a, λf + βg, ∀λ, β ≥ 0, §Þnh lý 1.1.3. [1] Cho f lµ hµm låi trªn tËp låi b, max(f, g). §Þnh lÝ 1.1.3 nh×n chung kh«ng ®óng cho hµm tùa låi. Mét hµm låi cã thÓ kh«ng liªn tôc t¹i mét ®iÓm trªn biªn miÒn x¸c ®Þnh cña nã. Tuy nhiªn, nã l¹i liªn tôc t¹i mäi ®iÓm trong cña tËp ®ã theo ®Þnh lÝ sau: §Þnh lý 1.1.4. [1] Mét hµm låi x¸c ®Þnh trªn tËp låi ®iÓm trong cña tËp A th× liªn tôc t¹i mäi A. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7 http://www.Lrc-tnu.edu.vn9 §Þnh lý 1.1.5. [4] Cho hµm f låi, kh¶ vi trªn tËp låi A. Khi ®ã víi mäi x, y ∈ A cã:  f (y) − f (x) ≥ ∇f (x), y − x . NÕu f låi chÆt, kh¶ vi trªn tËp låi A. Khi ®ã víi mäi x, y ∈ A vµ x 6= y ta cã:  f (y) − f (x) > ∇f (x), y − x . f lµ låi m¹nh x, y ∈ A ta cã: NÕu víi hÖ sè β > 0, kh¶ vi trªn tËp låi A. Khi ®ã víi mäi  f (y) − f (x) ≥ ∇f (x), y − x + β k y − x k2 . §Þnh lý 1.1.6. [1] Cho f lµ hµm låi, kh¶ vi trªn tËp låi ®ãng A. Mét ®iÓm x∗ ∈ A lµ nghiÖm tèi ­u cña bµi to¸n quy ho¹ch låi: min f (x) x∈A khi vµ chØ khi nã lµ ®iÓm dõng cña Tõ ®Þnh lÝ f trªn A, tøc lµ:  ∇f (x∗ ), y − x∗ ≥ 0, ∀y ∈ A. 1.1.5 vµ 1.1.6 cã: nÕu f lµ hµm låi m¹nh trªn tËp låi ®ãng A th× bµi to¸n: min f (x) x∈A cã nghiÖm duy nhÊt. f lµ mét hµm låi trªn tËp låi A. Mét vecto y ∗ ∈ Rn ®­îc gäi lµ d­íi vi ph©n cña f t¹i x∗ ∈ A nÕu:  f (x) ≥ f (x∗ ) + y ∗ , x − x∗ , ∀x ∈ A. §Þnh nghÜa 1.1.10. [1] Cho TËp hîp tÊt c¶ c¸c ®iÓm y ∗ tho¶ m·n bÊt ®¼ng thøc trªn ®­îc kÝ hiÖu ∂f (x∗ ). ∂f (x∗ ) nh×n chung th­êng chøa nhiÒu ®iÓm. Trong tr­êng hîp ∂f (x∗ ) chØ chøa duy nhÊt mét ®iÓm ta nãi r»ng f kh¶ vi t¹i x∗ . TËp Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 8 http://www.Lrc-tnu.edu.vn10 f (x) =k x k kh¶ vi t¹i mäi ®iÓm x 6= 0 do ∂f (x) = k x k−1 x,  kh«ng kh¶ vi t¹i x = 0 do ∂f (x) = {y : k x k≥ y, x , ∀y}. VÝ dô 1.1.2. D ⊂ Rn , D 6= ∅, f : D → R. Mét ®iÓm x∗ ∈ D ®­îc gäi lµ cùc tiÓu ®Þa ph­¬ng cña f trªn D, nÕu tån t¹i mét l©n cËn më U cña x∗ , sao cho f (x∗ ) ≤ f (x), ∀x ∈ D ∩ U . §iÓm x∗ ®­îc gäi lµ cùc tiÓu tuyÖt ®èi cña f trªn D nÕu f (x∗ ) ≤ f (x), ∀x ∈ D . §Þnh nghÜa 1.1.11. [3] §Þnh lý 1.1.7. [1] a, Cho Mäi ®iÓm cùc tiÓu ®Þa ph­¬ng cña mét hµm låi trªn mét tËp låi ®Òu lµ ®iÓm cùc tiÓu tuyÖt ®èi. b, NÕu x∗ lµ 0 ∈ ∂f (x∗ ). ®iÓm cùc tiÓu cña hµm låi §Þnh lý 1.1.8. [1] f trªn tËp låi D vµ x∗ ∈ intD th× Cùc ®¹i cña mét hµm låi (nÕu cã ) trªn mét tËp låi cã ®iÓm cùc biªn bao giê còng ®¹t t¹i mét ®iÓm cùc biªn. 1.2. Bµi to¸n c©n b»ng vµ c¸c tr­êng hîp riªng Bµi to¸n c©n b»ng cã ý nghÜa quan träng trong kinh tÕ vµ nhiÒu lÜnh vùc thùc tiÔn kh¸c. H¬n n÷a, bµi to¸n c©n b»ng lµ sù më réng cña nhiÒu bµi to¸n kh¸c nh­: bµi to¸n tèi ­u, bµi to¸n bÊt ®¼ng thøc biÕn ph©n, bµi to¸n c©n b»ng Nash... V× lÝ do ®ã mµ líp c¸c bµi to¸n c©n b»ng ®­îc nhiÒu nhµ to¸n häc quan t©m, nghiªn cøu. PhÇn nµy sÏ giíi thiÖu d¹ng to¸n häc cña bµi to¸n c©n b»ng vµ mét sè bµi to¸n t­¬ng ®­¬ng víi bµi to¸n c©n b»ng. Néi dung chñ yÕu cña phÇn nµy ®­îc tham kh¶o trong Trong toµn bé luËn v¨n nµy ta lu«n gi¶ thiÕt trong [2]. K lµ tËp låi ®ãng kh¸c rçng Rn . §Þnh nghÜa 1.2.1. [2] Cho hµm f : K × K → R tho¶ m·n f (x, x) = 0, ∀x ∈ K . Khi ®ã, bµi to¸n c©n b»ng ®­îc ph¸t biÓu nh­ sau: T×m x∗ ∈ K sao cho f (x∗ , y) ≥ 0, ∀y ∈ K. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 9 (1.1) http://www.Lrc-tnu.edu.vn11 Hµm sè f tho¶ m·n tÝnh chÊt f (x, x) = 0, ∀x ∈ K ®­îc gäi lµ b»ng trªn K . hµm c©n Nh­ ®· nãi ë trªn, c¸c bµi to¸n quan träng cã thÓ ®­a vÒ bµi to¸n c©n b»ng. D­íi ®©y ta tr×nh bµy sù t­¬ng ®­¬ng cña bµi to¸n c©n b»ng víi c¸c bµi to¸n kh¸c. Bµi to¸n tèi ­u Cho [2] J : K → R lµ mét hµm sè x¸c ®Þnh trªn K . Khi ®ã, bµi to¸n tèi ­u ®­îc ph¸t biÓu nh­ sau: T×m NÕu ta ®Æt x∗ ∈ K sao cho J(x∗ ) ≤ J(y), ∀y ∈ K. (1.2) f (x, y) := J(y) − J(x) víi ∀x, y ∈ K th× bµi to¸n tèi ­u t­¬ng ®­¬ng víi bµi to¸n c©n b»ng. ThËt vËy, gi¶ sö x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.2) nªn theo ®Þnh nghÜa ta cã: J(x∗ ) ≤ J(y), ∀y ∈ K. MÆt kh¸c, f (x, y) = J(y) − J(x), ∀x, y ∈ K. Do ®ã, f (x∗ , y) = J(y) − J(x∗ ) ≥ 0, ∀y ∈ K. x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.1). Ng­îc l¹i, cho x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.1) nªn ta cã: VËy f (x∗ , y) ≥ 0, ∀y ∈ K. Theo c¸ch ®Æt ta cã: f (x∗ , y) = J(y) − J(x∗ ) ≥ 0, ∀y ∈ K ⇒ J(y) ≥ J(x∗ ), ∀y ∈ K. VËy x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.2). Bµi to¸n bÊt ®¼ng thøc biÕn ph©n tæng qu¸t Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10 [2] http://www.Lrc-tnu.edu.vn12 n Cho T : K → 2R lµ ¸nh x¹ nöa liªn tôc trªn tõ mét ®iÓm vµo mét tËp hîp sao cho T (x) lµ tËp compact, ∀x ∈ K . Khi ®ã, bµi to¸n bÊt ®¼ng thøc biÕn ph©n tæng qu¸t ®­îc ph¸t biÓu nh­ sau:  x∗ ∈ K, ξ ∗ ∈ T (x∗ ) sao cho ξ ∗ , y − x∗ ≥ 0, ∀y ∈ K (1.3)  NÕu ta ®Æt f (x, y) := maxξ∈T (x) ξ, y − x , ∀x, y ∈ K th× bµi to¸n c©n b»ng (1.1) t­¬ng ®­¬ng víi bµi to¸n bÊt ®¼ng thøc biÕn ph©n tæng qu¸t. T×m ThËt vËy, gi¶ sö x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.3) nªn cã: ∗  ξ , y − x∗ ≥ 0, ∀y ∈ K, ξ ∗ ∈ T (x∗ ). MÆt kh¸c theo c¸ch ®Æt ta cã:  f (x∗ , y) = ∗max∗ ξ ∗ , y − x∗ ≥ 0, ∀y ∈ K. ξ ∈T (x ) x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.1). VËy Ng­îc l¹i, cho x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.1) nªn f (x∗ , y) ≥ 0, ∀y ∈ K. Theo c¸ch ®Æt ta cã:  f (x∗ , y) = ∗max∗ ξ ∗ , y − x∗ ≥ 0, ∀y ∈ K. ξ ∈T (x ) VËy x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.3). • NÕu T lµ ¸nh x¹ ®¬n trÞ th× bµi to¸n bÊt ®¼ng thøc biÕn ph©n tæng qu¸t lµ bµi to¸n bÊt ®¼ng thøc biÕn ph©n sau:  x∗ ∈ K sao cho T (x∗ ), y − x∗ ≥ 0, ∀y ∈ K. (1.4)  NÕu ta ®Æt f (x, y) := T (x), y − x , ∀x, y ∈ K th× víi c¸ch lËp luËn nh­ trªn bµi to¸n (1.4) t­¬ng ®­¬ng víi bµi to¸n c©n b»ng (1.1). T×m Bµi to¸n bï phi tuyÕn Cho [2]  K ⊆ Rn lµ mét nãn låi ®ãng, K ∗ = {x ∈ Rn | x, y ≥ 0, ∀y ∈ K} lµ nãn ®èi cùc cña nãn K. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11 http://www.Lrc-tnu.edu.vn13 Cho ¸nh x¹ T : K → Rn liªn tôc. Khi ®ã, bµi to¸n bï phi tuyÕn ®­îc ph¸t biÓu nh­ sau:  x∗ ∈ K sao cho T (x∗ ) ∈ K vµ T (x∗ ), x∗ = 0. (1.5)  NÕu ta ®Æt f (x, y) := T (x), y − x , ∀x, y ∈ K th× bµi to¸n bï phi tuyÕn (1.5) sÏ t­¬ng ®­¬ng víi bµi to¸n c©n b»ng (1.1). T×m ThËt vËy, gi¶ sö x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.5) nªn ta cã:  T (x∗ ) ∈ K vµ T (x∗ ), x∗ = 0. MÆt kh¸c theo c¸ch ®Æt ta cã:  f (x∗ , y) = T (x∗ ), y − x∗   = T (x∗ ), y − T (x∗ ), x∗  = T (x∗ ), y ≥ 0, ∀y ∈ K. x∗ ∈ K lµ nghiÖm cña bµi to¸n c©n b»ng (1.1). Ng­îc l¹i, cho x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.1) ta cã: VËy f (x∗ , y) ≥ 0 ∀y ∈ K. Theo c¸ch ®Æt ta cã:  f (x∗ , y) = T (x∗ ), y − x∗ , ∀y ∈ K. K lµ nãn nªn 0 ∈ K vµ 2x∗ ∈ K . Trong ®¼ng thøc trªn nÕu lÊy   y = 0 ∈ K cã T (x∗ ), −x∗ ≥ 0 hay T (x∗ ), x∗ ≤ 0, cßn nÕu lÊy   y = 2x∗ ∈ K ta cã T (x∗ ), 2x∗ − x∗ ≥ 0 hay T (x∗ ), x∗ ≥ 0.VËy  T (x∗ ), x∗ = 0. Do H¬n n÷a, do     0 ≤ T (x∗ ), y − x∗ = T (x∗ ), y − t(x∗ ), x∗ = T (x∗ ), y , ∀y ∈ K.  Do T (x∗ ), y ≥ 0, ∀y ∈ K nªn T (x∗ ) ∈ K . Do ®ã, x∗ ∈ K lµ nghiÖm cña (1.5). Chó ý Khi K lµ nãn låi ®ãng th× bµi to¸n bÊt ®¼ng thøc biÕn ph©n (1.4) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12 http://www.Lrc-tnu.edu.vn14 chÝnh lµ bµi to¸n bï phi tuyÕn (1.5). Bµi to¸n ®iÓm bÊt ®éng Kakutani Cho T [2] n : Rn → 2R víi K ∩T (x) lµ tËp compact låi, kh¸c rçng, víi ∀x ∈ K . Khi ®ã, bµi to¸n ®iÓm bÊt ®éng Kakutani ®­îc ph¸t biÓu nh­ sau: x∗ ∈ K sao cho x∗ ∈ T (x∗ ) (1.6)  NÕu ta ®Æt f (x, y) := maxξ∈T (x) x − ξ, y − x , ∀x, y ∈ K th× bµi to¸n c©n T×m b»ng (1.1) t­¬ng ®­¬ng víi bµi to¸n ®iÓm bÊt ®éng (1.6). ThËt vËy, gi¶ sö x∗ ∈ K lµ nghiÖm cña (1.6) nªn T (x∗ ) = x∗ . MÆt kh¸c theo c¸ch ®Æt ta cã  f (x∗ , y) = x∗ − T (x∗ ), y − x∗ , ∀y ∈ K. x∗ ∈ K lµ nghiÖm cña (1.1). Ng­îc l¹i, cho x∗ ∈ K lµ nghiÖm cña (1.1) nªn Do ®ã, f (x∗ , y) ≥ 0, ∀y ∈ K. Theo c¸ch ®Æt cã  f (x∗ , y) = x∗ − T (x∗ ), y − x∗ , ∀y ∈ K. Chän y = T (x∗ ) ∈ K ta cã  f (x∗ , y) = x∗ − T (x∗ ), T (x∗ ) − x∗ ≥ 0, ∀y ∈ K ⇒ − k x∗ − T (x∗ ) k≥ 0, ∀y ∈ K ⇒k x∗ − T (x∗ ) k≤ 0, ∀y ∈ K ⇒ x∗ = T (x∗ ), ∀y ∈ K. VËy x∗ ∈ K lµ nghiÖm cña (1.6). • NÕu T lµ ¸nh x¹ ®¬n trÞ th× bµi to¸n ®iÓm bÊt ®éng Kakutani trë thµnh bµi to¸n ®iÓm bÊt ®éng Brouwer sau: T×m x∗ ∈ K sao cho x∗ = T (x∗ ). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 13 (1.7) http://www.Lrc-tnu.edu.vn15  f (x, y) := x − T (x), y − x , ∀x, y ∈ K th× víi c¸ch lËp luËn nh­ trªn chØ ra ®­îc r»ng bµi to¸n (1.7) t­¬ng ®­¬ng víi bµi to¸n c©n b»ng. NÕu ta ®Æt Bµi to¸n c©n b»ng Nash (trong trß ch¬i kh«ng hîp t¸c) [2] • Cho I = {1, 2, . . . , p} lµ tËp chØ sè h÷u h¹n (tËp p−ng­êi ch¬i ). • Ki lµ tËp låi kh¸c rçng cña Rni (tËp chiÕn l­îc cña ng­êi ch¬i thø i ). • Hµm fi : K1 × . . . × Kp → R cho tr­íc (hµm tæn thÊt cña ng­êi ch¬i thø i khi vi ph¹m chiÕn l­îc cña nh÷ng ng­êi ch¬i víi ∀i ∈ I ) Cho x = (x1 , . . . , xp ) ∈ K1 × . . . Kp vµ y = (y1 , . . . , yp ) ∈ K1 × . . . Kp Ta ®Þnh nghÜa vecto x[yi ] ∈ K1 × . . . × Kp nh­ sau:  x , ∀j 6= i j x[yi ]j = y , ∀j = i i §Æt K = K1 × . . . × Kp Khi ®ã, bµi to¸n c©n b»ng Nash T×m ®­îc ph¸t biÓu nh­ sau: x∗ ∈ K sao cho fi (x∗ ) ≤ fi (x∗ [yi ]), ∀i ∈ I, ∀y ∈ K. §iÓm tho¶ m·n (1.8) (1.8) gäi lµ ®iÓm c©n b»ng Nash. VÒ ý nghÜa kinh tÕ, ®iÓm c©n b»ng nµy nãi lªn r»ng bÊt k× ®èi thñ nµo chän ph­¬ng ¸n ra khái ®iÓm c©n b»ng trong khi c¸c ®èi thñ cßn l¹i vÉn gi÷ ph­¬ng ¸n ®iÓm c©n b»ng th× ®èi thñ ra khái ®iÓm c©n b»ng sÏ bÞ thua thiÖt. NÕu ta ®Æt f : K×K → R ®­îc x¸c ®Þnh bëi f (x, y) := p P {fi (x[yi ]) − fi (x)} i=1 víi ∀x, y ∈ K th× bµi to¸n c©n b»ng Nash (1.8) t­¬ng ®­¬ng víi bµi to¸n c©n b»ng (1.1). ThËt vËy, gi¶ sö x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.8) nªn: fi (x∗ ) ≤ fi (x∗ [yi ]), ∀i ∈ I, ∀yi ∈ Ki ⇒ fi (x∗ [yi ]) − fi (x∗ ) ≥ 0, ∀i ∈ I, ∀yi ∈ Ki p X  ⇒ fi (x∗ [yi ]) − fi (x∗ ) ≥ 0, ∀y ∈ K. i=1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 14 http://www.Lrc-tnu.edu.vn16 Theo c¸ch ®Æt cã: f (x∗ , y) ≥ 0, ∀y ∈ K. x∗ ∈ K lµ nghiÖm cña (1.1). Ng­îc l¹i, cho x∗ ∈ K lµ nghiÖm cña (1.1) mµ kh«ng lµ nghiÖm cña (1.9). VËy Do x∗ ∈ K lµ nghiÖm cña (1.1) nªn ta cã: f (x∗ , y) ≥ 0, ∀y ∈ K. Theo c¸ch ®Æt cã: p X {fi (x∗ [yi ]) − fi (x∗ )} ≥ 0, ∀i ∈ K, ∀y ∈ K. i=1 Do x∗ ∈ K kh«ng lµ nghiÖm cña (1.8) nªn ∃i0 ∈ K sao cho: fi (x∗ ) > fi (x∗ [yi ]), ∀yi ∈ Ki . Ta lÊy x∗ [yj ] = x∗ , ∀j 6= i0 suy ra fi (x∗ [yj ]) − fi (x∗ ) = 0, ∀j 6= i0 . KÕt hîp hai ®iÒu trªn ta suy ra p X  fi (x∗ [yi ]) − fi (x∗ ) < 0, m©u thuÉn. i=1 VËy x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.8). KÕt luËn ch­¬ng Ch­¬ng nµy tr­íc tiªn nh¾c l¹i mét sè kÕt qu¶ c¬ b¶n cña gi¶i tÝch låi sÏ dïng ®Õn trong c¸c ch­¬ng sau. TiÕp theo lµ tr×nh bµy d¹ng to¸n häc cña bµi to¸n c©n b»ng, ®ång thêi th«ng qua c¸c phÐp biÕn ®æi phï hîp chØ ra sù t­¬ng ®­¬ng gi÷a bµi to¸n c©n b»ng víi bµi to¸n tèi ­u, bµi to¸n bÊt ®¼ng thøc biÕn ph©n, bµi to¸n bï phi tuyÕn, bµi to¸n ®iÓm bÊt ®éng, bµi to¸n c©n b»ng Nash. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 15 http://www.Lrc-tnu.edu.vn17 Ch­¬ng 2 Ph­¬ng ph¸p chiÕu vµ ®¹o hµm t¨ng c­êng gi¶i bµi to¸n c©n b»ng Bµi to¸n c©n b»ng cã ý nghÜa thùc tiÔn lín, do ®ã viÖc t×m lêi gi¶i cho bµi to¸n c©n b»ng lµ rÊt cÇn thiÕt. Ch­¬ng nµy nh»m giíi thiÖu ph­¬ng ph¸p chiÕu vµ ph­¬ng ph¸p ®¹o hµm t¨ng c­êng gi¶i bµi to¸n c©n b»ng. Néi dung chñ yÕu cña ch­¬ng nµy ®­îc xem trong 2.1. [2], [5]. Ph­¬ng ph¸p chiÕu gi¶i bµi to¸n c©n b»ng Ph­¬ng ph¸p chiÕu lµ ph­¬ng ph¸p c¬ b¶n nhÊt ®Ó gi¶i bµi to¸n ®èi ngÉu cña bµi to¸n c©n b»ng. Tr­íc tiªn ta ®Þnh nghÜa bµi to¸n ®èi ngÉu. §Þnh nghÜa 2.1.1. [2] Bµi to¸n ®èi ngÉu cña bµi to¸n c©n b»ng ®­îc ph¸t biÓu nh­ sau: T×m x∗ ∈ K sao cho : f (y, x∗ ) ≤ 0, ∀y ∈ K. (2.1) Trong ®ã, f : K × K → R lµ hµm liªn tôc tho¶ m·n: a, f (x, x) = 0, ∀x ∈ K , b, f (x, .) : K → R lµ hµm låi víi ∀x ∈ K . Víi mçi x ∈ K ®Æt Lf (x) = {y ∈ K | f (x, y) ≤ 0}. Râ rµng, x∗ ∈ K lµ T nghiÖm cña bµi to¸n ®èi ngÉu (2.1) khi vµ chØ khi x∗ ∈ Lf (y). y∈K §Þnh lÝ sau chØ ra mèi quan hÖ gi÷a nghiÖm cña bµi to¸n ®èi ngÉu vµ nghiÖm cña bµi to¸n c©n b»ng. §Þnh lý 2.1.1. [2] TËp nghiÖm cña bµi to¸n ®èi ngÉu lµ tËp con cña tËp nghiÖm cña bµi to¸n c©n b»ng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 16 http://www.Lrc-tnu.edu.vn18 Chøng minh Cho x∗ ∈ K lµ nghiÖm cña bµi to¸n ®èi ngÉu, lÊy y ∈ K, ∀λ ∈ [0, 1] ta ®Þnh nghÜa zλ ∈ K nh­ sau: zλ := λy + (1 − λ)x∗ . Víi mçi λ ∈ [0, 1] ta cã (b) (a) 0 =f (zλ , zλ ) = f (zλ , λy + (1 − λ)x∗ )≤λf (zλ , y) + (1 − λ)f (zλ , x∗ ). (2.2) Do x∗ lµ nghiÖm cña bµi to¸n ®èi ngÉu nªn: T T x∗ ∈ Lf (y) = {x ∈ K | f (y, x) ≤ 0}. y∈K y∈K y = zλ , víi ∀λ ∈ [0, 1] ta lu«n cã f (zλ , x∗ ) ≤ 0. Do ®ã, ∀λ ∈ [0, 1], ∀y ∈ K vµ tõ (2.1) ta cã: 0 ≤ λf (zλ , y) ≤ f (λy + (1 − λ)x∗ , y) = f (x∗ + λ(y − x∗ ), y). LÊy Cho λ → 0, do tÝnh liªn tôc cña f nªn: 0 ≤ f (x∗ , y), ∀y ∈ K . ⇒ x∗ lµ nghiÖm cña bµi to¸n c©n b»ng. Ta cã ®iÒu ph¶i chøng minh. NhËn xÐt  [2] ? MÖnh ®Ò ®¶o cña ®Þnh lÝ 2.1.1 kh«ng ®óng. ThËt vËy, lÊy N = 1 vµ lÊy K = [0, 2] vµ kÝ hiÖu S1 lµ tËp nghiÖm cña bµi to¸n ®èi ngÉu, S2 lµ tËp nghiÖm cña bµi to¸n c©n b»ng. Khi ®ã, a, f (x, y) = (x − y)2 ⇒ S1 = ∅, S2 = [0, 2] ⇒ S1 * S2 . b, f (x, y) = max{0, | x − y | −1} ⇒ S1 = {1}, S2 = [0, 2] ⇒ S1 * S2 . ? Khi f lµ gi¶ ®¬n ®iÖu, nghÜa lµ ∀x, y ∈ K : f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, mÖnh ®Ò ®¶o cña 2.1.1 ®óng. Khi ®ã, bµi to¸n ®èi ngÉu vµ bµi to¸n c©n b»ng cã cïng tËp nghiÖm. Ta cã thuËt to¸n chiÕu 2.1 sau ®Ó gi¶i bµi to¸n ®èi ngÉu. 2.1 [2] 0 0 B­íc 1: Cho k = 0, x ∈ K vµ r0 = k x k. ThuËt to¸n chiÕu B­íc 2: LÊy xk vµ rk (i) §Þnh nghÜa: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17 http://www.Lrc-tnu.edu.vn19 Kk = {x ∈ K : k x k ≤ rk + 1}. (2.1a) (ii) T×m y k ∈ Kk cã tÝnh chÊt: max f (y, xk ) − k ≤ f (y k , xk ), (2.1b) y∈Kk víi {k }k≥0 ⊂ [0, +∞] lµ d·y tho¶ m·n lim k = 0. k→+∞ (iii) TÝnh x k+1 d¹ng:   xk+1 = xk + tk PLf (yk ) (xk ) − xk , (2.1c) PLf (yk ) (xk ) lµ phÐp chiÕu trùc giao cña xk lªn Lf (yk ) , vµ Lf (yk ) = {x ∈ K | f (y k , x) ≤ 0} lµ tËp låi, {tk }k≥0 ⊂ [α, 2 − α] víi α ∈ [0, 1]. trong ®ã, (iv) TÝnh rk th«ng qua: rk+1 = max{rk , k xk+1 k} vµ trë vÒ (2.1d) (i) cña b­íc 2. MÖnh ®Ò 2.1.1. [2] ThuËt to¸n chiÕu 2.1 ®­îc x¸c ®Þnh ®óng ®¾n. Chøng minh • Chøng minh (2.1b) ®óng. ThËt vËy, tõ c«ng thøc (2.1a) vµ (2.1d) ta cã: Kk ⊂ Kk+1 , ∀k ∈ N. x0 ∈ K vµ k x0 k≤ r0 + 1 nªn suy ra x0 ∈ K0 ⇒ x0 ∈ Kk , ∀k ∈ N MÆt kh¸c, K lµ tËp ®ãng nªn mäi Kk lµ kh¸c rçng vµ compact. L¹i do tÝnh Do liªn tôc cña f nªn f (., y k ) ®¹t cùc ®¹i trªn Kk , v× vËy tån t¹i yk ∈ Kk tho¶ m·n: max f (y, xk ) − k ≤ f (y k , xk ). y∈Kk • Chøng minh (2.1c) ®óng. ThËt vËy, do tÝnh låi cña f (y k , .) vµ tÝnh låi cña tËp K nªn tËp kh¸c rçng: Lf (y k ) = {x ∈ K | f (y k , x) ≤ 0} Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 18 http://www.Lrc-tnu.edu.vn20