Tài liệu Thuật toán đạo hàm tăng cường lai ghép giải bài toán cân bằng đơn điệu

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐOÀN THỊ BÍCH THUẬT TOÁN ĐẠO HÀM TĂNG CƯỜNG LAI GHÉP GIẢI BÀI TOÁN CÂN BẰNG ĐƠN ĐIỆU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2013 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐOÀN THỊ BÍCH THUẬT TOÁN ĐẠO HÀM TĂNG CƯỜNG LAI GHÉP GIẢI BÀI TOÁN CÂN BẰNG ĐƠN ĐIỆU Chuyên ngành: TOÁN ỨNG DỤNG Mã số : 60.46.01.12 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 Thái Nguyên - Năm 2013 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i Mục lục Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Lời cảm ơn 1 Lời nói đầu 2 Một số ký hiệu và chữ viết tắt 5 1 Bài toán cân bằng 6 1.1 Một số khái niệm cơ bản . . . . . . . . . . . . . . . . . . . 1.2 Sự tồn tại nghiệm và các tính chất cơ bản của bài toán cân 6 bằng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 Các trường hợp riêng của bài toán cân bằng . . . . . . . . . 28 2 Phương pháp đạo hàm tăng cường lai ghép giải bài toán cân bằng 33 2.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . 34 2.2 Tính hội tụ của thuật toán . . . . . . . . . . . . . . . . . . 34 Kết luận 43 Tài liệu tham khảo 44 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 LỜI CẢM ƠN Luận văn này được hoàn thành dưới sự hướng dẫn tận tình và sự chỉ bảo nghiêm khắc của thầy giáo GS. TSKH. Lê Dũng Mưu (Viện Toán học Việt Nam). Tôi xin gửi lời cảm ơn chân thành và sâu sắc nhất đến thầy. Tác giả cũng xin kính gửi lời cảm ơn đến cô giáo TS. Nguyễn Thị Thu Thủy cùng các thầy, cô giáo tham gia giảng dạy khóa học cao học 2011 2013, những người đã tâm huyết giảng dạy và trang bị cho tác giả nhiều kiến thức cơ sở. Xin gửi lời cảm ơn đến Ban giám hiệu, phòng Đào tạo, khoa Toán Tin Trường ĐHKH, Đại học Thái Nguyên đã tạo điều kiện thuận lợi cho tôi trong quá trình học tập tại trường. Xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp và các thành viên trong lớp cao học toán K5B đã luôn quan tâm, động viên, giúp đỡ tôi trong thời gian học tập và quá trình làm luận văn. Tuy bản thân có nhiều cố gắng, song thời gian và năng lực của bản thân có hạn nên luận văn khó tránh khỏi những thiếu sót. Rất mong được sự đóng góp quý báu của Quý thầy, cô cùng toàn thể bạn đọc. Thái Nguyên, tháng 04 năm 2013. Tác giả Đoàn Thị Bích Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 LỜI NÓI ĐẦU Cho H là một không gian Hilbert thực với tích vô hướng h., .i và chuẩn k.k tương ứng. Giả sử C là một tập lồi, đóng, khác rỗng trong H và f là song hàm từ C × C vào R sao cho f (x, x) = 0 với mọi x ∈ C . Trong luận văn này ta sẽ xét bài toán cân bằng sau đây, được ký hiệu là EP(C, f ): Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C. Bài toán EP(C, f ) còn được gọi là bất đẳng thức Ky Fan để ghi nhận sự đóng góp của ông trong lĩnh vực này (xem [2], [5] và các trích dẫn). Một phương pháp cơ bản để giải bài toán cân bằng là phương pháp chiếu và các dạng của nó. Tuy nhiên phương pháp chiếu chỉ hội tụ với điều kiện song hàm có tính đơn điệu mạnh, hay là có tính tự bức (đơn điệu mạnh ngược), ngay cả cho bài toán bất đẳng thức biến phân đơn điệu, là một trường hợp đặc biệt của bài toán cân bằng đơn điệu. Để thu được phương pháp chiếu hội tụ cho bài toán cân bằng có tính đơn điệu nhẹ hơn, trong [16] các tác giả đã mở rộng phương pháp đạo hàm tăng cường (hay là chiếu hai lần) do Korpelevich [8] lần đầu tiên đề xuất cho bài toán tối ưu và bài toán điểm yên ngựa. Với phương pháp này sự hội tụ được đảm bảo ngay trong trường hợp song hàm f có tính giả đơn điệu. Bài toán cân bằng đơn điệu có liên quan chặt chẽ với bài toán tìm điểm bất động của một ánh xạ không giãn. Về mặt lý thuyết bài toán cân bằng đơn điệu và bài toán điểm bất động của ánh xạ không giãn có mối quan hệ tương hỗ lẫn nhau, theo nghĩa, với một vài giả thiết tự nhiên, bài toán này có thể mô tả dưới dạng bài toán kia và ngược lại. Cả hai lớp bài toán này thực chất đều thuộc bài toán chấp nhận lồi, tức là bài toán tìm một điểm chung của các tập lồi. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Phương pháp lặp Halpern là phương pháp cơ bản để tìm điểm bất động của ánh xạ không giãn. Tuy nhiên phương pháp này chỉ có tính hội tụ yếu. Để đảm bảo tính hội tụ mạnh, phương pháp Halpern và phương pháp cắt đã được kết hợp. Cụ thể Tada và Takahashi [13] đã trình bày một thuật toán kết hợp phương pháp điểm gần kề và siêu phẳng cắt để đảm bảo tính hội tụ mạnh của điểm gần kề, tại đó với mỗi bước lặp k , phép lặp xk+1 được định nghĩa như sau: 1 Tìm z k ∈ C sao cho f (z k , y) + hy − z k , z k − xk i ≥ 0, ∀y ∈ C, λk  k  xk + (1 − αk )T (z k ), ω =α k Ck = z ∈ H : ω k − z ≤ xk − z ,   D = z ∈ H : xk − z, x0 − xk  ≥ 0 , xk+1 = P 0 k Ck ∩Dk (x ), trong đó λk > 0 là tham số tại bước lặp k ; x0 ∈ C và PCk ∩Dk (x0 ) là phép chiếu khoảng cách trên Ck ∩ Dk của điểm x0 ; T : C → C là ánh xạ không giãn. Với giả thiết song hàm f đơn điệu trên C , các dãy {αk }, {λk } thỏa mãn các tính chất đề ra thì dãy {xk } hội tụ mạnh đến một nghiệm chung của bài toán cân bằng EP (C, f ) và điểm bất động của T . Mục đích của bản luận văn này là giới thiệu những kiến thức cơ bản nhất của bài toán cân bằng và trình bày một thuật toán lai ghép giữa phương pháp đạo hàm tăng cường với phép lặp Halpern cho bài toán tìm nghiệm chung của bài toán cân bằng giả đơn điệu và bài toán tìm điểm bất động của ánh xạ không giãn trong không gian Hilbert thực. Để bảo đảm tính hội tụ mạnh, kỹ thuật siêu phẳng cắt ở [13] đã được kết hợp trong thuật toán này. Sự hội tụ mạnh của thuật toán đã được chứng minh chi tiết cho trường hợp bài toán cân bằng giả đơn điệu. Các đặc điểm quan trọng của thuật toán trình bày trong luận văn so với các thuật toán trong [4] và [13, 14] là: 1. Sư hội tụ mạnh được bảo đảm mà không cần đến giả thiết chính quy; 2. Trong mỗi bước lặp của thuật toán, bài toán cân bằng đơn điệu mạnh nảy sinh trong thuật toán điểm gần kề trong [13] được thay thế bằng hai bài toán quy hoạch lồi mạnh. Về mặt tính toán các bài toán sau dễ giải hơn nhiều, đồng thời nó lại cho phép giải được bài toán cân bằng giả đơn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 điệu, trong khi thuật toán điểm gần kề chỉ có thể áp dụng cho bài toán cân bằng đơn điệu. Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục các tài liệu tham khảo. Chương 1 trình bày một số khái niệm cơ bản liên quan đến đề tài. Các vấn đề liên quan đến sự tồn tại nghiệm và các trường hợp riêng của bài toán cân bằng cũng được đề cập đến. Chương 2 trình bày phương pháp đạo hàm tăng cường lai ghép giải bài toán cân bằng. Các bổ đề cần thiết để chứng minh cho sự hội tụ mạnh của phương pháp cũng như định lý về sự hội tụ mạnh của phương pháp cũng được trình bày ở đây. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 MỘT SỐ KÝ HIỆU VÀ CHỮ VIẾT TẮT H : Không gian Hilbert thực; X : Không gian Banach thực; R: Tập các số thực; ∅: Tập rỗng; I : Ánh xạ đồng nhất; ha, bi: Tích vô hướng của 2 véc-tơ a và b; kxk: Chuẩn của x; ∂f (x): Dưới vi phân của hàm f tại x; ∀x: Với mọi x; xn → x: Dãy {xn } hội tụ mạnh tới x; xn * x: Dãy {xn } hội tụ yếu tới x; x := y : Nghĩa là, x được định nghĩa bằng y ; PC (x): Hình chiếu của x lên C . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 Chương 1 Bài toán cân bằng Chương này trình bày các khái niệm liên quan đến bài toán cân bằng, sự tồn tại nghiệm, các tính chất cơ bản và các trường hợp riêng quan trọng của bài toán cân bằng. Các kiến thức trong chương được trích từ tài liệu [1-5], [7], [12], [15]. 1.1 Một số khái niệm cơ bản Định nghĩa 1.1. Không gian định chuẩn thực là một không gian tuyến tính thực X trong đó ứng với mỗi phần tử x ∈ X ta có một số kxk gọi là chuẩn của x, thỏa mãn các điều kiện sau: 1. kxk > 0, ∀x 6= 0; kxk = 0 ⇔ x = 0; 2. kx + yk 6 kxk + kyk , ∀x, y ∈ X; 3. kαxk = |α| . kxk , ∀x ∈ X, α ∈ R. Định nghĩa 1.2. Cặp (H, h, i) trong đó H là một không gian tuyến tính thực và h, i : H × H → R (x, y) 7→ hx, yi thỏa mãn các điều kiện: 1. hx, xi ≥ 0, ∀x ∈ H; hx, xi = 0 ⇔ x = 0; 2. hx, yi = hy, xi , ∀x, y ∈ H ; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 3. hλx, yi = λ hx, yi , ∀λ ∈ R, ∀x, y ∈ H ; 4. hx + y, zi = hx, zi + hy, zi , ∀x, y, z ∈ H . được gọi là không gian tiền Hilbert. Không gian tiền Hilbert đầy đủ được gọi là không gian Hilbert. Ví dụ 1.1. L2[a,b] , không gian các hàm bình phương khả tích trên [a,b] Rb với f ∈ L2[a,b] sao cho f 2 (x) dx < +∞, là một không gian Hilbert với a tích vô hướng hf, gi = Zb f (x) g (x) dx; a và chuẩn kf kL2 [a,b] 1  b  Z 2 2 =  f (x)dx . a Trên H có hai kiểu hội tụ chính sau: Định nghĩa 1.3. Xét dãy {xn }n≥0 và x thuộc không gian Hilbert thực H . Khi đó: • Dãy {xn } được gọi là hội tụ mạnh tới x, ký hiệu xn → x, nếu như lim kxn − xk = 0. n→+∞ • Dãy {xn } được gọi là hội tụ yếu tới x, ký hiệu xn * x, nếu lim hω, xn i = hω, xi , n→+∞ ∀ω ∈ H. Ta nhắc lại các kết quả trong giải tích hàm (xem [1]) liên quan đến hai loại hội tụ này. Mệnh đề 1.1. • Nếu {xn } hội tụ mạnh đến x thì cũng hội tụ yếu đến x. • Mọi dãy hội tụ mạnh (yếu) đều bị chặn và giới hạn theo sự hội tụ mạnh (yếu) nếu tồn tại là duy nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 • Nếu không gian Hilbert thực H là không gian hữu hạn chiều thì sự hội tụ mạnh và sự hội tụ yếu là tương đương. • Nếu {xn }n≥0 là một dãy bị chặn trong không gian Hilbert thực H thì ta trích ra được một dãy con hội tụ yếu. • Nếu {xn }n≥0 là một dãy bị chặn trong không gian Hilbert thực hữu hạn chiều H thì ta trích ra được một dãy con hội tụ mạnh. Tiếp theo, ta sẽ nêu một số định nghĩa và kết quả cơ bản của giải tích lồi được phát biểu trong [2], [12]. Xét C là tập con khác rỗng trong không gian Hilbert thực H . Định nghĩa 1.4. Tập C trong không gian Hilbert thực H được gọi là một tập lồi nếu ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C. Định nghĩa 1.5. Điểm a được gọi là điểm biên của C nếu mọi lân cận của a đều có điểm thuộc C và điểm không thuộc C ; Tập C được gọi là tập đóng nếu C chứa mọi điểm biên của nó; Tập C được gọi là một tập compact yếu nếu C là một tập đóng và bị chặn. Định nghĩa 1.6. Cho C là một tập lồi và x ∈ C . Ký hiệu: NC (x) := {w| hw, y − xi ≤ 0, ∀y ∈ C} . gọi là một nón. Nón này được gọi là nón pháp tuyến ngoài của C tại x. Định nghĩa 1.7. Xét hàm f : H → R ∪ {+∞}. Khi đó: (i) Hàm f được gọi là hàm lồi trên H nếu f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ H, ∀λ ∈ (0, 1); (ii) Hàm f được gọi là hàm lồi chặt trên H nếu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x 6= y ∈ H, ∀λ ∈ (0, 1); (iii) Hàm f được gọi là hàm lồi mạnh trên H với hệ số η > 0 nếu f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − η λ(1 − λ) kx − yk2 , 2 với mọi x, y ∈ H, ∀λ ∈ (0, 1). Dưới đây là một số ví dụ quen thuộc về hàm lồi. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Ví dụ 1.2. 1. Hàm affine. f (x) = aT x + b, trong đó a ∈ Rn , b ∈ R là hàm lồi. Nó thoả mãn đẳng thức f (λx + (1 − λ)y) = λf (x) + (1 − λ)f (y), ∀x, y ∈ H, λ ∈ (0, 1). Do đó nó không lồi chặt. Cho C 6= ∅ là một tập lồi. 2. Hàm chỉ. Đặt ( δC (x) := 0 khi x ∈ C, +∞ khi x ∈ / C. Ta nói δC là hàm chỉ của C . Do C lồi nên δC là hàm lồi. 3. Hàm khoảng cách. Giả sử C là một tập đóng, khác rỗng. Hàm khoảng cách dC (y) được định nghĩa như sau: dC (y) = inf kx − yk. x∈C Khi đó, nếu C là tập lồi thì dC là hàm lồi. Thật vậy, xét x, y ∈ H và λ ∈ (0, 1) bất kỳ. Đặt z = λx + (1 − λ)y . Theo   định nghĩa của inf tồn tại các dãy xk , y k trong C sao cho lim x − xk = dC (x) và lim y − y k = dC (y). k→∞ k→∞ Do C lồi nên z k := λxk + (1 − λ)y k ∈ C . Ta có dC (z) ≤ z − z k = λ(x − xk ) + (1 − λ)(y − y k ) ≤ λ x − xk + (1 − λ) y − y k . Cho k → ∞ ta có dC (z) ≤ λdC (x) + (1 − λ)dC (y). Vậy dC là hàm lồi. 2 Nếu tồn tại π ∈ C sao cho kπ − yk = dC (y) thì π được gọi là hình chiếu khoảng cách của y trên C . Khi đó, π là nghiệm của bài toán tối ưu kx − yk2 . min x∈C 2 Ký hiệu hình chiếu của y trên C là PC (y). Khi đó, π = PC (y). Tiếp theo ta sẽ chứng minh sự tồn tại và tính duy nhất của hình chiếu xuống một tập lồi đóng. Sau đó ta sẽ khảo sát một số tính chất cơ bản Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 của toán tử chiếu được sử dụng trong chương sau của luận văn. Mệnh đề 1.2. (xem [2])Giả sử C là tập lồi, đóng khác rỗng trong H . Khi đó: (i) Với mọi y ∈ H , π ∈ C hai tính chất sau tương đương: (a) π = PC (y), (b) y − π ∈ NC (π). (ii) Với ∀y ∈ H , hình chiếu PC (y) của y trên C luôn tồn tại và duy nhất. (iii) Nếu y ∈ / C thì hPC (y) − y, x − PC (y)i = 0 là siêu phẳng tựa của C tại PC (y) và tách hẳn y khỏi C , tức là hPC (y) − y, x − PC (y)i ≥ 0, ∀x ∈ C; và hPC (y) − y, y − PC (y)i < 0. (iv) Ánh xạ y 7→ PC (y) có các tính chất sau: (a) kPC (x) − PC (y)k ≤ kx − yk, ∀x, y (tính không giãn); (b) hPC (x) − PC (y), x − yi ≥ kPC (x) − PC (y)k2 (tính đồng bức). Chứng minh. (i) Giả sử có (a), tức là π là hình chiếu của y trên C . Lấy x ∈ C . Đặt xλ := λx + (1 − λ)π. Do C lồi nên xλ ∈ C với mọi λ ∈ (0, 1). Theo định nghĩa hình chiếu ta có kπ − yk ≤ ky − xλ k. Hay kπ − yk2 ≤ ky − xλ k2 = k(π − y) + λ(x − π)k2 . Khai triển vế phải và giản ước ta thu được λkx − πk2 + 2 hx − π, π − yi ≥ 0, ∀x ∈ C, λ ∈ (0, 1). Cho λ tiến tới 0 ta thu được bất đẳng thức hπ − y, x − πi ≥ 0, ∀x ∈ C. Vậy y − π ∈ NC (π). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 Giả sử có (b) tức là giả sử y − π ∈ NC (π). Khi đó với mọi x ∈ C ta có ky − xk2 =k(y − π) + (π − x)k2 =ky − πk2 + kπ − xk2 + 2 hy − π, π − xi ≥ky − πk2 + kπ − xk2 ≥ky − πk2 . Suy ra π là hình chiếu của y trên C . (ii) Do dC (y) = inf kx − yk, nên theo định nghĩa của cận dưới đúng, x∈C k tồn tại một dãy x ∈ C sao cho lim xk − y = dC (y) < +∞. k  k  Suy ra dãy x bị chặn, do đó trích ra được một dãy con xkj hội tụ đến một điểm π nào đó. Mặt khác, do C đóng nên giới hạn này phải thuộc C . Ta có kπ − yk = lim xkj − y = lim xk − y = dC (y). j k Chứng tỏ π là hình chiếu của y trên C . Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, giả sử π và π đều là hình chiếu của y trên C thì 0 y − π ∈ NC (π), y − π 0 ∈ NC (π 0 ). Chọn x = π 0 trong mệnh đề trên ta có hy − π, π 0 − πi ≤ 0. Thay đổi vai trò của π và π 0 ta được hy − π 0 , π − π 0 i ≤ 0. Cộng hai bất đẳng thức trên suy ra kπ − π 0 k2 ≤ 0. Điều này chỉ xảy ra khi π = π 0 . (iii) Do y − π ∈ NC (π) nên hπ − y, x − πi ≥ 0, ∀x ∈ C. Vậy hπ − y, xi = hπ − y, πi là một siêu phẳng tựa của C tại π . Siêu phẳng này tách y khỏi C vì y 6= π nên hπ − y, y − πi = −kπ − yk2 < 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 (iv) (a) Theo phần (ii) ánh xạ x 7→ PC (x) xác định khắp nơi. Do z − PC (z) ∈ NC (PC (z)) với mọi z , áp dụng với z = x và z = y , ta có hx − PC (x), PC (y) − PC (x)i ≤ 0; và hy − PC (y), PC (x) − PC (y)i ≤ 0. Cộng hai bất đẳng thức trên, ta được hPC (y) − PC (x), PC (y) − PC (x) + x − yi ≤ 0. Kết hợp điều này và bất đẳng thức Cauchy-Schwarz, suy ra kPC (x) − PC (y)k ≤ kx − yk. (b) Áp dụng tính chất (b) của (i), lần lượt với PC (x) và PC (y), ta có: hPC (x) − x, PC (x) − PC (y)i ≤ 0; hy − PC (y), PC (x) − PC (y)i ≤ 0. Cộng hai bất đẳng thức trên, suy ra hPC (x) − PC (y) + y − x, PC (x) − PC (y)i =hPC (x) − PC (y), y − xi + kPC (x) − PC (y)k2 ≤ 0. Chuyển vế ta có hPC (x) − PC (y), x − yi ≥ kPC (x) − PC (y)k2 . Vậy mệnh đề đã được chứng minh. 2 Định nghĩa 1.8. Cho f : H → R ∪ {+∞}. Ta nói x∗ ∈ H là dưới đạo hàm của f tại x nếu hx∗ , z − xi + f (x) ≤ f (z), ∀z ∈ H. Ký hiệu tập tất cả các dưới đạo hàm của f tại x là ∂f (x). Khi ∂f (x) 6= ∅ thì ta nói hàm f khả dưới vi phân tại điểm x. f được gọi là khả dưới vi phân trên một tập nếu f khả dưới vi phân tại mọi điểm trên tập đó. Ví dụ 1.3. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 1. f (x) = kxk , x ∈ Rn . Tại điểm x = 0 hàm này không khả vi, nhưng nó khả dưới vi phân và ∂f (0) = {x∗ | hx∗ , xi ≤ kxk , ∀x} ; 2. f = δC là hàm chỉ của một tập lồi C 6= ∅. Khi đó, với x0 ∈ C ,   ∂δC (x0 ) = x∗ | x∗ , x − x0 ≤ δC (x), ∀x . Với x ∈ / C thì δC (x) = +∞, nên bất đẳng thức này luôn đúng. Vậy   ∂δC (x0 ) = x∗ | x∗ , x − x0 ≤ 0, ∀x ∈ C = NC (x0 ). Ta có mệnh đề sau nói lên tính khả dưới vi phân của hàm lồi. Mệnh đề 1.3. Nếu f : H → R là hàm lồi thì ∂f (x) 6= ∅ với mọi x ∈ X hay là f khả dưới vi phân khắp nơi. Mệnh đề này là trường hợp riêng của Định lý 23.4, trang 217 trong tài liệu [12]. Định nghĩa 1.9. Hàm f : H → R được gọi là nửa liên tục dưới đối với E ⊂ H tại một điểm x, nếu như với mọi dãy xk ⊂ E; xk → x ta có lim inf f (xk ) ≥ f (x); Hàm f được gọi là nửa liên tục trên đối với E ⊂ H tại một điểm x, nếu −f nửa liên tục dưới đối với E điểm x. Hay là với mọi dãy xk ⊂ E; xk → x thì lim sup f (xk ) ≤ f (x); Hàm f được gọi là liên tục đối với E ⊂ H tại một điểm x nếu như nó vừa nửa liên tục trên và nửa liên tục dưới đối với E tại x. Khi E là toàn không gian, ta nói đơn giản là nửa liên tục dưới, nửa liên tục trên hay liên tục. Định nghĩa 1.10. Một hàm số thực ϕ được gọi là tựa lồi trên tâp lồi C , nếu với mọi số thực γ tập mức dưới {x ∈ C|ϕ(x) ≤ γ} lồi. Tương tự, hàm một hàm ϕ được gọi là tựa lõm trên C , nếu −ϕ là hàm tựa lồi trên C . Nếu ϕ tựa lồi trên C thì ∀x, y ∈ C và λ ∈ [0, 1] ta có ϕ(λx + (1 − λ)y) ≤ max(ϕ(x), ϕ(y)); Tương tự, nếu ϕ tựa lõm trên C thì ∀x, y ∈ C và λ ∈ [0, 1] ta có ϕ(λx + (1 − λ)y) ≥ min(ϕ(x), ϕ(y)). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 Các định nghĩa về tính đơn điệu của song hàm và ánh xạ được sử dụng trong việc trình bày tính duy nhất nghiệm của bài toán cân bằng (xem [2], [7], [10], [15], [16]). Trong các định nghĩa sau xét C là tập khác rỗng, đóng, lồi trong không gian Hilbert thực H . Định nghĩa 1.11. Giả sử f : C × C → R. Ta nói (i) f đơn điệu mạnh trên C với hệ số β > 0, nếu f (x, y) + f (y, x) ≤ −βkx − yk2 , ∀x, y ∈ C; (ii) f đơn điệu chặt trên C , nếu f (x, y) + f (y, x) < 0, ∀x, y ∈ C, x 6= y; (iii) f đơn điệu trên C , nếu f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; (iv) f giả đơn điệu trên C , nếu f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C; (v) f liên tục có tính chất kiểu Lipschitz trên C với 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. Từ định nghĩa ta có (i) ⇒ (ii) ⇒ (iii) ⇒ (iv). Ví dụ 1.4. Xét hàm h : H → R. Khi đó: 1. f (x, y) := h(x) − h(y) là đơn điệu nhưng không đơn điệu chặt. 2. g(x, y) := h(x) − h(y) − 1 là đơn điệu chặt nhưng không đơn điệu mạnh. Thật vậy, xét g(x, y) + g(y, x) = −2 < 0 với mọi x, y ∈ H nên g đơn điệu chặt. Giả sử tồn tại hệ số β > 0 thỏa mãn điều kiện đơn điệu mạnh, suy ra βkx − yk2 ≤ 2, ∀x, y ∈ H. Chọn x = 0 và y = tv với v là một véc-tơ khác 0 trong H , ta được 2 β≤ , ∀t ∈ R. |t| .kvk Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 Cho t → ∞ thì điều kiện trên chỉ xảy ra khi β ≤ 0 (mâu thuẫn). 2 Các khái niệm về đơn điệu đối với song hàm có liên quan chặt chẽ với các khái niệm về đơn điệu của ánh xạ (toán tử), rất quen thuộc trong giải tích phi tuyến. Định nghĩa 1.12. Ánh xạ F : C → H được gọi là (i) đơn điệu mạnh trên C với hệ số β > 0, nếu hF (x) − F (y), x − yi ≥ βkx − yk2 , ∀x, y ∈ C; (ii) đơn điệu chặt trên C , nếu hF (x) − F (y), x − yi > 0, ∀x, y ∈ C, x 6= y; (iii) đơn điệu trên C , nếu hF (x) − F (y), x − yi ≥ 0, ∀x, y ∈ C; (iv) giả đơn điệu trên C , nếu hF (y), x − yi ≥ 0 ⇒ hF (x), x − yi ≥ 0, ∀x, y ∈ C; (v) liên tục L-Lipschitz trên C nếu kF (x) − F (y)k ≤ L kx − yk , ∀x, y ∈ C, L > 0. Từ định nghĩa ta có (i) ⇒ (ii) ⇒ (iii) ⇒ (iv). Ví dụ 1.5. Cho C là tập lồi, hàm f : C → R, và ∂f liên tục. Khi đó: • Nếu f là hàm khả vi, lồi trên C thì ∂f là đơn điệu trên C . Thật vậy, lấy tùy ý x, y ∈ C và do f là hàm lồi nên f (x) ≥ f (y) + h∂f (y), x − yi , f (y) ≥ f (x) + h∂f (x), y − xi . Cộng hai bất đẳng thức trên với nhau, suy ra h∂f (y) − ∂f (x), y − xi ≥ 0, ∀x, y ∈ C. 2 Vậy ∂f là đơn điệu trên C . • Nếu f là khả vi, lồi mạnh trên C thì ∂f là đơn điệu mạnh trên C . • Nếu f là hàm khả vi, lồi chặt trên C thì ∂f là đơn điệu chặt trên C . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 Nhận xét 1.1. Nếu F là L−Lipschitz trên C thì với mỗi x, y ∈ C, f (x, y) = hF (x), y − xi L có tính chất liên tục kiểu Lipschitz với hằng số c1 = c2 = trên C . 2 Thật vậy f (x, y) + f (y, z) − f (x, z) = hF (x), y − xi + hF (y), z − yi − hF (x), z − xi = − hF (y) − F (x), y − zi ≥ − kF (x) − F (y)k ky − zk ≥ − L kx − yk ky − zk L L ≥ − kx − yk2 − ky − zk2 2 2 2 =c1 kx − yk − c2 ky − zk2 . Do vậy, f là liên tục có tính chất kiểu Lipschitz trên C . 1.2 2 Sự tồn tại nghiệm và các tính chất cơ bản của bài toán cân bằng Trong phần này ta nhắc lại một số định lý quen thuộc trong giải tích phi tuyến. Các định lý này là công cụ sắc bén để nghiên cứu, đặc biệt là để chứng minh sự tồn tại nghiệm của bài toán cân bằng. Bài toán cân bằng Ta nhắc lại bài toán cân bằng (còn được gọi là bất đẳng thức Ky Fan): Xét H là không gian Hilbert thực; C là tập lồi, đóng, khác rỗng trong H và f : C × C → R ∪ {+∞}. Khi đó, bài toán cân bằng là bài toán Tìm x ∈ C sao cho f (x, y) ≥ 0, ∀y ∈ C. (EP ) Tập nghiệm của bài toán cân bằng được ký hiệu là Sol(C, f ). Dưới đây ta sẽ luôn giả thiết f (x, x) = 0 với mọi x ∈ C . Một song hàm thỏa mãn điều kiện này được gọi là song hàm cân bằng. C được gọi là tập chấp nhận được hay là tập chiến lược và f là hàm cân bằng của bài toán (EP). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 17 Tiếp theo ta xét sự tồn tại nghiệm và các tính chất cơ bản của bài toán cân bằng. Để chứng minh kết quả về sự tồn tại nghiệm của bài toán ta sử dụng định lý minimax quan trọng. Định lý minimax Cho một song hàm f : C × C → R. Nhiều vấn đề trong tối ưu hóa, lý thuyết trò chơi và các lĩnh vực khác đưa đến câu hỏi khi nào có đẳng thức γ := sup inf f (x, y) = inf sup f (x, y) := η. y∈D x∈C x∈C y∈D (1.1) Đẳng thức này nói rằng việc lấy cận trên đúng và cận dưới đúng có thể hoán vị cho nhau. Từ định nghĩa cận trên đúng, cận dưới đúng, ta có sup inf f (x, y) ≤ inf sup f (x, y). y∈D x∈C (1.2) x∈C y∈D Các định lý minimax là các định lý nghiên cứu các điều kiện để có đẳng thức (1.1). Ta xét bổ đề sau, là cơ sở để chứng minh các định lý minimax. Bổ đề 1.1. Cho C ⊆ H, D ⊆ H là các tập lồi, đóng khác rỗng và f : C × D → R. Giả sử với mọi y ∈ D, hàm f (., y) tựa lồi, nửa liên tục dưới trên C và với mọi x ∈ C , hàm f (x, .) tựa lõm, nửa liên tục trên trên D. Khi đó ta có: (i) Với mọi γ 0 > γ := sup inf f (x, y) và mọi tập hữu hạn N ⊂ D, tập y∈D x∈C  C (N ) := x ∈ C| max f (x, y) ≤ γ 0  6= ∅; y∈N (ii) Với mọi η 0 < η := inf sup f (x, y) và mọi tập hữu hạn M ⊂ C , tập x∈C y∈D  D (M ) := y ∈ D| min f (x, y) ≥ η 0  x∈M 6= ∅. Chứng minh. Đặt Cγ 0 (y) := {x ∈ C|f (x, y) ≤ γ 0 } . Do C lồi, f (., y) tựa lồi và nửa liên tục dưới, nên Cγ 0 (y) lồi, đóng. Khẳng định (i) có nghĩa là ∩ Cγ 0 (y) 6= ∅. y∈N Ta chứng minh (i) bằng quy nạp theo số phần tử của N . Khi N chỉ có duy nhất một phần tử y , tập Cγ 0 (N ) = Cγ 0 (y) = {x ∈ C|f (x, y) ≤ γ 0 } . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn