ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC SƢ PHẠM
TRẦN THỊ HỒNG NHUNG
THUẬT TOÁN TÁCH CHO BÀI TOÁN CÂN BẰNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2020
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC SƢ PHẠM
TRẦN THỊ HỒNG NHUNG
THUẬT TOÁN TÁCH CHO BÀI TOÁN CÂN BẰNG
Ngành: Toán Giải tích
Mã số: 8460102
LUẬN VĂN THẠC SĨ TOÁN HỌC
Cán bộ hướng dẫn khoa học: GS.TS. Nguyễn Xuân Tấn
THÁI NGUYÊN - 2020
i
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, các kết quả
nghiên cứu là trung thực và chưa được công bố trong bất kì công trình nào
khác.
Thái Nguyên, tháng 6 năm 2020
Tác giả luận văn
Trần Thị Hồng Nhung
ii
LỜI CẢM ƠN
Lời đầu tiên tác giả xin được trân trọng bày tỏ lòng biết ơn chân thành và
sự kính trọng sâu sắc đến GS.TS. Nguyễn Xuân Tấn, người thầy đã nghiêm
túc hướng dẫn, tận tâm chỉ bảo cho tác giả những kinh nghiệm trong học tập,
nghiên cứu khoa học và sáng tạo, định hướng đúng đắn để tác giả hoàn thành
tốt luận văn.
Tác giả xin chân thành bày tỏ lòng cảm ơn sâu sắc tới Ban lãnh đạo
Trường Đại học Sư phạm Thái Nguyên đã tạo điều kiện thuận lợi cho tác giả
trong thời gian học tập tại trường.
Tác giả xin chân trọng cảm ơn Ban chủ nhiệm Khoa Toán cùng các thầy
cô đã tạo điều kiện giúp đỡ, động viên tác giả trong quá trình học tập và hoàn
thành luận văn.
Tác giả xin chân thành cảm ơn bạn bè và những người thân trong gia đình
đã ủng hộ, động viên, giúp đỡ và đồng hành cùng tác giả trong suốt thời gian
học Cao học cũng như trong thời gian tác giả thực hiện luận văn này.
Thái Nguyên, ngày tháng năm 2020
Học viên
Trần Thị Hồng Nhung
iii
MỤC LỤC
Trang
Lời cam đoan
i
Lời cảm ơn
ii
Mục lục
iii
MỞ ĐẦU
1
Chƣơng 1. Bài toán cân bằng giả đơn điệu mạnh
3
1.1. Các kiến thức cơ sở về giải tích lồi
3
1.2. Bài toán cân bằng giả đơn điệu
13
Chƣơng 2. Bài toán cân bằng tách
29
2.1. Phát biểu bài toán
29
2.2. Thuật toán giải
30
2.3. Sự hội tụ của thuật toán
31
KẾT LUẬN VÀ ĐỀ NGHỊ
38
TÀI LIỆU THAM KHẢO
39
1
MÐ U
Cho C l mët tªp hñp, f : C×C → R l mët h m thäa m¢n f (x, x) = 0.
B i to¡n: t¼m x̄ ∈ C sao cho f (x̄, y) ≥ 0 vîi måi y ∈ C ÷ñc gåi l b i to¡n
c¥n b¬ng, x̄ ÷ñc gåi l iºm c¥n b¬ng. B i to¡n n y âng vai trá quan
trång c£ v· m°t l½ thuy¸t l¨n thüc t¸. Nâ bao gçm nhi·u b i to¡n trong
lþ thuy¸t tèi ÷u nh÷ nhúng tr÷íng hñp °c bi»t. Vi»c ch¿ ra i·u ki»n º
b i to¡n câ nghi»m v vi»c t¼m ra thuªt to¡n º t½nh nghi»m âng vai trá
quan trång.
Thuªt ngú c¥n b¬ng ¢ tø l¥u ÷ñc sû döng rëng r¢i trong c¡c ng nh
khoa håc nh÷ vªt lþ, hâa håc, k¾ thuªt, kinh t¸. . . d÷îi c¡c h¼nh thùc kh¡c
nhau, tòy thuëc v o c¡c mæ h¼nh to¡n håc kh¡c nhau. Trong thíi gian
g¦n ¥y, b i to¡n c¥n b¬ng ¢ thu hót ÷ñc r§t nhi·u sü quan t¥m nghi¶n
cùu cõa c¡c nh to¡n håc, c£ v· ph÷ìng di»n lþ thuy¸t l¨n thuªt to¡n. V·
ph÷ìng di»n lþ thuy¸t, ¢ câ kh¡ nhi·u nghi¶n cùu v· sü tçn t¤i nghi»m,
t½nh ên ành, sü mð rëng cõa b i to¡n c¥n b¬ng. C¡c thuªt to¡n hi»n nay
cì b£n düa tr¶n c¡c k¾ thuªt t¼m nghi»m cõa b i to¡n tèi ÷u nh÷ thuªt to¡n
chi¸u, thuªt to¡n chi¸u t«ng c÷íng, ph÷ìng ph¡p h m ¡nh gi¡,. . . .Ph¦n
lîn c¡c b i to¡n thuëc lîp c¡c b i to¡n ¤t khæng ch¿nh, muèn gi£i ÷ñc
th¼ ta ph£i ÷a b i to¡n °t ch¿nh. Vi»c ¡p döng c¡c thuªt to¡n chi¸u,
ho°c chi¸u t«ng c÷íng º gi£i mët b i to¡n c¥n b¬ng hi»u ch¿nh câ thº
g°p khâ kh«n trong t½nh to¡n khi song h m hi»u ch¿nh câ c§u tróc phùc
t¤p hìn so vîi tøng song h m f . Vi»c n y d¨n ¸n nhu c¦u gi£i b i to¡n
c¥n b¬ng khi song h m c¥n b¬ng câ thº t¡ch th nh têng cõa hai hay nhi·u
h m kh¡c v méi h m câ nhúng t½nh ch§t tèt hìn ho°c d¹ t½nh to¡n hìn.
Möc ½ch cõa luªn v«n l tr¼nh b y mët thuªt to¡n t¡ch cho b i to¡n c¥n
b¬ng.
Luªn v«n ÷ñc tr¼nh b y theo hai ch÷ìng:
2
Ch÷ìng 1: Tr¼nh b y c¡c ki¸n thùc cì b£n cõa gi£i t½ch lçi v b i to¡n c¥n
b¬ng gi£ ìn i»u m¤nh công nh÷ sü tçn t¤i nghi»m cõa b i to¡n c¥n b¬ng
gi£ ìn i»u m¤nh
Ch÷ìng 2: Tr¼nh b y thuªt to¡n t¡ch cho b i to¡n c¥n b¬ng
Th¡i Nguy¶n, ng y 15 th¡ng 6 n«m 2020
T¡c gi£
Tr¦n Thà Hçng Nhung
3
Ch֓ng 1
B i to¡n c¥n b¬ng gi£ ìn i»u m¤nh
Trong ch÷ìng n y, tæi tr¼nh b y c¡c ki¸n thùc cì b£n v· gi£i t½ch lçi v mët
sè bê · c¦n thi¸t s³ ÷ñc sû döng trong chùng minh sü tçn t¤i nghi»m
công nh÷ sü hëi tö cõa nhúng thuªt to¡n gi£i b i to¡n c¥n b¬ng trong c¡c
ch÷ìng sau. Nhúng k¸t qu£ trong luªn v«n cán câ thº óng cho c¡c khæng
gian têng qu¡t hìn nh÷ng º thuªn ti»n cho vi»c tr¼nh b y, ta ch¿ giîi h¤n
trong khæng gian Hilbert.
1.1 C¡c ki¸n thùc cì sð v· gi£i t½ch lçi
1. Khæng gian Hilbert
Cho H l khæng gian tuy¸n t½nh tr¶n R. T½ch væ h÷îng tr¶n H l ¡nh
x¤ h., .i : H × H → R, (x, y) → hx, yi thäa m¢n c¡c i·u ki»n sau:
(a) hx, xi ≥ 0 vîi måi x ∈ H, hx, xi = 0 ⇔ x = 0.
(b) hx, yi = hy, xi vîi måi x, y ∈ H.
(c) Vîi x ∈ H cè ành th¼ h m hx, .i : H → R l tuy¸n t½nh.
(d) Vîi y ∈ H cè ành th¼ h m h., yi : H → R l tuy¸n t½nh.
p
N¸u h., .i l mët t½ch væ h÷îng tr¶n H th¼ ¡nh x¤ x → hx, xi vîi x ∈ H l
mët chu©n tr¶n H, k½ hi»u l ||.|| v ¡nh x¤ (x, y) → ||x − y|| vîi x, y ∈ H
l kho£ng c¡ch tr¶n H, k½ hi»u l d(x, y). Ta nâi c°p (H, h., .i) l khæng
gian Hilbert n¸u khæng gian ành chu©n t÷ìng ùng ¦y õ.
2. Tªp lçi
4
Cho hai iºm a, b ∈ H. Khi â
• ÷íng th¯ng i qua hai iºm a, b l tªp hñp câ d¤ng:
{x ∈ H : x = λa + (1 − λ)b, λ ∈ R},
•
o¤n th¯ng nèi hai iºm a, b trong H câ d¤ng:
[a, b] = {x ∈ H : x = λa + (1 − λ)b, λ ∈ [0, 1]}
Cho u ∈ H \ {0} v η ∈ R. Mët si¶u ph¯ng vîi v²c tì ph¡p tuy¸n u
trong H l mët tªp câ d¤ng
{x ∈ H : hx, ui = η}.
Méi si¶u ph¯ng chia khæng gian th nh hai nûa, c¡c tªp
{x ∈ H : hx, ui ≤ η}
v
{x ∈ H : hx, ui < η}
l¦n l÷ñt ÷ñc gåi l nûa khæng gian âng v nûa khæng gian mð vîi v²c tì
ph¡p tuy¸n ngo i u.
ành ngh¾a 1.1.1. Mët tªp con C cõa H ÷ñc gåi l lçi n¸u vîi måi
x, y ∈ C th¼ [x, y] ⊂ C tùc l
λx + (1 − λ)y, ∀λ ∈ [0, 1] .
ành ngh¾a 1.1.2. Cho C l mët tªp con kh¡c réng cõa H, u
Kho£ng c¡ch tø u ¸n C , k½ hi»u l dC (u), ÷ñc x¡c ành bði
∈ H.
dC (u) = inf {d(u, y) : y ∈ C} = inf {||u − y|| : y ∈ C}.
N¸u câ iºm p ∈ C sao cho ||u − p|| = dC (u) th¼ p ÷ñc gåi l mët h¼nh
chi¸u cõa u tr¶n C . N¸u måi iºm trong H ·u câ duy nh§t mët h¼nh chi¸u
tr¶n C th¼ C ÷ñc gåi l tªp Chebyshev. Trong tr÷íng hñp n y, quy tc
ùng vîi méi iºm trong H mët h¼nh chi¸u duy nh§t cõa nâ tr¶n C cho ta
mët to¡n tû gåi l to¡n tû chi¸u tr¶n C , ÷ñc k½ hi»u l PC .
5
Ta câ mët k¸t qu£ cì b£n quen thuëc cho h¼nh chi¸u cõa mët iºm tr¶n
mët tªp lçi âng kh¡c réng sau.
ành lþ 1.1.1. Cho C l mët tªp con lçi âng kh¡c réng cõa H. Khi â
C l mët tªp Chebyshev v vîi måi u v p trong H,
p = PC (u) ⇐⇒ p ∈ C
v (∀y ∈ C)hu − p, y − pi ≤ 0
.
ành ngh¾a 1.1.3. Cho C l mët tªp con lçi âng kh¡c réng cõa H,
x ∈ H.
Nân ph¡p tuy¸n cõa C t¤i x, k½ hi»u l NC x, ÷ñc x¡c ành bði
(
{u ∈ H | hu, y − xi ≤ 0, ∀y ∈ C} n¸u x ∈ C ,
NC x =
∅
n¸u x ∈/ C.
Ti¸p theo ¥y l c¡c kh¡i ni»m hëi tö m¤nh v hëi tö y¸u trong khæng
gian Hilbert.
ành ngh¾a 1.1.4. Mët d¢y {xn} trong H ÷ñc gåi l
(i) hëi tö m¤nh ¸n iºm x n¸u ||xn − x|| → 0 khi n → ∞, k½ hi»u l
xn → x;
(ii) hëi tö y¸u ¸n iºm x n¸u vîi måi u ∈ H, hxn − x, ui → 0 khi n → ∞,
k½ hi»u l xn → x.
Bê · 1.1.1. Cho {xn}n≥0 v {un}n≥0 l c¡c d¢y trong H, x v u l c¡c
iºm trong H. Gi£ sû xn → x, un → ∞. Khi â hxn, uni → hx, ui khi
n → ∞.
Bê · 1.1.2. Cho {xn}n≥0 l mët d¢y bà ch°n trong H. Khi â câ mët d¢y
con cõa {xn}n ≥ 0 hëi tö y¸u.
Ti¸p theo sau ¥y l mët sè kh¡i ni»m quen thuëc v· h m sè.
3. H m lçi
ành ngh¾a 1.1.5. Cho C l mët tªp con kh¡c réng cõa H v h m f :
C → [−∞, +∞].
•
Mi·n húu hi»u cõa f l tªp: domf = {x ∈ C | f (x) < +∞}.
6
ç thà cõa f l tªp: graf = {(x, ξ) ∈ C × R | f (x) = ξ}.
• Tr¶n ç thà cõa f l tªp: epif = {(x, ξ) ∈ C × R | f (x) ≤ ξ}.
• Tªp d÷îi mùc cõa f t¤i ξ ∈ R l tªp: lev≤ξ f = {x ∈ C | f (x) ≤ ξ}.
• H m f ÷ñc gåi l ch½nh th÷íng n¸u −∞ ∈
/ f (C) v domf 6= ∅.
ành ngh¾a 1.1.6. Mët h m f : C → [−∞, +∞] ÷ñc gåi l lçi tr¶n C
n¸u tr¶n ç thà cõa nâ l mët tªp lçi. H m f gåi l lãm n¸u −f l h m lçi.
Trong tr÷íng hñp h m f ch½nh th÷íng th¼ f lçi tr¶n C n¸u v ch¿ n¸u
vîi måi x, y ∈ C , vîi måi λ ∈ [0, 1], ta câ
•
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y).
D¹ th§y r¬ng, h m f lçi tr¶n C n¸u v ch¿ n¸u vîi måi Phå húu h¤n
x1 , x2 , . . . , xn ∈ C v c¡c sè thüc khæng ¥m λ1 , λ2 , . . . , λn m nk=1 λk = 1,
ta câ
n
n
X
X
f(
λk xk ) ≤
λk f (xk )
k=1
k=1
(B§t ¯ng thùc Jensen).
H m ch½nh th÷íng f ÷ñc gåi l lçi m¤nh vîi h» sè τ > 0 tr¶n tªp lçi
C n¸u vîi måi x, y ∈ C v vîi måi λ ∈ [0, 1], ta câ
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) −
τ (1 − τ )
||x − y||2 .
2
H m f ÷ñc gåi l tüa lçi n¸u vîi méi c°p x, y ∈ C v vîi måi α ∈ [0, 1],
ta câ
f (λx + (1 − λ)y) ≤ max{f (x), f (y)},
v ÷ñc gåi l tüa lçi ch°t n¸u nâ l tüa lçi v vîi méi c°p x, y ∈ C sao
cho f (x) 6= f (y) v vîi måi α ∈ (0, 1), ta câ
f (λx + (1 − λ)y) < max{f (x), f (y)}.
Giîi h¤n d÷îi cõa d¢y {ak }k≥0 trong [−∞, +∞] l
lim ak = lim inf an ,
k→∞ n≥k
7
v giîi h¤n tr¶n cõa d¢y {ak }k≥0 trong [−∞, +∞] l
lim ak = lim sup an .
k→∞ n≥k
ành ngh¾a 1.1.7. Cho C l mët tªp con cõa H. Mët h m f
: C →
÷ñc gåi l nûa li¶n töc d÷îi (nûa li¶n töc d÷îi y¸u) t¤i iºm
x̄ ∈ C n¸u vîi måi d¢y {xn } ⊂ C
R ∪ {+∞}
xn → x̄ =⇒ f (x̄) ≤ lim f (xn ).
(xn * x̄ ⇐⇒ f (x̄) ≤ lim f (xn ).)
H m f gåi l nûa li¶n töc d÷îi (nûa li¶n töc d÷îi y¸u) ð tr¶n C n¸u nâ
nûa li¶n töc d÷îi (nûa li¶n töc d÷îi y¸u) t¤i måi iºm trong C .
H m f ÷ñc gåi l nûa li¶n töc tr¶n (nûa li¶n töc tr¶n y¸u) t¤i iºm
x̄ ∈ C n¸u vîi måi d¢y {xn } ⊂ C
xn → x̄ =⇒ f (x̄) ≥ lim f (xn ).
(xn * x̄ ⇐⇒ f (x̄) ≥ lim f (xn ).)
H m f gåi l nûa li¶n töc tr¶n (nûa li¶n töc tr¶n y¸u) ð tr¶n C n¸u nâ nûa
li¶n töc d÷îi (nûa li¶n töc d÷îi y¸u) t¤i måi iºm trong C .
H m f l li¶n töc (li¶n töc y¸u) t¤i iºm x̄ n¸u nâ çng thíi nûa li¶n
töc tr¶n (nûa li¶n töc tr¶n y¸u) v nûa li¶n töc d÷îi (nûa li¶n töc d÷îi
y¸u) t¤i â. H m f ÷ñc gåi l li¶n töc (li¶n töc y¸u) ð tr¶n C n¸u nâ li¶n
töc (li¶n töc y¸u) t¤i måi iºm trong C .
H m f ÷ñc gåi l b¡n li¶n töc tr¶n ð tr¶n C n¸u vîi måi x, y ∈ C v
α ∈ [0, 1], h m sè τ (α) = f [αx + (1 − α)y] l nûa li¶n töc tr¶n t¤i 0+ .
4. D÷îi vi ph¥n h m lçi.
N¸u h m f x¡c ành tr¶n C th¼ ta câ thº th¡c triºn l¶n to n khæng gian
b¬ng c¡ch °t
(
f (x) n¸u x ∈ C
F (x) =
+∞ n¸u x ∈
/ C.
Do â sau ¥y ta câ thº x²t vîi h m x¡c ành tr¶n to n khæng gian.
8
ành ngh¾a 1.1.8. Cho f : H → R ∪ +∞ l h m ch½nh th÷íng, x ∈ domf
v y ∈ H. N¸u tçn t¤i giîi h¤n
lim
α↓0
f (x + αy) − f (x)
α
th¼ giîi h¤n n y ÷ñc gåi l ¤o h m cõa f t¤i x theo h÷îng y, k½ hi»u l
f (x; y).
N¸u h m f câ ¤o h m t¤i x theo måi h÷îng v f (x; .) l mët ¡nh x¤
tuy¸n t½nh li¶n töc tr¶n H th¼ f ÷ñc gåi l kh£ vi Gaateaux t¤i x v theo
biºu di¹n Riesz-Frechet, tçn t¤i duy nh§t mët v²c tì 5f (x) ∈ H sao cho
0
0
0
(∀y ∈ H)f (x; y) = hy, 5f (x)i.
N¸u câ
f (x + y) − f (x) − hy, 5f (x)i
=0
06=y→0
||y||
lim
th¼ ta nâi f l kh£ vi Frechet t¤i x v 5f (x) ÷ñc gåi l ¤o h m Frechet
cõa f t¤i x.
Mët h m câ thº khæng kh£ vi t¤i mët iºm, khi â trong nhi·u b i to¡n
ta câ thº sû döng kh¡i ni»m d÷îi vi ph¥n cõa h m t¤i mët iºm º nghi¶n
cùu, ¡nh gi¡.
ành ngh¾a 1.1.9. Cho f : H → R ∪ {+∞} l h m ch½nh th÷íng.
(i) Mët vectì p ∈ H ÷ñc gåi l d÷îi ¤o h m cõa f t¤i x ∈ H n¸u
f (x) + hp, y − xi ≤ f (y), ∀y ∈ H.
Tªp t§t c£ c¡c d÷îi ¤o h m cõa f t¤i x ÷ñc gåi l d÷îi vi ph¥n cõa
f t¤i x, k½ hi»u l ∂f (x). H m f ÷ñc gåi l kh£ vi d÷îi vi ph¥n t¤i
x n¸u ∂f (x) 6= ∅.
(ii) Cho sè thüc d÷ìng , mët vectì p ∈ H ÷ñc gåi l mët -d÷îi ¤o
h m cõa f t¤i iºm x ∈ H n¸u
f (x) + hp, y − xi − ≤ f (y), ∀y ∈ H.
Tªp t§t c£ c¡c -d÷îi ¤o h m cõa f t¤i x ÷ñc gåi l -d÷îi vi ph¥n
cõa f t¤i x, k½ hi»u l ∂ f (x).
9
H m ch¿ cõa tªp C , k½ hi»u l ιC , ÷ñc x¡c ành bði
(
0
n¸u x ∈ C ,
ιC (x) =
+∞ n¸u x ∈
/ C.
N¸u C l mët tªp con lçi kh¡c réng cõa H, th¼ ta câ ∂ιC (x) = NC (x).
Ti¸p theo ¥y l mët sè kh¡i ni»m v· ¡nh x¤ trong khæng gian Hilbert.
ành ngh¾a 1.1.10. Cho C l mët tªp con kh¡c réng cõa H v ¡nh x¤
T : C → H.
(i) T ÷ñc gåi l li¶n töc Lipschitz tr¶n C vîi h» sè L > 0 n¸u
||T x − T y|| ≤ L||x − y|| ∀x, y ∈ C.
N¸u L = 1 th¼ T ÷ñc gåi l ¡nh x¤ khæng gi¢n v n¸u 0 < L < 1 th¼
T gåi l ¡nh x¤ co.
(ii) T ÷ñc gåi l b¡n li¶n töc tr¶n C n¸u vîi x ∈ C, y ∈ H v x+tny ∈ C , ð
â {tn} l mët d¢y sè d÷ìng sao cho n→∞
lim tn = 0, k²o theo T (x+tn y) *
T (x).
ành ngh¾a 1.1.11. Cho C l mët tªp lçi kh¡c réng trong H. nh x¤
÷ñc gåi l
(i) ìn i»u m¤nh vîi h» sè β > 0 tr¶n C n¸u
T :C→H
hT x − T y, x − yi ≥ β||x − y||2
∀x, y ∈ C;
(ii) ìn i»u tr¶n C n¸u
hT x − T y, x − yi ≥ 0 ∀x, y ∈ C;
(iii) gi£ ìn i»u m¤nh vîi h» sè β > 0 tr¶n C n¸u vîi måi x, y ∈ C
hT y, x − yi ≥ 0 =⇒ hT x, x − yi ≥ β||x − y||2 ;
(iv) gi£ ìn i»u tr¶n C n¸u vîi måi x, y ∈ C
hT y, x − yi ≥=⇒ hT x, x − yi ≥ 0;
10
(v) ìn i»u m¤nh ng÷ñc (çng bùc, khæng gi¢n vúng) vîi h» sè β > 0
tr¶n C n¸u
hT x − T y, x − yi ≥ β||T x − T y||2
∀x, y ∈ C.
T÷ìng tü ta câ mët sè kh¡i ni¶m v· ¡nh x¤ a trà.
Cho F : H → 2H l mët ¡nh x¤ a trà. Tªp x¡c ành cõa F , k½ hi»u l
domF , ÷ñc x¡c ành bði
domF = {x ∈ H : F (x) 6= ∅},
ç thà cõa F l tªp
graF = {(x, y) ∈ H × H : y ∈ F (x)}.
Cho A v B l c¡c tªp con cõa H. Kho£ng c¡ch Hausdorff giúa A v
B ÷ñc x¡c ành bði
dH (A, B) := max{d(A, B), d(B, A)},
ð â
d(A, B) = sup inf ||a − b||, d(B, A) = sup inf ||a − b||.
a∈A b∈B
b∈B a∈A
nh x¤ F ÷ñc gåi l li¶n töc Lipschitz tr¶n C vîi h» sè L > 0 n¸u
dH (F (x), F (y)) ≤ L||x − y|| ∀x, y ∈ C.
ành ngh¾a 1.1.12. Cho F l mët ¡nh x¤ a trà, C ⊆ domF . nh x¤ F
÷ñc gåi l
(i) ìn i»u m¤nh tr¶n C vîi h» sè β > 0 n¸u
hy − y 0 , x − x0 i ≥ β||y − x||2 , ∀x, x0 ∈ C, ∀y ∈ F (x), ∀y 0 ∈ F (x0 );
(ii) ìn i»u tr¶n C n¸u
hy − y 0 , x − x0 i ≥ 0, ∀x, x0 ∈ C, ∀y ∈ F (x), ∀y 0 ∈ F (x0 );
(iii) ìn i»u cüc ¤i n¸u F ìn i»u v vîi måi (x, u) ∈ H × H
(x, u) ∈ graF ⇔ ∀(y, v) ∈ graF : hx − y, u − vi ≥ 0.
11
Ph¦n cuèi trong möc n y l mët sè kh¡i ni»m cho song h m.
ành ngh¾a 1.1.13. Cho song h m f : H × H → R. D÷îi vi ph¥n ÷íng
ch²o cõa f t¤i x ∈ H, k½ hi»u l ∂2f (x, x) l tªp:
∂2 f (x, x) = {g ∈ H : f (x, x) + hg, y − xi ≤ f (x, y), ∀y ∈ H}.
Cho
> 0, -d֔i
∂2 f (x, x) l tªp:
vi ph¥n ÷íng ch²o cõa
t¤i
f
x ∈ H,
k½ hi»u l
∂2 f (x, x) = {g ∈ H : f (x, x) + hg, y − xi − ≤ f (x, x), ∀y ∈ H}.
Ti¸p theo ta s³ x²t ¸n t½nh ch§t ìn i»u cõa song h m f .
5. T½nh ìn i»u.
ành ngh¾a 1.1.14. Cho C
⊂ H
l mët tªp kh¡c réng, song h m f
÷ñc gåi l
(i) ìn i»u m¤nh tr¶n C vîi h» sè β > 0 n¸u
:
C ×C →R
f (x, y) + f (y, x) ≤ −β||y − x||2
∀x, y ∈ C;
(ii) ìn i»u tr¶n C n¸u
f (x, y) + f (y, x) ≤ 0
∀x, y ∈ C;
(iii) gi£ ìn i»u m¤nh tr¶n C vîi h» sè β > 0 n¸u
f (x, y) ≥ 0 =⇒ f (y, x) ≤ −β||y − x||2
∀x, y ∈ C;
(iv) gi£ ìn i»u tr¶n C n¸u
f (x, y) ≥ 0 =⇒ f (y, x) ≤ 0
∀x, y ∈ C.
Chó þ r¬ng, vîi f (x, y) = hF (x), y − xi th¼ f câ c¡c t½nh ch§t ìn i»u
tr¶n C khi v ch¿ khi F câ c¡c t½nh ch§t t÷ìng ùng. Ngo i ra, c¡c kh¡i
ni»m ìn i»u cõa to¡n tû trong ành ngh¾a 1.1.11 v cõa song h m trong
ành ngh¾a 1.1.14 câ c¡c mèi quan h» nh÷ sau:
12
t½nh ìn i»u m¤nh k²o theo t½nh ìn i»u v t½nh ìn i»u k²o theo
t½nh gi£ ìn i»u;
• t½nh ìn i»u m¤nh k²o theo t½nh gi£ ìn i»u m¤nh v t½nh gi£ ìn
i»u m¤nh k²o theo t½nh gi£ ìn i»u.
Tuy nhi¶n, t½nh gi£ ìn i»u khæng suy ng÷ñc ra ÷ñc t½nh ìn i»u hay
gi£ ìn i»u m¤nh, çng thíi ta công khæng câ k¸t luªn n o v· mèi quan
h» giúa t½nh ìn i»u v t½nh gi£ ìn i»u m¤nh. C¡c v½ dö sau ch¿ ra i·u
n y.
V½ dö 1.1.1. X²t trong R2, C := R, cho
•
0 1
A=
.
−1 0
X²t song h m
f (x, y) := hAx, y − xi.
D¹ th§y, f (x, y) + f (y, x) = 0, ∀x, y ∈ C n¶n f ìn i»u tr¶n C nh÷ng
khæng ìn i»u m¤nh tr¶n C v do â khæng gi£ ìn i»u m¤nh tr¶n C .
X²t song h m
g(x, y) := ||x||2 hAT x, y − xi.
Song h m g l gi£ ìn i»u tr¶n C , tuy nhi¶n nâ khæng gi£ ìn i»u
m¤nh v công khæng ìn i»u. Thªt vªy, l§y x = (1, 1), y = (0, 1), ta câ:
f (x, y) + f (y, x) = 1 > 0.
V½ dö 1.1.2. Cho 0 < r < R, °t C = B(r) := {x ∈ H : ||x|| ≤ r} v
song h m f ÷ñc x¡c ành bði
f (x, y) := h(x, y) + (R − ||x||)g(x, y),
ð â h v g thäa m¢n c¡c i·u ki»n sau:
(i) h(x, y) ≤ 0, ∀x, y ∈ C v g l ìn i»u m¤nh h» sè β tr¶n C ;
(ii) ∃y0 ∈ C sao cho
(
h(0, y 0 ) + h(y 0 , 0) = 0;
Rg(0, y 0 ) + (R − ||y 0 ||)g(y 0 , 0) > 0.
13
º ch¿ ra f l gi£ ìn i»u m¤nh tr¶n C , ta gi£ thi¸t r¬ng f (x, y) ≥ 0.
Khi â, do h(x, y) ≤ 0, ta suy ra g(x, y) ≥ 0. Do t½nh ìn i»u m¤nh cõa
g , k²o theo g(y, x) ≤ −β||x − y||2 . Tø â, theo ành ngh¾a cõa f (y, x) ta
câ
f (y, x) = h(y, x) + (R − ||y||)g(y, x) ≤ −(R − r)β||y − x||2 ∀x, y ∈ C.
Do â f l gi£ ìn i»u m¤nh h» sè (R − r)β tr¶n C .
Song h m f khæng ìn i»u tr¶n C v¼ tø gi£ thi¸t (ii) ta ÷ñc
f (0, y 0 ) + f (y 0 , 0) = h(0, y 0 ) + Rg(0, y 0 ) + h(y 0 , 0) + (R − ||y 0 ||)g(y 0 , 0) > 0.
Mët v½ dö cö thº v· c¡c h m g v h thäa m¢n c¡c i·u ki»n (i) v (ii) l
g(x, y) := hx, y − xi + m(||y||2 − ||x||2 ) vîi m > 0
v
h(x, y) := (x − y)T A(y − x)
vîi A : H → H l mët to¡n tû tuy¸n t½nh thäa m¢n h(x, y) ≥ 0 vîi måi
x, y ∈ C .
D¹ th§y g l song h m ìn i»u m¤nh vîi måi m > 0. Hìn núa ta câ
Rg(0, y) + (R − ||y||)g(y, 0) = [mR − (m + 1)R + (m + 1)||y||] |y||2 |
= [(m + 1)||y|| − R] ||y||2 .
0
Do â, n¸u m > R−r
r , th¼ i·u ki»n (ii) ÷ñc thäa m¢n vîi måi y ∈ C =
R
B(r) vîi ||y 0 || > m+1
v (y0)T Ay0 = 0.
1.2 B i to¡n c¥n b¬ng gi£ ìn i»u
Trong möc n y, tæi tr¼nh b y mët sè k¸t qu£ s³ ÷ñc dòng trong chùng
minh sü tçn t¤i nghi»m công nh÷ sü hëi tö cõa c¡c thuªt to¡n gi£i b i
to¡n c¥n b¬ng ð nhúng ch÷ìng sau.
1. B i to¡n tèi ÷u.
Cho f : H → R ∪ {+∞} l h m ch½nh th÷íng, x̄ ∈ H. Khi â x̄ ÷ñc
gåi l mët cüc iºm cüc trà cõa f n¸u f (x̄) ≤ f (x) vîi måi x ∈ H v f (x̄)
14
÷ñc gåi l gi¡ trà cüc tiºu cõa f , ta vi¸t f (x̄) = minHf . Tªp c¡c iºm cüc
tiºu cõa f ÷ñc k½ hi»u l argminf .
Cho C l mët tªp con cõa H sao cho C ∩ domf 6= ∅. iºm x̄ ∈ C ÷ñc
gåi l mët iºm cüc tiºu cõa f tr¶n C n¸u f (x̄) ≤ f (x) vîi måi x ∈ C v
f (x̄) ÷ñc gåi l gi¡ trà cüc tiºu cõa f tr¶n C , ta vi¸t f (x̄) = minC f . Tªp
c¡c iºm cüc tiºu cõa f tr¶n C ÷ñc k½ hi»u l argminC f .
Chó þ r¬ng minC f = minH(f + ιC ), ð â ιC l h m ch¿ cõa tªp C .
ành ngh¾a 1.2.1. Cho C ⊂ H l mët tªp lçi âng, kh¡c réng, f :
C × C → R l mët h m sè thäa m¢n f (x, x) = 0. B i to¡n: t¼m x̄ ∈ C sao
cho f (x̄, y) ≥ 0 vîi måi y ∈ C ÷ñc gåi l b i to¡n c¥n b¬ng, x̄ ÷ñc gåi
l iºm c¥n b¬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 kh¡c, nâ bao h m ÷ñc r§t nhi·u b i to¡n kh¡c: b i to¡n tèi ÷u, b i
to¡n b§t ¯ng thùc bi¸n ph¥n...
ành ngh¾a 1.2.2. Cho C ⊂ H l tªp lçi âng kh¡c réng v f : C ×C → R
x¡c ành tr¶n C . Khi â, b i to¡n tèi ÷u ÷ñc ph¡t biºu nh÷ sau: T¼m
x̄ ∈ C : f (x, y) ≥ f (x̄, y), ∀y ∈ C . iºm x̄ ÷ñc gåi l nghi»m cõa b i to¡n
tèi ÷u.
Bê · 1.2.1. Cho C ⊂ H l mët tªp lçi âng kh¡c réng, f : H × H →
R ∪ {+∞} l mët song h m c¥n b¬ng tr¶n C , tùc l f (x, x) = 0, ∀x ∈ C .
Khi â b i to¡n tèi ÷u t÷ìng ÷ìng vîi b i to¡n c¥n b¬ng.
X²t b i to¡n c¥n b¬ng
T¼m x̄ ∈ C : f (x̄, y) ≥ 0, ∀y ∈ C.
(EP )
B i to¡n èi ng¨u cõa (EP) l b i to¡n
T¼m x̄ ∈ C : f (y, x̄) ≤, ∀y ∈ C.
(DEP )
Tªp nghi»m cõa b i to¡n c¥n b¬ng (EP) v b i to¡n èi ng¨u cõa nâ
(DEP) ÷ñc k½ hi»u l¦n l÷ñt l (SEP) v (SDEP). Ta câ mèi li¶n h» giúa
hai tªp nghi»m (SEP) v (SDEP) nh÷ sau.
15
Bê · 1.2.2. (a) N¸u f gi£ ìn i»u th¼ (SEP ) ⊆ (SDEP );
(b) N¸u f (., y) b¡n li¶n töc tr¶n v f (x, .) l tüa lçi ch°t vîi måi x, y ∈ C
th¼ (SDEP ) ⊆ (SEP ).
Do â, n¸u song h m f l gi£ ìn i»u tr¶n C v f (., y) nûa li¶n töc
tr¶n ð tr¶n C th¼ ta câ (SEP ) = (SDEP ).
Cho ¡nh x¤ T : H → H, tªp c¡c iºm b§t ëng cõa T , k½ hi»u l F ixT ,
l tªp:
F ixT = {x ∈ H : T x = x}.
Bê · 1.2.3. Cho C l mët tªp lçi âng kh¡c réng cõa H, T : C → H l
mët ¡nh x¤ khæng gi¢n, {xk }k≥0 ⊂ C v x l mët ph¦n tû trong H. Gi£ sû
r¬ng xk * x v xk − T (xk ) → 0. Khi â x ∈ F ixT .
Bê · 1.2.4. Cho C l mët tªp lçi âng kh¡c réng trong H v T : C → H
l ¡nh x¤ khæng gi¢n. Khi â F ixT l tªp lçi âng.
Bê · 1.2.5. Gi£ sû tªp iºm b§t ëng chungPS cõa c¡c ¡nh x¤ khæng
gi¢n Tj , j = 1, . . . , N khæng réng. °t T (x) := Nj=1 µj Tj (x) vîi 0 < µj <
P
1, j = 1, . . . , N v N
j=1 µj = 1. Khi â T l ¡nh x¤ khæng gi¢n v S tròng
vîi tªp iºm b§t ëng cõa T .
Chùng minh. Tr÷îc h¸t, d¹ th§y T l ¡nh x¤ khæng gi¢n v S ⊆ F ix(T ).
º chùng minh F ix(T ) ⊆ S , ta l§y x ∈ F ix(T ) v ch¿ ra r¬ng x ∈ S . Thªt
vªy, l§y u ∈ S , ta câ:
2
||x − u|| = ||
N
X
µj Tj (x) − u||2
j=1
= ||
N
X
µj [Tj (x) − Tj (u)] ||2
j=1
=
N
X
µj || [Tj (x) − Tj (u)] ||2 −
j=1
≤
N
X
j=1
X
µj µk || [j (x) − Tk (x)] ||2
1≤j
- Xem thêm -