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 nhng 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 lu 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ã lu 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
- Xem thêm -