ĐẠ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 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
2
http://www.Lrc-tnu.edu.vn4
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
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
- Xem thêm -