Tài liệu Về sự tồn tại nghiệm của bài toán bất đẳng thức biến phân

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HÀ THỊ NGỌC BÍCH VỀ SỰ TỒN TẠI NGHIỆM CỦA BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN Chuyên ngành: Toán ứng dụng Mã số: 8460112 LUẬN VĂN THẠC SĨ TOÁN HỌC CÁN BỘ HƯỚNG DẪN KHOA HỌC TS. Nguyễn Song Hà THÁI NGUYÊN - 2020 i LỜI CẢM Ơ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 Tiến sĩ Nguyễn Song Hà. Tôi xin bày tỏ lòng kính trọng và sự biết ơn sâu sắc tới người thầy đã dành nhiều thời gian trực tiếp hướng dẫn cũng như giải đáp những thắc mắc của tôi trong suốt quá trình làm và hoàn thiện luận văn. Qua đây, tôi cũng xin được gửi lời cảm ơn tới các thầy cô giáo tại Trường Đại học Khoa học - Đại học Thái Nguyên đã tận tình giảng dạy và giúp đỡ tôi hoàn thành khóa học. Cuối cùng, xin gửi lời cảm ơn tới Ban giám hiệu, tập thể giáo viên trường THPT Nam Phù Cừ, nơi tôi đang công tác đã động viên và tạo điều kiện thuận lợi cho tôi trong thời gian tôi học tập và làm luận văn tốt nghiệp. Tác giả Hà Thị Ngọc Bích ii Mục lục Trang b¼a phö i Lời cảm ơn ii Mục lục iii Danh mục ký hiệu và chữ viết tắt iv Danh sách bảng v Mở đầu 1 Chương 1. Kiến thức chuẩn bị 1.1. Một số vấn đề về điểm bất động và phép chiếu mêtric . . . . . 2 2 1.2. Dưới vi phân hàm lồi . . . . . . . . . . . . . . . . . . . . . . . 1.3. Ánh xạ đơn điệu và liên tục . . . . . . . . . . . . . . . . . . . 1.4. Ánh xạ KKM . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 16 21 Chương 2. Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân trong Rn 24 2.1. Mô hình bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2. Sự tồn tại nghiệm trường hợp miền ràng buộc là tập compact 28 2.3. Sự tồn tại nghiệm trường hợp miền ràng buộc không compact 31 2.4. Một vài phương pháp xấp xỉ nghiệm bài toán (VIP) . . . . . . 40 Kết luận chung và đề nghị 51 Tài liệu tham khảo 52 iii Danh mục ký hiệu và chữ viết tắt Rn Không gian thực hữu hạn chiều co(C) Bao lồi của tập C cl(C) Bao đóng của tập C C\D Phần bù của tập hợp D trong C hx, yi Tích vô hướng của hai véctơ x và y kxk Chuẩn của véctơ x ∀x Với mọi x F :X→Y Ánh xạ đơn trị từ X vào Y F :X⇒Y Ánh xạ đa trị từ X vào Y PC (x) Phép chiếu mêtric phần tử x lên tập C α↓0 α giảm dần về 0 ∇f (x) Gradient của ánh xạ f tại x ∂f (x) Dưới vi phân của ánh xạ f tại x xn → x Dãy {xn } hội tụ đến x khi n → +∞ (VIP) Bài toán bất đẳng thức biến phân (MVIP) Bài toán bất đẳng thức biến phân Minty Fix(T ) Tập điểm bất động của ánh xạ T KKM Knaster-Kuratowski-Mazurkiewicz iv Danh sách bảng 2.1 2.2 2.3 2.4 2.5 Kết quả tính toán cho phương pháp (2.14) với ρ = 1/4 . . . . Kết quả tính toán cho phương pháp (2.14) tương ứng với các 43 giá trị ρ thay đổi . . . . . . . . . . . . . . . . . . . . . . Kết quả tính toán cho phương pháp (2.16) tương ứng với giá trị λ thay đổi . . . . . . . . . . . . . . . . . . . . . . Kết quả tính toán cho phương pháp (2.17) với τ = 1/4 . Kết quả tính toán cho phương pháp (2.17) tương ứng với giá trị τ thay đổi . . . . . . . . . . . . . . . . . . . . . . 43 . . . các . . . . . . các . . . 45 49 50 1 Mở đầu Bài toán bất đẳng thức biến phân được hình thành từ những công trình nghiên cứu của Lion, Stampacchia và Minty [1, 6] vào những năm 50 của thế kỉ trước. Bài toán này có liên hệ mật thiết với nhiều bài toán lí thuyết như: bài toán tối ưu, bài toán cân bằng, bài toán điểm bất động, bài toán minimax, bài toán điểm yên ngựa, phương trình với toán tử đơn điệu, bài toán biên có dạng của phương trình đạo hàm riêng ... và đóng vai trò rất quan trọng trong nghiên cứu nhiều lĩnh vực thực tiễn như: công nghệ thông tin và truyền thông, giao thông, kinh tế, y học, quân sự ... Vì lẽ đó, trong suốt hơn 70 mươi năm qua, bài toán này đã và đang thu hút được sự quan tâm nghiên cứu của nhiều nhà toán học trong và ngoài nước. Những nghiên cứu về bài toán này chủ yếu theo ba hướng chính: Một là, nghiên cứu các tính chất định tính của bài toán về sự tồn tại và tính duy nhất nghiệm, tính ổn định nghiệm, độ nhạy nghiệm hay tính chất tôpô của tập nghiệm. Hai là, nghiên cứu đề xuất các thuật toán hoặc phương pháp giải số hữu hiệu tìm nghiệm xấp xỉ của bài toán. Ba là, nghiên cứu ứng dụng lí thuyết bài toán này vào giải quyết các mô hình thực tiễn. Mục đích chính của luận văn này là nghiên cứu và trình bày lại có hệ thống về sự tồn tại nghiệm của bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều cùng một số phương pháp xấp xỉ nghiệm. Với mục tiêu như vậy, ngoài phần mở đầu, luận văn gồm có hai chương, kết luận và tài liệu tham khảo. Chương 1, hệ thống lại một số kiến thức cơ bản của giải tích lồi và giải tích hàm nhằm phục vụ cho việc trình bày các nội dung chính ở phần sau của luận văn. Chương 2, dành để giới thiệu lớp bài toán nghiên cứu cùng các kết quả tồn tại nghiệm được xây dựng trên tính chất loại đơn điệu của ánh xạ mục tiêu và cấu trúc tôpô của miền ràng buộc. Phần cuối chương, chúng tôi trình bày ba phương pháp chiếu (phương pháp chiếu gradient, phương pháp chiếu lai ghép và phương pháp chiếu tăng cường) tìm nghiệm xấp xỉ của bài toán cùng các ví dụ số minh họa cụ thể. 2 Chương 1 Kiến thức chuẩn bị Trong chương này, chúng tôi hệ thống lại một số kiến thức cơ bản phục vụ cho việc trình bày các nội dung chính ở phần sau của luận văn. Cấu trúc của chương được chia thành ba phần: Mục 1.1 chúng tôi trình bày một số nội dung cơ bản về lý thuyết điểm bất động và phép chiếu mêtric trên tập con lồi khác rỗng trong không gian hữu hạn chiều. Mục 1.2 trình bày một số khái niệm và tính chất cơ bản về dưới vi phân hàm lồi. Các khái niệm về ánh xạ loại đơn điệu và liên tục được cụ thể hóa trong Mục 1.3. Phần cuối chương, Mục 1.4 dùng để giới thiệu về lớp ánh xạ đa trị KKM và nguyên lí ánh xạ KKM. Đây là công cụ chính để chứng minh các kết quả tồn tại nghiệm trong Chương 2. 1.1. Một số vấn đề về điểm bất động và phép chiếu mêtric Giả sử Rn là không gian Euclide n chiều, tích vô hướng và chuẩn trên không gian này được kí hiệu lần lượt là h., .i và k.k. Tích vô hướng của hai véctơ x = (x1 , x2 , ..., xn ) ∈ Rn và y = (y1 , y2 , ..., yn ) ∈ Rn xác định bởi hx, yi = x1 y1 + x2 y2 + ... + xn yn và chuẩn của véctơ x = (x1 , x2 , ..., xn ) ∈ Rn p tương ứng sinh bởi tích vô hướng này là kxk = x21 + x22 + ... + x2n . Định nghĩa 1.1. Tập C ⊆ Rn được gọi là tập lồi nếu với mọi x, y ∈ C và với mọi λ ∈ [0, 1] ta có λx + (1 − λ)y ∈ C. Hay nói cách khác, tập C ⊆ Rn là tập lồi nếu nó chứa mọi đoạn thẳng nối hai điểm bất kì thuộc nó. Ví dụ 1.1. Trong không gian Rn , các tập hợp S = {x = (x1 , x2 , ..., xn ) ∈ Rn : kx − x0 k ≤ r}, Hα = {x = (x1 , x2 , ..., xn ) ∈ Rn : ha, xi ≤ α}, 3 ∆ = {x = (x1 , x2 , ..., xn ) ∈ Rn : hA, xi ≤ b}, trong đó x0 ∈ Rn , r là số thực dương, a ∈ Rn , α ∈ R, A là ma trận thực cỡ m × n và b ∈ Rm , tương ứng là hình cầu tâm x0 với bán kính r, nửa không gian đóng, hình đa diện. Các tập hợp này là các tập lồi. Ví dụ 1.2. Một số ví dụ đơn giản về tập hợp không là tập lồi trong không gian R2 và R3 là C1 = {x = (x1 , x2 ) ∈ R2 : x21 + x22 > 1}, C2 = {x = (x1 , x2 ) ∈ R2 : x1 x2 > 1}, C3 = {x = (x1 , x2 , x3 ) ∈ R3 : x3 = x21 + x22 }, C4 = {x = (x1 , x2 , x3 ) ∈ R3 : |x1 | + |x2 | + |x3 | = 1}. Một số tính chất cơ bản về tập lồi được phát biểu trong mệnh đề sau. Mệnh đề 1.1. Trong không gian Rn , ta có các khẳng định sau: (i) Giao của một họ tùy ý các tập lồi là tập lồi. (ii) Nếu C là tập lồi thì αC cũng là tập lồi với mọi số thực α. (iii) Tổng của hai tập lồi là tập lồi. (iv) Tích Descartes của hai tập lồi là tập lồi. (v) Ảnh và nghịch ảnh của một tập lồi qua một phép biến đổi tuyến tính là tập lồi. Chứng minh. (i) Giả sử {Ci }, i ∈ I là một họ tùy ý các tập lồi, ở đây I là tập \ chỉ số nào đó. Khi đó, với mọi x, y ∈ Ci và với mọi λ ∈ [0, 1] ta có: i∈I x, y ∈ Ci , ∀i ∈ I. Vì Ci là tập lồi nên λx + (1 − λ)y ∈ Ci , ∀i ∈ I. Từ đây suy ra λx + (1 − λ)y ∈ \ i∈I Ci . 4 Hay nói cách khác, \ Ci là tập lồi. i∈I (ii) Lấy tùy ý hai phần tử x, y ∈ αC và λ ∈ [0, 1]. Khi đó, x và y tương ứng có dạng x = αu và y = λv với u, v ∈ C. Do C lồi nên λu + (1 − λ)v ∈ C. Điều này dẫn đến λx + (1 − λ)y = λ(αu) + (1 − λ)(αv) = α[λu + (1 − λ)v] ∈ αC. Do đó, αC là tập lồi. (iii) Giả sử C và D là hai tập lồi. Lấy tùy ý hai phần tử x, y ∈ C + D và λ ∈ [0, 1]. Khi đó, x và y lần lượt có dạng x = u + v và y = w + z, trong đó u, w ∈ C và v, z ∈ D. Do C, D lồi nên λu+(1−λ)w ∈ C và λv +(1−λ)z ∈ D. Từ đó suy ra λx + (1 − λ)y = λ(u + v) + (1 − λ)(w + z) = [λu + (1 − λ)w] + [λv + (1 − λ)z] ∈ C + D. Vì vậy, C + D là tập lồi. (iv) Giả sử H và K là hai tập lồi. Lấy tùy ý hai phần tử x = (u, v) ∈ H × K, y = (w, z) ∈ H × K và λ ∈ [0, 1]. Từ tính lồi của H, K suy ra λu + (1 − λ)w ∈ H và λv + (1 − λ)z ∈ K. Mặt khác, để ý rằng λx + (1 − λ)y = (λu, λv) + ((1 − λ)w, (1 − λ)z) = (λu + (1 − λ)w, λv + (1 − λ)z) ∈ H × K. Vì thế, ta có H × K là tập lồi. (v) Giả sử f là một toán tử tuyến tính, C và D là các tập lồi. Khi đó, ∀x, y ∈ f (C), ∀λ ∈ [0, 1] ta có λx + (1 − λ)y = λf (u) + (1 − λ)f (v) = f (λu + (1 − λ)v), ở đây, u, v ∈ C và x = f (u), y = f (v) ∈ f (C). Vì C lồi nên λu + (1 − λ)v ∈ C và vì thế suy ra λx + (1 − λ)y ∈ f (C). Hay nói cách khác ảnh của C qua phép biến đổi f là tập lồi. Bây giờ, nếu x, y ∈ f −1 (D) thì f (x) ∈ D và f (y) ∈ D. Vì D lồi nên f (λx + (1 − λ)y) = λf (x) + (1 − λ)f (y) ∈ D. 5 Điều này dẫn đến λx + (1 − λ)y ∈ f −1 (D). Do đó, f −1 (D) là tập lồi. Định nghĩa 1.2. Véctơ x ∈ Rn được gọi là tổ hợp lồi của các véctơ xi ∈ Rn m X (i = 1, 2, · · · , m) nếu tồn tại λi ≥ 0 (i = 1, 2, · · · , m) với λi = 1 sao cho i=1 x= m X λi x i . i=1 Mệnh đề 1.2. Cho C ⊂ Rn là tập lồi và x1 , x2 , · · · , xm ∈ C. Khi đó, C chứa tất cả các tổ hợp lồi của x1 , x2 , · · · , xm . Chứng minh. Ta chứng minh quy nạp theo m. Trường hợp m = 2, ta có λ1 x1 + λ2 x2 ∈ C, vì C là tập lồi. Do đó, kết luận của mệnh đề là đúng trong trường hợp này. Giả sử khẳng định của mệnh đề đúng với m = k ≥ 2. Ta cần chứng minh k+1 X x= λi xi ∈ C. i=1 với λi ≥ 0, i = 1, 2, · · · , k + 1, k+1 X λi = 1. i=1 Thật vậy, nếu λk+1 = 1 thì λi = 0 với mọi 1 ≤ i ≤ k. Do đó, ta nhận được x = λk+1 xk+1 = xk+1 ∈ C. Bây giờ, giả sử λk+1 < 1. Khi đó, ta thấy 1 − λk+1 = λ1 + · · · + λk > 0, và k X i=1 λi ≥ 0, 1 − λk+1 λi = 1. 1 − λk+1 ∀i = 1, 2, · · · , k 6 Do đó, theo giả thiết quy nạp ta có y= k X i=1 Từ đây suy ra x = k+1 X λi x i ∈ C. 1 − λk+1 λi xi = (1 − λk+1 )y + λk+1 xk+1 ∈ C. Ta có điều cần i=1 chứng minh. Định nghĩa 1.3. Cho C ⊆ Rn . Giao của các tập con lồi chứa C được gọi là bao lồi của tập C và kí hiệu là co(C). Nhận xét 1.1. co(C) là một tập lồi (Mệnh đề 1.1) và đó là tập lồi nhỏ nhất chứa C. Nếu C là tập lồi thì co(C) = C. Hơn nữa, co(C) trùng với tập tất cả các tổ hợp lồi của C, tức là x ∈ co(C) khi và chỉ khi x biểu diễn được dưới dạng x= m X i=1 λi x i , λi ∈ [0, 1], m X λi = 1, xi ∈ C. i=1 Thật vậy, vì C ⊆ co(C) nên co(C) chứa tất cả các tổ hợp của C (Mệnh đề 1.2). Mặt khác, tập tất cả các tổ hợp lồi của C là lồi và chứa C nên nó chứa co(C). Định nghĩa 1.4. Tập con C ⊆ Rn được gọi là: (i) tập bị chặn nếu với mọi x ∈ C đều tồn tại số thực dương M sao cho kxk ≤ M . (ii) tập đóng nếu với mọi dãy {xn } ⊆ C, xn → x thì ta đều có x ∈ C. (iii) tập compact nếu với mọi dãy {xn } ⊆ C đều tồn tại một dãy con {xnk } thỏa mãn xnk → x và x ∈ C. Mệnh đề 1.3. [1, 2] Trong Rn , ta có các khẳng định sau: (i) Tập con đóng của một tập compact là tập comapct. (ii) Một tập là compact khi và chỉ khi tập đó đóng và bị chặn. Định nghĩa 1.5. Cho C là một tập con khác rỗng của Rn và F : C → C là một ánh xạ xác định trên C. Điểm x ∈ C được gọi là điểm bất động của 7 F nếu F (x) = x. Tập tất các điểm bất động của ánh xạ F được kí hiệu là Fix(F ), tức là Fix(F ) = {x ∈ C : F (x) = x}. Ví dụ 1.3. Cho C = [0, 1] ⊂ R. Nếu ánh xạ F xác định bởi F (x) = 1 − x thì F có duy nhất điểm bất động và Fix(F ) = {1/2}, nếu ánh xạ F xác định bởi F (x) = x2 thì F có hai điểm bất động và Fix(F ) = {0, 1}, nếu ánh xạ F xác định bởi F (x) = x thì F có vô số điểm bất động và Fix(F ) = [0, 1]. Tuy nhiên, nếu ánh xạ F xác định bởi   cos(x) nếu 0 ≤ x < 1 , 2 F (x) = 1  0 nếu ≤ x ≤ 1, 2 thì F không có điểm bất động. Ví dụ 1.4. Xét trường hợp tập C = R3 . Với mỗi x = (x1 , x2 , x3 ) ∈ C, khi đó ta có: x x x  2 3 1 3 3 , , thì F có duy Nếu ánh xạ F : R → R xác định bởi F (x) = 2 3 4 nhất điểm bất động và Fix(F ) = {(0, 0, 0)}. Nếu ánh xạ F : R3 → R3 xác định bởi F (x) = (−x3 , x42 , x1 ) thì F có hai điểm bất động và Fix(F ) = {(0, 0, 0), (0, 1, 0)}. Nếu ánh xạ F : R3 → R3 xác định bởi F (x) = (x1 , 1, x3 ) thì F có vô số điểm bất động và Fix(F ) = R × {1} × R. Nếu ánh xạ F : R3 → R3 xác định bởi F (x) = (x1 , x22 + 1, x43 + 1) thì F không có điểm bất động. Định nghĩa 1.6. Cho C là một tập con khác rỗng của Rn và F : C → Rn là một ánh xạ xác định trên C. Ánh xạ F được gọi là L-liên tục Lipschitz nếu tồn tại L ≥ 0 sao cho kF (x) − F (y)k ≤ Lkx − yk ∀x, y ∈ C. Bất đẳng thức trên đúng với 0 ≤ L < 1 thì F được gọi là ánh xạ co còn nếu L = 1 thì F được gọi là ánh xạ không giãn. 1 Ví dụ 1.5. Ánh xạ F : R → R xác định bởi F (x) = x (hoặc F (x) = cos(x)) 2 là ánh xạ co (tương ứng, là ánh xạ không giãn). 8 1 1 Ánh xạ F : R2 → R2 xác định bởi F (x) = Ax (hoặc F (x) = √ Ax) với 3 2 ! 1 1 A= là ánh xạ co (tương ứng, là ánh xạ không giãn). −1 1 Định lí 1.1. [6] (Nguyên lí ánh xạ co) Nếu ánh xạ F : Rn → Rn là ánh xạ co thì F có duy nhất điểm bất động. Nhận xét 1.2. Định lí trên nói chung là không còn đúng trong trường hợp F là ánh xạ không giãn. Chẳng hạn, tính duy nhất của điểm bất động không còn bảo đảm với ánh xạ F : Rn → Rn xác định bởi F (x) = x vì trong trường hợp này Fix(F ) = Rn . Ngoài ra, điều kiện ánh xạ co chỉ là điều kiện cần. Chẳng hạn, F : R → R xác định bởi F (x) = sin(x) là ánh xạ không giãn và F có duy nhất điểm bất động với Fix(F ) = {0}. Định lí 1.2. [6] (Brouwer) Cho F : S → S là một ánh xạ liên tục trên hình cầu đóng S ⊂ Rn . Khi đó, ánh xạ F có ít nhất một điểm bất động. Nhận xét 1.3. Nếu F là một ánh xạ liên tục trên hình cầu đóng S ⊂ Rn vào chính nó thì tập điểm bất động của F có thể không duy nhất. Chẳng hạn, xét hình cầu đóng S = {x ∈ R : |x| ≤ 1} và ánh xạ F : S → S xác định bởi  1 + 2x nếu − 1 ≤ x < 0, F (x) = 1 nếu 0 ≤ x ≤ 1. Khi đó, dễ thấy rằng F là ánh xạ liên tục trên S và Fix(F ) = {−1, 1}. Hơn nữa, điều kiện F liên tục chỉ là điều kiện cần. Thật vậy, ta xét ánh xạ F : S → S sau đây  0 nếu − 1 ≤ x < 1, F (x) = 1 nếu x = 1. Khi đó, dễ thấy rằng ánh xạ F không liên tục trên S nhưng Fix(F ) = {0, 1}. Định lí 1.3. [6] (Brouwer) Cho C là tập con lồi compact trong không gian Rn và F : C → C là ánh xạ liên tục. Khi đó, ánh xạ F có điểm bất động. 9 Định nghĩa 1.7. Cho C là tập con khác rỗng trong không gian Rn . Khi đó với mỗi x ∈ Rn , ánh xạ PC : Rn → C thỏa mãn điều kiện kx − PC (x)k = inf kx − zk. z∈C gọi là phép chiếu mêtric trên Rn và y = PC (x) được gọi là hình chiếu của x trên C. Sự tồn tại và tính duy nhất của phép chiếu mêtric được phát biểu trong mệnh đề dưới đây. Mệnh đề 1.4. [2] Cho C là tập con lồi đóng khác rỗng trong không gian Rn . Khi đó với mỗi x ∈ Rn tồn tại duy nhất một phần tử y ∈ C sao cho kx − yk = inf kx − zk. z∈C Chứng minh. Nếu x ∈ C thì chọn y = x. Nếu x ∈ / C, khi đó vì C đóng nên d := inf kx − zk > 0 và tồn tại một dãy {yn } ⊂ C sao cho z∈C kx − yn k → d. Để ý rằng kyn − ym k2 = k(x − yn ) − (x − ym )k2 = 2kx − yn k2 + 2kx − ym k2 − k2x − (yn + ym )k2 2 y + y n m 2 2 = 2kx − yn k + 2kx − ym k − 4 x − 2 ≤ 2kx − yn k2 + 2kx − ym k2 − 4d2 , (vì C là tập lồi nên ∀m, n ∈ N, yn + ym ∈ C). Cho m, n → ∞ trong bất đẳng thức trên 2 ta nhận được kyn − ym k → 0. Điều này suy ra {yn } là dãy Cauchy trong không gian đầy đủ Rn . Do đó, tồn tại giới hạn của dãy trên và giả sử rằng yn → y. 10 Vì C là tập đóng nên y ∈ C. Hơn nữa, ta lại có kx − yn k → kx − yk. Từ đó dẫn đến d = kx − yk. Cuối cùng, giả sử tồn tại z ∈ C thỏa mãn kx − zk = d. Khi đó, ta có ky − zk2 = k(x − y) − (x − z)k2 = 2kx − yk2 + 2kx − zk2 − k2x − (y + z)k2 2 y + z = 2kx − yk2 + 2kx − zk2 − 4 x − 2 ≤ 2d2 + 2d2 − 4d2 = 0. Điều này suy ra y = z hay y là phần tử xác định duy nhất. Dưới đây là một số ví dụ cụ thể về phép chiếu mêtric lên các nửa không gian đóng, hình cầu đóng trong không gian hữu hạn chiều. Ví dụ 1.6. [2] Giả sử C := {x ∈ Rn : hx, ui ≤ ζ} là nửa không gian đóng trong Rn với ζ ∈ R và u ∈ Rn là phần tử cố định. Khi ấy, ta có (i) Nếu u = 0 và ζ ≥ 0 thì C = Rn và PC = I. (ii) Nếu u = 0 và ζ < 0 thì C = ∅. (iii) Nếu u 6= 0 thì C 6= ∅ và với mọi x ∈ Rn ta có   x nếu hx, ui ≤ ζ, PC (x) = ζ − hx, ui  u nếu hx, ui > ζ. x + kuk2 Ví dụ 1.7. [2] Cho C := {x ∈ Rn : kx − x0 k ≤ r} là hình cầu đóng tâm x0 ∈ Rn và bán kính r > 0. Khi ấy, với mọi x ∈ Rn ta có   x nếu kx − x0 k ≤ r, PC (x) = x − x0  nếu kx − x0 k > r. x0 + r kx − x0 k Mệnh đề sau cho ta một đặc trưng hình học về phép chiếu mêtric. 11 Mệnh đề 1.5. [2] Cho C ⊆ Rn là tập con lồi đóng khác rỗng. Khi đó, y = PC (x) là hình chiếu của x trên C khi và chỉ khi y∈C: hy, z − yi ≥ hx, z − yi ∀z ∈ C. Chứng minh. Từ Mệnh đề 1.4, ta thấy y = PC (x) ⇔ kx − yk = inf kx − zk. z∈C Mặt khác, với mọi z ∈ C và λ ∈ (0, 1) ta có uλ = λz + (1 − λ)y ∈ C, (vì tính lồi của C) và vì thế ta nhận được y = PC (x) khi và chỉ kx − yk ≤ kx − uλ k, ∀z ∈ C, ∀λ ∈ (0, 1). Bất đẳng thức này tương đương với kx − yk2 ≤ kx − y + λ(y − z)k2 = kx − yk2 + λ2 ky − zk2 + 2λhx − y, y − zi, ∀z ∈ C, ∀λ ∈ (0, 1). hay λ ky − zk2 , 2 Từ đây suy ra y = PC (x) nếu và chỉ nếu hx − y, z − yi ≤ ∀z ∈ C, ∀λ ∈ (0, 1). hx − y, z − yi ≤ 0, ∀z ∈ C. Ta có điều cần chứng minh. Hệ quả 1.1. Cho C là tập con lồi đóng khác rỗng trong không gian Rn . Khi đó, phép chiếu mêtric PC là ánh xạ không giãn, tức là kPC (x) − PC (y)k ≤ kx − yk ∀x, y ∈ Rn . Chứng minh. Với mọi x, y ∈ Rn , từ Mệnh đề 1.5 ta có hPC (y) − PC (x), x − PC (x)i ≤ 0, và hPC (x) − PC (y), y − PC (y)i ≤ 0. 12 Cộng hai bất đẳng thức trên ta nhận được hPC (x) − PC (y), −(x − PC (x)) + (y − PC (y))i ≤ 0. Bất đẳng thức này suy ra kPC (x) − PC (y)k2 ≤ hPC (x) − PC (y), x − yi ≤ kPC (x) − PC (y)kkx − yk. Từ đây, ta có điều cần chứng minh. 1.2. Dưới vi phân hàm lồi Định nghĩa 1.8. Cho C ⊆ Rn là một tập con lồi và khác rỗng. Hàm số f : C → R được gọi là (i) hàm lồi trên 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). (ii) hàm lồi chặt trên C nếu với mọi x 6= y ∈ C và với mọi λ ∈ [0, 1] ta có f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y). Ví dụ 1.8. Xét C = Rn và hàm số f : Rn → R xác định bởi f (x) = kxk là một hàm lồi. Ví dụ 1.9. Xét C = R và hàm số f : R → R xác định bởi f (x) = x2 là một hàm lồi và cũng là hàm lồi chặt. Tuy nhiên, hàm số  0 nếu x < 0, f (x) = x nếu x ≥ 0. là một hàm lồi nhưng không là hàm lồi chặt. Định lí 1.4. [2] Cho C ⊆ Rn là tập lồi khác rỗng. Hàm f : C → R là hàm lồi khi và chỉ m X khi ∀λi ≥ 0 (i = 1, . . . , m), λi = 1 và ∀x1 , . . . , xm ∈ C ta có i=1 f (λ1 x1 + · · · + λm xm ) ≤ λ1 f (x1 ) + · · · + λm f (xm ). 13 Định nghĩa 1.9. Cho f : C → R là hàm xác định trên C ⊆ Rn . Khi đó, hàm f được gọi là (i) khả vi Gâteaux tại x ∈ C nếu tồn tại phiếm hàm tuyến tính liên tục x∗ trên C thỏa mãn lim α↓0 f (x + αy) − f (x) = hx∗ , yi, α ∀y ∈ C. Toán tử x∗ được gọi là đạo hàm Gâteaux của f tại x và thường được kí hiệu là fG0 (x) hoặc ∇f (x). (ii) khả vi Gâteaux nếu f khả vi Gâteaux tại mọi x ∈ C. (iii) khả vi Fréchet tại x ∈ C nếu tồn tại phiếm hàm tuyến tính liên tục x∗ trên C thỏa mãn |f (x + y) − f (x) − hx∗ , yi| = 0. lim kyk kyk→0 Toán tử x∗ được gọi là đạo hàm Fréchet của f tại x và thường được kí hiệu là fF0 (x) hoặc f 0 (x). (iv) khả vi Fréchet nếu f khả vi Fréchet tại mọi x ∈ C. Nhận xét 1.4. Nếu f : C → R khả vi Fréchet tại x ∈ C thì nó cũng khả vi Gâteaux. Thật vậy, điều cần chứng minh được suy ra trực tiếp từ mối liên hệ sau: |f (x + y) − f (x) − hx∗ , yi| =0 kyk kyk→0 |f (x + αz) − f (x) − αhx∗ , zi| ⇒ lim =0 α→0 αkzk    f (x + αz) − f (x)  ⇒ lim  − hx∗ , zi = 0, α→0 α lim ở đây, ta thay y = αz với α > 0 và z 6= 0 là phần tử cố định tùy ý trong C. Tuy nhiên, một hàm f : C → R khả vi Gâteaux tại x ∈ C thì nó có thể không khả vi Fréchet. Thật vậy, chẳng hạn ta xét hàm số f : R2 → R xác định bởi  3   uv f (u, v) = u4 + v 2  0 nếu (u, v) 6= (0, 0), nếu (u, v) = (0, 0). 14 Khi đó, hàm số trên khả vi Gâteaux tại 0 vì α4 u3 v 4 4 2 2 f (0 + αy) − f (0) = lim α u + α v = 0 = h0, yi, lim α↓0 α↓0 α α ∀y = (u, v) ∈ R2 . hay fG0 (0) = 0. Trong khi đó, f không khả vi Fréchet tại điểm này vì với y = (u, v) mà v = u2 , ta lại có    u5     4 4 1 |f (y)| u +u  . =√ = √ kyk u2 + u4 2 u2 + 1 Từ đó suy ra |f (0 + y) − f (0)| |f (y)| 1 = lim = 6= 0. kyk 2 kyk→0 kyk→0 kyk lim Định nghĩa 1.10. Cho f : C → R là hàm lồi trên C ⊆ Rn . (i) Phần tử x∗ ∈ Rn được gọi là dưới gradient của hàm f tại điểm x̄ ∈ E nếu f (x) − f (x̄) ≥ hx∗ , x − x̄i ∀x ∈ C. (ii) Tập tất cả các dưới gradient 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̄), tức là ∂f (x̄) = {x∗ ∈ Rn : f (x) − f (x̄) ≥ hx∗ , x − x̄i, ∀x ∈ C}. (iii) Hàm f được gọi là khả dưới vi phân tại x̄ nếu ∂f (x̄) 6= ∅. Ví dụ 1.10. Cho f : R → R xác định bởi f (x) =| x − a |. Khi đó, ta có dưới vi phân của hàm f là    {−1} nếu x < a,   ∂f (x) = {[−1, 1]} nếu x = a,    {1} nếu x > a. Mối liên hệ giữa dưới vi phân và tính khả vi Gâteaux (hoặc khả vi Frétchet) được phát biểu trong mệnh đề dưới đây. Mệnh đề 1.6. [2] Cho f : Rn → R là hàm lồi. Khi đó, ta có các khẳng định sau: 15 0 (i) Nếu f khả vi Gâteaux tại x ∈ Rn với fG (x) = x∗ và f khả dưới vi phân tại x thì ∂f (x) = {x∗ }. (ii) Nếu f là hàm liên tục tại x ∈ Rn và ∂f (x) chỉ gồm một phần tử duy nhất x∗ thì f khả vi Gâteaux tại x và 0 fG (x) = x∗ . 0 Chứng minh. (i) Giả sử f khả vi Gâteaux tại x ∈ Rn với fG (x) = x∗ . Ta có lim α↓0 f (x + αy) − f (x) = hx∗ , yi, α ∀y ∈ Rn . Mặt khác, từ tính lồi của f ta lại có f (x + λ(z − x)) ≤ λf (z) + (1 − λ)f (x), ∀λ ∈ (0, 1). Ta đặt y = z − x. Khi đó, ta nhận được f (x + λy) ≤ f (x) + λ(f (y + x) − f (x)), ∀λ ∈ (0, 1). Từ đó suy ra f (x + λy) − f (x) ≤ f (y + x) − f (x), λ ∀λ ∈ (0, 1). Điều này dẫn đến f (x) − f (y + x) ≤ −hx∗ , yi, hay tương đương với f (x) − f (y + x) ≤ hx∗ , x − (y + x)i, ∀y ∈ Rn . Vì thế, ta có x∗ ∈ ∂f (x). Mặt khác, nếu y ∗ ∈ ∂f (x) thì hy ∗ , yi = 1 ∗ f (x + λy) − f (x) hy , (x + λy) − xi ≤ , λ λ Cho λ → 0 ta được hy ∗ , yi ≤ hx∗ , yi, ∀y ∈ Rn , hy ∗ − x∗ , yi ≤ 0, ∀y ∈ Rn , hay ∀y ∈ Rn , ∀λ > 0.