Luận văn: NGHIÊN CỨU HIỆU CHỈNH HÓA TRONG BÀI TOÁN CÂN BẰNG

Chia sẻ: Qsczaxewd Qsczaxewd | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

85
lượt xem 17
download

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

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...

Chủ đề:

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

Lưu

Nội dung Text: Luận văn: 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 http://www.Lrc-tnu.edu.vn3 1
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. 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 Ch¬ng 1 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. tr×nh bµy hai ph¬ng ph¸p hiÖu chØnh bµi to¸n c©n b»ng, ®ã Ch¬ng 2 lµ ph¬ng ph¸p chiÕu vµ ph¬ng ph¸p ®¹o hµm t¨ng cêng. giíi thiÖu hai lo¹i hµm ®¸nh gi¸ lµ hµm ®¸nh gi¸ Auslender vµ Ch¬ng 3 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 Mu. 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 http://www.Lrc-tnu.edu.vn4 2
v¨n ®îc hoµn thµnh. MÆc dï t¸c gi¶ ®· cè g¾ng nhng 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 http://www.Lrc-tnu.edu.vn5 3
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 [4]. R lµ tËp sè thùc, Rn lµ kh«ng gian Euclid n chiÒu. KÝ hiÖu Cho hai ®iÓm a, b trong kh«ng gian Euclid n-chiÒu §Þnh nghÜa 1.1.1. [4] Rn . a, b lµ tËp hîp c¸c ®iÓm x trong Rn cã d¹ng: ®i qua hai ®iÓm §êng th¼ng x = λa + (1 − λ)b, ∀λ ∈ R. a, b lµ tËp hîp tÊt c¶ c¸c ®iÓm x trong Rn cã d¹ng: nèi §o¹n th¼ng x = λa + (1 − λ)b = λ(a − b) + b, 0 ≤ λ ≤ 1. A ⊆ Rn gäi lµ TËp , nÕu nã chøa trän ®o¹n §Þnh nghÜa 1.1.2. [4] tËp låi th¼ng nèi hai ®iÓm bÊt k× thuéc nã. H×nh 1.1 cho ta vÝ dô ®¬n gi¶n vÒ tËp låi vµ tËp kh«ng låi VÝ dô 1.1.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.vn6 4
(b) (c) (a) (d) H×nh 1.1. (a), (c)- TËp låi; (b), (d)- TËp kh«ng låi TËp låi lµ ®ãng víi phÐp giao, phÐp hîp, phÐp céng, phÐp §Þnh lý 1.1.1. [1] A B nh©n víi mét sè vµ phÐp lÊy tæ hîp tuyÕn tÝnh. Tøc lµ, nÕu vµ lµ hai Rn tËp låi trong 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 }. A ⊂ Rn ®îc gäi lµ nãn nÕu: TËp §Þnh nghÜa 1.1.3. [1] x ∈ A, λ ≥ 0 ⇒ λx ∈ A. 0 ∈ Rn . TËp A ⊂ Rn ®îc gäi lµ nãn låi nÕu Mét nãn lu«n chøa ®iÓm gèc 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 Cho tËp låi §Þnh nghÜa 1.1.4. [4] NC (x0 ) = t ∈ Rn : t, x − x0 ≤ 0, ∀x ∈ A A t¹i x0 . lµ hay lµ nãn ph¸p tuyÕn ngoµi cña mét nãn låi ®ãng A ⊆ Rn . Vecto d = 0 ®îc Cho tËp låi kh¸c rçng §Þnh nghÜa 1.1.5. [3] gäi lµ ph¬ng lïi xa cña A nÕu víi mçi x ∈ A cã: {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 http://www.Lrc-tnu.edu.vn7 5
vµ chØ khi A cã mét ph¬ng lïi xa. A ⊆ Rn cïng vecto 0 t¹o thµnh TËp tÊt c¶ c¸c ph¬ng lïi xa cña tËp låi 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 = α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 = λ1 d1 + λ2 d2 , λ1 , λ2 > 0. Mét tËp hîp lµ giao cña mét sè h÷u h¹n c¸c nöa §Þnh nghÜa 1.1.6. [1] kh«ng gian ®ãng ®îc gäi lµ hay gäi lµ . tËp låi ®a diÖn khóc låi TËp con B cña khóc låi A ®îc gäi lµ mét diÖn cña §Þnh nghÜa 1.1.7. [1] 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. lµ diÖn cã thø nguyªn b»ng 1. C¹nh a, Mäi tËp låi ®a diÖn kh«ng chøa trän mét ®êng th¼ng §Þnh lý 1.1.2. [1] ®Òu cã Ýt nhÊt mét ®Ønh. A cã ®Ønh b»ng tËp hîp cña c¸c ®iÓm x cã d¹ng: b, Mäi tËp låi ®a diÖn λi v i + βj dj x= i∈I j ∈J vi dj λi = 1, λi , βj ≥ 0 i, j trong ®ã, víi mäi cßn lµ c¸c ®Ønh, lµ c¸c i∈I A. ph¬ng cña c¸c c¹nh v« h¹n cña M, K lµ c¸c tËp låi kh¸c rçng cña Rn , M ⊆ K Cho §Þnh nghÜa 1.1.8. [5] 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 x, y ∈ M ta cã: 2 f (x, y ) + f (y, x) ≤ −τ x−y . b, Hµm f trªn M nÕu víi mäi x, y ∈ M ta cã: ®¬n ®iÖu chÆt 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 http://www.Lrc-tnu.edu.vn8 6
c, Hµm f trªn M nÕu víi mçi cÆp x, y ∈ M ta cã: ®¬n ®iÖu f (x, y ) + f (y, x) ≤ 0. d, Hµm f trªn M nÕu víi mçi cÆp x, y ∈ M th×: gi¶ ®¬n ®iÖu f (x, y ) ≥ 0 ⇒ f (y, x) ≤ 0. X ⊆ Rn , a, Hµm f lµ x¸c ®Þnh trªn tËp låi §Þnh nghÜa 1.1.9. [4] hµm låi 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 = 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: 2 f λx + (1 − λ)y ≤ λf (x) + (1 − λ)f (y ) − β (1 − λ)λ x−y , 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. f A vµ g lµ hµm låi trªn tËp Cho lµ hµm låi trªn tËp låi §Þnh lý 1.1.3. [1] 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, 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: A Mét hµm låi x¸c ®Þnh trªn tËp låi th× liªn tôc t¹i mäi §Þnh lý 1.1.4. [1] A. ®iÓm trong cña tË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.vn9 7
f A. Cho hµm låi, kh¶ vi trªn tËp låi Khi ®ã víi mäi §Þnh lý 1.1.5. [4] x, y ∈ A cã: f (y ) − f (x) ≥ f (x), y − x . A. Khi ®ã víi mäi x, y ∈ A vµ x = y f NÕu låi chÆt, kh¶ vi trªn tËp låi ta cã: f (y ) − f (x) > f (x), y − x . f lµ låi m¹nh β > 0, A. NÕu víi hÖ sè kh¶ vi trªn tËp låi Khi ®ã víi mäi x, y ∈ A ta cã: 2 f (y ) − f (x) ≥ f (x), y − x + β y−x . f A. Mét ®iÓm Cho lµ hµm låi, kh¶ vi trªn tËp låi ®ãng §Þnh lý 1.1.6. [1] x∗ ∈ A lµ nghiÖm tèi u cña bµi to¸n quy ho¹ch låi: min f (x) x∈A f A, tøc lµ: khi vµ chØ khi nã lµ ®iÓm dõng cña trªn f (x∗ ), y − x∗ ≥ 0, ∀y ∈ A. Tõ ®Þnh lÝ 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. Cho f lµ mét hµm låi trªn tËp låi A. Mét vecto §Þnh nghÜa 1.1.10. [1] 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. 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∗ ) TËp chØ chøa duy nhÊt mét ®iÓm ta nãi r»ng f kh¶ vi t¹i 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.vn10 8
−1 f (x) = x kh¶ vi t¹i mäi ®iÓm x = 0 do ∂f (x) = x, x VÝ dô 1.1.2. kh«ng kh¶ vi t¹i x = 0 do ∂f (x) = {y : x ≥ y , x , ∀y }. D ⊂ Rn , D = ∅, f : D → R. Mét ®iÓm Cho §Þnh nghÜa 1.1.11. [3] 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 . a, Mäi ®iÓm cùc tiÓu ®Þa ph¬ng cña mét hµm låi trªn §Þnh lý 1.1.7. [1] mét tËp låi ®Òu lµ ®iÓm cùc tiÓu tuyÖt ®èi. b, NÕu x∗ lµ x∗ ∈ intD f D ®iÓm cùc tiÓu cña hµm låi trªn tËp låi vµ th× 0 ∈ ∂f (x∗ ). Cùc ®¹i cña mét hµm låi (nÕu cã ) trªn mét tËp låi cã §Þnh lý 1.1.8. [1] ®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 [2]. Trong toµn bé luËn v¨n nµy ta lu«n gi¶ thiÕt K lµ tËp låi ®ãng kh¸c rçng Rn . trong Cho hµm f : K × K → R tho¶ m·n f (x, x) = §Þnh nghÜa 1.2.1. [2] 0, ∀x ∈ K . Khi ®ã, bµi to¸n c©n b»ng ®îc ph¸t biÓu nh sau: x∗ ∈ K sao cho f (x∗ , y ) ≥ 0, ∀y ∈ K. T×m (1.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.vn11 9
Hµm sè f tho¶ m·n tÝnh chÊt f (x, x) = 0, ∀x ∈ K ®îc gäi lµ hµm c©n b»ng trªn K . 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 [2] Cho 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: x∗ ∈ K sao cho J (x∗ ) ≤ J (y ), ∀y ∈ K. T×m (1.2) NÕu ta ®Æt 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. x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.2) nªn theo ®Þnh nghÜa ThËt vËy, gi¶ sö 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). VËy Ngîc l¹i, cho x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.1) nªn ta cã: 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. x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.2). VËy Bµi to¸n bÊt ®¼ng thøc biÕn ph©n tæng qu¸t [2] Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn12 10
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 ®îc ph¸t biÓu nh sau: ph©n tæng qu¸t x∗ ∈ K, ξ ∗ ∈ T (x∗ ) sao cho ξ ∗ , y − x∗ ≥ 0, ∀y ∈ K T×m (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. x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.3) nªn cã: ThËt vËy, gi¶ sö ξ ∗ , 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 x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.1) nªn Ngîc l¹i, cho f (x∗ , y ) ≥ 0, ∀y ∈ K. 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.3). VËy • 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. T×m (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). Bµi to¸n bï phi tuyÕn [2] K ⊆ Rn lµ mét nãn låi ®ãng, K ∗ = {x ∈ Rn | x, y ≥ 0, ∀y ∈ K } Cho 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 http://www.Lrc-tnu.edu.vn13 11
T : K → Rn liªn tôc. Khi ®ã, Cho ¸nh x¹ ®îc ph¸t bµi to¸n bï phi tuyÕn biÓu nh sau: x∗ ∈ K sao cho T (x∗ ) ∈ K vµ T (x∗ ), x∗ = 0. T×m (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). x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.5) nªn ta cã: ThËt vËy, gi¶ sö 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). VËy Ngîc l¹i, cho x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.1) ta cã: 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 Do 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. H¬n n÷a, do 0 ≤ T (x∗ ), y − x∗ = T (x∗ ), y − t(x∗ ), x∗ = T (x∗ ), y , ∀y ∈ K. T (x∗ ), y ≥ 0, ∀y ∈ K nªn T (x∗ ) ∈ K . Do ®ã, x∗ ∈ K lµ nghiÖm Do cña (1.5). Khi K lµ nãn låi ®ãng th× bµi to¸n bÊt ®¼ng thøc biÕn ph©n (1.4) Chó ý Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn14 12
chÝnh lµ bµi to¸n bï phi tuyÕn (1.5). Bµi to¸n ®iÓm bÊt ®éng Kakutani [2] n : Rn → 2R víi K ∩ T (x) lµ tËp compact låi, kh¸c rçng, víi ∀x ∈ K . Cho T Khi ®ã, ®îc ph¸t biÓu nh sau: bµi to¸n ®iÓm bÊt ®éng Kakutani x∗ ∈ K sao cho x∗ ∈ T (x∗ ) T×m (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 b»ng (1.1) t¬ng ®¬ng víi bµi to¸n ®iÓm bÊt ®éng (1.6). x∗ ∈ K lµ nghiÖm cña (1.6) nªn ThËt vËy, gi¶ sö 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). Do ®ã, Ngîc l¹i, cho x∗ ∈ K lµ nghiÖm cña (1.1) nªn f (x∗ , y ) ≥ 0, ∀y ∈ K. Theo c¸ch ®Æt cã f (x∗ , y ) = x∗ − T (x∗ ), y − x∗ , ∀y ∈ K. y = T (x∗ ) ∈ K ta cã Chän f (x∗ , y ) = x∗ − T (x∗ ), T (x∗ ) − x∗ ≥ 0, ∀y ∈ K x∗ − T (x∗ ) ≥ 0, ∀y ∈ K ⇒− ⇒ x∗ − T (x∗ ) ≤ 0, ∀y ∈ K ⇒ x∗ = T (x∗ ), ∀y ∈ K. x∗ ∈ K lµ nghiÖm cña (1.6). VËy • 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: x∗ ∈ K sao cho x∗ = T (x∗ ). T×m (1.7) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn15 13
NÕu ta ®Æt 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. 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 Rn (tËp chiÕn lîc cña ngêi ch¬i thø i ). 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 = i j x[yi ]j = y , ∀j = i i §Æt K = K1 × . . . × Kp Khi ®ã, ®îc ph¸t biÓu nh sau: bµi to¸n c©n b»ng Nash x∗ ∈ K sao cho fi (x∗ ) ≤ fi (x∗ [yi ]), ∀i ∈ I, ∀y ∈ K. T×m (1.8) §iÓm tho¶ m·n (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. p NÕu ta ®Æt f : K ×K → R ®îc x¸c ®Þnh bëi f (x, y ) := {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). x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.8) nªn: ThËt vËy, gi¶ sö fi (x∗ ) ≤ fi (x∗ [yi ]), ∀i ∈ I, ∀yi ∈ Ki ⇒ fi (x∗ [yi ]) − fi (x∗ ) ≥ 0, ∀i ∈ I, ∀yi ∈ Ki p 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 http://www.Lrc-tnu.edu.vn16 14
Theo c¸ch ®Æt cã: f (x∗ , y ) ≥ 0, ∀y ∈ K. x∗ ∈ K lµ nghiÖm cña (1.1). VËy Ngîc l¹i, cho x∗ ∈ K lµ nghiÖm cña (1.1) mµ kh«ng lµ nghiÖm cña (1.9). x∗ ∈ K lµ nghiÖm cña (1.1) nªn ta cã: Do f (x∗ , y ) ≥ 0, ∀y ∈ K. Theo c¸ch ®Æt cã: p {fi (x∗ [yi ]) − fi (x∗ )} ≥ 0, ∀i ∈ K, ∀y ∈ K. i=1 x∗ ∈ K kh«ng lµ nghiÖm cña (1.8) nªn ∃i0 ∈ K sao cho: Do fi (x∗ ) > fi (x∗ [yi ]), ∀yi ∈ Ki . x∗ [yj ] = x∗ , ∀j = i0 suy ra Ta lÊy fi (x∗ [yj ]) − fi (x∗ ) = 0, ∀j = i0 . KÕt hîp hai ®iÒu trªn ta suy ra p fi (x∗ [yi ]) − fi (x∗ ) < 0, m©u thuÉn. i=1 x∗ ∈ K lµ nghiÖm cña bµi to¸n (1.8). VËy 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 http://www.Lrc-tnu.edu.vn17 15
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], [5]. 2.1. 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. ®îc ph¸t §Þnh nghÜa 2.1.1. [2] Bµi to¸n ®èi ngÉu cña bµi to¸n c©n b»ng biÓu nh sau: x∗ ∈ K sao cho : f (y, x∗ ) ≤ 0, ∀y ∈ K. T×m (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µ 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. TËp nghiÖm cña bµi to¸n ®èi ngÉu lµ tËp con cña tËp §Þnh lý 2.1.1. [2] 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 http://www.Lrc-tnu.edu.vn18 16
Cho x∗ ∈ K lµ nghiÖm cña bµi to¸n ®èi ngÉu, lÊy y ∈ K, ∀λ ∈ Chøng minh [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) x∗ lµ nghiÖm cña bµi to¸n ®èi ngÉu nªn: Do x∗ ∈ {x ∈ K | f (y, x) ≤ 0}. Lf (y ) = y ∈K y ∈K y = zλ , víi ∀λ ∈ [0, 1] ta lu«n cã f (zλ , x∗ ) ≤ 0. LÊy 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 ). 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] ThuËt to¸n chiÕu 0 0 Bíc 1: Cho k = 0, x ∈ K vµ r0 = x . xk vµ rk LÊy Bíc 2: (i) §Þnh nghÜa: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn19 17
Kk = {x ∈ K : x ≤ rk + 1}. (2.1a) (ii) T×m y k ∈ Kk cã tÝnh chÊt: max f (y, xk ) − ≤ f (y k , xk ), (2.1b) k y ∈Kk víi { k }k≥0 ⊂ [0, +∞] lµ d·y tho¶ m·n lim = 0. k k →+∞ (iii) TÝnh xk+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µ trong ®ã, Lf (yk ) = {x ∈ K | f (y k , x) ≤ 0} lµ tËp låi, {tk }k≥0 ⊂ [α, 2 − α] víi α ∈ [0, 1]. (iv ) TÝnh rk th«ng qua: xk+1 } rk+1 = max{rk , (2.1d) vµ trë vÒ (i) cña bíc 2. 2.1 ®îc x¸c ®Þnh ®óng ®¾n. ThuËt to¸n chiÕu MÖnh ®Ò 2.1.1. [2] 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µ x0 ≤ r0 + 1 nªn suy ra x0 ∈ K0 ⇒ x0 ∈ Kk , ∀k ∈ N Do 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 f nªn f (., y k ) ®¹t cùc ®¹i trªn Kk , v× vËy tån t¹i yk ∈ Kk tho¶ liªn tôc cña m·n: max f (y, xk ) − ≤ f (y k , xk ). k 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 http://www.Lrc-tnu.edu.vn20 18