Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Sư phạm Luận văn phương pháp lai ghép cho bài toán cân bằng và bài toán điểm bất động củ...

Tài liệu Luận văn phương pháp lai ghép 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

.PDF
60
103
106

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 ====== NGUYỄN THỊ VÂN TRANG PHƯƠNG PHÁP LAI GHÉP 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 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Ị VÂN TRANG PHƯƠNG PHÁP LAI GHÉP 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 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 Luận văn được hoàn thành dưới sự hướng dẫn chỉ bảo tận tình, nghiêm khắc của TS. Lê Quang Thủy. Qua đây, tác giả xin bày tỏ lòng kính trọng, biết ơn chân thành và sâu sắc đến thầy về sự giúp đỡ nhiệt tình, chu đáo trong suốt quá trình tác giả thực hiện luận văn. Tác giả xin gửi lời cảm ơn tới các thầy, cô trong khoa Toán trường Đại học Sư phạm Hà Nội II đã nhiệt tình giảng dạy và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Nhân dịp này tác giả xin chân thành cảm ơn khoa Toán, Phòng Sau đại học trường trường Đại học Sư phạm Hà Nội II đã tạo mọi điều kiện thuận lợi cho tác giả trong quá trình học tập và hoàn thành luận văn. Cuối cùng, tác giả xin bày tỏ sự biết ơn tới gia đình, cơ quan đã luôn bên cạnh ủng hộ, động viên và tạo mọi điều kiện thuận lợi nhất trong quá trình học tập và hoàn thành luận văn này. 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ị Vân Trang 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ị Vân Trang Mục lục Một số kí hiệu và chữ viết tắt v 1 Kiến thức chuẩn bị 1.1 1 n Một số kiến thức về giải tích lồi trong R . . . . . . . . . . . . . . . . . 1 1.1.1 Tập lồi và nón lồi . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Phép chiếu lên tập lồi đóng . . . . . . . . . . . . . . . . . . . . 2 1.1.3 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.4 Dưới vi phân của hàm lồi . . . . . . . . . . . . . . . . . . . . . 6 1.1.5 Cực trị của hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Bài toán cân bằng trong không gian Hilbert . . . . . . . . . . . . . . . 10 1.3 Điểm bất động của ánh xạ không giãn trong không gian Hilbert . . . . 11 2 Phương pháp đạo hàm tăng cường cho bài toán cân bằng 16 2.1 Sự tồn tại nghiệm của bài toán cân bằng trong không gian Rn . . . . . 16 2.2 Phương pháp bài toán cân bằng phụ . . . . . . . . . . . . . . . . . . . 21 2.2.1 Bài toán cân bằng phụ . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 Phương pháp bài toán cân bằng phụ . . . . . . . . . . . . . . . 24 Phương pháp đạo hàm tăng cường cho bài toán cân bằng . . . . . . . . 29 2.3.1 29 2.3 Thuật toán đạo hàm tăng cường . . . . . . . . . . . . . . . . . . 3 Phương pháp lai ghép 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 37 3.1 Phương pháp lai ghép cho bài toán cân bằng và bài toán điểm bất động 37 3.2 Ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 i MỞ ĐẦU 1. Lý do chọn đề tài 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. 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 [8] năm 1992 và E. Blum, W. Oettli [4] năm 1994. 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 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 là đề xuất các phương pháp, thuật toán giải, tính hội tụ của các thuật toán,. . . Mục đích của luận văn là ii giới thiệu về bài toán cân bằng, ánh xạ không giãn; một số kết quả về sự tồn tại nghiệm cùng một số phương pháp cơ bản giải bài toán cân bằng đơn điệu, giả đơn điệu và một phương pháp lai ghép 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. 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 “Kiến thức chuẩn bị” trình bày một số khái niệm và kết quả cơ bản của giải tích lồi như tập lồi, hàm lồi, cực trị hàm lồi,. . . làm cơ sở cho các phần trình bày trong các chương sau; bài toán cân bằng và ánh xạ không giãn cũng được đề cập trong nội dung của chương này. Chương 2 “Phương pháp đạo hàm cường cho bài toán cân bằng” trình bày 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 đạo hàm tăng cường cho việc giải bài toán cân bằng. Chương 3 “Phương pháp lai ghép 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 lai ghép 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 giả đơ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 • Bài toán cân bằng; • Ánh xạ không giãn; • 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 • Bài toán cân bằng, các trường hợp đặc biệt của bài toán cân bằng; • Ánh xạ không giãn, điểm bất động của ánh xạ không giãn; • Thuật toán 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. 4. Đối tượng và phạm vi nghiên cứu • Bài toán cân bằng, bài toán điểm bất động của ánh xạ không giãn trong không gian Hilbert. • Thuật toán lai ghép 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. iii 5. 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. 6. Đóng góp của luận văn Luận văn là một bài tổng quan về phương pháp lai ghép 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. iv Một số 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 x∈C x là phần tử của tập C x∈ /C x không là phần tử của tập C ∃x tồn tại x ∀x với mọi x NC (x0 ) nón pháp tuyến ngoài của tập C ⊂ H tại x0 ∈ C, tức NC (x0 ) = {v ∈ H : hv, x − x0 i ≤ 0 ∀x ∈ C} A∩B giao của hai tập hợp A và B A∪B hợp của hai tập hợp A và B A×B tích Descartes của hai tập hợp A và B A+B tổng của hai tập hợ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∗ ) véc tơ 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(f, C) 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} v Chương 1 Kiến thức 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, bài toán qui hoạch lồi,. . . Điểm bất động của ánh xạ không giãn cũng như bài toán cân bằng và một số trường đặc biệt của bài toán cân bằng 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], [7]. 1.1 1.1.1 Một số kiến thức về giải tích lồi trong Rn Tập lồi và nón lồi Cho hai điểm x, y ∈ Rn . Đ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. Đườ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 ⊆ Rn đượ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 ⊆ Rn 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ứ C. Ví dụ bao afin của hình cầu  C = x ∈ R3 : kxk ≤ 1 là cả không gian R3 . 1 Định nghĩa 1.1. Tập C ⊆ Rn đượ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 Rn 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} ; α, β ∈ R. Bao lồi(convex full) của tập C ⊂ Rn là giao của tất cả các tập lồi chứa C và được kí hiệu là convC. Đó là tập lồi nhỏ nhất chứa C. Định nghĩa 1.2. Tập C ⊂ Rn được gọi là một nón nếu với mọi x ∈ C, λ ≥ 0 thì λx ∈ C. Tập C là nón lồi nếu C vừa là nón vừa là tập lồi. Nón C không chứa đường thẳng nào gọi là nón nhọn. Định nghĩa 1.3. Cho C ⊆ Rn là một tập lồi và x ∈ C i) Tập NC (x) = {ω ∈ Rn : hω, y − xi ≤ 0 ∀y ∈ C} được gọi là nón pháp tuyến ngoài của C tại x. ii) Tập −NC (x) := {ω ∈ Rn : hω, y − xi ≥ 0 ∀y ∈ C} được gọi là nón pháp tuyến trong của C tại x. 1.1.2 Phép chiếu lên tập lồi đóng Định nghĩa 1.4. Cho C là tập lồi đóng trong Rn . Với mọi x ∈ Rn , 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 Rn . 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 : Rn → C x 7→ x b = PC (x) 2 là phép chiếu của x lên tập C. Với mỗi x ∈ Rn , ta gọi dC (x) = 21 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}. 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: min{ 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 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à tập một tập lồi đóng khác rỗng trong không gian Rn . Khi đó các khẳng định sau là đúng. (i) Với mọi x ∈ Rn , x̄ = PC (x) tồn tại và duy nhất; (ii) Với mọi x ∈ Rn , 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 ∈ Rn ; (iv) PC là ánh xạ không giãn (Non-expansive), nghĩa là kPC (x) − PC (y)k ≤ kx − yk ∀x, y ∈ Rn ; Do đó PC là hàm liên tục Lipschitz trên Rn ; (v) kPC (x) − yk2 ≤ kx − yk2 − kPC (x) − xk2 ∀y ∈ C, ∀x ∈ Rn ; (vi) kPC (x) − PC (y)k2 ≤ kx − yk2 − kPC (x) − x + y − PC (y)k2 1.1.3 ∀x, y ∈ Rn . Hàm lồi Định nghĩa 1.5. 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 ); 3 (ii) Hàm lồi chặt (Strictly convex function) trên C nếu với mọi x1 , x2 ∈ C,x1 6= x2 và với mọi t ∈ (0, 1) ta có 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. Nhận xét 1.1. Từ định nghĩa, ta có f lồi mạnh ⇒ f lồi chặt ⇒ f lồi. Cho hàm f xác định trên tập lồi C ⊆ Rn , khi đó miền xác định hữu hiệu (Effective domain) của hàm f là tập domf = {x ∈ C : f (x) < +∞} . Trên đồ thị (Epigaraph) của hàm f là tập Epif = {(x, λ) ∈ C × R : f (x) ≤ λ} . Hàm f gọi là chính thường trên C nếu domf 6= ∅ và f (x) > −∞ với mọi x ∈ domf. Định nghĩa 1.6. Cho C ⊆ Rn và hàm lồi f : C → R ∪ {+∞}. Hàm f được gọi là: i) Nửa liên tục dưới (Lower semi continuos) tại x ∈ C nếu lim inf f (y) ≥ f (x) ∀x ∈ C; y→x ii) Nửa liên tục (Upper semi continuos) tại x ∈ C nếu lim sup f (y) ≤ f (x) ∀x ∈ C. y→x Hàm f được gọi là liên tục tại điểm x ∈ C nếu nó vừa nửa liên tục trên vừa nửa liên tục dưới tại điểm x. Hàm f được gọi là nửa liên tục dưới (nửa liên tục trên) trên C nếu nó nửa liên tục dưới (nửa liên tục trên) tại mọi x ∈ C. Một hàm lồi có thể không liên tục trên biên miền xác định của nó, tuy nhiên nó liên tục tại mọi điểm trong của tập đó theo định lý sau. Định lý 1.1. Một hàm lồi xác định trên C ⊆ Rn thì liên tục tại mọi điểm trong C. 4 Cho hàm số f xác định trên tập lồi mở C ⊆ Rn . Hàm f khả vi tại x∗ ∈ C nếu tồn tại các đạo hàm riêng của f theo mọi biến và với mọi d ∈ Rn , kdk đủ nhỏ sao cho x∗ + d ∈ C, ta có f (x∗ ) = f (x∗ ) + h∇f (x∗ ), di + dT ∇2 f (x∗ )d + o (kdk) , 2 trong đó ∇f (x∗ )là véc tơ Gradient và ∇2 f (x∗ )là ma trận Hesse của hàm f tại 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.2. 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.3. 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 khi 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} . Định nghĩa 1.7. Cho C là tập lồi, khác rỗng trong không gian Rn và hàm số f : C → R ∪ {+∞}. Ta nói hàm f là (i) Tựa lồi (Quasiconvex) 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] ≤ max {f (x), f (y)} ; (ii) Tựa lồi nửa chặt(Semistrictly quasiconvex) trên C và với mọi x, y ∈ C, ta có f (x) < f (y) ⇒ f (z) < f (y) ∀z ∈ (x, y); (iii) Tựa lồi chặt (Strictly quasiconvex) trên C nếu với mọi x, y ∈ C, x 6= y và với mọi λ ∈ (0, 1) ta có f [λx + (1 − λ)y] ≤ max {f (x), f (y)} 5 1.1.4 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.4. 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). Định lý 1.5. Cho f là hàm lồi chính thường trên Rn . Khi đó i) p ∈ ∂f (x0 ) ⇔ (p, −1) ∈ Nepif (x0 , f (x0 )); ii) ∂f (x0 là tập đóng; iii) Nếu f (x) khả vi tại x0 thì ∂f (x0 ) = {∇ϕf (x0 )} Mệnh đề 1.2. Cho f là hàm lồi chính thường trên Rn và λ> 0. Khi đó ∂(λf )(x) = λ∂f (x) ∀x ∈ Rn . Định lý 1.6. (Định lí Moreau-Rockafellar) cho f1 , f2 , f3 , . . . , fm là các hàm lồi chính thường trên Rn . Khi đó m  m P P a) ∂ fi (x) ⊇ ∂fi (x) ∀x ∈ Rn ; i=1 b) Nếu m T i=1 fi (domfi ) thì i=1 ∂ m X i=1 1.1.5 ! fi (x) = m X ∂fi (x) ∀x ∈ Rn . i=1 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), ϕ : 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 6 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ào toán quy hoạch lồi (CP ). Mệnh đề 1.3. 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 ). Đị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. Chứng minh. Giả sử tồn tại p ∈ ∂f (x∗ ) sao cho hp, x − x∗ i ≥ 0, với mọi x ∈ C. Vì f là hàm lồi, nên theo Định lý 1.2, ta có 7 f (x) ≥ f (x∗ ) + hp, x − x∗ i ∀x ∈ C. Mà hp, x − x∗ i ≥ 0, nên f (x) ≥ f (x∗ ) với mọi x ∈ C. Điều này chứng tỏ x∗ là nghiệm của bài toán (CP ). Ngược lại, giả sử x∗ là nghiệm của bài toán (CP ). Xét tập A = {(y − x∗ , t) ∈ Rn+1 : y ∈ Rn , t > f (y) − f (x∗ )} và B = {(x − x∗ , 0) ∈ Rn+1 : x ∈ C} . Ta có A và B là các tập lồi. Hơn nữa, nếu tồn tại (x−x∗ , 0) ∈ A∩B thì do (x−x∗ , 0) ∈ A nên f (x) − f (x∗ ) < 0. Suy ra f (x) < f (x∗ ) với x ∈ C. Điều này mâu thuẫn với x∗ là nghiệm của bài toán (CP ). Vậy A ∩ B = ∅. Theo Định lý 1.4 ([10]), tồn tại (v 0 , µ) ∈ Rn+1 \ {0} sao cho 0 v , y − x∗ + µt ≤ v 0 , x − x∗ ∀x ∈ C ∀y ∈ Rn : t > f (y) − f (x∗ ). (1.2) Từ (1.2), lấy y = x∗ , và do t > f (x∗ ) − f (x∗ ) = 0 nên ta có µ ≤ 0. Nếu µ = 0 thì từ (1.2) ta có 0 v , y − x∗ ≤ v 0 , x − x∗ ∀x ∈ C ∀y ∈ Rn . (1.3) Lấy y = x∗ + v 0 ∈ Rn , x = x∗ ∈ C. Khi đó, từ (1.3) ta có hv 0 , v 0 i ≤ 0. Do đó v 0 = 0. Suy ra (v 0 , µ) = (0, 0), mâu thuẫn với (v 0 , µ) 6= (0, 0). Vậy phải có µ < 0. Từ (1.2), chọn y = x∗ ta có µt ≤ v 0 , x − x∗ ∀t > f (x∗ ) − f (x∗ ) = 0 ∀x ∈ C. Cho t → 0, ta có v 0 , x − x∗ ≥ 0 ∀x ∈ C. Cũng từ (1.2), chọn x = x∗ , ta có hv 0 , y − x∗ i + µt ≤ 0 ∀y ∈ Rn , t > f (y) − f (x∗ ). Cho t → (f (y) − f (x∗ )) ta có v 0 , y − x∗ + µ (f (y) − f (x∗ )) ≤ 0. Kết hợp µ < 0 và bất đẳng thức này, ta suy ra   0 v − , y − x∗ − (f (y) − f (x∗ )) ≤ 0. µ 8 (1.4) 0 Đặt p = − vµ , ta có hp, y − x∗i + f (x∗ ) ≤ f (y) ∀y ∈ C. Suy ra p ∈ ∂f (x∗ ). Thay v 0 = −µp vào (1.4) ta được hp, y − 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) , đ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.2. Nếu f là hàm khả vi thì ∂f (x∗ ) = {∇f (x∗ )}. Khi đó ta nhận được kết quả như sau x∗ ∈ intC và x∗ ∈ Arg min {f (x) : x ∈ C} ⇔ ∇f (x∗ ) = 0. 9 Đặc biệt x∗ ∈ Arg min {f (x) : x ∈ Rn } ⇔ ∇f (x∗ ) = 0. 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.2 Bài toán cân bằng trong không gian Hilbert Cho C là tập lồi đóng khác rỗng trong không gian Hilbert H và f : C × C → R là ánh xạ thỏa mãn f (x, x) = 0 với mọi x ∈ C. Bài toán cân bằng được phát biểu như sau: Tìm điểm x∗ ∈ C sao cho f (x∗ , y) ≥ 0 ∀y ∈ C. (EP ) Hàm f còn được gọi là song hàm cân bằng trên C. Như ta thấy, bài toán cân bằng khá đơn giản về mặt hình thức, tuy nhiên nó bao hàm được nhiều lớp bài toán quan trọng thuộc các lĩnh vực khác nhau như bài tối ưu, bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán điểm yên ngựa, bài toán cân bằng Nash trong trò chơi không hợp tác,. . . . Các nhà nghiên cứu cũng chỉ ra rằng, nhiều bài toán thực tế trong kinh tế và kỹ thuật có thể mô tả được dưới dạng bài toán cân bằng. Bằng các phép biến đổi thích hợp ta có thể đưa các bài toán này về bài toán cân bằng. Chẳng hạn, xét bài toán điểm bất động Kakutani. Tìm điểm x∗ ∈ C cho x∗ = T (x∗ ), (FP) trong đó C là tập con khác rỗng trong Rn và ánh xạ liên tục T : C → C. Đặt f (x, y) = hx − T (x), y − xi với mọi x, y ∈ C. Khi đó bài toán điểm bất động (FP) là bài toán cân bằng. Thật vậy, giả sử x∗ ∈ C là nghiệm bài toán (FP), theo định nghĩa ta có T (x∗ ) = x∗ . Mặt khác f (x, y) = hx − T (x), y − xi , 10 nên f (x∗ , y) = hx∗ − T (x∗ ), y − x∗ i = 0 ∀y ∈ C. Vậy x∗ là nghiệm bài toán cân bằng (EP ). Ngược lại, nếu x∗ ∈ C là nghiệm bài toán (EP ), thì theo định nghĩa ta có f (x∗ , y) ≥ 0 ∀y ∈ C, tức hx∗ − T (x∗ ), y − x∗ i ≥ 0 ∀y ∈ C. Suy ra kx∗ − T (x∗ )k2 ≤ 0 . Do đó, x∗ = T (x∗ ). 1.3 Điểm bất động của ánh xạ không giãn trong không gian Hilbert Định nghĩa 1.8. 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ý sau chứng tỏ sự tồn tại điểm bất động của ánh xạ co. Đị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 y ∈ H để f (y) = y. Định nghĩa 1.9. 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 ∀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 là mở rộng một phần cơ bản của hai định lý trên. Phần này trình bày định lý của Kirk. Đị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. 11
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng