Luận văn Thạc sĩ Toán học: Thuật toán tách cho bài toán cân bằng

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

Thêm vào BST

Báo xấu

23
lượt xem 7
download

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

Luận văn được trình bày theo hai chương: 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. Chương 2 - Trình bày thuật toán tách cho bài toán cân bằng. Mời các bạn tham khảo!

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: Thuật toán tách cho bài toán cân bằng

ĐẠ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. 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 p 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 ∈ H. Kho£ng c¡ch tø u ¸n C , k½ hi»u l dC (u), ÷ñc x¡c ành bði 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, v (∀y ∈ C)hu − p, y − pi ≤ 0 p = PC (u) ⇐⇒ p ∈ C . à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â τ (1 − τ ) f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − ||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 → R ∪ {+∞} ÷ñ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 x) ≤ lim f (xn ). xn → x¯ =⇒ f (¯ x) ≤ lim f (xn ).) (xn * x¯ ⇐⇒ f (¯ 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 f (x + αy) − f (x) lim α↓0 α 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). 0 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¤ 0 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 (∀y ∈ H)f (x; y) = hy, 5f (x)i. N¸u câ f (x + y) − f (x) − hy, 5f (x)i lim =0 06=y→0 ||y|| 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 n¸u x ∈ C , ( 0 ι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¤ T :C→H ÷ñc gåi l (i) ìn i»u m¤nh vîi h» sè β > 0 tr¶n C n¸u 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 vi ph¥n ÷íng ch²o cõa f t¤i x ∈ H, k½ hi»u l ∂2 f (x, x) l tªp: ∂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 ×C →R ÷ñc gåi l (i) ìn i»u m¤nh tr¶n C vîi h» sè β > 0 n¸u 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 . Do â, n¸u m > R−r r , th¼ i·u ki»n (ii) ÷ñc thäa m¢n vîi måi y ∈ C = 0 B(r) vîi ||y 0 || > m+1 R 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 x) ÷ñc gåi l gi¡ trà cüc tiºu cõa f tr¶n C , ta vi¸t f (¯ 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, y), ∀y ∈ C . iºm x¯ ÷ñc gåi l nghi»m cõa b i to¡n x¯ ∈ C : f (x, y) ≥ f (¯ 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 < 1, j = 1, . . . , N v N j=1 µj = 1. Khi â T l ¡nh x¤ khæng gi¢n v S tròng P 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â: N X 2 ||x − u|| = || µj Tj (x) − u||2 j=1 N X = || µj [Tj (x) − Tj (u)] ||2 j=1 N X X = µj || [Tj (x) − Tj (u)] ||2 − µj µk || [j (x) − Tk (x)] ||2 j=1 1≤j