Tài liệu Về toán tử tựa không giãn với bài toán bất đẳng thức biến phân

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN XUÂN THÙY VỀ TOÁN TỬ TỰA-KHÔNG GIÃN VỚI BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội - 2017 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN NGUYỄN XUÂN THÙY VỀ TOÁN TỬ TỰA-KHÔNG GIÃN VỚI BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN Chuyên ngành: Toán giải tích Mã số: 60460102 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: GS. TSKH. LÊ DŨNG MƯU Hà Nội - 2017 LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học Khoa học Tự nhiên Đại học Quốc Gia Hà Nội dưới sự hướng dẫn của Thầy giáo GS. TSKH. Lê Dũng Mưu. Sự định hướng của Thầy trong nghiên cứu, sự tận tình của Thầy trong học tập và trên hết tình yêu thương Thầy dành cho em trong cuộc sống, đó là những thứ quý giá nhất mà em đã may mắn mới có được. Em xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất đến với Thầy. Em xin bày tỏ sự biết ơn chân thành đến Ban Giám hiệu trường Đại học Khoa học Tự nhiên - Đại học Quốc Gia Hà Nội, Khoa Sau đại học, Ban Chủ nhiệm Khoa Toán - Cơ - Tin học đã tạo cơ hội cho em được làm luận văn tốt nghiệp. Đặc biệt, em xin bày tỏ lòng biết ơn đến các Thầy, Cô giáo trong Khoa Toán - Cơ - Tin học, trường Đại học Khoa học Tự nhiên - Đại học Quốc Gia Hà Nội đã nhiệt tình giảng dạy em trong suốt các năm học vừa qua. Mặc dù đã rất cố gắng, song luận văn cũng không tránh khỏi những thiếu sót. Em mong được những ý kiến đóng góp từ các Thầy, Cô giáo và các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Hà Nội, ngày 09 tháng 10 năm 2017 Nguyễn Xuân Thùy 1 Mục lục LỜI CẢM ƠN 1 LỜI MỞ ĐẦU 3 1 KIẾN THỨC CHUẨN BỊ 6 1.1 Tập lồi, hàm lồi và nón pháp tuyến ngoài . . . . . . . . . . 6 1.2 Hàm nửa liên tục dưới . . . . . . . . . . . . . . . . . . . . 12 1.3 Hàm khả dưới vi phân . . . . . . . . . . . . . . . . . . . . 13 1.4 Tính đơn điệu và kiểu-Lipschitz cho các song hàm . . . . . 16 1.5 Toán tử chiếu và bất đẳng thức biến phân . . . . . . . . . . 18 1.6 Dãy hội tụ yếu, ánh xạ nửa-đóng và ánh xạ tựa-không giãn 22 2 ÁNH XẠ TỰA-KHÔNG GIÃN VỚI ĐIỀU KIỆN LIPSCHITZ VÀ BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN 26 2.1 Định nghĩa của ánh xạ tựa-không giãn trên một tập lồi . . . 26 2.2 Ánh xạ tựa-không giãn ΦF với bài toán V IP (C, F ) . . . . 27 3 VỀ ÁNH XẠ TỰA-KHÔNG GIÃN KHÔNG ĐIỀU KIỆN LIPSCHITZ 35 3.1 Định nghĩa của ánh xạ . . . . . . . . . . . . . . . . . . . . 35 3.2 Tính chất của ánh xạ . . . . . . . . . . . . . . . . . . . . . 36 KẾT LUẬN 46 Tài liệu tham khảo 47 2 LỜI MỞ ĐẦU Cho H là một không gian Hilbert thực với tích trong và chuẩn của nó lần lượt được ký hiệu bởi h·, ·i và k · k. Gọi C là một tập lồi, đóng và khác rỗng trong H. Một ánh xạ T : C −→ C được gọi là không giãn trên C , nếu kT (x) − T (y)k ≤ kx − yk với mọi x, y ∈ C . Ánh xạ T được gọi là tựa-không giãn ([1]) trên C nếu kT (x) − pk ≤ kx − pk với mọi x ∈ C và với mọi điểm bất động p của T bất cứ khi nào T có một điểm bất động. Rõ ràng, với mọi ánh xạ (toán tử) không giãn có một điểm bất động là tựa-không giãn, nhưng điều ngược lại không đúng. Các ánh xạ tựa-không giãn đã được nghiên cứu bởi nhiều tác giả và một số phương pháp nghiệm của một số bài toán có thể đưa về việc tìm một điểm bất động của các ánh xạ tựa-không giãn đã được phát triển trong tài liệu chuyên khảo [4] và các bài báo [1, 6, 8, 13, 16]. Nói chung, cách tiếp cận dựa trên điểm bất động của các ánh xạ không giãn và không giãn suy rộng được sử dụng rộng rãi trong nhiều lĩnh vực của toán học. Trong [5], Combettes và cộng sự đã giới thiệu một ánh xạ không giãn Pf , được gọi là toán tử xấp xỉ, xác định bởi, với mọi x ∈ H, 1 Pf (x) := {z ∈ C : f (z, y) + hy − z, z − xi ≥ 0 ∀y ∈ C}, r trong đó r > 0 và f : C × C −→ R. Với các giả thiết rằng f là đơn điệu, nửa liên tục dưới, lồi trên C đối với đối số thứ hai và nửa liên tục (hemicontinuous) trên C đối với đối số thứ nhất, họ đã chứng minh được rằng Pf là đơn trị, không giãn trên C . Hơn nữa, nhóm tác giả này cũng chỉ ra rằng tập điểm bất động của Pf trùng với tập nghiệm của bài toán cân bằng Tìm x∗ ∈ C : f (x∗ , y) ≥ 0 ∀y ∈ C. 3 EP (C, f ) MỤC LỤC Liên quan đến bài toán EP (C, f ), mặc dù nó có một công thức đơn giản, nhưng nó bao hàm rất nhiều bài toán như tối ưu hóa, điểm bất động Kakutani, mô hình cân bằng Nash và bất đẳng thức biến phân, được xem như là các trường hợp đặc biệt (xem trong [2, 3, 14]). Toán tử xấp xỉ Pf trở thành một công cụ hữu hiệu cho bất đẳng thức biến phân đơn điệu, bài toán cân bằng và một số chủ đề có liên quan. Tuy nhiên, nói chung đối với các song hàm giả đơn điệu, toán tử này không là không giãn, thậm chí các giá trị của nó có thể không lồi. Luận văn này nghiên cứu về ánh xạ tựa-không giãn với bài toán bất đẳng thức biến phân dựa trên bài báo [18]. Với nội dung nghiên cứu này, ngoài phần lời mở đầu, kết luận và tài liệu tham khảo, luận văn được chia thành 3 chương. Kết quả chính tập trung trong Chương 2 và Chương 3. Chương 1. Kiến thức chuẩn bị. Trong chương này, luận văn phần đầu trình bày những kiến thức cần thiết về giải tích lồi và giải tích hàm để sử dụng cho các chương tiếp theo như tập lồi, hàm lồi, hàm nửa liên tục dưới, hàm khả dưới vi phân, vv. . . Phần tiếp theo, luận văn trình bày các khái niệm về tính đơn điệu, kiểu-Lipschitz cho các song hàm, toán tử chiếu, bất đẳng thức biến phân, ánh xạ nửa-đóng và ánh xạ tựa-không giãn trong không gian Hilbert thực. Chương 2. Ánh xạ tựa-không giãn với điều kiện Lipschitz và bài toán bất đẳng thức biến phân. Trong chương này, ta sẽ định nghĩa một ánh xạ tựa-không giãn (được ký hiệu là ΦF ) với một ánh xạ thỏa mãn điều kiện Lipschitz. Sau đó, ta xét một trường hợp đặc biệt của ΦF xảy ra trong bất đẳng thức biến phân khi song hàm f (x, y) := hF (x), y − xi và ánh xạ ΦF được xác định bởi ΦF (x) = PC (x − λF (PC (x − λF (x)))). Qua đó, ta sẽ nghiên cứu một số tính chất liên quan đến tập điểm bất động của nó và tập nghiệm của bài toán bất đẳng thức biến phân. 4 MỤC LỤC Chương 3. Về ánh xạ tựa-không giãn không điều kiện Lipschitz. Trong chương này, chúng ta sẽ nghiên cứu ánh xạ tựa-không giãn LFω mà không đòi hỏi điều kiện Lipschitz đối với ánh xạ F . 5 Chương 1 KIẾN THỨC CHUẨN BỊ Trong chương này, luận văn sẽ trình bày một số khái niệm, định nghĩa và các kết quả cần thiết về giải tích lồi và giải tích hàm nhằm phục vụ cho Chương 2 và Chương 3. Tài liệu tham khảo chính cho chương này là [1], [5], [18], [22] và [23]. 1.1 Tập lồi, hàm lồi và nón pháp tuyến ngoài Trong phần này, ta ký hiệu Rn là không gian Euclide n-chiều trên trường số thực R. Mỗi véc tơ x ∈ Rn sẽ gồm n tọa độ là các số thực. Với hai véc tơ x = (x1 , . . . , xn )T và y = (y1 , . . . , yn )T thuộc Rn , ta nhắc lại rằng hx, yi := n X xk yk k=1 gọi là tích vô hướng của hai véc tơ x và y . Chuẩn Euclide của phần tử x và khoảng cách Euclide giữa hai phần tử x và y lần lượt được định nghĩa như sau: kxk := q hx, xi, d(x, y) := kx − yk. Ký hiệu R := [−∞, +∞] = R ∪ {−∞} ∪ {+∞} là tập số thực mở rộng. 6 Chương 1. KIẾN THỨC CHUẨN BỊ Một đường thẳng nối hai điểm (hai véc tơ) a, b trong Rn là tập hợp tất cả các véc tơ x ∈ Rn có dạng {x ∈ Rn : x = αa + βb, α, β ∈ R, α + β = 1}. Đoạn thẳng nối hai điểm a, b trong Rn là tập hợp tất cả các véc tơ x ∈ Rn có dạng {x ∈ Rn : x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}. Một tập C ⊆ Rn được gọi là một tập lồi, nếu C Định nghĩa 1.1.1 chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Nói khác đi, tập C là lồi nếu và chỉ nếu ∀x, y ∈ C, ∀λ ∈ [0, 1] =⇒ λx + (1 − λ)y ∈ C. Ta gọi x là tổ hợp lồi của các điểm (véc tơ) x1 , x2 , . . . , xk nếu x= k X λj x j với λj > 0; ∀j = 1, . . . , k; j=1 Ví dụ 1.1.2 k X λj = 1. j=1 Một số ví dụ về tập lồi. (1) Tập rỗng ∅ và Rn là các tập con lồi của Rn . (2) Tập Ω = {x ∈ Rn |kxk ≤ 1} là một tập lồi. Lớp các tập lồi là đóng với các phép giao, phép cộng đại số và phép nhân tích Descartes. Cụ thể, ta có mệnh đề sau: Mệnh đề 1.1.3 Cho A, B là các tập lồi trong Rn và C là tập lồi trong Rm . Khi đó, các tập sau là lồi: A ∩ B := {x|x ∈ A, x ∈ B}; αA + βB := {x|x = αa + βb, a ∈ A, b ∈ B; α, β ∈ R}; A × C := {x ∈ Rn+m |x = (a, c) : a ∈ A, c ∈ C}. 7 Chương 1. KIẾN THỨC CHUẨN BỊ Trong bất đẳng thức biến phân, tối ưu hoá, lý thuyết trò chơi và nhiều chuyên ngành toán ứng dụng khác, khái niệm về nón có một vai trò quan trọng. Cho C là một tập trong Rn . Định nghĩa 1.1.4 Tập C được gọi là nón nếu (1) ∀λ > 0, ∀x ∈ C =⇒ λx ∈ C. (2) Một nón C được gọi là nón lồi nếu C đồng thời là một tập lồi. (3) Một nón lồi được gọi là nón nhọn nếu nó không chứa đường thẳng. Khi đó, ta nói O là đỉnh của nón. Nếu nón lồi này lại là một tập lồi đa diện thì ta nói nó là nón lồi đa diện. Ví dụ 1.1.5 Một ví dụ điển hình của nón lồi đa diện, thường được sử dụng, là tập hợp nghiệm của hệ bất phương trình tuyến tính có dạng: {x|Ax ≥ 0}, với A là một ma trận thực cấp hữu hạn (số dòng và số cột là hữu hạn). Mệnh đề 1.1.6 Một tập C là nón lồi nếu và chỉ nếu nó có các tính chất sau: (1) λC ⊆ C, (2) C + C ⊆ C. với mọi λ > 0; Giả sử C là một nón lồi. Do C là một nón, nên ta có 1 (1). Từ C là một tập lồi, nên với mọi x, y ∈ C , thì (x + y) ∈ C . Vậy 2 theo (1) ta có x + y ∈ C . Chứng minh. Ngược lại, giả sử ta có (1) và (2). Từ (1) suy ra ngay C là một nón. Giả sử x, y ∈ C và λ ∈ [0, 1]. Từ (1) suy ra λx ∈ C và (1 − λ)y ∈ C . Theo (2) 8 Chương 1. KIẾN THỨC CHUẨN BỊ ta có λx + (1 − λ)y ∈ C . Vậy C là một nón lồi. Cho C ⊆ Rn là một tập lồi và x ∈ C . Khi đó, Định nghĩa 1.1.7 (1) Tập n o NC (x) := w|hw, y − xi ≤ 0, ∀y ∈ C được gọi là nón pháp tuyến ngoài của C tại x. (2) Tập n o −NC (x) := w|hw, y − xi ≥ 0, ∀y ∈ C được gọi là nón pháp tuyến trong của C tại x. Cho C ⊆ Rn , bao affine của C , ký hiệu là affC Định nghĩa 1.1.8 được xác định bởi n 1 m j affC = λ1 x + · · · + λm x |x ∈ C, m X o λj = 1 . j=1 Một điểm a ∈ C được gọi là điểm trong tương đối của C , nếu nó là điểm trong của C theo tô pô cảm sinh bởi affC và được ký hiệu là riC . Như vậy, ta có riC := {a ∈ C|∃B : (a + B) ∩ affC ⊂ C}, ở đây B là một lân cận mở của gốc. Cho C ⊆ Rn là một tập lồi và f : C −→ R. Ta ký hiệu tập n o domf := x ∈ C|f (x) < +∞ là miền hữu dụng của f . Tập n o epif := (x, µ) ∈ C × R|f (x) ≤ µ được gọi là trên đồ thị của hàm f . 9 Chương 1. KIẾN THỨC CHUẨN BỊ Bằng cách cho f (x) = +∞ nếu x ∈ / C , ta có thể xem f được xác định trên toàn không gian, và ta có n o n domf = x ∈ R |f (x) < +∞ , n o n epif = (x, µ) ∈ R × R|f (x) ≤ µ . Định nghĩa 1.1.9 Cho C ⊆ Rn là một tập lồi, khác rỗng và ánh xạ f : C −→ R. Ta nói f là hàm lồi trên C , nếu epif là một tập lồi trong Rn+1 . Trong trường hợp ta làm việc với hàm f : Rn −→ R ∪ {+∞}, thì định nghĩa trên tương đương với f là hàm lồi trên C nếu và chỉ nếu f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ∀x, y ∈ C, Ví dụ 1.1.10 (1) ∀λ ∈ [0, 1]. Các ví dụ về hàm lồi. Cho C 6= ∅ là một tập lồi. Đặt ( 0 khi x ∈ C, δC (x) := +∞ khi x ∈ / C. δC là một hàm lồi. Hàm này có tên là hàm chỉ. (2) Hàm khoảng cách đến tập lồi đóng C được định nghĩa bởi dC (x) := min kx − yk, y∈C là một hàm lồi. Định nghĩa 1.1.11 (1) Cho C ⊆ Rn là một tập lồi, khác rỗng. Khi đó, f : Rn −→ R ∪ {+∞} được gọi là hàm lồi chặt trên C , nếu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) ∀x, y ∈ C, (2) ∀λ ∈ (0, 1). f : Rn −→ R ∪ {+∞} được gọi là hàm lồi mạnh trên C với hệ số k > 0, nếu 1 f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − kλ(1 − λ)kx − yk2 , 2 với mọi x, y ∈ C và với mọi λ ∈ (0, 1). 10 Chương 1. KIẾN THỨC CHUẨN BỊ (3) f được gọi là hàm lõm trên C , nếu −f là hàm lồi trên C . Dưới đây là một điều kiện cần và đủ về hàm lồi, rất tiện ích trong nhiều trường hợp. Hàm f : C −→ R là lồi trên C nếu và chỉ nếu Mệnh đề 1.1.12 ∀x, y ∈ C , ∀λ ∈ [0, 1], ∀α > f (x) và ∀β > f (y), ta có f (λx + (1 − λ)y) ≤ λα + (1 − λ)β. Một lớp hàm lồi rất quan trọng mà ta sẽ xét ngay sau đây, đó là hàm lồi thuần nhất dương. Định nghĩa 1.1.13 Hàm f được gọi là thuần nhất dương (bậc 1) trên Rn nếu với mọi x ∈ Rn và với mọi λ > 0, ta có f (λx) = λf (x). Mệnh đề 1.1.14 Cho f là một hàm thuần nhất dương trên Rn . Khi đó, f là hàm lồi nếu và chỉ nếu f là dưới cộng tính theo nghĩa f (x + y) ≤ f (x) + f (y) với mọi x, y ∈ Rn . Một hàm thuần nhất dương và dưới cộng tính được gọi là dưới tuyến tính. Một ví dụ điển hình về hàm dưới tuyến tính là hàm chuẩn f (x) = kxk. Định nghĩa 1.1.15 Hàm f được gọi là chính thường nếu domf 6= ∅ và f (x) > −∞ ∀x ∈ C. Mệnh đề 1.1.16 Nếu f1 , f2 là các hàm lồi và chính thường thì f1 + f2 là hàm lồi. Hệ quả 1.1.17 Cho f1 , f2 , . . . , fm là các hàm lồi, chính thường và λ1 , λ2 , . . . , λm là các số dương. Khi đó, λ1 f1 + λ2 f2 + . . . + λm fm là hàm lồi. 11 Chương 1. KIẾN THỨC CHUẨN BỊ 1.2 Hàm nửa liên tục dưới Cho hàm f : Rn −→ R. Khi đó, Định nghĩa 1.2.1 f được gọi là nửa liên tục dưới đối với E tại một điểm x, nếu (1) với mọi dãy {xk } ⊂ E , xk −→ x ta có lim inf f (xk ) ≥ f (x). f được gọi là nửa liên tục trên đối với E tại x, nếu −f là nửa (2) liên tục dưới đối với E tại x. Hay là, với mọi dãy {xk } ⊂ E , xk −→ x thì lim sup f (xk ) ≤ f (x). (3) f được gọi là liên tục đối với E tại x, nếu nó vừa là nửa liên tục trên, vừa là nửa liên tục dưới đối với E tại x. (4) f được gọi là hàm nửa liên tục dưới đối với E trong tập A, nếu nó là nửa liên tục dưới đối với E tại mọi điểm thuộc A. Tương tự, ta cũng nói như vậy với hàm nửa liên tục trên và hàm liên tục. Khi f liên tục (nửa liên tục) tại một điểm x, đối với toàn không gian, thì ta nói đơn giản f liên tục (nửa liên tục) tại x. Cho hai hàm f và g xác định trên Rn , ta nói g là bao Định nghĩa 1.2.2 đóng của f , nếu epig = epif . Hàm f được gọi là đóng nếu epif = epif . Bao đóng của f được ký hiệu là f . Mệnh đề 1.2.3 Với mọi hàm f : Rn −→ R ∪ {+∞}, các khẳng định sau là tương đương: (1) Trên đồ thị của f là một tập đóng trên Rn+1 , nói cách khác f = f. (2) Với mọi số thực α, tập mức dưới Lf (α) := {x|f (x) ≤ α} là một tập đóng. 12 Chương 1. KIẾN THỨC CHUẨN BỊ (3) f là nửa liên tục dưới trên Rn . (1) =⇒ (2). Giả sử xj −→ x, f (xj ) ≤ α. Khi đó, Chứng minh. (xj , α) ∈ epif . Do epif đóng, nên (x, α) ∈ epif . Vậy x ∈ Lf (α). (2) =⇒ (3). Giả sử xj −→ x. Nếu lim inf f (xj ) < f (x), khi đó tồn tại α < f (x) sao cho f (xj ) ≤ α với mọi j đủ lớn. Vậy xj ∈ Lf (α) với mọi j đủ lớn. Do xj −→ x và Lf (α) đóng, nên x ∈ Lf (α). Tức là, f (x) ≤ α. Mâu thuẫn với điều ta đã giả sử là α < f (x). (3) =⇒ (1). Giả sử (xj , µj ) ∈ epif và (xj , µj ) −→ (x, µ). Khi đó, f (xj ) ≤ µj với mọi j . Từ (3), ta suy ra lim inf f (xj ) ≥ f (x). Do vậy, µ ≥ f (x) hay (x, µ) ∈ epif . Từ đó, ta có tập epif là đóng. Đến đây ta kết thúc chứng minh Mệnh đề 1.2.3. 1.3 Hàm khả dưới vi phân Định nghĩa 1.3.1 Cho f : Rn −→ R ∪ {+∞}. Ta nói x∗ ∈ Rn là dưới đạo hàm của f tại điểm x0 ∈ Rn nếu f (x) − f (x0 ) ≥ hx∗ , x − x0 i ∀x ∈ Rn . Tập hợp tất cả các dưới đạo hàm của f tại điểm x0 được gọi là dưới vi phân của f tại điểm đó và được ký hiệu là ∂f (x0 ), nghĩa là n o ∗ ∗ n ∂f (x0 ) = x |f (x) − f (x0 ) ≥ hx , x − x0 i ∀x ∈ R . Hàm f được gọi là khả dưới vi phân tại điểm x0 nếu ∂f (x0 ) 6= ∅. Ví dụ 1.3.2 Các ví dụ về dưới vi phân. 13 Chương 1. KIẾN THỨC CHUẨN BỊ Cho C 6= ∅ là một tập lồi trong Rn . Hàm chỉ ( 0 khi x ∈ C, δC (x) := +∞ khi x ∈ / C. (1) Nếu x0 ∈ C thì n o ∗ ∗ n ∂δC (x0 ) = x |δC (x) ≥ hx , x − x0 i ∀x ∈ R . Với x ∈ / C thì δC (x) = +∞. Do đó, δC (x) ≥ hx∗ , x − x0 i luôn đúng. Từ đó n ∗ o ∗ ∂δC (x0 ) = x |hx , x − x0 i ≤ 0 ∀x ∈ C = NC (x0 ). Tức là, dưới vi phân của hàm chỉ của tập C tại điểm x0 ∈ C chính là nón pháp tuyến ngoài của C tại điểm x0 . Hàm f (x) = kxk với mọi x ∈ Rn . (2) Tại điểm x = 0, hàm này không khả vi. Tuy nhiên, nó khả dưới vi phân và ta có ∂f (0) = {x∗ |hx∗ , xi ≤ kxk ∀x ∈ Rn }. Định nghĩa 1.3.3 Cho f : Rn −→ R, ta ký hiệu tập các điểm cực tiểu của hàm f trên C trong Rn là argminf (x) và x∈C ( argminf (x) := x∈C {x ∈ C|f (x) = inf x∈C f (x)} nếu inf x∈C f (x) 6= ∞ ∅ nếu inf x∈C f (x) = ∞. Hai định lý sau đây thể hiện đặc trưng liên quan giữa argmin và tính khả dưới vi phân của hàm lồi f . Định lý 1.3.4 Cho f là hàm lồi và khả dưới vi phân trên Rn . Khi đó, y ∈ argminf (x) x∈Rn 14 Chương 1. KIẾN THỨC CHUẨN BỊ nếu và chỉ nếu 0 ∈ ∂f (y). Chứng minh. Ta có 0 ∈ ∂f (y) = {y ∗ ∈ Rn |f (x) − f (y) ≥ hy ∗ , x − yi, ∀x ∈ Rn } ⇔ f (x) − f (y) ≥ 0, ∀x ∈ Rn ⇔ f (y) ≤ f (x), ∀x ∈ Rn ⇔ y ∈ argminf (x). x∈Rn Định lý 1.3.5 Cho C là một tập lồi, khác rỗng trong Rn . Giả sử rằng ri(domf ) ∩ riC 6= ∅. Khi đó, y ∈ argminf (x) x∈C nếu và chỉ nếu 0 ∈ ∂f (y) + NC (y), trong đó n n NC (y) := w ∈ R |hw, x − yi ≤ 0, ∀x ∈ C o là nón pháp tuyến ngoài của C tại y . Chứng minh. Ta xét hàm chỉ δC (·) của tập C . Khi đó, y là điểm cực tiểu của f trên C nếu và chỉ nếu nó là cực tiểu của hàm h(x) = f (x) + δC (x) trên toàn không gian. Theo định lý trên, điều kiện cần và đủ để y là điểm cực tiểu của h trên Rn là 0 ∈ ∂h(y). Hơn nữa, từ ri(domf ) ∩ riC 6= ∅, kết hợp với Định lý Moreau-Rockafellar (xem Mệnh đề 11.11 trong [22]), ta có ∂h(y) = ∂f (y) + ∂δC (y). 15 Chương 1. KIẾN THỨC CHUẨN BỊ Cuối cùng, do y ∈ C , nên ∂δC (y) = NC (y). Từ đó, ta có 0 ∈ ∂f (y) + NC (y). Định lý được chứng minh hoàn toàn. 1.4 Tính đơn điệu và kiểu-Lipschitz cho các song hàm Một song hàm f : C × C −→ R ∪ {+∞} Định nghĩa 1.4.1 ([5], [12]) được gọi là (1) β -đơn điệu mạnh trên C nếu tồn tại β > 0 sao cho f (x, y) + f (y, x) ≤ −βkx − yk2 ∀x, y ∈ C; (2) đơn điệu trên C nếu f (x, y) + f (y, x) ≤ 0 ∀x, y ∈ C; (3) giả đơn điệu trên C f (x, y) ≥ 0 =⇒ f (y, x) ≤ 0 ∀x, y ∈ C; (4) kiểu-Lipschitz (Lipschitz-type) trên C với các 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, z ∈ C. Các khái niệm về tính đơn điệu và kiểu-Lipschitz cho các song hàm chính là các suy rộng của khái niệm về tính đơn điệu và kiểu-Lipschitz cho các toán tử và chúng được định nghĩa như sau: Định nghĩa 1.4.2 ([18]) Một ánh xạ F : C −→ H được gọi là 16 Chương 1. KIẾN THỨC CHUẨN BỊ β -đơn điệu mạnh trên C nếu tồn tại β > 0 sao cho (1) hF (x) − F (y), x − yi ≥ βkx − yk2 ∀x, y ∈ C; đơn điệu trên C nếu (2) hF (x) − F (y), x − yi ≥ 0 ∀x, y ∈ C; giả đơn điệu trên C nếu (3) hF (x), y − xi ≥ 0 =⇒ hF (y), x − yi ≤ 0 ∀x, y ∈ C; L-Lipschitz liên tục trên C nếu tồn tại L > 0 sao cho (4) kF (x) − F (y)k ≤ Lkx − yk ∀x, y ∈ C. Nhận xét 1.4.3 Các khẳng định sau là đúng. Song hàm f (x, y) := hF (x), y − xi là β -đơn điệu mạnh (tương (1) ứng với đơn điệu, giả đơn điệu) trên C nếu và chỉ nếu F là β -đơn điệu mạnh (tương ứng với đơn điệu, giả đơn điệu) trên C . (2) Nếu F là L-Lipschitz liên tục trên C thì f (x, y) := hF (x), y − xi L là kiểu-Lipschitz trên C với các hằng số c1 = c2 = ([17]). 2 (3) Nếu f (x, y) := ϕ(y) − ϕ(x) thì f là kiểu-Lipschitz với mọi hàm ϕ. Ngoài ra, để sử dụng trong Chương 2 và Chương 3, ta cần đến định nghĩa sau đây: Định nghĩa 1.4.4 Cho f : C × C −→ R là một song hàm. Khi đó, f được gọi là liên tục yếu liên kết (jointly weakly continuous) ([18]) trên C × C , nếu với x, y ∈ C và các dãy {xn }, {yn } trong C lần lượt hội tụ yếu đến x và y thỏa mãn f (xn , yn ) −→ f (x, y) khi n −→ ∞. 17 Chương 1. KIẾN THỨC CHUẨN BỊ 1.5 Toán tử chiếu và bất đẳng thức biến phân Trong phần này, ta sẽ đề cập đến một vấn đề quan trọng trong giải tích lồi. Đó là phép chiếu metric (còn được gọi là phép chiếu Euclide) lên một tập lồi đóng. Bài toán tìm hình chiếu lên một tập lồi có vai trò rất quan trọng trong tối ưu và nhiều lĩnh vực khác như cân bằng, bất đẳng thức biến phân . . . Bài toán này có rất nhiều ứng dụng, đặc biệt nó xuất hiện như một bài toán phụ trong rất nhiều phương pháp số trong tối ưu, cân bằng và bất đẳng thức biến phân. Đây cũng là một công cụ sắc bén và khá đơn giản để chứng minh nhiều định lý quan trọng như định lý tách, các định lý về sự tồn tại nghiệm của nhiều vấn đề khác nhau trong toán học ứng dụng. Cụ thể hơn, trong phần này, trước hết ta sẽ chứng minh sự tồn tại và tính duy nhất của hình chiếu lên một tập lồi đóng. Tiếp đến, ta sẽ khảo sát một số tính chất cơ bản của toán tử chiếu. Cuối phần, sẽ trình bày việc sử dụng toán tử chiếu để chứng minh sự tồn tại nghiệm cũng như vai trò của toán tử này trong một thuật toán giải bất đẳng thức biến phân. Định nghĩa 1.5.1 Cho C 6= ∅ (không nhất thiết lồi) và y là một véc tơ bất kỳ. Đặt dC (y) := inf kx − yk. x∈C Ta nói dC (y) là khoảng cách từ y đến C . Nếu tồn tại π ∈ C sao cho dC (y) = kπ − yk, thì ta nói π là hình chiếu (vuông góc) của y trên C . Chú ý 1.5.2 Từ định nghĩa này, ta thấy rằng hình chiếu PC (y) của y trên C sẽ là nghiệm của bài toán tối ưu o n1 2 min kx − yk |x ∈ C . x 2 Do đó, việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực tiểu của hàm toàn phương kx − yk2 trên C . 18