Luận văn Thạc sĩ Toán học: Nguyên lý ánh xạ co và phương pháp điểm gần kề cho bài toán bất đẳng thức biến phân đa trị đơn điệu

Chia sẻ: Quỳnh Quỳnh | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

323
lượt xem 70
download

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

Luận văn Thạc sĩ Toán học: Nguyên lý ánh xạ co và phương pháp điểm gần kề cho bài toán bất đẳng thức biến phân đa trị đơn điệu trình bày sự kết hợp giữa nguyên lý ánh xạ co và phương pháp điểm gần kề cho bài toán bất đẳng thức biến phân đa trị đơn điệu qua 3 chương. Mời bạn đọc cùng 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: Nguyên lý ánh xạ co và phương pháp điểm gần kề cho bài toán bất đẳng thức biến phân đa trị đơn điệu

VI N KHOA H C VÀ CÔNG NGH VI T NAM VI N TOÁN H C Đ NG XUÂN SƠN NGUYÊN LÝ ÁNH X CO VÀ PHƯƠNG PHÁP ĐI M G N K CHO BÀI TOÁN B T Đ NG TH C BI N PHÂN ĐA TR ĐƠN ĐI U 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 HÀ N I - NĂM 2010
i M cl c M cl c i L i c m ơn iii M đ u 1 1 Bài toán b t đ ng th c bi n phân đa tr 3 1.1 M t s khái ni m và tính ch t cơ b n . . . . . . . . . . . . . 3 1.1.1 T p l i và hàm l i . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Dư i vi phân . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Ánh x đa tr . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Bài toán b t đ ng th c bi n phân đa tr . . . . . . . . . . . . 11 1.3.1 B t đ ng th c bi n phân đa tr và các bài toán liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.2 S t n t i nghi m c a bài toán b t đ ng th c bi n phân đa tr . . . . . . . . . . . . . . . . . . . . . . . . . 15 2 Phương pháp l p gi i bài toán b t đ ng th c bi n phân đơn đi u m nh 17 2.1 Tính co c a ánh x nghi m . . . . . . . . . . . . . . . . . . . 18 2.2 Mô t thu t toán và s h i t . . . . . . . . . . . . . . . . . 24 3 K t h p nguyên lý ánh x co và thu t toán đi m g n k gi i bài toán b t đ ng th c bi n phân đa tr đơn đi u 28 3.1 Thu t toán đi m g n k . . . . . . . . . . . . . . . . . . . . . 28 3.1.1 Sơ b v phương pháp đi m g n k . . . . . . . . . . . 28
ii 3.1.2 Áp d ng thu t toán đi m g n k gi i bài toán b t đ ng th c bi n phân đa tr . . . . . . . . . . . . . . . 31 3.2 K t h p nguyên lý ánh x co và thu t toán đi m g n k . . 32 3.2.1 Sơ b v phương pháp . . . . . . . . . . . . . . . . . . 32 3.2.2 Mô t thu t toán . . . . . . . . . . . . . . . . . . . . . 34 K t lu n chung 39 Tài li u tham kh o 40
iii L i c m ơn Trong su t quá trình làm Lu n văn, tôi luôn nh n đư c s hư ng d n và giúp đ c a GS. Lê Dũng Mưu (Vi n Toán h c Vi t Nam). Tôi xin chân thành bày t lòng bi t ơn sâu s c đ n th y. Tôi xin c m ơn quý th y, cô gi ng d y l p cao h c khóa 16 (2008 - 2010) đã mang đ n cho tôi nhi u ki n th c b ích trong khoa h c và cu c s ng. Tôi xin chân thành c m ơn Ban giám hi u, các b n đ ng nghi p trư ng THPT Chuyên Tr n Phú đã t o đi u ki n t t nh t đ tôi hoàn thành Lu n văn này. M c dù đã có nhi u c g ng nhưng Lu n văn khó tránh kh i nh ng thi u sót. Tác gi mong nh n đư c nh ng ý ki n đóng góp c a quý th y, cô và b n đ c đ Lu n văn đư c hoàn thi n hơn. Xin trân tr ng c m ơn! Hà N i, tháng 7 năm 2011. Ngư i vi t Lu n văn Đ ng Xuân Sơn
1 M đ u Bài toán b t đ ng th c bi n phân đư c n y sinh trong quá trình nghiên c u và gi i các bài toán th c t như các bài toán cân b ng trong kinh t , tài chính, phương trình v t lý toán, giao thông đô th , lí thuy t trò chơi, bài toán cân b ng m ng và nhi u bài toán khác. Bài toán b t đ ng th c bi n phân đư c gi i thi u b i Hartman và Stampacchia vào năm 1966. Nh ng nghiên c u đ u tiên v bài toán này liên quan t i vi c gi i các bài toán đi u khi n t i ưu và các bài toán biên c a phương trình đ o hàm riêng. Bài toán b t đ ng th c 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 Applications" c a Kinderlehrer D. và Stampacchia G., xu t b n năm 1980 và trong cu n sách "Variational and Quasivariational Inequalities: Application to Free Boundary Problems" c a Baiocci C. và Capelo A., xu t b n năm 1984. T đó, bài toán b t đ ng th c bi n phân đã có nh ng bư c phát tri n r t m nh và thu hút đư c s quan tâm c a nhi u nhà nghiên c u. 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. Có r t nhi u phương pháp gi i, trong đó có phương pháp d a vào cách ti p c n đi m b t đ ng. Ý tư ng chính c a phương pháp này là chuy n vi c gi i b t đ ng th c bi n phân v bài toán tìm đi m b t đ ng c a m t ánh x thích h p. M t trong nh ng cách ti p c n đi m b t đ ng là d a trên phương pháp l p c a nguyên lý ánh x co. Thu t toán thu c lo i này khá hi u qu v i vi c gi i bài toán c l n và trong nhi u trư ng h p cho phép đánh giá đư c t c đ h i t . Cách ti p c n đi m b t đ ng không ch làm vi c v i không gian h u h n chi u mà
2 còn đư c s d ng trong không gian Hilbert. Lu n văn này trình bày s k t h p gi a nguyên lý ánh x co và phương pháp đi m g n k đ gi i bài toán b t đ ng th c bi n phân đa tr đơn đi u. Lu n văn bao g m 3 chương: Chương 1 nh c l i các ki n th c cơ b n c a ánh x đa tr , ánh x đa tr n a liên t c, ánh x đa tr đơn đi u, kho ng cách Hausdorff, phát bi u bài toán b t đ ng th c bi n phân đa tr , các bài toán liên quan và m t s ví d th c t , đ ng th i trình bày đi u ki n có nghi m c a bài toán này. Chương 2 g m hai ph n chính. Ph n th nh t đ nh nghĩa ánh x nghi m và tính co c a nó. Ph n th hai trình bày nguyên lý ánh x co đ gi i bài toán b t đ ng th c bi n phân đa tr đơn đi u m nh, nêu thu t toán và ch ng minh s h i t c a thu t toán. Chương 3 là s k t h p nguyên lý ánh x co và phương pháp đi m g n k đ gi i bài toán b t đ ng th c bi n phân đơn đi u.
3 Chương 1 Bài toán b t đ ng th c bi n phân đa tr 1.1 M t s khái ni m và tính ch t cơ b n Trong Lu n văn này, chúng ta làm vi c trên không gian Hilbert th c H, v i tích vô hư ng đư c kí hi u là ., . và chu n tương ng đư c kí hi u là ||.||. Dư i đây, ta nh c l i m t s khái ni m và tính ch t cơ b n c a gi i tích l i như: T p l i, hàm l i, dư i vi phân, · · · Các ki n th c trong chương này đư c l y ch y u t các tài li u [1],[2],[3],[4]. 1.1.1 T p l i và hàm l i Đ nh nghĩa 1.1. M t t p C ⊆ H đư c g i là t p l i n u ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C. Đ nh nghĩa 1.2. M t t p C ⊆ H đư c g i là nón n u ∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C. • M t nón đư c g i là nón l i n u nó là nón và là m t t p l i. • T p C ⊆ H dư i đây luôn đư c gi thi t là m t t p l i (n u không gi i thích gì thêm). Đ nh nghĩa 1.3. Cho x ∈ C , nón pháp tuy n ngoài c a C t i x, kí hi u là NC (x), đư c xác đ nh b i công th c NC (x) := {w ∈ H| w, y − x ≤ 0, ∀y ∈ C}.
4 ¯ Đ nh nghĩa 1.4. Cho ánh x f : H → R. Khi đó, mi n h u hi u c a f , kí hi u là domf , đư c xác đ nh b i domf := {x ∈ H| f (x) < +∞}. Hàm f đư c g i là chính thư ng n u: domf = ∅ và f (x) > −∞, ∀x ∈ domf. Đ nh nghĩa 1.5. Cho hàm f : H → R ∪ {+∞}. Khi đó, hàm f đư c g i là: (i) l i n u f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ domf, λ ∈ [0, 1]; (ii) l i m nh v i h s β > 0 n u v i m i x, y ∈ domf, λ ∈ (0, 1), ta có f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − λ(1 − λ)β||x − y||2 . Đ nh lí 1.1. Gi s f là hàm s kh vi. Khi đó, f là hàm l i khi và ch khi f (y) − f (x) ≥ f (x), y − x , v i m i x, y ∈ domf. 1.1.2 Dư i vi phân ¯ Gi s f : H → R là hàm l i. Dư i vi phân c a hàm f đư c đ nh nghĩa như sau: Đ nh nghĩa 1.6. (xem[1]) Véc tơ w ∈ H đư c g i là dư i đ o hàm c a f t i x0 ∈ H n u w, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ H. • T p h p t t c các dư i đ o hàm c a hàm f t i x0 đư c g i là dư i vi phân c a f t i x0 , kí hi u ∂f (x0 ), t c là ∂f (x0 ) := {w ∈ H : w, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ H}. • Hàm f đư c g i là kh dư i vi phân t i x0 n u ∂f (x0 ) = ∅. Ví d 1.1. Cho C là m t t p l i, khác r ng c a không gian H. Xét hàm ch trên t p C có d ng 0 n u x ∈ C, δC (x) := +∞ n u x ∈ C. /
5 Khi đó, ∂δC (x0 ) = NC (x0 ), ∀x0 ∈ C. Th t v y, n u x0 ∈ C thì δC (x0 ) = 0 và ∂δC (x0 ) = {w ∈ H : δC (x) ≥ w, x − x0 , ∀x ∈ C}. Hay ∂δC (x0 ) = {w ∈ H : 0 ≥ w, x − x0 , ∀x ∈ C} = NC (x0 ). 2 Ví d 1.2. (Hàm l i thu n nh t dương) Cho f : Rn → R là hàm l i thu n nh t dương, t c là hàm l i f : Rn → R th a mãn f (λx) = λf (x), ∀λ > 0, ∀x ∈ Rn . Khi đó, ∂f (x0 ) = {w ∈ Rn | w, x0 = f (x0 ), w, x ≤ f (x), ∀x ∈ C}. Ch ng minh. N u w ∈ ∂f (x0 ) thì w, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ C. (1.1) Thay x = 2x0 vào (1.1), ta có w, x0 ≤ f (2x0 ) − f (x0 ) = f (x0 ). (1.2) Còn n u thay x = 0 vào (1.1), ta đư c − w, x0 ≤ −f (x0 ). (1.3) K t h p (1.2) và (1.3), suy ra w, x0 = f (x0 ). Hơn n a w, x − x0 = w, x − w, x0 = w, x − f (x0 ). Do đó, w, x ≤ f (x), ∀x ∈ C.
6 • Ngư c l i, n u x0 ∈ Rn th a mãn: w, x0 = f (x0 ) và w, x ≤ f (x), ∀x ∈ C thì w, x − x0 = w, x − w, x0 ≤ f (x) − f (x0 ), ∀x ∈ C. V y nên w ∈ ∂f (x0 ). 2 • N u f là hàm l i thu n nh t dương th a mãn: f (−x) = f (x) ≥ 0, ∀x ∈ C , thì w, x ≤ f (x) ∀x ∈ C , tương đương v i | w, x | ≤ f (x), ∀x ∈ C. Đ nh lí 1.2. (xem [5]) Cho fi , i = 1, · · · , m là các hàm l i, chính thư ng trên H. Khi đó, v i m i x ∈ H thì m m ∂( fi (x)) ⊇ ∂fi (x). i=1 i=1 • N u t n t i m t đi m a ∈ ∩n domfi mà t i đi m đó m i hàm fi (có i=1 th tr ra m t hàm nào đó) là liên t c, thì bao hàm th c trên s x y ra d u b ng v i m i x ∈ H. Đ nh lí 1.3. (xem [5]) Gi s C là t p l i, khác r ng. Hàm f : C → R là hàm l i, kh dư i vi phân trên C . Khi đó, x∗ là nghi m c a bài toán min{f (x)/x ∈ C} khi và ch khi 0 ∈ ∂f (x∗ ) + NC (x∗ ). 1.2 Ánh x đa tr Trong m c này, ta nh c l i m t s khái ni m cơ b n c a ánh x đa tr và đưa ra m t s ví d minh h a. Đ nh nghĩa 1.7. Cho X, Y là hai t p con b t kì c a H và F : X → 2Y là ánh x t X vào t p h p toàn b các t p con c a Y. Khi đó, ta nói F là ánh x đa tr t X vào Y , t c là, v i m i x ∈ X, F (x) là t p con c a Y . (F (x) có th là t p r ng). • N u v i m i x ∈ X , t p F (x) ch có đúng m t ph n t thì ta nói F là ánh x đơn tr t X vào Y .
7 Ví d 1.3. Xét phương trình đa th c: xn + a1 xn−1 + · · · + an−1 x + an = 0, trong đó: ai ∈ R. Qui t c cho tương ng m i đi m a = (a1 , a2 , · · · , an ) ∈ Rn v i t p nghi m c a phương trình trên, kí hi u là F (a) cho ta m t ánh x đa tr F : Rn → C. Đ nh nghĩa 1.8. Đ th và mi n h u hi u c a ánh x F : X → Y đư c đ nh nghĩa tương ng b ng các công th c sau: gphF : = {(x, y) ∈ X × Y | y ∈ F (x)}, domF : = {x ∈ X| F (x) = ∅}. • V i F là ánh x đa tr trong Ví d 1.3, ta có gphF= {(a, x) ∈ Rn × C/xn + a1 xn−1 + · · · + an−1 x + an = 0}. • Ánh x ngư c F −1 : Y → X c a ánh x đa tr F : X → Y đư c xác đ nh b i công th c F −1 (y) = {x ∈ X : y ∈ Y ∩ F (x)}. Đ nh nghĩa 1.9. Ánh x đa tr F : H → 2H , đư c g i là: (i) N a liên t c trên t i x ∈ domF n u v i m i t p m V ch a F (¯), t n t i ¯ x lân c n m U c a x sao cho ¯ F (x) ⊆ V, ∀x ∈ U ; (ii) N a liên t c dư i t i x ∈ domF n u v i m i t p m V th a mãn F (¯) ∩ ¯ x V = ∅, t n t i lân c n m U c a x sao cho ¯ F (x) ∩ V = ∅, ∀x ∈ U ∩ domF. • Ánh x F đư c g i là n a liên t c trên (n a liên t c dư i) trên C n u nó n a liên t c trên (n a liên t c dư i) t i m i đi m thu c C . • Ta nói F là liên t c t i x ∈ C n u F đ ng th i là n a liên t c trên và ¯ n a liên t c dư i t i x. N u F liên t c t i m i đi m thu c C , thì F đư c ¯ g i là liên t c trên C . Ví d 1.4. Cho ánh x đa tr F : R → 2R th a mãn:  {0} n u x < 0, F (x) = [−1, 1] n u x = 0, {1} n u x > 0. 
8 Khi đó, ánh x F là n a liên t c trên trên R nhưng không n a liên t c dư i t i x = 0. ¯ Th t v y, d th y ánh x F n a liên t c trên t i m i đi m x = 0. Hơn n a, F n a liên t c trên t i x = 0, vì v i m i t p m (a, b) ⊃ [−1, 1] = F (0), ¯ t n t i lân c n c a 0, ch ng h n (−1, 1), ta có  {0} n u − 1 < x < 0, F (x) = [−1, 1] n u x = 0, {1} n u 0 < x < 1.  Do đó, F (x) ⊆ (a, b) v i m i x ∈ (−1, 1). V y F là ánh x n a liên t c trên trên R . 2 Ví d 1.5. Cho ánh x đa tr F : R → 2R th a mãn [0, 1] n u x = 0, F (x) = {0} n u x = 0. Khi đó, F n a liên t c dư i t i x = 0. ¯ Th t v y, v i m i t p m (a, b) th a mãn (a, b) ∩ F (0) = {0} = ∅, 1 t n t i lân c n c a 0, ch ng h n U = (− 2 , 1 ). Ta có 2 [0, 1] 1 n u x ∈ (− 2 , 1 )\{0}, 2 F (x) = {0} n u x = 0. Do đó 1 1 F (x) ∩ (a, b) = 0, ∀x ∈ (− , ). 2 2 V y F n a liên t c dư i t i x = 0. ¯ 2 Đ nh nghĩa 1.10. M t ánh x F : H → 2H đư c g i là đóng t i x, n u v i m i dãy xk → x, m i dãy y k ∈ F (xk ) và y k → y , thì y ∈ F (x). • Ánh x F đư c g i là đóng trên C n u nó đóng t i m i đi m thu c C . • Ánh x F đư c g i là ánh x giá tr l i n u F (x) là t p l i v i m i x ∈ domF . M nh đ dư i đây cho ta m i quan h gi a tính n a liên t c trên và ánh x đóng.
9 M nh đ 1.1. Gi s F : C → 2H là ánh x đa tr , U là t p con l i c a C . (i) N u F là n a liên t c trên trên U , có giá tr đóng thì nó đóng trên U ; (ii) N u F đóng và v i m i t p compact X ⊆ U , t p F (X) là compact thì F là n a liên t c trên trên U . Ta bi t r ng ánh x liên t c Lipschitz là m t khái ni m có vai trò quan tr ng trong gi i tích toán h c. Trong m c này, ta s đ nh nghĩa tính liên t c Lipschitz c a m t ánh x đa tr d a trên kho ng cách Hausdorff như sau: Đ nh nghĩa 1.11. (Kho ng cách Hausdorff) Gi s A, B là hai t p con đóng và khác r ng b t kì c a H. Kho ng cách Hausdorff gi a hai t p A và B đư c xác đ nh b i ρ(A, B) := max{d(A, B), d(B, A)}, trong đó d(A, B) = sup inf ||a − b||, a∈A b∈B d(B, A) = sup inf ||a − b||. b∈B a∈A Đ nh nghĩa 1.12. (Ánh x đa tr liên t c Lipschitz) Cho C ⊆ H. Ánh x đa tr F : C → 2H đư c g i là liên t c Lipschitz v i h ng s L > 0 (vi t t t là L-Lipschitz) trên C , n u ρ(F (x), F (y)) ≤ L||x − y||, ∀x, y ∈ C. • N u L < 1 thì ta nói F là ánh x co trên C . • N u L = 1 thì ta nói F là ánh x không giãn trên C . 2 Ví d 1.6. Cho C = {(x, 0) ∈ R2 | 0 ≤ x ≤ 1} và ánh x F : C → 2R th a mãn F (x, 0) := {(x, y) ∈ R2 | 0 ≤ y ≤ x2 }. √ Khi đó, F là ánh x đa tr liên t c Lipschitz, v i h ng s L = 5.
10 Th t v y, v i m i (x1 , 0), (x2 , 0) ∈ C (x1 < x2 ) thì d(F (x1 , 0), F (x2 , 0)) = max min ||(x1 , y1 ) − (x2 , y2 )|| (x1 ,y1 )∈F (x1 ,0) (x2 ,y2 )∈F (x2 ,0) = max min (x1 − x2 )2 + (y1 − y2 )2 (x1 ,y1 )∈F (x1 ,0) (x2 ,y2 )∈F (x2 ,0) = max |x1 − x2 | (x1 ,y1 )∈F (x1 ,0) = |x1 − x2 | = ||(x1 , 0) − (x2 , 0)||. d(F (x2 , 0), F (x1 , 0)) = max min ||(x1 , y1 ) − (x2 , y2 )|| (x2 ,y2 )∈F (x2 ,0) (x1 ,y1 )∈F (x1 ,0) = max min (x1 − x2 )2 + (y1 − y2 )2 (x2 ,y2 )∈F (x2 ,0) (x1 ,y1 )∈F (x1 ,0) ≤ max min |x1 − x2 | 1 + (x1 + x2 )2 (x2 ,y2 )∈F (x2 ,0) (x1 ,y1 )∈F (x1 ,0) √ ≤ max 5|x1 − x2 | (x2 ,y1 )∈F (x1 ,0) √ = 5|x1 − x2 | √ = 5||(x1 , 0) − (x2 , 0)||. Do đó √ ρ(F (x1 , 0), F (x2 , 0)) ≤ 5||(x1 , 0) − (x2 , 0)||, ∀(x1 , 0), (x2 , 0) ∈ C √ hay F là ánh x đa tr liên t c Lipschitz, v i h ng s L = 5. 2 Đ nh nghĩa 1.13. V i C ⊆ H, ánh x đa tr F : C → 2H , đư c g i là: (i) đơn đi u m nh trên C v i h ng s β > 0, n u w − w , x − x ≥ β||x − x ||2 , ∀x, x ∈ C, w ∈ F (x), w ∈ F (x ); (ii) đơn đi u ng t trên C , n u w − w , x − x > 0, ∀x, x ∈ C, w ∈ F (x), w ∈ F (x ), x = x ; (iii) đơn đi u trên C , n u w − w , x − x ≥ 0, ∀x, x ∈ C, w ∈ F (x), w ∈ F (x ); (iv) gi đơn đi u trên C , n u v i m i x, x ∈ C, w ∈ F (x), w ∈ F (x ), ta có w ,x − x ≥ 0 kéo theo w, x − x ≥ 0.
11 Ví d 1.7. (Tính đơn đi u c a dư i vi phân c a hàm l i) ¯ V i m i hàm l i, chính thư ng f : H → R thì ánh x đa tr ∂f : H → 2H là đơn đi u trên dom(∂f ). Ch ng minh. Gi s f là hàm l i, v i m i x, x ∈ dom(∂f ), w ∈ ∂f (x) và w ∈ ∂f (x ), ta có: w , x − x ≤ f (x) − f (x ); w, x − x ≤ f (x ) − f (x) v i các giá tr f (x) và f (x ) h u h n. C ng hai b t đ ng th c trên ta đư c w , x − x + w, x − x ≤ 0 hay w − w , x − x ≥ 0, ∀x, x ∈ dom(∂f ), w ∈ ∂f (x), w ∈ ∂f (x ). V y ∂f đơn đi u. 2 1.3 Bài toán b t đ ng th c bi n phân đa tr 1.3.1 B t đ ng th c bi n phân đa tr và các bài toán liên quan Cho C là m t t p l i, đóng, khác r ng trong H và F : C → 2H là m t ánh x đa tr . Khi đó bài toán b t đ ng th c bi n phân đa tr đư c phát bi u như sau: Tìm x∗ ∈ C và w∗ ∈ F (x∗ ) sao cho (M V I) w∗ , x − x∗ ≥ 0, ∀x ∈ C. • F đư c g i là ánh x giá c a bài toán b t đ ng th c bi n phân (M V I ). • Khi F là ánh x đơn tr thì bài toán b t đ ng th c bi n phân (vi t t t (V I )) có d ng: Tìm x∗ ∈ C sao cho F (x∗ ), x − x∗ ≥ 0, ∀x ∈ C. • Bài toán b t đ ng th c bi n phân (M V I ) có liên h m t thi t v i nhi u bài toán khác như: Bài toán bù phi tuy n, bài toán đi m b t đ ng, bài toán quy ho ch l i, · · · Bài toán đi m b t đ ng Kakutani
12 Cho C là t p l i, đóng tùy ý trong H và T là ánh x đa tr t C vào 2C . Bài toán đi m b t đ ng c a ánh x đa tr T đư c phát bi u như sau: Tìm x∗ ∈ C sao cho x∗ ∈ T (x∗ ). (1.4) Đ c bi t, 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 Brower có d ng: Tìm x∗ ∈ C sao cho x∗ = T (x∗ ). M nh đ sau cho ta th y m i liên h gi a bài toán (M V I ) v i bài toán đi m b t đ ng (1.4). M nh đ 1.2. Gi s ánh x F đư c xác đ nh b i F (x) := x − T (x), ∀x ∈ C. Khi đó, bài toán b t đ ng th c bi n phân đa tr (M V I ) tương đương v i bài toán đi m b t đ ng (1.4). Ch ng minh . Gi s x∗ là nghi m c a bài toán (M V I ) và F (x) = x − T (x), t c là w∗ , x − x∗ ≥ 0, ∀x ∈ C, w∗ ∈ F (x∗ ). Do w∗ ∈ F (x∗ ) = x∗ − T (x∗ ) nên t n t i ξ ∗ ∈ T (x∗ ) sao cho w∗ = x∗ − ξ ∗ . Ta có x∗ − ξ ∗ , x − x∗ ≥ 0, ∀x ∈ C. Cho x = ξ ∗ ta đư c ||x∗ − ξ ∗ || ≤ 0. Suy ra x∗ = ξ ∗ hay x∗ ∈ T (x∗ ). V y nên x∗ là nghi m c a bài toán (1.4). Chi u ngư c l i hi n nhiên đúng. 2 Đ nh lí 1.4. (xem [5]). Cho C ⊆ H là t p l i compact và F : C → 2C là ánh x n a liên t c trên, F (x) khác r ng, l i, compact, v i m i x ∈ C . Khi đó, t n t i x∗ ∈ C sao cho x∗ ∈ F (x∗ ). Bài toán bù phi tuy n
13 Chú ý r ng khi C là m t nón l i trong H thì bài toán (M V I ) tr thành bài toán bù: Tìm x∗ ∈ C, w∗ ∈ F (x∗ ), w∗ ∈ C sao cho w∗ , x∗ = 0, (CP ) trong đó C := {y ∈ H | x, y ≥ 0, ∀x ∈ C} là nón đ i ng u c a C . Khi đó, ta có m nh đ sau: M nh đ 1.3. N u C là m t nón l i, đóng trong H thì bài toán bù (CP ) tương đương v i bài toán b t đ ng th c bi n phân (M V I ). Ch ng minh. N u x∗ là nghi m c a bài toán b t đ ng th c bi n phân (M V I ) và w∗ ∈ F (x∗ ) thì w∗ , x − x∗ ≥ 0, ∀x ∈ C. (1.5) Do C là nón l i, x∗ ∈ C nên x∗ + x ∈ C, ∀x ∈ C. Trong b t đ ng th c trên, thay x b i x∗ + x ta đư c w∗ , x∗ + x − x∗ = w∗ , x ≥ 0, ∀x ∈ C. Suy ra w∗ thu c nón đ i nh u C . Còn n u thay x = 0 vào (1.5), ta đư c w∗ , x∗ ≤ 0. Suy ra w∗ , x∗ = 0, hay x∗ ∈ C, w∗ ∈ F (x∗ ), w∗ ∈ C là nghi m c a bài toán bù (CP ). Ngư c l i, n u x∗ ∈ C là nghi m c a bài toán bù thì w∗ , x∗ = 0, w∗ ∈ F (x∗ ), w∗ ∈ C . Vì w∗ ∈ C nên w∗ , x ≥ 0, ∀x ∈ C . Ta có w∗ , x − x∗ ≥ 0, ∀x ∈ C,
14 hay x∗ ∈ C, w∗ ∈ F (x∗ ) là nghi m c a bài toán (M V I ). 2 Bài toán quy ho ch l i Cho C là t p l i, đóng, khác r ng trong H và f : C → R ∪ {+∞} là m t hàm l i trên C . Bài toán quy ho ch l i đư c phát bi u như sau: Tìm x∗ ∈ C sao cho f (x∗ ) = min{f (x) | x ∈ C}. (1.6) Trong trư ng h p f là hàm l i, kh vi, ta có m nh đ sau: M nh đ 1.4. Gi s f : C → R là hàm kh vi, l i trên t p l i C ⊂ H. Khi đó, x∗ ∈ C là nghi m c a bài toán (1.6) khi và ch khi x∗ là nghi m c a bài toán b t đ ng th c bi n phân (V I ), v i F (x) := f (x). Ch ng minh. Gi s x∗ là nghi m c a bài toán (1.6), t c là: f (x∗ ) ≤ f (x), ∀x ∈ C. N u x∗ không là nghi m c a bài toán (V I ) thì t n t i x ∈ C sao cho: f (x∗ ), x − x∗ < 0. Khi đó, l y α > 0 đ nh , do C là t p l i nên yα = x∗ + α(x − x∗ ) = αx + (1 − α)x∗ ∈ C và f (yα ) = f (x∗ ) + α f (x∗ ), x − x∗ + θ(α) < f (x∗ ), t c là x∗ không là nghi m c a bài toán (1.6). Đi u này trái v i gi thi t. V y x∗ là nghi m c a bài toán (V I ). Ngư c l i, n u x∗ là nghi m c a bài toán (V I ), t c là: f (x∗ ), x − x∗ ≥ 0, ∀x ∈ C. Do f là hàm l i, kh vi nên f (x) − f (x∗ ) ≥ f (x∗ ), x − x∗ , ∀x ∈ C. Suy ra f (x) ≥ f (x∗ ), ∀x ∈ C,
15 hay x∗ là nghi m c a bài toán (1.6). 2 Trong trư ng h p f là hàm không kh vi thì ta có cách ti p c n d a trên m nh đ sau: M nh đ 1.5. (xem [2], Đ nh lý 3.5) Cho C là m t t p l i, đóng, khác r ng c a không gian Hilbert H. Hàm f : C → R là hàm l i, kh dư i vi phân trên C . Khi đó, x∗ là nghi m c a bài toán (1.6) khi và ch khi x∗ là nghi m c a bài toán b t đ ng th c bi n phân (M V I ), v i F (x) := ∂f (x). Ch ng minh. Gi s x∗ ∈ C và w∗ ∈ ∂f (x∗ ) th a mãn w∗ , x − x∗ ≥ 0, ∀x ∈ C. Vì w∗ ∈ ∂f (x∗ ) nên w∗ , x − x∗ ≤ f (x) − f (x∗ ), ∀x ∈ C. T đó suy ra f (x∗ ) ≤ f (x), ∀x ∈ C. hay x∗ là nghi m c a bài toán (1.6). Ngư c l i hi n nhiên đúng (s d ng Đ nh lí 1.3). 2 Dư i đây ta xét ví d th c t c a bài toán b t đ ng th c bi n phân. Ví d 1.8. Bài toán xác đ nh phương án s n xu t. G i C là t p các phương án s n xu t ch p nh n đư c và x = (x1 , x2 , · · · , xn ) ∈ Rn , đư c g i là vectơ s lư ng s n ph m, v i xi là s s n ph m th i. • Đ t F (x) là t p các chi phí s n xu t ng v i phương án x. Bài toán đ t ra là hãy tìm m t phương án ch p nh n đư c sao cho ng v i phương án y có m t chi phí là th p nh t. Bài toán này có th đư c mô t dư i d ng bài toán b t đ ng th c bi n phân đa tr sau: Tìm x∗ ∈ C sao cho t n t i w∗ ∈ F (x∗ ) : w∗ , x − x∗ ≥ 0. 1.3.2 S t n t i nghi m c a bài toán b t đ ng th c bi n phân đa tr . S t n t i nghi m c a bài toán (M V I ) ph thu c vào hàm giá F và mi n ràng bu c C . Đ nh lí sau đây kh ng đ nh s t n t i nghi m c a bài toán (M V I ).
16 Đ nh lí 1.5. (xem [6]) Cho C là m t t p l i, đóng, khác r ng c a không gian H và F : C → 2H là ánh x n a liên t c trên y u, F (x) là t p l i, compact y u v i m i x ∈ C . Gi s r ng m t trong các đi u ki n sau đư c th a mãn: (i) C là t p b ch n, (ii) T n t i m t t p con U khác r ng, đóng và b ch n c a C sao cho v i m i x ∈ C\U , t n t i y ∈ U th a mãn w, x − y > 0, ∀w ∈ F (x). Khi đó, bài toán (M V I ) có nghi m. M nh đ sau ch ra tính ch t nghi m c a bài toán (M V I ). M nh đ 1.6. (xem [6]) Cho C là m t t p l i, đóng, khác r ng c a không gian H và F : C → 2H là ánh x đa tr . Khi đó: (i) N u F đơn đi u ng t trên C thì bài toán (M V I ) có nhi u nh t m t nghi m. (ii) N u F là đơn đi u m nh, n a liên t c trên y u và F (x) l i, compact y u, khác r ng v i m i x ∈ C thì bài toán (M V I ) có duy nh t nghi m. K t lu n chương Trong chương 1, chúng ta đã nh c l i các k t qu quan tr ng c a gi i tích l i, m i quan h gi a bài toán b t đ ng th c bi n phân đa tr v i các mô hình toán h c khác. Đ ng th i, chương này cũng trình bày các khái ni m v ánh x đa tr n a liên t c, đơn đi u m nh, đơn đi u và các đi u ki n t n t i nghi m c a bài toán (M V I ).