Tài liệu Luận văn phương pháp xấp xỉ gắn kết cho bài toán cân bằng và bài toán điểm bất động

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ====== NGUYỄN THỊ THÚY MÙI PHƯƠNG PHÁP XẤP XỈ GẮN KẾT CHO BÀI TOÁN CÂN BẰNG VÀ BÀI TOÁN ĐIỂM BẤT ĐỘNG LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI, 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ====== NGUYỄN THỊ THÚY MÙI PHƯƠNG PHÁP XẤP XỈ GẮN KẾT CHO BÀI TOÁN CÂN BẰNG VÀ BÀI TOÁN ĐIỂM BẤT ĐỘNG Chuyên ngành: Toán Giải tích Mã số: 8 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: TS. Lê Quang Thủy HÀ NỘI, 2018 LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc tới TS Lê Quang Thuỷ. Thầy đã tận tình hướng dẫn và giải đáp những thắc mắc của tôi, giúp đỡ tôi hoàn thành luận văn này. Qua đây, tôi xin chân thành cảm ơn tới các thầy cô giáo phòng Sau đại học, các thầy cô giáo khoa Toán cũng như các thầy cô giáo giảng dạy lớp thạc sĩ K18 chuyên ngành Toán giải tích trường Đại học Sư phạm Hà Nội 2 đã giúp đỡ tôi trong suốt quá trình học tập. Tôi xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè, đồng nghiệp đã luôn quan tâm, động viên và tạo mọi điều kiện thuận lợi cho tôi trong quá trình học tập và hoàn thành luận văn. Mặc dù đã rất cố gắng, nhưng do điều kiện về thời gian và khả năng bản thân có hạn nên luận văn không thể tránh khỏi những thiếu sót. Vì vậy, tác giả rất mong nhận được sự đóng góp ý kiến của các thầy cô để luận văn được hoàn thiện hơn. Hà Nội, tháng 7 năm 2018 Nguyễn Thị Thuý Mù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. Số liệu và các kết quả nghiên cứu trong luận văn là hoàn toàn trung thực, được tham khảo từ các tài liệu chuyên khảo cùng các công trình khoa học đã được công bố tại các nhà xuất bản hoặc các tạp chí chuyên ngành có uy tín trong và ngoài nước. Hà Nội, tháng 7 năm 2018 Nguyễn Thị Thuý Mùi Mục lục 1 Một số kiến thức cơ bản và kết quả chuẩn bị 1.1 1 Một số kiến thức cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.3 Phép chiếu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Bài toán qui hoạch lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Dưới vi phân của hàm lồi . . . . . . . . . . . . . . . . . . . . . 6 1.2.3 Cực trị của hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Ánh xạ co . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Ánh xạ không giãn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 2 Bài toán cân bằng 2.1 16 Bài toán cân bằng và các trường hợp riêng . . . . . . . . . . . . . . . . 16 2.1.1 Bài toán cân bằng . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.2 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.3 Bài toán điểm bất động Kakutani . . . . . . . . . . . . . . . . . 17 2.1.4 Bài toán bù phi tuyến . . . . . . . . . . . . . . . . . . . . . . . 18 2.1.5 Bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . 19 2.1.6 Bài toán cân bằng Nash trong trò chơi không hợp tác . . . . . . 19 2.2 Sự tồn tại nghiệm của bài toán cân bằng . . . . . . . . . . . . . . . . . 21 2.3 Phương pháp bài toán cân bằng phụ . . . . . . . . . . . . . . . . . . . 26 2.3.1 Bài toán cân bằng phụ . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.2 Phương pháp bài toán cân bằng phụ . . . . . . . . . . . . . . . 29 3 Phương pháp xấp xỉ gắn kết cho bài toán cân bằng và bài toán điểm bất động 35 i 3.1 3.2 Phương pháp xấp xỉ gắn kết cho bài toán cân bằng và bài toán điểm bất động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.1 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.1.2 Định lý hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 ii MỞ ĐẦU 1. Lí do chọn đề tài Sự ra đời của Nguyên lý điểm bất động Brouwer (1912) và ánh xạ co Banach (1922) đã hình thành 2 hướng chính của lý thuyết điểm bất động: sự tồn tại điểm bất động của ánh xạ liên tục và sự tồn tại điểm bất động dạng co. Lý thuyết điểm bất động có nhiều ứng dụng như: chứng minh sự tồn tại nghiệm của phương trình vi phân và phương trình tích phân (định lý Picard và định lý Peano), chứng minh nguyên lý biến phân Ekeland, chứng minh sự tồn tại điểm cân bằng trong mô hình kinh tế, sự tồn tại nghiệm tối ưu của nhiều bài toán trong lý thuyết tối ưu. Nguyên lý ánh xạ co Banach (1922) là kết quả khởi đầu cho lý thuyết điểm bất động dạng co. Một trong những mở rộng tự nhiên và quan trọng của ánh xạ co là ánh xạ không giãn. Các nghiên cứu đầu tiên về ánh xạ không giãn được bắt đầu từ năm 1965 trong các công trình của Browder, Goebel, Kirk và được tiếp tục cho tới nay. Lý thuyết điểm bất động cho phép ta xây dựng thuật toán tìm nghiệm của nhiều bài toán khác nhau. Một trong những bài toán nhận được sự quan tâm nghiên cứu của nhiều nhà toán học trong và ngoài nước là bài toán tìm điểm chung của tập điểm bất động của ánh xạ không giãn và tập nghiệm bài toán cân bằng. Bài toán cân bằng lần đầu tiên được đưa ra vào năm 1955 bởi H. Nikaido, K. Isoda nhằm tổng quát hóa bài toán cân bằng Nash trong trò chơi không hợp tác. Đến năm 1972 bài toán này được xét đến dưới dạng một bất đẳng thức minimax bởi tác giả Ky Fan, người đã có nhiều đóng góp quan trọng cho bài toán, nên bài toán này còn được gọi là bất đẳng thức Ky Fan (Ky Fan inequality). Bài toán này còn được sử dụng để thiết lập điểm cân bằng trong lý thuyết trò chơi (Game theory), bởi thế nó còn có tên gọi khác là Bài toán cân bằng (Equilibrium problem) theo cách gọi của tác giả L. D. Muu, W. Oettli [7] năm 1992 và E. Blum, W. Oettli [3] năm 1994. iii Cho tới nay, một vấn đề nhận được sự quan tâm nghiên cứu của nhiều nhà toán học trong và ngoài nước là đề xuất các phương pháp, thuật toán giải cho bài toán tìm điểm chung của tập nghiệm bài toán cân bằng và tập điểm bất động của ánh xạ không giãn.Vì vậy, việc tìm hiểu các thuật toán đã có, cũng như xây dựng các thuật toán mới hữu hiệu cho việc giải bài toán này luôn là vấn đề cần được tiếp tục được quan tâm nghiên cứu, đây là lý do tôi nghiên cứu luận văn "Phương pháp xấp xỉ gắn kết cho bài toán cân bằng và bài toán điểm bất động". Ngoài phần mở đầu, kết luận và danh mục các tài liệu tham khảo, cấu trúc của luận văn gồm ba chương như sau: Chương 1 “Ánh xạ không giãn” trình bày về ánh xạ không giãn cùng một số kết quả về sự tồn tại điểm bất động của ánh xạ không giãn. Chương 2 “Bài toán cân bằng” trình bày bài toán cân bằng và một số kết quả về sự tồn tại nghiệm của bài toán cân bằng cùng phương pháp bài toán phụ cho bài toán cân bằng. Chương 3 “Phương pháp xấp xỉ gắn kết cho bài toán cân bằng và bài toán điểm bất động” trình bày một phương pháp xấp xỉ gắn kết cho bài toán tìm điểm chung của tập nghiệm bài toán cân bằng với song hàm cân bằng đơn điệu và tập điểm bất động của ánh xạ không giãn. 2. Mục đích nghiên cứu Mục đích của luận văn là giới thiệu về ánh xạ không giãn và bài toán cân bằng; một số kết quả về sự tồn tại nghiệm cùng phương pháp bài toán cân bằng phụ giải bài toán cân bằng và một phương pháp xấp xỉ gắn kết cho bài toán tìm điểm chung của tập nghiệm bài toán cân bằng và tập điểm bất động của ánh xạ không giãn. 3. Nhiệm vụ nghiên cứu Nghiên cứu một số kết quả về điểm bất động của ánh xạ không giãn, bài toán cân bằng và một phương pháp xấp xỉ gắn kết cho bài toán cân bằng và bài toán điểm bất động của ánh xạ không giãn. 4. Đối tượng và phạm vi nghiên cứu - Đối tượng nghiên cứu: Ánh xạ không giãn, bài toán cân bằng. iv - Phạm vi nghiên cứu: Một số kết quả về sự tồn tại điểm bất động của ánh xạ không giãn cũng như sự tồn tại nghiệm của bài toán cân bằng, và một phương pháp xấp xỉ gắn kết cho bài toán tìm điểm chung của tập nghiệm bài toán cân bằng và tập điểm bất động của ánh xạ không giãn trong không gian Hilbert. 5. Đóng góp mới của luận văn Luận văn là bài tổng quan về một phương pháp xấp xỉ gắn kết cho bài toán cân bằng và bài toán điểm bất động của ánh xạ không giãn trong không gian Hilbert. 6. Phương pháp nghiên cứu - Dịch, đọc và nghiên cứu tài liệu. - Tổng hợp, phân tích, sử dụng kiến thức của giải tích hàm, giải tích lồi và lý thuyết tối ưu nghiên cứu bài toán cân bằng và bài toán điểm bất động của ánh xạ không giãn. v Các kí hiệu và chữ viết tắt R Tập số thực ∅ Tập rỗng H Không gian Hillbert thực hx, yi Tích vô hướng của hai véc tơ x, y kxk Chuẩn của véc tơ x A∩B Giao của 2 tập A và B A∪B Hợp của 2 tập A và B A×B Tích Descartes của A và B A+B Tổng của hai tập A và B T :C→H Ánh xạ T từ tập C ⊂ H vào H F ix(T ) Tập các điểm bất động của ánh xạ T domf Miền xác định hữu hiệu của hàm f domf = {x ∈ C : f (x) < +∞} ∇f (x∗ ) Vecto Gradient của hàm f tại x∗ ∇2 f (x∗ ) Ma trận Hessen của hàm f tại x∗ (EP ) Bài toán cân bằng (AuxEP ) Bài toán cân bằng phụ Sol(C, f ) Tập nghiệm của bài toán cân bằng [a, b] Đoạn thẳng nối hai điểm a, b ∈ H, tức [a, b] = {x ∈ H : x = λa + (1 − λ)b, 0 ≤ λ ≤ 1} vi Chương 1 Một số kiến thức cơ bản và kết quả chuẩn bị Chương này trình bày một số khái niệm cơ bản của giải tích lồi như tập lồi, hàm lồi, phép chiếu, bài toán qui hoạch lồi,. . . Điểm bất động của ánh xạ không giãn cùng một số kết quả về sự tồn tại điểm bất động của ánh xạ không giãn cũng được đề cập trong nội dung của chương này. Nội dung của chương được tham khảo từ các tài liệu [1], [2], [5], [9]. 1.1 Một số kiến thức cơ bản 1.1.1 Không gian Hilbert Định nghĩa 1.1. X là không gian định chuẩn trên trường K tức là đối với mỗi x ∈ X xác định một số không âm kxk, gọi là chuẩn của x thoả mãn các điều kiện sau: • kxk ≥ 0 ∀x ∈ X; kxk = 0 ⇔ x = 0. • kλxk = |λ| kxk ∀λ ∈ K, ∀x ∈ X. • kx + yk ≤ kxk + kyk ∀x, y ∈ X. Định nghĩa 1.2. Không gian X được gọi là đầy đủ nếu mọi dãy Cauchy trong X đều là dãy hội tụ (tức là, nếu {xn }∞ n=1 là dãy Cauchy trong X thì tồn tại x0 ∈ X mà xn → x0 (n → ∞)). Định nghĩa 1.3. Nếu không gian tuyến tính định chuẩn (X, k.k) là không gian đầy đủ thì (X, k.k) được gọi là không gian Banach. 1 Định nghĩa 1.4. Không gian tuyến tính X xác định trên trường số thực được gọi là không gian tiền Hilbert nếu mọi x, y ∈ X, xác định một số hx, yi gọi là tích vô hướng của x và y thoả mãn các điều kiện • Xác định dương: hx, xi ≥ 0 với ∀x ∈ X; hx, xi = 0 ⇐⇒ x = 0. • Đối xứng: hx, yi = hy, xi với ∀x, y ∈ X. • Song hàm tuyến tính: hαx + βy, zi = αhx, zi + βhy, zi với ∀α, β ∈ R, ∀x, y, z ∈ X. Định nghĩa 1.5. (Không gian Hilbert) Không gian Hilbert là không gian tiền Hilbert đầy đủ. Định lý 1.1. (Bất đẳng thức Schwarz) Cho không gian Hilbert H, với bất kì x, y ∈ H ta có |hx, yi| ≤ kxk kyk . Chứng minh. Hiển nhiên, bất đẳng thức đúng với x = 0, hoặc y = 0. Với x 6= 0, y 6= 0, ta có htx + y, tx + yi ≥ 0 t ∈ R. Do đó kxk2 t2 + 2thx, yi + kyk2 ≥ 0 t ∈ R. Vì x 6= 0 nên kxk > 0. Suy ra (hx, yi)2 − kxk2 kyk2 ≤ 0. Do đó ta có điều phải chứng minh. Định lý 1.2. (Đẳng thức hình bình hành) Cho không gian Hilbert H, với bất kì x, y ∈ H ta có kx + yk2 + kx − yk2 = 2kxk2 + 2kyk2 Chứng minh. Với bất kì x, y ∈ H, ta có kx + yk2 = hx + y, x + yi = kxk2 + hx, yi + hy, xi + kyk2 , kx + yk2 = hx − y, x − yi = kxk2 − hx, yi − hy, xi + kyk2 . Cộng vế với vế hai đẳng thức trên ta được đẳng thức hình bình hành. 2 Định lý 1.3. Trong không gian Hilbert H, cho dãy {xn }. Giả sử lim xn = x0 . Khi n→∞ đó, với mọi y ∈ H, y 6= x0 , ta có lim inf kxn − x0 k < lim inf kxn − yk . n→∞ n→∞ Chứng minh. Theo đẳng thức hình bình hành ta có 2 2kxn − x0 k2 + 2kx0 − yk2 = kxn − yk2 + xn − x0 − (x0 − y)2 . Do đó 2kxn − x0 k2 + 2kx0 − yk2 = kxn − yk2 + kx0 − yk2 + kxn − x0 k2 − 2 hxn − x0 ; x0 − yi , hay kx0 − yk2 + 2 hxn − x0 ; x0 − yi = kxn − yk2 − kxn − x0 k2 = (kxn − yk − kxn − x0 k) (kxn − yk + kxn − x0 k) . Do xn → x0 nên tồn tại số nguyên dương n0 sao cho với mọi n ≥ n0 ta có kxn − yk2 − kxn − x0 k2 > 0. Đặt M = Sup {kxn − yk + kxn − x0 k}. Khi đó ta có n∈Y kxn − yk2 + 2 hxn − x0 ; x0 − yi ≤ M (kxn − yk − kxn − x0 k) ∀n ≥ n0 . Vì vậy, kxn − yk2 ≤ M (kxn − yk − kxn − x0 k) với mọi n ≥ n0 . Bất đẳng thức này kéo theo kx0 − yk2 ≤ M lim inf kxn − yk − M lim inf kxn − x0 k . n→∞ n→∞ Vì x0 6= y nên kx0 − yk > 0. Do đó lim inf kxn − x0 k < lim inf kxn − yk. n→∞ 1.1.2 n→∞ Tập lồi Cho hai điểm x, y ∈ H. Đoạn thẳng nối x và y là tập các điểm có dạng z = λx + (1 − λ)y = y + λ(x − y), 0 ≤ λ ≤ 1. 3 Đường thẳng qua x và y là tập các điểm có dạng z = λx + (1 − λ)y, λ ∈ R. Tập C ⊆ H được gọi là tập afin (Hay đa tạp afin) nếu C chứa trọn cả đường thẳng đi qua hai điểm bất kỳ của C, nghĩa là ∀x, y ∈ C, λ ∈ R : z = λx + (1 − λ)y ∈ C. Bao afin(afin hull) của C ⊆ H là giao của tất cả các tập afin chứ C và được kí hiệu là af f C. Đó là tập afin nhỏ nhất chứa C. Ví dụ bao afin của hình cầu  C = x ∈ R3 : kxk ≤ 1 là cả không gian R3 . Định nghĩa 1.6. Tập C ⊆ H được gọi là tập lồi (convex set) nếu C chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó, tức là λx + (1 − λ)y ∈ C ∀x, y ∈ C, 0 ≤ λ ≤ 1. Tập lồi đóng kín với phép giao, phép cộng, phép nhân với một số và phép lấy tổ hợp tuyến tính, tức nếu A và B là hai tập lồi trong H thì các tập sau cũng là tập lồi: A ∩ B = {x : x ∈ A, x ∈ B} ; αA + βB = {x : αa + βb, a ∈ A, b ∈ B} . 1.1.3 Phép chiếu Định nghĩa 1.7. Cho H không gian Hilbert thực với tích vô hướng h., .i và chuẩn k.k . Cho C là tập con lồi đóng trong H. Với mọi x ∈ H, tồn tại duy nhất phần tử x̄ ∈ C sao cho x̄ gần x nhất theo chuẩn k.k trong không gian H Phần tử x̄ gọi là hình chiếu của x lên C, kí hiệu PC (x). Khi đó ta gọi ánh xạ PC : H → C x 7→ x b = PC (x) là phép chiếu của x lên tập C. Với mỗi x ∈ H, ta gọi dC (x) = 12 kx − PC (x)k là khoảng cách từ x đến C. Dễ thấy nếu x ∈ C thì dC (x) = 0 và PC (x) = {x}. 4 Từ định nghĩa ta thấy hình chiếu PC (x) của x lên tập C chính là nghiệm duy nhất của bài toán tối ưu: 1 ky − xk2 : y ∈ C }. 2 Do đó, việc tìm hình chiếu PC (x) có thể đưa về việc tìm cực tiểu hàm toàn phương min{ trên tập lồi. Mệnh đề dưới đây chỉ ra một số tính chất cơ bản của phép chiếu. Mệnh đề 1.1. Cho C là một tập lồi đóng khác rỗng trong không gian Hilbert thực H. Khi đó các khẳng định sau là đúng. (i) Với mọi x ∈ H, x̄ = PC (x) tồn tại và duy nhất; (ii) Với mọi x ∈ H, x̄ = PC (x) khi và chỉ khi hy − x̄, x̄ − xi ≥ 0 ∀y ∈ C; (iii) PC là đồng bức (Co-Coercive), tức hPC (x) − PC (y), x − yi ≥ kPC (x) − PC (y)k2 ∀x, y ∈ H; (iv) PC là ánh xạ không giãn (Non-expansive), nghĩa là kPC (x) − PC (y)k ≤ kx − yk ∀x, y ∈ H; Do đó PC là hàm liên tục Lipschitz trên H; (v) kPC (x) − yk2 ≤ kx − yk2 − kPC (x) − xk2 ∀y ∈ C, ∀x ∈ H; (vi) kPC (x) − PC (y)k2 ≤ kx − yk2 − kPC (x) − x + y − PC (y)k2 ∀x, y ∈ H. 1.2 Bài toán qui hoạch lồi 1.2.1 Hàm lồi Định nghĩa 1.8. Cho C là tập lồi, khác rỗng trong không gian Rn và hàm số f : C → R ∪ {+∞}. Ta gọi f là (i) Hàm lồi (Convex function) trên C nếu mọi x1 , x2 ∈ C và với mọi t ∈ [0, 1] ta có f [(tx1 + (1 − t)x2 )] ≤ tf (x1 ) + (1 − t)f (x2 ); (ii) Hàm lồi chặt (Strictly convex function) trên C nếu ∀x1 , x2 ∈ C, x1 6= x2 và với mọi t ∈ (0, 1) ta có 5 f [(tx1 + (1 − t)x2 )] < tf (x1 ) + (1 − t)f (x2 ); (iii) Hàm lồi mạnh (Strongly convex function) trên C với hệ số η > 0, nếu với mọi x1 , x2 ∈ C và với mọi t ∈ (0, 1) ta có 1 f [(tx1 + (1 − t)x2 )] ≤ tf (x1 ) + (1 − t)f (x2 ) − ηt(1 − t)kx1 − x2 k2 ; 2 (iv) Hàm lõm (Concave function) trên C nếu −f là hàm lồi trên C; (v) Hàm lõm chặt (Strictly concave function) nếu −f là hàm lồi chặt trên C; (vi) Hàm lồi chính thường nếu f là hàm lồi, domf 6= ∅ và f (x) > −∞, ∀x. Các định lý sau đây cho ta điều kiện cần và đủ để nhận biết hàm lồi, lồi chặt. Định lý 1.4. Cho f là khả vi trên tập lồi mở C ⊆ Rn . Khi đó, f là hàm lồi trên C khi và chỉ khi f (y) − f (x) ≥ h∇f (x), y − xi ∀x, y ∈ C. Định lý 1.5. Cho f là hàm khả vi hai lần trên tập lồi mở C ⊆ Rn . Khi đó: i) Hàm f là hàm lồi trên C khi và chỉ khi ma trận Hesse ∇2 f (x∗ ) là nửa xác định dương trên C, nghĩa là với mỗi x ∈ C, ta có y T ∇2 f (x)y ≥ 0 ∀y ∈ Rn . ii) Hàm f là hàm lồi chặt trên C nếu ma trận Hesse ∇2 f (x) là xác định dương trên C, nghĩa là với mỗi x ∈ C, ta có y T ∇2 f (x)y > 0 ∀y ∈ Rn \ {0} . 1.2.2 Dưới vi phân của hàm lồi Cho hàm lồi chính thường f trên Rn . Véc tơ p được gọi là dưới gradient của f tại điểm x0 nếu hp, x − x0 i + f (x0 ) ≤ f (x) ∀x ∈ Rn . Tập tất cả các dưới gradient của hàm f tại điểm x0 được gọi là dưới vi phân của hàm f tại điểm x0 , kí hiệu ∂f (x0 ). Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂f (x0 ) 6= ∅. Tập ∂f (x0 ) thường chứa nhiều phần tử. Trong trường hợp hàm lồi f khả vi thì ∂f (x0 ) chứa duy nhất một phần tử. Định lý 1.6. Mọi hàm lồi chính thường f trên Rn có dưới vi phân không rỗng tại mỗi điểm x0 ∈ int(domf). 6 1.2.3 Cực trị của hàm lồi Cho C ⊆ Rn là một tập khác rỗng. Bài toán tối ưu có dạng: min {f (x) : x ∈ C} (1.1) trong đó C là tập chấp nhận được (hay tập ràng buộc), f : C → R là hàm mục tiêu. Mỗi véc tơ x → C được gọi là phương án chấp nhận được (gọi tắt là một phương án). Phương án x∗ ∈ C được gọi là nghiệm tối ưu toàn cục (nghiệm tối ưu) nếu f (x∗ ) ≤ f (x) ∀x ∈ C. Phương án x∗ ∈ C được gọi là nghiệm tối ưu toàn cục chặt nếu f (x∗ ) < f (x) ∀x ∈ C, x 6= x∗ . Phương án x∗ ∈ C được gọi là nghiệm tối ưu địa phương nếu tồn tại một lân cận U của x∗ sao cho f (x∗ ) < f (x) ∀x ∈ U ∩ C. Phương án x∗ ∈ C được gọi là nghiệm tối ưu địa phương chặt nếu tồn tại một lần cận U của x∗ sao cho f (x∗ ) < f (x) ∀x ∈ U ∩ C, x 6= x∗ . Nếu C = Rn , ta nói bài toán (1.1) là bài toán tối ưu không ràng buộc. Chú ý 1.1. Nghiệm tối ưu toàn cục cũng là nghiệm tối ưu địa phương, nhưng điều ngược lại không đúng và max {f (x) : x ∈ C} = − min {−f (x) : x ∈ C} . Nếu C là tập lồi khác rỗng và f : C → R là hàm lồi thì bài toán (1.1) là bài toán quy hoạch lồi và được kí hiệu min {f (x), x ∈ C} (CP ) Mệnh đề sau cho ta kết quả đặc trưng của bài toán quy hoạch lồi (CP ). Mệnh đề 1.2. Xét bài toán qui hoạch lồi (CP ). Khi đó các phát biểu sau là đúng: i) Mọi điểm cực tiểu địa phương của bài toán (CP ) đều là cực tiểu toàn cục. ii) Tập nghiệm của bài toán (CP ) là tập lồi trong Rn . iii) Nếu f lồi chặt thì điểm cực tiểu của bài toán (CP ), nếu tồn tại là duy nhất. Định lý sau đây cho ta điều kiện cần và đủ về sự tồn tại nghiệm tối ưu của bài toán qui hoạch lồi (CP ). 7 Định lý 1.7. Xét bài toán qui hoạch lồi (CP ). Điểm x∗ ∈ C là nghiệm tối ưu của bài toán qui hoạch lồi (CP ) khi và chỉ khi tồn tại p ∈ ∂f (x∗ ) sao cho hp, x − x∗ i ≥ 0 ∀x ∈ C. Hệ quả 1.1. Cho hàm lồi f : Rn → [−∞; +∞] và một tập lồi khác rỗng C ⊂ int (domf). Khi đó x∗ ∈ Arg min {f (x) : x ∈ C} ⇔ 0 ∈ ∂f (x∗ ) + NC (x∗ ), trong đó Arg min {f (x) : x ∈ C} là tập nghiệm tối ưu của bài toán quy hoạch lồi (CP ). Chứng minh. Ta chỉ cần chứng minh: 0 ∈ ∂f (x∗ ) + NC (x∗ ) khi và chỉ khi tồn tại p ∈ ∂f (x∗ ) sao cho hp, x − x∗ i ≥ 0. Thật vậy, ta có 0 ∈ ∂f (x∗ ) + NC (x∗ ) ⇔ ∂f (x∗ ) ∩ (−NC (x∗ )) 6= ∅. Suy ra h−p, x − x∗ i ≤ 0 ∀x ∈ C. Hay hp, x − x∗ i ≥ 0 ∀x ∈ C. Hệ quả 1.2. Cho hàm lồi f : Rn → [−∞; +∞] , một tập lồi khác rỗng C ⊂ int (domf) và điểm x∗ ∈ intC. Khi đó x∗ ∈ Arg min {f (x) : x ∈ C} ⇔ 0 ∈ ∂f (x∗ ). Chứng minh. Vì x∗ ∈ intC nên NC (x∗ ) = {0}. Áp dụng Hệ quả 1.1 suy ra điều phải chứng minh. Nhận xét 1.1. Nếu f là hàm khả vi thì ∂f (x∗ ) = {∇f (x∗ )}. Khi đó ta nhận được kết quả sau x∗ ∈ intC và x∗ ∈ Arg min {f (x) : x ∈ C} ⇔ ∇f (x∗ ) = 0. Đặc biệt x∗ ∈ Arg min {f (x) : x ∈ Rn } ⇔ ∇f (x∗ ) = 0. 8 Hệ quả 1.3. Cho f là hàm lồi khả vi trên tập mở chứa tập lồi C ⊂ Rn . Điểm x∗ ∈ C là điểm cực tiểu toàn cục của bài toán quy hoạch lồi (CP ) khi và chỉ khi h∇f (x∗ ), x − x∗ i ≥ 0 ∀x ∈ C. Chứng minh. Vì hàm f khả vi nên ∂f (x∗ ) = {∇f (x∗ )}. Áp dụng Định lý 1.7 , ta suy ra điều phải chứng minh. 1.3 Ánh xạ co Định nghĩa 1.9. Cho C là tập con của không gian Hilbert H. Ánh xạ T : C → H được gọi là ánh xạ co nếu tồn tại số thực r ∈ [0, 1) sao cho với mọi x, y ∈ C, ta có kT x − T yk ≤ r kx − yk . Định lý 1.8. (Nguyên lý điểm bất động của ánh xạ co) Cho không gian Hilbert H và ánh xạ f : H → H. Nếu f là ánh xạ co thì f có duy nhất điểm bất động, tức tồn tại duy nhất x0 ∈ H để f (x0 ) = x0 . Chứng minh. ε Với mọi ε > 0, tồn tại δ = (r 6= 0), sao cho kx − yk ≤ δ. Khi đó, ta có r kf (x) − f (y)k ≤ r kx − yk < ε ∀ x, y ∈ H. Suy ra f : H → H là hàm liên tục. Với bất kì x ∈ H, đặt x1 = f (x) x2 = f (x1 ) = f 2 (x) .. . xn = f (xn−1 ) = f n (x). Khi đó kxn+1 − xn k = kf (xn ) − f (xn−1 )k ≤ r kxn − xn−1 k = r kf (xn−1 ) − f (xn−2 )k ≤ r2 kxn−1 − xn−2 k ... ≤ rn kx1 − xk . 9 Với bất kì m, n ∈ N; m > n ta có kxm − xn k ≤ kxm − xm−1 k + kxm−1 − xm−2 k + ... + kxm+1 − xn k ≤ rm−1 kx1 − xk + rm−2 kx1 − xk + ... + rn kx1 − xk = (rm−1 + rm−2 + ... + rn ) kx1 − xk ≤ rn kx1 − xk . 1−r Theo giả thuyết, 0 ≤ r < 1 nên {xn } là dãy Cauchy trong không gian Hilber H, vì vậy tồn tại x0 ∈ X sao cho x0 = lim xn n→∞ Vì f : H → H là hàm liên tục nên f (x0 ) = f   lim xn = lim xn+1 = x0 n→∞ n→∞ điều này chứng tỏ f : H → H có điểm bất động x0 ∈ H. Giả sử f : H → H có điểm bất động y0 ∈ H ta có kx0 − y0 k = kf (x0 ) − f (y0 )k ≤ r kx0 − y0 k Vì 0 ≤ r < 1 nên kx0 − y0 k = 0hay x0 = y0 , tức f có duy nhất điểm bất động x0 ∈ H. 1.4 Ánh xạ không giãn Định nghĩa 1.10. Cho C là tập con của không gian Hilbert H. Ánh xạ T : C → H thỏa mãn kT x − T yk ≤ kx − yk với mọi x, y ∈ C được gọi là ánh xạ không giãn. Trong năm 1965 xuất hiện ba định lý điểm bất động, trong đó hai định lý của Browder và của Gohde được chứng minh độc lập nhưng kết quả trùng nhau, còn định lý của Kirk mở rộng một phần cơ bản của hai định lý trên. Trong mục này chúng ta chứng minh định lý của Kirk rồi sau đó suy ra định lý của Browder và Gohde. Định lý 1.9. (Kirk). Cho C là một tập lồi, compact yếu, có cấu trúc chuẩn tắc trong không gian định chuẩn X và T : C → C là một ánh xạ không giãn. Khi đó T có điểm bất động trong C. Chứng minh. Đặt F = {L ⊂ C : L lồi, đóng khác rỗng, T (L) ⊂ L}. 10