Luận văn Thạc sĩ Toán học: Một phương pháp tách giải một lớp bài toán cân bằng

Chia sẻ: Tri Lễ | Ngày: | Loại File: PDF | Số trang:43

Thêm vào BST

Báo xấu

13
lượt xem 4
download

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

Mục đích của bài luận văn này là giới thiệu những kiến thức cơ bản nhất của bài toán cân bằng và trình bày một phương pháp tách giải một lớp bài toán cân bằng mới được công bố gần đây. Mời các bạn cùng tham khảo nội dung chi tiết.

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 Thạc sĩ Toán học: Một phương pháp tách giải một lớp bài toán cân bằng

I HÅC THI NGUYN TR×ÍNG I HÅC KHOA HÅC NGUYN B ÆN MËT PH×ÌNG PHP TCH GII MËT LÎP BI TON CN BNG LUN VN THC S TON HÅC Th¡i Nguy¶n - N«m 2018
I HÅC THI NGUYN TR×ÍNG I HÅC KHOA HÅC NGUYN B ÆN MËT PH×ÌNG PHP TCH GII MËT LÎP BI TON CN BNG Chuy¶n ng nh: TON ÙNG DÖNG M¢ sè : 8460112 LUN VN THC S TON HÅC Ng÷íi h÷îng d¨n khoa håc: GS. TSKH. L DÔNG M×U Th¡i Nguy¶n - N«m 2018
i Möc löc Möc löc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Líi c£m ìn 1 Líi nâi ¦u 2 Mët sè kþ hi»u v chú vi¸t tt 4 1 B i to¡n c¥n b¬ng 5 1.1 Mët sè kh¡i ni»m cì b£n . . . . . . . . . . . . . . . . . . . . 5 1.2 Sü tçn t¤i nghi»m v c¡c t½nh ch§t cì b£n cõa b i to¡n c¥n b¬ng 14 1.3 C¡c tr÷íng hñp ri¶ng cõa b i to¡n c¥n b¬ng . . . . . . . . . . 18 2 Thuªt to¡n t¡ch gi£i b i to¡n c¥n b¬ng ìn i»u 23 2.1 Thuªt to¡n tu¦n tü v sü hëi tö . . . . . . . . . . . . . . . . 24 2.2 Thuªt to¡n song song v sü hëi tö . . . . . . . . . . . . . . . 33 K¸t luªn 38 T i li»u tham kh£o 39
1 LÍI CM ÌN Luªn v«n n y ÷ñc ho n th nh d÷îi sü h÷îng d¨n tªn t¼nh v sü ch¿ b£o nghi¶m khc cõa th¦y gi¡o GS. TSKH. L¶ Dông M÷u (Tr÷íng ¤i håc Th«ng Long H Nëi). Tæi xin gûi líi c£m ìn ch¥n th nh v s¥u sc nh§t ¸n th¦y. T¡c gi£ công xin k½nh gûi líi c£m ìn ¸n cæ gi¡o PGS.TS. Nguy¹n Thà Thu Thõy còng c¡c th¦y, cæ gi¡o tham gia gi£ng d¤y khâa håc cao håc 2016 - 2018, nhúng ng÷íi ¢ t¥m huy¸t gi£ng d¤y v trang bà cho t¡c gi£ nhi·u ki¸n thùc cì sð. Xin gûi líi c£m ìn ¸n Ban gi¡m hi»u, pháng o t¤o, khoa To¡n - Tin Tr÷íng HKH, ¤i håc Th¡i Nguy¶n ¢ t¤o i·u ki»n thuªn lñi cho tæi trong qu¡ tr¼nh håc tªp t¤i tr÷íng. Xin ch¥n th nh c£m ìn gia ¼nh, b¤n b± çng nghi»p v c¡c th nh vi¶n trong lîp cao håc to¡n K10A ¢ luæn quan t¥m, ëng vi¶n, gióp ï tæi trong thíi gian håc tªp v qu¡ tr¼nh l m luªn v«n. Tuy b£n th¥n câ nhi·u cè gng, song thíi gian v n«ng lüc cõa b£n th¥n câ h¤n n¶n luªn v«n khâ tr¡nh khäi nhúng thi¸u sât. R§t mong ÷ñc sü âng gâp quþ b¡u cõa Quþ th¦y, cæ còng to n thº b¤n åc. T¡c gi£
2 LÍI NÂI U Cho H l mët khæng gian Hilbert thüc vîi t½ch væ h÷îng h., .i v chu©n k.k t÷ìng ùng. Cho C l mët tªp lçi, âng, kh¡c réng trong H v f l song h m tø C × C v o R sao cho f (x, x) = 0 vîi måi x ∈ C . Trong luªn v«n n y ta s³ x²t b i to¡n c¥n b¬ng sau ¥y, ÷ñc kþ hi»u l EP(C, f ): T¼m x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C. (1) B i to¡n EP(C, f ) cán ÷ñc gåi l b§t ¯ng thùc Ky Fan º ghi nhªn sü âng gâp cõa æng trong l¾nh vüc n y. B§t ¯ng thùc (1) l¦n ¦u ti¶n, n«m 1955, ÷ñc Nikaido v Isoda dòng trong trá chìi khæng hñp t¡c. N«m 1972, Ky Fan gåi (1) l b§t ¯ng thùc minimax v ÷a ra mët ành lþ v· sü tçn t¤i nghi»m cho b i to¡n n y trong khæng gian húu h¤n chi·u. Ngay trong n«m â, ành lþ n y ÷ñc mð rëng ra trong khæng gian væ h¤n chi·u bði Br²sis v Stampacchia. N«m 1984, L.D. Muu gåi (1) l b i to¡n b§t ¯ng thùc bi¸n ph¥n v nghi¶n cùu t½nh ên ành cho b i to¡n n y. N«m 1992, l¦n ¦u ti¶n (1) ÷ñc gåi l b i to¡n c¥n b¬ng trong t i li»u [9]. C¡c nghi¶n cùu v· b i to¡n c¥n b¬ng câ thº chia theo hai h÷îng ch½nh bao gçm nhúng nghi¶n cùu v· sü tçn t¤i nghi»m v c¡c thuªt to¡n gi£i b i to¡n c¥n b¬ng. Cho ¸n nay ng÷íi ta ¢ ÷a ra nhi·u ph÷ìng ph¡p º gi£i b i to¡n c¥n b¬ng ch¯ng h¤n nh÷ ph÷ìng ph¡p chi¸u v c¡c bi¸n d¤ng cõa nâ. Tuy nhi¶n, º t«ng c÷íng sü hi»u qu£ ng÷íi ta ¢ nghi¶n cùu c¡c ph÷ìng ph¡p t¡ch(splitting method) º gi£i b i to¡n c¥n b¬ng. Möc ½ch cõa b£n luªn v«n n y l giîi thi»u nhúng ki¸n thùc cì b£n nh§t cõa b i to¡n c¥n b¬ng v tr¼nh b y mët ph÷ìng ph¡p t¡ch gi£i mët lîp b i to¡n c¥n b¬ng mîi ÷ñc cæng bè g¦n ¥y. Luªn v«n bao gçm ph¦n mð ¦u, hai ch÷ìng, k¸t luªn v danh möc c¡c t i li»u tham kh£o. Ch÷ìng 1 tr¼nh b y mët sè kh¡i ni»m cì b£n li¶n quan ¸n · t i. C¡c v§n · li¶n quan ¸n sü tçn t¤i nghi»m v c¡c tr÷íng hñp ri¶ng cõa b i to¡n
3 c¥n b¬ng công ÷ñc · cªp ¸n. Ch÷ìng 2 tr¼nh b y hai thuªt to¡n t¡ch gi£i b i to¡n c¥n b¬ng trong â song h m l têng cõa hai song h m. Thuªt to¡n ¦u l mët thuªt to¡n t¡ch tu¦n tü, thuªt to¡n sau l mët thuªt to¡n t¡ch song song.
4 MËT SÈ KÞ HIU V CHÚ VIT TT H : Khæng gian Hilbert thüc; X : Khæng gian Banach thüc; R: Tªp c¡c sè thüc; ∅: Tªp réng; I : nh x¤ çng nh§t; ha, bi = T½ch væ h÷îng cõa 2 v²c-tì a v b; kxk = Chu©n cõa x; ∂f (x): D÷îi vi ph¥n cõa h m f t¤i x; ∀x: Vîi måi x; xn → x: D¢y {xn } hëi tö m¤nh tîi x; xn * x: D¢y {xn } hëi tö y¸u tîi x; x := y : Ngh¾a l , x ÷ñc ành ngh¾a b¬ng y ; PC (x): H¼nh chi¸u cõa x l¶n C .
5 Ch÷ìng 1 B i to¡n c¥n b¬ng Ch÷ìng n y tr¼nh b y c¡c kh¡i ni»m li¶n quan ¸n b i to¡n c¥n b¬ng, sü tçn t¤i nghi»m, c¡c t½nh ch§t cì b£n v c¡c tr÷íng hñp ri¶ng quan trång cõa b i to¡n c¥n b¬ng. C¡c ki¸n thùc trong ch÷ìng ÷ñc tr½ch tø t i li»u [1-4], [7], [10]. 1.1 Mët sè kh¡i ni»m cì b£n ành ngh¾a 1.1.(xem [4]) C°p (H, h, i) trong â H l mët khæng gian tuy¸n t½nh thüc v h, i : H × H → R (x, y) 7→ hx, yi thäa m¢n c¡c i·u ki»n: 1. hx, xi ≥ 0, ∀x ∈ H; hx, xi = 0 ⇔ x = 0; 2. hx, yi = hy, xi , ∀x, y ∈ H ; 3. hλx, yi = λ hx, yi , ∀λ ∈ R, ∀x, y ∈ H ; 4. hx + y, zi = hx, zi + hy, zi , ∀x, y, z ∈ H . ÷ñc gåi l khæng gian ti·n Hilbert. Khæng gian ti·n Hilbert ¦y õ ÷ñc gåi l khæng gian Hilbert. V½ dö 1.1. L2[a,b] l khæng gian c¡c h m b¼nh ph÷ìng kh£ t½ch tr¶n [a,b] Rb vîi f ∈ L2[a,b] sao cho f 2 (x) dx < +∞ l mët khæng gian Hilbert vîi t½ch a væ h÷îng Zb hf, gi = f (x) g (x) dx; a
6 v chu©n 1  b  Z 2 2 kf kL2 =  f (x)dx . [a,b] a Tr¶n H câ hai kiºu hëi tö ch½nh sau: ành ngh¾a 1.2.(xem [4]) X²t d¢y {xn}n≥0 v x thuëc khæng gian Hilbert thüc H . Khi â: • D¢y {xn } ÷ñc gåi l hëi tö m¤nh tîi x, kþ hi»u xn → x, n¸u nh÷ lim kxn − xk = 0. n→+∞ • D¢y {xn} ÷ñc gåi l hëi tö y¸u tîi x, kþ hi»u xn * x, n¸u lim hω, xn i = hω, xi , ∀ω ∈ H. n→+∞ Ta nhc l¤i c¡c k¸t qu£ trong gi£i t½ch h m (xem [4]) li¶n quan ¸n hai lo¤i hëi tö n y. M»nh · 1.1. • N¸u {xn} hëi tö m¤nh ¸n x th¼ công hëi tö y¸u ¸n x. • Måi d¢y hëi tö m¤nh (y¸u) ·u bà ch°n v giîi h¤n theo sü hëi tö m¤nh (y¸u) n¸u tçn t¤i l duy nh§t. • N¸u khæng gian Hilbert thüc H l khæng gian húu h¤n chi·u th¼ sü hëi tö m¤nh v sü hëi tö y¸u l t÷ìng ÷ìng. • N¸u {xn }n≥0 l mët d¢y bà ch°n trong khæng gian Hilbert thüc H th¼ ta tr½ch ra ÷ñc mët d¢y con hëi tö y¸u. • N¸u {xn }n≥0 l mët d¢y bà ch°n trong khæng gian Hilbert thüc húu h¤n chi·u H th¼ ta tr½ch ra ÷ñc mët d¢y con hëi tö m¤nh. Ti¸p theo, ta s³ n¶u mët sè ành ngh¾a v k¸t qu£ cì b£n cõa gi£i t½ch lçi ÷ñc ph¡t biºu trong [1], [10]. X²t C l tªp con kh¡c réng trong khæng gian Hilbert thüc H . ành ngh¾a 1.3.(xem [10]) Tªp C trong khæng gian Hilbert thüc H ÷ñc gåi l mët tªp lçi n¸u ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
7 ành ngh¾a 1.4.(xem [10]) iºm a ÷ñc gåi l iºm bi¶n cõa C n¸u måi l¥n cªn cõa a ·u câ iºm thuëc C v iºm khæng thuëc C ; Tªp C ÷ñc gåi l tªp âng n¸u C chùa måi iºm bi¶n cõa nâ; Tªp C ÷ñc gåi l mët tªp compact n¸u C l mët tªp âng v bà ch°n. ành ngh¾a 1.5.(xem [10]) Cho C l mët tªp lçi cõa khæng gian Hilbert H v x ∈ C . Nân ph¡p tuy¸n ngo i cõa C ÷ñc kþ hi»u v ành ngh¾a bði: NC (x) := {w| hw, y − xi ≤ 0, ∀y ∈ C} . ành ngh¾a 1.6.(xem [10]) X²t h m f : H → R ∪ {+∞}. Khi â: (i) H m f ÷ñc gåi l h m lçi tr¶n H n¸u f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ H, ∀λ ∈ (0, 1); (ii) H m f ÷ñc gåi l h m lçi ch°t tr¶n H n¸u f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x 6= y ∈ H, ∀λ ∈ (0, 1); (iii) H m f ÷ñc gåi l h m lçi m¤nh tr¶n H vîi h» sè η > 0 n¸u λ(1 − λ) f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − η kx − yk2 , 2 vîi måi x, y ∈ H, ∀λ ∈ (0, 1). D÷îi ¥y l mët sè v½ dö quen thuëc v· h m lçi. V½ dö 1.2. 1. H m affine. f (x) = aT x + b, trong â a ∈ Rn, b ∈ R l h m lçi. Nâ tho£ m¢n ¯ng thùc f (λx + (1 − λ)y) = λf (x) + (1 − λ)f (y), ∀x, y ∈ H, λ ∈ (0, 1). Do â nâ khæng lçi ch°t. Cho C 6= ∅ l mët tªp lçi. 2. H m ch¿. °t 0 khi x ∈ C δC := +∞ khi x ∈ /C h m ch¿ cõa C . Do C lçi n¶n δC l h m lçi. Ta nâi δC l 3. H m kho£ng c¡ch. Gi£ sû C l mët tªp âng, kh¡c réng. H m kho£ng c¡ch dC (y) ÷ñc ành ngh¾a nh÷ sau: dC (y) = inf kx − yk. x∈C
8 Khi â, n¸u C l tªp lçi th¼ dC l h m lçi. Thªt vªy, x²t x, y ∈ H v λ ∈ (0, 1) b§t ký. °t z = λx + (1 − λ)y . Theo ành ngh¾a tçn t¤i c¡c d¢y {xk } , {yk } trong C sao cho lim kx − xk k = dC (x) v lim ky − yk k = dC (y). k→∞ k→∞ Do C lçi n¶n zk := λxk + (1 − λ)yk ∈ C . Ta câ dC (z) ≤ kz − zk k = kλ(x − xk ) + (1 − λ)(y − yk )k ≤ λ kx − xk k + (1 − λ) ky − yk k . Cho k → ∞ ta câ dC (z) ≤ λdC (x) + (1 − λ)dC (y). Vªy dC l h m lçi. 2 N¸u tçn t¤i π ∈ C sao cho kπ − yk = dC (y) th¼ π ÷ñc gåi l h¼nh chi¸u kho£ng c¡ch cõa y tr¶n C . Khi â, π l nghi»m cõa b i to¡n tèi ÷u kx − yk2 min . y∈C 2 Kþ hi»u h¼nh chi¸u cõa y tr¶n C l PC (y). Khi â, π = PC (y). Ti¸p theo ta s³ chùng minh sü tçn t¤i v t½nh duy nh§t cõa h¼nh chi¸u xuèng mët tªp lçi âng. Sau â ta s³ kh£o s¡t mët sè t½nh ch§t cì b£n cõa to¡n tû chi¸u ÷ñc sû döng trong ch÷ìng sau cõa luªn v«n. M»nh · 1.2.(xem [10]) Gi£ sû C l lçi, âng kh¡c réng trong H . Khi â: (i) Vîi måi y ∈ H , π ∈ C hai t½nh ch§t sau t÷ìng ÷ìng: (a) π = PC (y), (b) y − π ∈ NC (π). (ii) Vîi ∀x ∈ H , h¼nh chi¸u PC (x) cõa x tr¶n C luæn tçn t¤i v duy nh§t. (iii) N¸u y ∈/ C th¼ hPC (y) − y, x − PC (y)i = 0 l si¶u ph¯ng tüa cõa C t¤i PC (y) v t¡ch h¯n y khäi C , tùc l hPC (y) − y, x − PC (y)i ≥ 0, ∀x ∈ C; v hPC (y) − y, y − PC (y)i < 0. (iv) nh x¤ y 7→ PC (y) câ c¡c t½nh ch§t sau: (a) kPC (x) − PC (y)k ≤ kx − yk, ∀x, ∀y (t½nh khæng gi¢n); (b) hPC (x) − PC (y), x − yi ≥ kPC (x) − PC (y)k2 (t½nh çng bùc). Chùng minh. (i) Gi£ sû câ (a), tùc l π l h¼nh chi¸u cõa y tr¶n C . L§y x ∈ C . °t xλ := λx + (1 − λ)π.
9 Do C lçi n¶n xλ ∈ C vîi måi λ ∈ (0, 1). Theo ành ngh¾a h¼nh chi¸u ta câ kπ − yk ≤ ky − xλ k. Hay kπ − yk2 ≤ ky − xλ k2 = k(π − y) + λ(x − π)k2 . Khai triºn v¸ ph£i v gi£n ÷îc ta thu ÷ñc λkx − πk2 + 2 hx − π, π − yi ≥ 0, x ∈ C, λ ∈ (0, 1). Cho λ ti¸n tîi 0 ta thu ÷ñc b§t ¯ng thùc hπ − y, x − πi ≥ 0. i·u n y óng vîi x ∈ C b§t ký n¶n suy ra y − π ∈ NC (π). Gi£ sû câ (b) tùc l gi£ sû y − π ∈ NC (π). Khi â vîi måi x ∈ C ta câ ky − xk2 =k(y − π) + (π − x)k2 =ky − πk2 + kπ − xk2 + 2 hy − π, π − xi ≥ky − πk2 + kπ − xk2 ≥ky − πk2 . Suy ra π l h¼nh chi¸u cõa y tr¶n C . (ii) Chùng minh. Thªt vªy, °t d = u∈C inf kx − uk. Khi â, tçn t¤i {un } ⊂ C sao cho kx − un k −→ d, n −→ ∞. Tø â ta câ kun − um k2 = k(x − un ) − (x − um )k2 2 2 un + um 2 = 2kx − un k + 2kx − um k − 4kx − k 2 ≤ 2(kx − un k2 + kx − um k2 ) − 4d2 −→ 0, khi n, m −→ ∞. Do â {un } l d¢y Cauchy trong H . Suy ra tçn t¤i u = lim un ∈ C . Do chu©n l h m sè li¶n töc n¶n kx − uk = d. Gi£ sû n→∞ tçn t¤i v ∈ C sao cho kx − vk = d. Ta câ ku − vk2 = k(x − u) − (x − v)k2 u+v 2 = 2(kx − uk2 + kx − vk2 ) − 4kx − k 2 ≤ 0. Suy ra u = v . Vªy tçn t¤i duy nh§t mët ph¦n tû PC x ∈ C sao cho kx − PC xk = inf u∈C kx − uk.
10 (iii) Do y − π ∈ NC (π) n¶n hπ − y, x − πi ≥ 0, ∀x ∈ C. Vªy hπ − y, xi = hπ − y, πi l mët si¶u ph¯ng tüa cõa C t¤i π . Si¶u ph¯ng n y t¡ch y khäi C v¼ y 6= π n¶n hπ − y, y − πi = −kπ − yk2 < 0. (iv) (a) Theo ph¦n (ii) ¡nh x¤ x 7→ PC (x) x¡c ành khp nìi. Do z − PC (z) ∈ NC (PC (z)) vîi måi z , ¡p döng vîi z = x v z = y , ta câ hx − PC (x), PC (y) − PC (x)i ≤ 0; v hy − PC (y), PC (x) − PC (y)i ≤ 0. Cëng hai b§t ¯ng thùc tr¶n, ta ÷ñc hPC (y) − PC (x), PC (y) − PC (x) + x − yi ≤ 0. K¸t hñp i·u n y v b§t ¯ng thùc Cauchy-Schwarz, suy ra kPC (x) − PC (y)k ≤ kx − yk. (b) p döng t½nh ch§t (b) cõa (i), l¦n l÷ñt vîi PC (x) v PC (y), ta câ: hPC (x) − x, PC (x) − PC (y)i ≤ 0; hy − PC (y), PC (x) − PC (y)i ≤ 0 Cëng hai b§t ¯ng thùc tr¶n, suy ra hPC (x) − PC (y) + y − x, PC (x) − PC (y)i =hPC (x) − PC (y), y − xi + kPC (x) − PC (y)k2 ≤ 0. Chuyºn v¸ ta câ hPC (x) − PC (y), x − yi ≥ kPC (x) − PC (y)k2 . Vªy m»nh · ¢ ÷ñc chùng minh. 2 ành ngh¾a 1.7.(xem [10]) Cho f : H → R ∪ {+∞}. Ta nâi x ∗ ∈H l d÷îi ¤o h m cõa f t¤i x n¸u hx∗ , z − xi + f (x) ≤ f (z), ∀z. Kþ hi»u tªp t§t c£ c¡c d÷îi ¤o h m cõa f t¤i x l ∂f (x). Khi ∂f (x) 6= ∅ th¼ ta nâi h m f kh£ d÷îi vi ph¥n t¤i iºm x.
11 f ÷ñc gåi l kh£ d÷îi vi ph¥n tr¶n mët tªp n¸u f kh£ d÷îi vi ph¥n t¤i måi iºm tr¶n tªp â. V½ dö 1.3. 1. f (x) = kxk , x ∈ Rn . T¤i iºm x = 0 h m n y khæng kh£ vi, nh÷ng nâ kh£ d÷îi vi ph¥n v ∂f (0) = {x∗ | hx∗ , xi ≤ kxk , ∀x} ; 2. f = δC l h m ch¿ cõa mët tªp lçi C 6= ∅. Khi â, vîi x0 ∈ C , 0 ∗ ∗ 0 ∂δC (x ) = x | x , x − x ≤ δC (x), ∀x . Vîi x ∈ / C th¼ δC (x) = +∞, n¶n b§t ¯ng thùc n y luæn óng. Vªy 0 ∗ ∗ 0 0 ∂δC (x ) = x | x , x − x ≤ 0, ∀x ∈ C = NC (x ). Ta câ m»nh · sau nâi l¶n t½nh kh£ d÷îi vi ph¥n cõa h m lçi. M»nh · 1.3. (xem [10]) N¸u f : H → R l h m lçi th¼ ∂f (x) 6= ∅ vîi måi x∈X hay l f kh£ d÷îi vi ph¥n khp nìi. ành ngh¾a 1.8.(xem [10]) H m k f : H →kR ÷ñc gåi l nûa li¶n töc d÷îi t¤i mët iºm x, n¸u vîi måi d¢y x ⊂ E; x → x ta câ k→∞ lim inf f (xk ) ≥ f (x); H m f ÷ñc gåi l nûa li¶n töc tr¶n t¤i mët iºm x , n¸u −f nûa li¶n töc d÷îi t¤i mët iºm x. Hay l vîi måi d¢y x ⊂ E; x → x th¼ k→∞ k k lim sup f (xk ) ≤ f (x); H m f ÷ñc gåi l li¶n töc t¤i mët iºm x n¸u nh÷ nâ vøa nûa li¶n töc tr¶n v nûa li¶n töc d÷îi t¤i x. Khi E l to n khæng gian, ta nâi ìn gi£n l nûa li¶n töc d÷îi, nûa li¶n töc tr¶n hay li¶n töc. ành ngh¾a 1.9.(xem [10]) Mët h m sè thüc ϕ ÷ñc gåi l tüa lçi tr¶n tªp lçi C , n¸u vîi måi sè thüc γ tªp mùc d÷îi {x ∈ C|ϕ(x) ≤ γ} lçi. T÷ìng tü, h m mët h m ϕ ÷ñc gåi l tüa lãm tr¶n C , n¸u −ϕ l h m tüa lçi tr¶n C . N¸u ϕ tüa lçi tr¶n C th¼ ∀x, y ∈ C v λ ∈ [0, 1] ta câ ϕ(λx + (1 − λ)y) ≤ max {ϕ(x), ϕ(y)} ; T÷ìng tü, n¸u ϕ tüa lãm tr¶n C th¼ ∀x, y ∈ C v λ ∈ [0, 1] ta câ ϕ(λx + (1 − λ)y) ≤ min {ϕ(x), ϕ(y)} . C¡c ành ngh¾a v· t½nh ìn i»u cõa song h m v ¡nh x¤ ÷ñc sû döng trong vi»c tr¼nh b y t½nh duy nh§t nghi»m cõa b i to¡n c¥n b¬ng (xem [1], [7]).
12 Trong c¡c ành ngh¾a sau x²t C l tªp kh¡c réng, âng, lçi trong khæng gian Hilbert thüc H . ành ngh¾a 1.10. (xem [7]) Gi£ sû f : C × C → R. Ta nâi (i) f ìn i»u m¤nh tr¶n C vîi h» sè β > 0, n¸u f (x, y) + f (y, x) ≤ −βkx − yk2 , ∀x, y ∈ C; (ii) f ìn i»u ch°t tr¶n C , n¸u f (x, y) + f (y, x) < 0, ∀x, y ∈ C, x 6= y; (iii) f ìn i»u tr¶n C , n¸u f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; (iv) f gi£ ìn i»u tr¶n C , n¸u f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C; (v) f li¶n töc câ t½nh ch§t kiºu Lipschitz tr¶n C vîi h¬ng sè c1 > 0 v c2 > 0, n¸u f (x, y) + f (y, z) ≥ f (x, z) − c1 kx − yk2 − c2 ky − zk2 , ∀x, y ∈ C. Tø ành ngh¾a ta câ (i) ⇒ (ii) ⇒ (iii) ⇒ (iv). V½ dö 1.4. X²t h m h : H → R. Khi â: 1. f (x, y) := h(x) − h(y) l ìn i»u nh÷ng khæng ìn i»u ch°t. 2. g(x, y) := h(x) − h(y) − 1 l ìn i»u ch°t nh÷ng khæng ìn i»u m¤nh. Thªt vªy, x²t g(x, y) + g(y, x) = −2 < 0 vîi måi x, y ∈ H n¶n g ìn i»u ch°t. Gi£ sû tçn t¤i h» sè β > 0 thäa m¢n i·u ki»n ìn i»u m¤nh, suy ra βkx − yk2 ≤ 2. ∀x, y ∈ H. Chån x = 0 v y = tv vîi v l mët v²c-tì kh¡c 0 trong H , ta ÷ñc 2 β≤ , ∀t ∈ R. |t| .kvk Cho t → ∞ th¼ i·u ki»n tr¶n ch¿ x£y ra khi β ≤ 0 (m¥u thu¨n). 2 C¡c kh¡i ni»m v· ìn i»u èi vîi song h m câ li¶n quan ch°t ch³ vîi c¡c kh¡i ni»m v· ìn i»u cõa ¡nh x¤ (to¡n tû), r§t quen thuëc trong gi£i t½ch phi tuy¸n.
13 ành ngh¾a 1.11.(xem [1-7]) nh x¤ F : C → H ÷ñc gåi l (i) ìn i»u m¤nh tr¶n C vîi h» sè β > 0, n¸u hF (x) − F (y), x − yi ≥ βkx − yk2 , ∀x, y ∈ C; (ii) ìn i»u ch°t tr¶n C , n¸u hF (x) − F (y), x − yi > 0, ∀x, y ∈ C; (iii) ìn i»u tr¶n C , n¸u hF (x) − F (y), x − yi ≥ 0, ∀x, y ∈ C; (iv) gi£ ìn i»u tr¶n C , n¸u hF (y), x − yi ≥ 0 ⇒ hF (x), x − yi ≥ 0, ∀x, y ∈ C; (v) li¶n töc L -Lipschitz tr¶n C n¸u kF (x) − F (y)k ≤ L kx − yk , ∀x, y ∈ C. Tø ành ngh¾a ta câ (i) ⇒ (ii) ⇒ (iii) ⇒ (iv). V½ dö 1.5.Cho C l tªp lçi, h m f : C → R. Khi â: • N¸u f l h m kh£ d÷îi vi ph¥n, lçi tr¶n C th¼ ∂f l ìn i»u tr¶n C . Thªt vªy, l§y tòy þ x, y ∈ C v u ∈ ∂f (x), v ∈ ∂f (y) theo ành ngh¾a cõa d÷îi vi ph¥n n¶n f (x) ≥ f (y) + hu, x − yi , f (y) ≥ f (x) + hv, y − xi . Cëng hai b§t ¯ng thùc tr¶n vîi nhau, suy ra hv − u, y − xi ≥ 0, ∀x, y ∈ C. Vªy ∂f l ìn i»u tr¶n C . 2 • N¸u f l kh£ d÷îi vi ph¥n, lçi m¤nh tr¶n C th¼ ∂f l ìn i»u m¤nh tr¶n C . • N¸u f l h m kh£ d÷îi vi ph¥n, lçi ch°t tr¶n C th¼ ∂f l ìn i»u ch°t tr¶n C . Nhªn x²t 1.1. N¸u F l L - Lipschitz tr¶n C th¼ vîi méi x, y ∈ C, f (x, y) = hF (x), y − xi L câ t½nh ch§t li¶n töc kiºu Lipschitz vîi h¬ng sè c1 = c2 = tr¶n C . 2
14 Thªt vªy f (x, y) + f (y, z) − f (x, z) = hF (x), y − xi + hF (y), z − yi − hF (x), z − xi = − hF (y) − F (x), y − zi ≥ − kF (x) − F (y)k ky − zk ≥ − L kx − yk ky − zk L L ≥ − kx − yk2 − ky − zk2 2 2 =c1 kx − yk − c2 ky − zk2 . 2 Do vªy, f l li¶n töc câ t½nh ch§t kiºu Lipschitz tr¶n C . 2 1.2 Sü tçn t¤i nghi»m v c¡c t½nh ch§t cì b£n cõa b i to¡n c¥n b¬ng Trong ph¦n n y ta nhc l¤i mët sè ành lþ quen thuëc trong gi£i t½ch phi tuy¸n. C¡c ành lþ n y l cæng cö sc b²n º nghi¶n cùu, °c bi»t l º chùng minh sü tçn t¤i nghi»m cõa b i to¡n c¥n b¬ng. B i to¡n c¥n b¬ng Ta nhc l¤i b i to¡n c¥n b¬ng (cán ÷ñc gåi l b§t ¯ng thùc Ky Fan): X²t H l khæng gian Hilbert thüc; C l tªp lçi, âng, kh¡c réng cõa H v f : C × C → R ∪ {+∞}. Khi â, b i to¡n c¥n b¬ng l b i to¡n T¼m x ∈ C sao cho f (x, y) ≥ 0, ∀y ∈ C. EP (C, f ) Tªp nghi»m cõa b i to¡n c¥n b¬ng ÷ñc kþ hi»u l Sol(C, f ). D÷îi ¥y ta s³ luæn gi£ thi¸t f (x, x) = 0 vîi måi x ∈ C . Mët song h m tho£ m¢n i·u ki»n n y ÷ñc gåi l song h m c¥n b¬ng. C ÷ñc gåi l tªp ch§p nhªn ÷ñc hay l tªp chi¸n l÷ñc v f l h m c¥n b¬ng cõa b i to¡n EP(C, f ). Ti¸p theo ta x²t sü tçn t¤i nghi»m v c¡c t½nh ch§t cì b£n cõa b i to¡n c¥n b¬ng. º chùng minh sü tçn t¤i nghi»m cõa b i to¡n c¥n b¬ng, ta c¦n ¸n c¡c ành lþ iºm b§t ëng trong gi£i t½ch h m l ành lþ Brouwer. º ti»n theo dãi, ta nhc l¤i c¡c ành lþ n y trong khæng gian Euclide húu h¤n chi·u, m°c
15 dò c¡c ành lþ n y ¢ ÷ñc chùng minh trong khæng gian væ h¤n chi·u. Ta công s³ sû döng ành lþ quen thuëc sau, l ành lþ cüc ¤i Berge. ành lþ . Cho X, Y l c¡c khæng gian tæ-pæ, F : X → 2Y l ¡nh x¤ nûa li¶n töc tr¶n tr¶n X sao cho F (x) compact, hìn núa F (X) compact. Gi£ sû f : X × X → R l h m sè nûa li¶n töc tr¶n tr¶n X . Khi â h m gi¡ trà tèi ÷u g(x) := max {f (x, y) : y ∈ F (x)} nûa li¶n töc tr¶n v ¡nh x¤ tªp nghi»m tèi ÷u S(x) := {y ∈ F (x) : f (x, y) = g(x)} nûa li¶n töc tr¶n. ành lþ (iºm b§t ëng Brouwer). Cho C l mët tªp lçi compact trong khæng gian Rn v F l mët ¡nh x¤ (ìn trà) li¶n töc tø C v o C . Khi â, tçn t¤i x∗ ∈ C tho£ m¢n x∗ = F (x∗). Düa v o ành lþ iºm b§t ëng Brouwer v ành lþ cüc ¤i Berge, ta câ m»nh · sau nâi v· sü tçn t¤i nghi»m cõa b i to¡n c¥n b¬ng. M»nh · 1.4. Cho C l mët tªp lçi, compact kh¡c réng v song h m c¥n b¬ng f : C x C → R ∪ {+∞} câ c¡c t½nh ch§t: (i) f (., y) nûa li¶n töc tr¶n vîi måi y ∈ C; (ii) f (x, .) lçi, nûa li¶n töc d÷îi v kh£ d÷îi vi ph¥n tr¶n C vîi måi x ∈ C. Khi â, b i to¡n EP(C, f ) câ nghi»m. Chùng minh. Vîi méi x ∈ C , ta gåi S(x) l tªp nghi»m cõa b i to¡n min {f (x, y) : y ∈ C} . (CO) Do C compact v f (x, .) nûa li¶n töc d÷îi n¶n theo ành lþ Weistrass, b i to¡n n y tçn t¤i nghi»m. Hìn núa, do C lçi, compact, f (x, .) lçi, n¶n S(x) lçi, compact. Theo ành lþ cüc ¤i Berge, ¡nh x¤ S nûa li¶n töc tr¶n. Vîi S l mët ¡nh x¤ tø C v o C . Vªy theo ành lþ iºm b§t ëng Brouwer, tçn t¤i x∗ ∈ C tho£ m¢n x∗ ∈ S(x∗ ). B¥y gií ta s³ ch¿ ra x∗ l nghi»m cõa b i to¡n c¥n b¬ng EP(C, f ). Thªt vªy, do f (x, .) lçi, kh£ d÷îi vi ph¥n tr¶n C , theo i·u ki»n c¦n v õ tèi ÷u cõa quy ho¤ch lçi, ta câ 0 ∈ ∂2 f (x∗ , x∗ ) + NC (x∗ ).
16 Theo ành ngh¾a cõa d÷îi vi ph¥n v nân ph¡p tuy¸n, tø ¥y ta câ v ∗ thuëc ∂2 f (x∗ , x∗ ) tho£ m¢n: hv ∗ , y − x∗ i ≥ 0, ∀y ∈ C. Do v ∗ ∈ ∂2 f (x∗ , x∗ ) n¶n hv ∗ , y − x∗ i ≤ f (x∗ , y) − f (x∗ , x∗ ) = f (x∗ , y), ∀y ∈ C. Vªy f (x∗ , y) ≥ 0, ∀y ∈ C . i·u n y chùng tä x∗ l nghi»m cõa EP(C, f ). M»nh · ¢ ÷ñc chùng minh. 2 H» qu£ 1.1. Cho C l mët tªp lçi, âng (khæng c¦n compact) v song h m c¥n b¬ng f nh÷ ð m»nh · tr¶n. Gi£ sû i·u ki»n bùc (C1) sau ¥y ÷ñc tho£ m¢n Tçn t¤i tªp compact B sao cho C ∩ B 6= ∅, ∀x ∈ C\B, ∃y ∈ C : f (x, y) < 0. Khi â, b i to¡n EP(C, f ) câ nghi»m. Chùng minh. Theo m»nh · tr¶n, b i to¡n c¥n b¬ng tr¶n tªp compact C ∩ B vîi h m c¥n b¬ng f câ nghi»m, tùc l tçn t¤i x∗ ∈ C ∩ B . Tø i·u ki»n bùc (C1) v t½nh lçi cõa tªp C , ta suy ra nghi»m x∗ công l nghi»m cõa b i to¡n EP(C, f ). 2 M»nh · tr¶n l mët tr÷íng hñp ri¶ng cõa ành lþ sau ¥y cõa Ky Fan. ành lþ (Ky Fan). Cho f : C × C → R ∪ {+∞} l mët song h m c¥n b¬ng câ c¡c t½nh ch§t sau: (i) f (., y) nûa li¶n töc tr¶n vîi måi y ∈ C ; (ii) f (x, .) tüa lçi tr¶n C vîi måi x ∈ C . Khi â, b i to¡n c¥n b¬ng EP(C, f ) câ nghi»m, n¸u nh÷ C compact, ho°c i·u ki»n bùc (C1) tho£ m¢n. B¥y gií ta x²t t½nh duy nh§t nghi»m cõa b i to¡n c¥n b¬ng. M»nh · 1.5. Cho C l tªp lçi, âng kh¡c réng v f : C × C → R ∪ {+∞} l song h m c¥n b¬ng. Khi â: (i) N¸u f l ìn i»u ch°t tr¶n C , th¼ b i to¡n c¥n b¬ng EP(C, f ) câ nhi·u nh§t mët nghi»m; (ii) f (., y) nûa li¶n töc tr¶n vîi måi y ∈ C v f (x, .) lçi, nûa li¶n töc d÷îi vîi méi x ∈ C v f ìn i»u m¤nh tr¶n C , th¼ b i to¡n EP(C, f ) luæn câ v câ duy nh§t nghi»m. Chùng minh. (i) Gi£ sû EP(C, f ) câ hai nghi»m x∗ v y ∗ . Khi â f (x∗ , y ∗ ) ≥ 0 v f (y ∗ , x∗ ) ≥ 0. Th¸ nh÷ng, n¸u f (x∗ , y ∗ ) ≥ 0, th¼ theo t½nh ìn i»u ch°t, ta ph£i câ f (y ∗ , x∗ ) < 0. i·u n y m¥u thu¨n vîi f (y ∗ , x∗ ) ≥ 0.
17 (ii) L§y x0 ∈ C b§t ký. Do f (x0 , .) nûa li¶n töc d÷îi v f (x0 , x0 ) = 0, n¶n tçn t¤i µ sao cho f (x0 , v) ≥ µ, ∀v ∈ B(x0 , 1) ∩ C, trong â B(x0 , 1) kþ hi»u qu£ c¦u âng t¥m x0 , b¡n k½nh b¬ng 1. Ta s³ ch¿ ra f tho£ m¢n i·u ki»n bùc (C1). 1 Thªt vªy, vîi b§t ký x ∈ C\B(x0 , 1), th¼ λ = < 1. kx0 − xk Vªy v = λx + (1 − λ)x0 ∈ C ∩ B(x0 , 1). Theo t½nh lçi cõa f (x0 , .) ta câ f (x0 , v) ≤ λf (x0 , x) + (1 − λ)f (x0 , x0 ) = λf (x0 , x). 1 V¼ λ = , n¶n tø ¥y suy ra x − x . Tø ¥y v ¡p 0 0 f (x , x) ≥ µ kx0 − xk döng t½nh ch§t ìn i»u m¤nh (vîi h» sè β ) cõa f , ta câ 2 f (x, x0 ) ≤ − f (x0 , x) − β x − x0 2 ≤ − µ x0 − x − β x − x0 = − x0 − x µ + β x0 − x . Do â, n¸u x0 − x > −µ/β , th¼ 2 f (x, x0 ) ≤ −µ x0 − x − β x − x0 < 0. B¥y gií l§y tªp compact U := C ∩ B(x0 , ε) vîi ε > max {1, −µ/β}, ta s³ câ f (x, x0 ) < 0 khi x ∈ C\U . Vªy t½nh bùc cõa f ÷ñc tho£ m¢n. Theo M»nh · 1.4, b i to¡n EP(C, f ) câ nghi»m. T½nh duy nh§t nghi»m ÷ñc suy ra tø ph¦n (i) do t½nh ìn i»u m¤nh k²o theo ìn i»u ch°t. M»nh · ¢ ÷ñc chùng minh. 2 B i to¡n c¥n b¬ng EP(C, f ) câ mèi li¶n h» ch°t ch³ vîi b i to¡n sau, ÷ñc gåi l b i to¡n èi ng¨u cõa EP(C, f ). T¼m y ∗ ∈ C : f (x, y ∗ ) ≤ 0, ∀x ∈ C. (DEP ) Ta kþ hi»u tªp nghi»m cõa b i to¡n èi ng¨u l DS . Mèi quan h» giúa hai b i to¡n n y ÷ñc thº hi»n ð m»nh · d÷îi ¥y. M»nh · 1.6. Gi£ sû f : C × C → R ∪ {+∞} l song h m c¥n b¬ng. Khi â: (i) N¸u f (x, .) l lçi tr¶n C vîi måi x ∈ C th¼ tªp nghi»m DS lçi;