Luận văn Nghiên cứu hiệu chỉnh hóa trong bài toán cân bằng

ĐẠI HỌC THÁI NGUYấN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ KIM NGỌC NGHIấN CỨU HIỆU CHỈNH HểA TRONG BÀI TOÁN CÂN BẰNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYấN – 2009 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn ĐẠI HỌC THÁI NGUYấN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ KIM NGỌC NGHIấN CỨU HIỆU CHỈNH HểA TRONG BÀI TOÁN CÂN BẰNG Chuyờn ngành: Toỏn ứng dụng Mó số: 60. 46. 36 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 - 2009 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Mục lục Mục lục 1 Mở đầu 2 Chương 1. Bài toán cân bằng 4 1.1. Các kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . 4 1.2. Bài toán cân bằng và các trường hợp riêng . . . . . . . . . . 9 Chương 2. Phương pháp chiếu và đạo hàm tăng cường giải bài toán cân bằng 16 2.1. Phương pháp chiếu giải bài toán cân bằng . . . . . . . . . . 16 2.2. Phương pháp đạo hàm tăng cường giải bài toán cân bằng . . 25 Chương 3. Phương pháp hàm đánh giá 40 3.1. Hàm đánh giá A.Auslender . . . . . . . . . . . . . . . . . . 42 3.2. Hàm đánh giá M.Fukushima . . . . . . . . . . . . . . . . . 48 Kết luận 53 Tài liệu tham khảo 54 1 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Mở đầu Bài toán cân bằng có nhiều ứng dụng trong khoa học, kĩ thuật và đời sống như: vật lí (đặc biệt là cơ học), hoá học, sinh học, quân sự, nông nghiệp, kinh tế, viễn thông... Bài toán cân bằng là bài toán tổng quát, nó bao gồm các trường hợp riêng như: bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán bù phi tuyến, bài toán Nash trong trò chơi hợp tác... Do có ứng dụng thực tế rộng rãi nên việc quy về bài toán cân bằng và đưa ra các thuật toán giải bài toán cân bằng là cần thiết. Ngày nay với sự phát triển nhanh chóng của kĩ thuật tin học nên phạm vi và khả năng ứng dụng của bài toán cân bằng ngày càng mở rộng. Luận văn này nhằm giới thiệu về bài toán cân bằng và một số phương pháp hiệu chỉnh cho bài toán cân bằng. Luận văn gồm mục lục, ba chương, phần kết luận và tài liệu tham khảo. Chương 1 trước hết nhắc lại khái niệm và kết quả cơ bản nhất về tập lồi và hàm lồi sẽ được dùng ở các chương sau. Tiếp theo là giới thiệu về bài toán cân bằng và các trường hợp riêng của nó. Phần này được coi là cơ sở lí thuyết cho các phương pháp sẽ dùng đến ở các chương sau. Chương 2 trình bày hai phương pháp hiệu chỉnh bài toán cân bằng, đó là phương pháp chiếu và phương pháp đạo hàm tăng cường. Chương 3 giới thiệu hai loại hàm đánh giá là hàm đánh giá Auslender và hàm đánh giá Fukushima. Các thuật toán tương ứng với hai loại hàm đánh giá này được trình bày chi tiết trong chương 3. Để hoàn thành luận văn này, tác giả đã nhận được sự giúp đỡ và hướng dẫn tận tình của GS.TSKH. Lê Dũng Mưu. Tác giả xin bày tỏ lòng biết ơn sâu sắc đến thày của mình. Tác giả xin chân thành cảm ơn các thày cô trong Bộ môn toán, Trường Đại học Khoa học- Đại học Thái Nguyên, cùng các bạn học viên lớp cao học toán K1 đã luôn tạo điều kiện thuận lợi, động viên, khích lệ để luận 2 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn văn được hoàn thành. Mặc dù tác giả đã cố gắng nhưng luận văn khó tránh khỏi những thiếu sót, hạn chế. Tác giả mong nhận được những ý kiến đóng góp của các thày cô và bạn đọc để luận văn được hoàn thiện hơn. Thái Nguyên, 10/2009 Học viên Hoàng Thị Kim Ngọc 3 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chương 1 Bài toán cân bằng Chương này nhằm giới thiệu một số khái niệm và kiến thức cơ bản về bài toán cân bằng và các trường hợp riêng của nó. Trước tiên ta khái quát lại một số kiến thức về giải tích lồi sẽ dùng đến trong các phần của luận văn. 1.1. Các kiến thức chuẩn bị Giải tích lồi đóng vai trò quan trọng trong việc nghiên cứu, phân tích và xây dựng các thuật toán giải bài toán cân bằng. Mục đích chính của phần này là nhắc lại một số kiến thức về giải tích lồi, các định lý không được chứng minh có thể xem trong [4]. Kí hiệu R là tập số thực, Rn là không gian Euclid n chiều. Định nghĩa 1.1.1. [4] Cho hai điểm a, b trong không gian Euclid n-chiều Rn. Đường thẳng đi qua hai điểm a, b là tập hợp các điểm x trong Rn có dạng: x = λa + (1− λ)b, ∀λ ∈ R. Đoạn thẳng nối a, b là tập hợp tất cả các điểm x trong Rn có dạng: x = λa + (1− λ)b = λ(a− b) + b, 0 ≤ λ ≤ 1. Định nghĩa 1.1.2. [4] Tập A ⊆ Rn gọi là tập lồi, nếu nó chứa trọn đoạn thẳng nối hai điểm bất kì thuộc nó. Ví dụ 1.1.1. Hình 1.1 cho ta ví dụ đơn giản về tập lồi và tập không lồi 4 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn (a) (b) (c) (d) Hình 1.1. (a), (c)- Tập lồi; (b), (d)- Tập không lồi Định lý 1.1.1. [1] Tập lồi là đóng với phép giao, phép hợp, 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 là, 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,A ∩B := {x : x ∈ A, x ∈ B}, b, αA + βB := {x = αa + βb : a ∈ A, b ∈ B}. Định nghĩa 1.1.3. [1] Tập A ⊂ Rn được gọi là nón nếu: x ∈ A, λ ≥ 0 ⇒ λx ∈ A. Một nón luôn chứa điểm gốc 0 ∈ Rn. Tập A ⊂ Rn được gọi là nón lồi nếu A vừa là nón vừa là tập lồi, tức là λ1x + λ2y ∈ A, ∀x, y ∈ A, ∀λ1, λ2 ≥ 0. Định nghĩa 1.1.4. [4] Cho tập lồi A ⊂ Rn và điểm x0 ∈ clA. Tập NC(x 0) = { t ∈ Rn : 〈t, x− x0〉 ≤ 0, ∀x ∈ A} là một nón lồi đóng hay là nón pháp tuyến ngoài của A tại x0. Định nghĩa 1.1.5. [3] Cho tập lồi khác rỗng A ⊆ Rn. Vecto d 6= 0 được gọi là phương lùi xa của A nếu với mỗi x ∈ A có: {x + λd | λ ≥ 0} ⊂ A. Nhận xét [3] ?Mọi nửa đường thẳng song song với một phương lùi xa d xuất phát từ một điểm bất kì của A đều nằm trọn trong A. Rõ ràng, tập A không bị chặn khi 5 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn và chỉ khi A có một phương lùi xa. ? Tập tất cả các phương lùi xa của tập lồi A ⊆ Rn cùng vecto 0 tạo thành nón lồi. Nón lồi được gọi là nón lùi xa của tập A và kí hiệu là recA. ? Ta nói hai phương d1 và d2 là khác biệt nếu d1 6= αd2, α > 0. Phương lùi xa d của tập A được gọi là phương cực biên của A nếu không tồn tại các phương lùi xa khác biệt d1 và d2 của A sao cho d = λ1d 1+λ2d 2, λ1, λ2 > 0. Định nghĩa 1.1.6. [1] Một tập hợp là giao của một số hữu hạn các nửa không gian đóng được gọi là tập lồi đa diện hay gọi là khúc lồi. Định nghĩa 1.1.7. [1] Tập con B của khúc lồi A được gọi là một diện của A nếu hễ B chứa một điểm trong của một đoạn thẳng nào đó của A thì B chứa cả đoạn thẳng đó của A. Tức là, ∀a, b ∈ A nếu x = λa + (1− λ)b ∈ B, 0 < λ < 1 ⇒ a, b ∈ B. Một diện có thứ nguyên bằng 0 được gọi là một đỉnh hay một điểm cực biên. Cạnh là diện có thứ nguyên bằng 1. Định lý 1.1.2. [1] a, Mọi tập lồi đa diện không chứa trọn một đường thẳng đều có ít nhất một đỉnh. b, Mọi tập lồi đa diện A có đỉnh bằng tập hợp của các điểm x có dạng: x = ∑ i∈I λiv i + ∑ j∈J βjd j trong đó, ∑ i∈I λi = 1, λi, βj ≥ 0 với mọi i, j còn vi là các đỉnh, dj là các phương của các cạnh vô hạn của A. Định nghĩa 1.1.8. [5] ChoM,K là các tập lồi khác rỗng của Rn,M ⊆ K và f : K ìK → R ∪ {+∞}. Khi đó: a, Hàm f đơn điệu mạnh trên M với hằng số τ > 0 nếu với mỗi cặp x, y ∈ M ta có: f(x, y) + f(y, x) ≤ −τ ‖ x− y ‖2 . b, Hàm f đơn điệu chặt trên M nếu với mọi x, y ∈ M ta có: f(x, y) + f(y, x) < 0. 6 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn c, Hàm f đơn điệu trên M nếu với mỗi cặp x, y ∈ M ta có: f(x, y) + f(y, x) ≤ 0. d, Hàm f giả đơn điệu trên M nếu với mỗi cặp x, y ∈ M thì: f(x, y) ≥ 0 ⇒ f(y, x) ≤ 0. Định nghĩa 1.1.9. [4] a, Hàm f là hàm lồi xác định trên tập lồi X ⊆ Rn, nếu: f [ λx + (1− λ)y] ≤ λf(x) + (1− λ)f(y), với bất kì x, y ∈ X và số thực λ ∈ [0, 1]. b, Hàm f là hàm lồi chặt trên tập lồi X , nếu: f [ λx + (1− λ)y] < λf(x) + (1− λ)f(y), với bất kì x, y ∈ X, x 6= y và λ ∈ (0, 1). c, Hàm f là hàm lồi mạnh với hệ số β > 0 trên tập lồi X nếu: f [ λx + (1− λ)y] ≤ λf(x) + (1− λ)f(y)− β(1− λ)λ ‖ x− y ‖2, với bất kì x, y ∈ X và λ ∈ (0, 1). d, Hàm f được gọi là hàm tựa lồi trên tập lồi X , nếu với ∀α ∈ R, tập mức dưới Lα(f) = {x ∈ X : f(x) ≤ α} là tập lồi. Định lý 1.1.3. [1] Cho f là hàm lồi trên tập lồi A và g là hàm lồi trên tập lồi B. Khi đó, các hàm sau là hàm lồi trên tập lồi A ∩B: a, λf + βg, ∀λ, β ≥ 0, b,max(f, g). Định lí 1.1.3 nhìn chung không đúng cho hàm tựa lồi. Một hàm lồi có thể không liên tục tại một điểm trên biên miền xác định của nó. Tuy nhiên, nó lại liên tục tại mọi điểm trong của tập đó theo định lí sau: Định lý 1.1.4. [1] Một hàm lồi xác định trên tập lồi A thì liên tục tại mọi điểm trong của tập A. 7 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Định lý 1.1.5. [4] Cho hàm f lồi, khả vi trên tập lồi A. Khi đó với mọi x, y ∈ A có: f(y)− f(x) ≥ 〈∇f(x), y − x〉. Nếu f lồi chặt, khả vi trên tập lồi A. Khi đó với mọi x, y ∈ A và x 6= y ta có: f(y)− f(x) > 〈∇f(x), y − x〉. Nếu f là lồi mạnh với hệ số β > 0, khả vi trên tập lồi A. Khi đó với mọi x, y ∈ A ta có: f(y)− f(x) ≥ 〈∇f(x), y − x〉+ β ‖ y − x ‖2 . Định lý 1.1.6. [1] Cho f là hàm lồi, khả vi trên tập lồi đóng A. Một điểm x∗ ∈ A là nghiệm tối ưu của bài toán quy hoạch lồi: min x∈A f(x) khi và chỉ khi nó là điểm dừng của f trên A, tức là:〈∇f(x∗), y − x∗〉 ≥ 0, ∀y ∈ A. Từ định lí 1.1.5 và 1.1.6 có: nếu f là hàm lồi mạnh trên tập lồi đóng A thì bài toán: min x∈A f(x) có nghiệm duy nhất. Định nghĩa 1.1.10. [1] Cho f là một hàm lồi trên tập lồi A. Một vecto y∗ ∈ Rn được gọi là dưới vi phân của f tại x∗ ∈ A nếu: f(x) ≥ f(x∗) + 〈y∗, x− x∗〉, ∀x ∈ A. Tập hợp tất cả các điểm y∗ thoả mãn bất đẳng thức trên được kí hiệu ∂f(x∗). Tập ∂f(x∗) nhìn chung thường chứa nhiều điểm. Trong trường hợp ∂f(x∗) chỉ chứa duy nhất một điểm ta nói rằng f khả vi tại x∗. 8 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Ví dụ 1.1.2. f(x) =‖ x ‖ khả vi tại mọi điểm x 6= 0 do ∂f(x) = ‖ x ‖−1x, không khả vi tại x = 0 do ∂f(x) = {y : ‖ x ‖≥ 〈y, x〉,∀y}. Định nghĩa 1.1.11. [3] Cho D ⊂ Rn, D 6= ∅, f : D → R. Một điểm x∗ ∈ D được gọi là cực tiểu địa phương của f trên D, nếu tồn tại một lân cận mở U của x∗, sao cho f(x∗) ≤ f(x), ∀x ∈ D ∩ U . Điểm x∗ được gọi là cực tiểu tuyệt đối của f trên D nếu f(x∗) ≤ f(x), ∀x ∈ D. Định lý 1.1.7. [1] a, Mọi điểm cực tiểu địa phương của một hàm lồi trên một tập lồi đều là điểm cực tiểu tuyệt đối. b, Nếu x∗ là điểm cực tiểu của hàm lồi f trên tập lồi D và x∗ ∈ intD thì 0 ∈ ∂f(x∗). Định lý 1.1.8. [1] Cực đại của một hàm lồi (nếu có ) trên một tập lồi có điểm cực biên bao giờ cũng đạt tại một điểm cực biên. 1.2. Bài toán cân bằng và các trường hợp riêng Bài toán cân bằng có ý nghĩa quan trọng trong kinh tế và nhiều lĩnh vực thực tiễn khác. Hơn nữa, bài toán cân bằng là sự mở rộng của nhiều bài toán khác như: bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán cân bằng Nash... Vì lí do đó mà lớp các bài toán cân bằng được nhiều nhà toán học quan tâm, nghiên cứu. Phần này sẽ giới thiệu dạng toán học của bài toán cân bằng và một số bài toán tương đương với bài toán cân bằng. Nội dung chủ yếu của phần này được tham khảo trong [2]. Trong toàn bộ luận văn này ta luôn giả thiết K là tập lồi đóng khác rỗng trong Rn. Định nghĩa 1.2.1. [2] Cho hàm f : K ì K → R thoả mãn f(x, x) = 0, ∀x ∈ K. Khi đó, bài toán cân bằng được phát biểu như sau: Tìm x∗ ∈ K sao cho f(x∗, y) ≥ 0, ∀y ∈ K. (1.1) 9 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Hàm số f thoả mãn tính chất f(x, x) = 0, ∀x ∈ K được gọi là hàm cân bằng trên K. Như đã nói ở trên, các bài toán quan trọng có thể đưa về bài toán cân bằng. Dưới đây ta trình bày sự tương đương của bài toán cân bằng với các bài toán khác. Bài toán tối ưu [2] Cho J : K → R là một hàm số xác định trên K. Khi đó, bài toán tối ưu được phát biểu như sau: Tìm x∗ ∈ K sao cho J(x∗) ≤ J(y), ∀y ∈ K. (1.2) Nếu ta đặt f(x, y) := J(y)− J(x) với ∀x, y ∈ K thì bài toán tối ưu tương đương với bài toán cân bằng. Thật vậy, giả sử x∗ ∈ K là nghiệm của bài toán (1.2) nên theo định nghĩa ta có: J(x∗) ≤ J(y), ∀y ∈ K. Mặt khác, f(x, y) = J(y)− J(x), ∀x, y ∈ K. Do đó, f(x∗, y) = J(y)− J(x∗) ≥ 0, ∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán (1.1). Ngược lại, cho x∗ ∈ K là nghiệm của bài toán (1.1) nên ta có: f(x∗, y) ≥ 0, ∀y ∈ K. Theo cách đặt ta có: f(x∗, y) = J(y)− J(x∗) ≥ 0, ∀y ∈ K ⇒ J(y) ≥ J(x∗), ∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán (1.2). Bài toán bất đẳng thức biến phân tổng quát [2] 10 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Cho T : K → 2Rn là ánh xạ nửa liên tục trên từ một điểm vào một tập hợp sao cho T (x) là tập compact, ∀x ∈ K. Khi đó, bài toán bất đẳng thức biến phân tổng quát được phát biểu như sau: Tìm x∗ ∈ K, ξ∗ ∈ T (x∗) sao cho 〈ξ∗, y − x∗〉 ≥ 0, ∀y ∈ K (1.3) Nếu ta đặt f(x, y) := maxξ∈T (x) 〈 ξ, y − x〉,∀x, y ∈ K thì bài toán cân bằng (1.1) tương đương với bài toán bất đẳng thức biến phân tổng quát. Thật vậy, giả sử x∗ ∈ K là nghiệm của bài toán (1.3) nên có:〈 ξ∗, y − x∗〉 ≥ 0, ∀y ∈ K, ξ∗ ∈ T (x∗). Mặt khác theo cách đặt ta có: f(x∗, y) = max ξ∗∈T (x∗) 〈 ξ∗, y − x∗〉 ≥ 0,∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán (1.1). Ngược lại, cho x∗ ∈ K là nghiệm của bài toán (1.1) nên f(x∗, y) ≥ 0, ∀y ∈ K. Theo cách đặt ta có: f(x∗, y) = max ξ∗∈T (x∗) 〈 ξ∗, y − x∗〉 ≥ 0,∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán (1.3). • Nếu T là ánh xạ đơn trị thì bài toán bất đẳng thức biến phân tổng quát là bài toán bất đẳng thức biến phân sau: Tìm x∗ ∈ K sao cho 〈T (x∗), y − x∗〉 ≥ 0, ∀y ∈ K. (1.4) Nếu ta đặt f(x, y) := 〈 T (x), y − x〉, ∀x, y ∈ K thì với cách lập luận như trên bài toán (1.4) tương đương với bài toán cân bằng (1.1). Bài toán bù phi tuyến [2] Cho K ⊆ Rn là một nón lồi đóng, K∗ = {x ∈ Rn | 〈x, y〉 ≥ 0, ∀y ∈ K} là nón đối cực của nón K. 11 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Cho ánh xạ T : K → Rn liên tục. Khi đó, bài toán bù phi tuyến được phát biểu như sau: Tìm x∗ ∈ K sao cho T (x∗) ∈ K và 〈T (x∗), x∗〉 = 0. (1.5) Nếu ta đặt f(x, y) := 〈 T (x), y − x〉, ∀x, y ∈ K thì bài toán bù phi tuyến (1.5) sẽ tương đương với bài toán cân bằng (1.1). Thật vậy, giả sử x∗ ∈ K là nghiệm của bài toán (1.5) nên ta có: T (x∗) ∈ K và 〈T (x∗), x∗〉 = 0. Mặt khác theo cách đặt ta có: f(x∗, y) = 〈 T (x∗), y − x∗〉 = 〈 T (x∗), y 〉− 〈T (x∗), x∗〉 = 〈 T (x∗), y 〉 ≥ 0, ∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán cân bằng (1.1). Ngược lại, cho x∗ ∈ K là nghiệm của bài toán (1.1) ta có: f(x∗, y) ≥ 0 ∀y ∈ K. Theo cách đặt ta có: f(x∗, y) = 〈 T (x∗), y − x∗〉, ∀y ∈ K. Do K là nón nên 0 ∈ K và 2x∗ ∈ K. Trong đẳng thức trên nếu lấy y = 0 ∈ K có 〈T (x∗),−x∗〉 ≥ 0 hay 〈T (x∗), x∗〉 ≤ 0, còn nếu lấy y = 2x∗ ∈ K ta có 〈T (x∗), 2x∗ − x∗〉 ≥ 0 hay 〈T (x∗), x∗〉 ≥ 0.Vậy〈 T (x∗), x∗ 〉 = 0. Hơn nữa, do 0 ≤ 〈T (x∗), y − x∗〉 = 〈T (x∗), y〉− 〈t(x∗), x∗〉 = 〈T (x∗), y〉, ∀y ∈ K. Do 〈 T (x∗), y 〉 ≥ 0, ∀y ∈ K nên T (x∗) ∈ K. Do đó, x∗ ∈ K là nghiệm của (1.5). Chú ý Khi K là nón lồi đóng thì bài toán bất đẳng thức biến phân (1.4) 12 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn chính là bài toán bù phi tuyến (1.5). Bài toán điểm bất động Kakutani [2] Cho T : Rn → 2Rn vớiK∩T (x) là tập compact lồi, khác rỗng, với ∀x ∈ K. Khi đó, bài toán điểm bất động Kakutani được phát biểu như sau: Tìm x∗ ∈ K sao cho x∗ ∈ T (x∗) (1.6) Nếu ta đặt f(x, y) := maxξ∈T (x) 〈 x− ξ, y − x〉,∀x, y ∈ K thì bài toán cân bằng (1.1) tương đương với bài toán điểm bất động (1.6). Thật vậy, giả sử x∗ ∈ K là nghiệm của (1.6) nên T (x∗) = x∗. Mặt khác theo cách đặt ta có f(x∗, y) = 〈 x∗ − T (x∗), y − x∗〉, ∀y ∈ K. Do đó, x∗ ∈ K là nghiệm của (1.1). Ngược lại, cho x∗ ∈ K là nghiệm của (1.1) nên f(x∗, y) ≥ 0, ∀y ∈ K. Theo cách đặt có f(x∗, y) = 〈 x∗ − T (x∗), y − x∗〉, ∀y ∈ K. Chọn y = T (x∗) ∈ K ta có f(x∗, y) = 〈 x∗ − T (x∗), T (x∗)− x∗〉 ≥ 0, ∀y ∈ K ⇒ − ‖ x∗ − T (x∗) ‖≥ 0, ∀y ∈ K ⇒‖ x∗ − T (x∗) ‖≤ 0, ∀y ∈ K ⇒ x∗ = T (x∗), ∀y ∈ K. Vậy x∗ ∈ K là nghiệm của (1.6). • Nếu T là ánh xạ đơn trị thì bài toán điểm bất động Kakutani trở thành bài toán điểm bất động Brouwer sau: Tìm x∗ ∈ K sao cho x∗ = T (x∗). (1.7) 13 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Nếu ta đặt f(x, y) := 〈 x − T (x), y − x〉,∀x, y ∈ K thì với cách lập luận như trên chỉ ra được rằng bài toán (1.7) tương đương với bài toán cân bằng. Bài toán cân bằng Nash (trong trò chơi không hợp tác) [2] • Cho I = {1, 2, . . . , p} là tập chỉ số hữu hạn (tập p−người chơi ). • Ki là tập lồi khác rỗng của Rni (tập chiến lược của người chơi thứ i ). • Hàm fi : K1ì . . .ìKp → R cho trước (hàm tổn thất của người chơi thứ i khi vi phạm chiến lược của những người chơi với ∀i ∈ I ) Cho x = (x1, . . . , xp) ∈ K1 ì . . . Kp và y = (y1, . . . , yp) ∈ K1 ì . . . Kp Ta định nghĩa vecto x[yi] ∈ K1 ì . . .ìKp như sau: x[yi]j = xj, ∀j 6= iyi, ∀j = i Đặt K = K1 ì . . .ìKp Khi đó, bài toán cân bằng Nash được phát biểu như sau: Tìm x∗ ∈ K sao cho fi(x∗) ≤ fi(x∗[yi]), ∀i ∈ I,∀y ∈ K. (1.8) Điểm thoả mãn (1.8) gọi là điểm cân bằng Nash. Về ý nghĩa kinh tế, điểm cân bằng này nói lên rằng bất kì đối thủ nào chọn phương án ra khỏi điểm cân bằng trong khi các đối thủ còn lại vẫn giữ phương án điểm cân bằng thì đối thủ ra khỏi điểm cân bằng sẽ bị thua thiệt. Nếu ta đặt f : KìK → R được xác định bởi f(x, y) := p∑ i=1 {fi(x[yi])− fi(x)} với ∀x, y ∈ K thì bài toán cân bằng Nash (1.8) tương đương với bài toán cân bằng (1.1). Thật vậy, giả sử x∗ ∈ K là nghiệm của bài toán (1.8) nên: fi(x ∗) ≤ fi(x∗[yi]), ∀i ∈ I, ∀yi ∈ Ki ⇒ fi(x∗[yi])− fi(x∗) ≥ 0, ∀i ∈ I, ∀yi ∈ Ki ⇒ p∑ i=1 { fi(x ∗[yi])− fi(x∗) } ≥ 0, ∀y ∈ K. 14 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Theo cách đặt có: f(x∗, y) ≥ 0, ∀y ∈ K. Vậy x∗ ∈ K là nghiệm của (1.1). Ngược lại, cho x∗ ∈ K là nghiệm của (1.1) mà không là nghiệm của (1.9). Do x∗ ∈ K là nghiệm của (1.1) nên ta có: f(x∗, y) ≥ 0, ∀y ∈ K. Theo cách đặt có: p∑ i=1 {fi(x∗[yi])− fi(x∗)} ≥ 0, ∀i ∈ K, ∀y ∈ K. Do x∗ ∈ K không là nghiệm của (1.8) nên ∃i0 ∈ K sao cho: fi(x ∗) > fi(x∗[yi]), ∀yi ∈ Ki. Ta lấy x∗[yj] = x∗, ∀j 6= i0 suy ra fi(x ∗[yj])− fi(x∗) = 0, ∀j 6= i0. Kết hợp hai điều trên ta suy ra p∑ i=1 { fi(x ∗[yi])− fi(x∗) } < 0, mâu thuẫn. Vậy x∗ ∈ K là nghiệm của bài toán (1.8). Kết luận chương Chương này trước tiên nhắc lại một số kết quả cơ bản của giải tích lồi sẽ dùng đến trong các chương sau. Tiếp theo là trình bày dạng toán học của bài toán cân bằng, đồng thời thông qua các phép biến đổi phù hợp chỉ ra sự tương đương giữa bài toán cân bằng với bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán bù phi tuyến, bài toán điểm bất động, bài toán cân bằng Nash. 15 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chương 2 Phương pháp chiếu và đạo hàm tăng cường giải bài toán cân bằng Bài toán cân bằng có ý nghĩa thực tiễn lớn, do đó việc tìm lời giải cho bài toán cân bằng là rất cần thiết. Chương này nhằm giới thiệu phương pháp chiếu và phương pháp đạo hàm tăng cường giải bài toán cân bằng. Nội dung chủ yếu của chương này được xem trong [2], [5]. 2.1. Phương pháp chiếu giải bài toán cân bằng Phương pháp chiếu là phương pháp cơ bản nhất để giải bài toán đối ngẫu của bài toán cân bằng. Trước tiên ta định nghĩa bài toán đối ngẫu. Định nghĩa 2.1.1. [2] Bài toán đối ngẫu của bài toán cân bằng được phát biểu như sau: Tìm x∗ ∈ K sao cho : f(y, x∗) ≤ 0, ∀y ∈ K. (2.1) Trong đó, f : K ìK → R là hàm liên tục thoả mãn: a, f(x, x) = 0, ∀x ∈ K, b, f(x, .) : K → R là hàm lồi với ∀x ∈ K. Với mỗi x ∈ K đặt Lf(x) = {y ∈ K | f(x, y) ≤ 0}. Rõ ràng, x∗ ∈ K là nghiệm của bài toán đối ngẫu (2.1) khi và chỉ khi x∗ ∈ ⋂ y∈K Lf(y). Định lí sau chỉ ra mối quan hệ giữa nghiệm của bài toán đối ngẫu và nghiệm của bài toán cân bằng. Định lý 2.1.1. [2] Tập nghiệm của bài toán đối ngẫu là tập con của tập nghiệm của bài toán cân bằng. 16 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứngminh Cho x∗ ∈ K là nghiệm của bài toán đối ngẫu, lấy y ∈ K, ∀λ ∈ [0, 1] ta định nghĩa zλ ∈ K như sau: zλ := λy + (1− λ)x∗. Với mỗi λ ∈ [0, 1] ta có 0 (a) =f(zλ, zλ) = f(zλ, λy+(1−λ)x∗) (b) ≤λf(zλ, y)+(1−λ)f(zλ, x∗). (2.2) Do x∗ là nghiệm của bài toán đối ngẫu nên: x∗ ∈ ⋂ y∈K Lf(y) = ⋂ y∈K {x ∈ K | f(y, x) ≤ 0}. Lấy y = zλ, với ∀λ ∈ [0, 1] ta luôn có f(zλ, x∗) ≤ 0. Do đó, ∀λ ∈ [0, 1],∀y ∈ K và từ (2.1) ta có: 0 ≤ λf(zλ, y) ≤ f(λy + (1− λ)x∗, y) = f(x∗ + λ(y − x∗), y). Cho λ → 0, do tính liên tục của f nên: 0 ≤ f(x∗, y), ∀y ∈ K. ⇒ x∗ là nghiệm của bài toán cân bằng. Ta có điều phải chứng minh.  Nhận xét [2] ? Mệnh đề đảo của định lí 2.1.1 không đúng. Thật vậy, lấy N = 1 và lấy K = [0, 2] và kí hiệu S1 là tập nghiệm của bài toán đối ngẫu, S2 là tập nghiệm của bài toán cân bằng. Khi đó, a, f(x, y) = (x− y)2 ⇒ S1 = ∅, S2 = [0, 2] ⇒ S1 * S2. b, f(x, y) = max{0, | x− y | −1} ⇒ S1 = {1}, S2 = [0, 2] ⇒ S1 * S2. ? Khi f là giả đơn điệu, nghĩa là ∀x, y ∈ K : f(x, y) ≥ 0 ⇒ f(y, x) ≤ 0, mệnh đề đảo của 2.1.1 đúng. Khi đó, bài toán đối ngẫu và bài toán cân bằng có cùng tập nghiệm. Ta có thuật toán chiếu 2.1 sau để giải bài toán đối ngẫu. Thuật toán chiếu 2.1 [2] Bước 1: Cho k = 0, x0 ∈ K và r0 = ‖ x0 ‖. Bước 2: Lấy xk và rk (i) Định nghĩa: 17 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Kk = {x ∈ K : ‖ x ‖≤ rk + 1}. (2.1a) (ii) Tìm yk ∈ Kk có tính chất: max y∈Kk f(y, xk)− k ≤ f(yk, xk), (2.1b) với {k}k≥0 ⊂ [0,+∞] là dãy thoả mãn lim k→+∞ k = 0. (iii) Tính xk+1 dạng: xk+1 = xk + tk [ PLf (yk)(x k)− xk], (2.1c) trong đó, PLf (yk)(x k) là phép chiếu trực giao của xk lên Lf(yk), và Lf(yk) = {x ∈ K | f(yk, x) ≤ 0} là tập lồi, {tk}k≥0 ⊂ [α, 2− α] với α ∈ [0, 1]. (iv) Tính rk thông qua: rk+1 = max{rk, ‖ xk+1 ‖} (2.1d) và trở về (i) của bước 2. Mệnh đề 2.1.1. [2] Thuật toán chiếu 2.1 được xác định đúng đắn. Chứng minh • Chứng minh (2.1b) đúng. Thật vậy, từ công thức (2.1a) và (2.1d) ta có: Kk ⊂ Kk+1, ∀k ∈ N. Do x0 ∈ K và ‖ x0 ‖≤ r0 + 1 nên suy ra x0 ∈ K0 ⇒ x0 ∈ Kk, ∀k ∈ N Mặt khác, K là tập đóng nên mọi Kk là khác rỗng và compact. Lại do tính liên tục của f nên f(., yk) đạt cực đại trên Kk, vì vậy tồn tại yk ∈ Kk thoả mãn: max y∈Kk f(y, xk)− k ≤ f(yk, xk). • Chứng minh (2.1c) đúng. Thật vậy, do tính lồi của f(yk, .) và tính lồi của tập K nên tập khác rỗng: Lf(y k) = {x ∈ K | f(yk, x) ≤ 0} 18 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn là tập lồi, đóng. Do đó, xk+1 = xk + tk [ PLf (yk)(x k)− xk] được xác định duy nhất. Vậy mệnh đề được chứng minh.  Mệnh đề 2.1.2. [2] Giả sử rằng: +∞⋂ k=0 Lf(y k) 6= ∅, (2.3) thì: a, ∀x∗ ∈ +∞⋂ k=0 Lf(y k) dãy {‖ xk − x∗ ‖}k≥0 không tăng và do đó hội tụ. b, Dãy {xk}k≥0 bị chặn. c, lim k→+∞ ‖ xk+1 − xk ‖= 0. Chứng minh a, Cho x∗ ∈ +∞⋂ k=0 Lf(y k), từ công thức (2.1c) của thuật toán 2.1 ta có xk+1 = xk + tk [ PLf (yk)(x k)− xk] do đó: ‖ xk+1 − x∗ ‖2 = ‖ xk + tk[PLf (yk)(xk)− xk]− x∗ ‖2 = ‖ xk − x∗ ‖2 + tk2 ‖ PLf (yk)(xk)− xk ‖2 + 2 tk 〈 xk − x∗, PLf (yk)(xk)− xk 〉 . (2.4) Ta lại có: 2 tk 〈 xk − x∗, PLf (yk)(xk)− xk 〉 = = 2 tk 〈 xk − PLf (yk)(xk) + PLf (yk)(xk)− x∗, PLf (yk)(xk)− xk 〉 = −2 tk ‖ xk − PLf (yk)(xk) ‖2 +2 tk 〈 PLf (yk)(x k)− x∗, PLf (yk)(xk)− xk 〉 . (2.5) Từ (2.4) và (2.5) ta có: ‖ xk+1 − x∗ ‖2 = ‖ xk − x∗ ‖2 + tk2 ‖ PLf (yk)(xk)− xk ‖2 − − 2 tk ‖ xk − PLf (yk)(xk) ‖2 + + 2 tk 〈 PLf (yk)(x k)− x∗, PLf (yk)(xk)− xk 〉 . (2.6) 19 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Do tính chất của phép chiếu trực giao và x∗ ∈ Lf(yk) nên số hạng cuối cùng của (2.6) không dương, tức là: 2 tk 〈 PLf (yk)(x k)− x∗, PLf (yk)(xk)− xk 〉 ≤ 0. (2.7) Từ (2.6), (2.7) và ∀k ∈ N ta suy ra: ‖ xk+1 − x∗ ‖2 ≤‖ xk − x∗ ‖2 + tk2 ‖ PLf (yk)(xk)− xk ‖2 − − 2 tk ‖ xk − PLf (yk)(xk) ‖2 = ‖ xk − x∗ ‖2 −tk(2− tk) ‖ xk − PLf (yk)(xk) ‖2 ≤‖ xk − x∗ ‖2 . (2.8) Vậy dãy {‖ xk − x∗ ‖}k≥0 không tăng và do đó hội tụ. b, Theo kết quả a, ta có dãy {‖ xk − x∗ ‖}k≥0 hội tụ. Mặt khác, ‖ xk ‖= ‖ xk − x∗ + x∗ ‖≤‖ xk − x∗ ‖ + ‖ x∗ ‖. ⇒ {xk}k≥0 bị chặn. c, Ta viết lại (2.8) dạng: tk(2− tk) ‖ xk − PLf (yk)(xk) ‖2≤‖ xk − x∗ ‖2 − ‖ xk+1 − x∗ ‖2 . (2.9) Vì 0 < α ≤ tk ≤ 2− α với 0 < α < 1 ta có 0 < α(2− α) ≤ tk(2− tk). Từ (2.9) ta suy ra: α(2− α) ‖ xk − PLf (yk)(xk) ‖2≤‖ xk − x∗ ‖2 − ‖ xk+1 − x∗ ‖2 . (2.10) Từ (2.10), 0 < α(2− α) và tính hội tụ của {‖ xk − x∗ ‖}k≥0 ta có: lim k→+∞ {xk − PLf(yk)(xk)} = 0. (2.11) Do đó, lim k→+∞ xk+1 − xk tk = 0. Vì 0 < α ≤ tk ≤ 2−α nên (xk+1−xk) → 0 khi k → +∞.  Mệnh đề 2.1.3. [3] Giả sử: i, Dãy {xk}k≥0 bị chặn, ii, lim k→+∞ ‖ xk+1 − xk ‖= 0. Khi đó, dãy {xk}k≥0 hội tụ tới nghiệm x∗ của bài toán cân bằng. 20 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứng minh • Do xk+1 = xk + tk [ PLf(yk)(x k)− xk]⇒ xk+1 − xktk = [PLf(yk)(xk)− xk]. Từ giả thiết ii, ta suy ra: lim k→+∞ {xk − PLf(yk)(xk)} = 0. • Chứng minh {yk}k≥0 bị chặn? Theo giả thiết ta có dãy {xk}k≥0 bị chặn, do vậy ∃ r > 0 sao cho: ‖ xk ‖≤ r, ∀k ∈ N. Từ công thức (2.1d) của thuật toán chiếu 2.1: rk+1 = max{rk, ‖ xk+1 ‖} ta có: rk = max{‖ x0 ‖, . . . , ‖ xk ‖}. Do đó, rk ≤ r, ∀k ∈ N. Lại từ (2.1a) ta có Kk = {x ∈ K : ‖ x ‖≤ rk + 1} nên Kk ⊂ B(0, r + 1). Từ (2.1b) ta có max y∈Kk f(y, xk)− k ≤ f(yk, xk), yk ∈ Kk, ∀k ∈ N, do vậy: ‖ yk ‖≤ r + 1. Do đó, {yk}k≥0 bị chặn. • Giả sử x là điểm giới hạn của dãy {xk}k≥0 ⊂ K, với K đóng, x ∈ K. Tồn tại dãy con {xkn}kn≥0 của dãy {xk}k≥0 thoả mãn: lim kn→+∞ xkn = x. Tương ứng ta xét dãy con {ykn}kn≥0 cũng bị chặn. Do đó, tồn tại dãy con {yknp}knp≥0 của dãy {ykn}kn≥0 hội tụ, giả sử hội tụ tới y, tức là: lim knp→+∞ yknp = y. Để cho ngắn gọn, ta kí hiệu yknp ≡ ykn, ta cũng làm tương tự với xknp , ta kí hiệu xknp ≡ xkn. • Ta chứng minh f(y, x) = 0? Thật vậy, từ trên có lim k→+∞ {xk−PLf(yk)(xk)} = 0 nên limk→+∞PLf(yk)(x k) = x. 21 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Do tính liên tục của f nên suy ra: f(y, x) = f ( lim kn→+∞ ykn, lim kn→+∞ PLf(ykn )(x kn) ) = lim kn→+∞ f ( ykn, PLf(ykn )(x kn) ) ≤ 0. (2.12) Trong đó, PLf(ykn )(x kn) ∈ Lf(ykn) = {x ∈ K | f(ykn, x) ≤ 0}. Từ (2.1a), (2.1d) có xk ∈ Kk, ∀k ∈ N. Từ định nghĩa 2.1.1 và (2.1b), với ∀k ∈ N ta có: 0 = f(xk, xk) ≤ max y∈Kk f(y, xk) ≤ f(yk, xk) + k. (2.13) Do lim k→+∞ k = 0 và f liên tục nên từ (2.12) suy ra: 0 ≤ lim kn→+∞ {f(ykn, xkn) + kn} = f( lim kn→+∞ ykn, lim kn→+∞ xkn) + lim kn→+∞ kn = f(y, x). (2.14) Kết hợp (2.12), (2.14) suy ra: f(y, x) = 0. (2.15) • Với mọi 0 < δ < 1, x ∈ [intB(0, r∗ + 1− δ)] ∩K, với r∗ = sup k∈N rk? Do rk bị chặn nên r ∗ = sup k∈N rk là hữu hạn. Với 0 < δ < 1 xét B(0, r∗ + 1− δ) ≡ B(δ) Từ (2.1d) có ‖ xk ‖≤ rk ≤ r∗ < r∗+1−δ, ∀k ∈ N, nên suy ra x ∈ intB(δ). Vậy x ∈ [intB(0, r∗ + 1− δ)] ∩K. • Cho B̂(δ) = B(δ) ∩ K, xét bài toán cân bằng (ÊPδ) với hàm f và tập chấp nhận B̂(δ): Tìm x̂ ∈ (ÊPδ) thoả mãn f(x̂, y) ≥ 0, ∀y ∈ B̂(δ) (ÊPδ) Khi đó ta có khẳng định sau: x ∈ B̂(δ) là nghiệm của bài toán (ÊPδ), với 0 < δ < 1. Thật vậy, lấy dãy {rk}k∈N không giảm: rk ≤ rk+1. Chọn k0 ∈ N thoả mãn 22 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn rk0 ≥ r∗ − δ. Khi đó: r∗ + 1− δ ≤ rk + 1, ∀k ≥ k0. Do đó, B̂(δ) ⊂ Kk, ∀k ≥ k0. Lấy z ∈ B̂(δ), ta có z ∈ Kk, ∀k ≥ k0. Vì vậy, f(z, xk) ≤ max y∈Kk f(y, xk) ≤ f(yk, xk) + k, ∀k ≥ k0. (2.16) Do tính liên tục của f , công thức (2.14), (2.15), (2.16) ta có: f(z, x) = f(z, lim kn→+∞ xkn) = lim kn→+∞ f(z, xkn) (2.16) ≤ lim kn→+∞ {f(ykn, xkn) + kn} = f(y, x) = 0. (2.17) Tức là, f(z, x) ≤ 0, ∀z ∈ B̂(δ). (2.18) Từ (2.18), do x ∈ K, với mỗi 0 < δ < 1 ta có: x ∈ ⋂ x∈B̂(δ) Lf(z). Theo định lí 2.1.1 suy ra x là nghiệm của bài toán (ÊP δ) với 0 < δ < 1. • x là nghiệm của bài toán cân bằng 1.1? Cho x là nghiệm của bài toán (ÊPδ), tức là f(x, y) ≥ 0, ∀y ∈ B̂(δ). Theo giả thiết có f(x, x) = 0. Từ các điều trên ta khẳng định x là nghiệm của bài toán tối ưu lồi: min y∈B̂(δ) f(x, y). (2.19) Hàm g : Rn → R ∪ {+∞} có dạng: g(y) = f(x, y) si y ∈ K,+∞ si y 6∈ K. 23 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Với hàm g vừa định nghĩa ta có thể viết lại (2.19) như sau: min y∈B(δ) g(y). Ta đã chứng minh được x là điểm cực tiểu của g trên B(δ), thuộc phần trong của B(δ). Lại do g là hàm lồi, nên x là điểm cực tiểu không ràng buộc của g. Tức là, g(x) ≤ g(y), ∀y ∈ Rn, trong đó g(x) = f(x, x) = 0 ≤ g(y) = f(x, y), ∀y ∈ K. Vậy x là nghiệm của bài toán cân bằng 1.1. •Ta chứng minh lim k→+∞ xk = x ? Ta đã chứng minh được x ∈ ⋂ z∈B̂(δ) Lf(z). Vì thế f(z, x) ≤ 0, ∀z ∈ K, ‖ z ‖≤ r∗ + 1− δ. Do δ ∈ [0, 1] ta có f(z, x) ≤ 0, ∀z ∈ K, ‖ z ‖≤ r∗ + 1. Lại do tính liên tục của hàm f nên f(z, x) ≤ 0, ∀z ∈ K, ‖ z ‖≤ r∗ + 1. Do yk ∈ Kk, ∀k ∈ N nên ‖ yk ‖≤ rk+1 ≤ r∗+1 ⇒ f(yk, x) ≤ 0, ∀k ∈ N. ⇒ x ∈ +∞⋂ k=0 Lf(y k). Theo mệnh đề 2.1.2a, ta có {‖ xk − x}k≥0 hội tụ. Vì thế dãy con {‖ xkn−x}kn≥0 hội tụ về 0, nên {‖ xk−x}k≥0 hội tụ về 0, tức là lim k→+∞ xk = x.  Định lí sau đây sẽ chỉ ra tính chất hội tụ thuật toán chiếu liên tiếp 2.1. Định lý 2.1.2. [2] Cho {xk}k≥0 và {yk}k≥0 ⊂ K là dãy được tính từ thuật toán 2.1. Khi đó: a, Nếu +∞⋂ k=0 Lf(y k) 6= ∅, (2.20) thì {xk}k≥0 hội tụ đến nghiệm của bài toán cân bằng. b, Nếu bài toán cân bằng vô nghiệm thì {xk}k≥0 không hội tụ. 24 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứng minh a, Do +∞⋂ k=0 Lf(y k) 6= ∅ và theo mệnh đề 2.1.2, 2.1.3 suy ra {xk}k≥0 hội tụ đến nghiệm của bài toán cân bằng. b, Bằng phản chứng, giả sử {xk}k≥0 ⊂ Rn hội tụ tới nghiệm x∗ ∈ Rn. Do {xk}k≥0 hội tụ nên {xk}k≥0 bị chặn và lim k→+∞ {xk+1 − xk} = 0. Phần còn lại của chứng minh được lập luận như trong chứng minh mệnh đề 2.1.3. Do đó, x∗ là nghiệm của bài toán cân bằng 1.2.1. Mâu thuẫn với giả thiết. Vậy bài toán cân bằng vô nghiệm.  Hệ quả 2.1.1. [2] Nếu bài toán đối ngẫu có nghiệm thì {xk}k≥0 hội tụ tới nghiệm của bài toán cân bằng. Chứng minh Do bài toán đối ngẫu có nghiệm nên ⋂ y∈K Lf(y) 6= ∅ nên +∞⋂ k=0 Lf(y k) 6= ∅, vì ⋂ y∈K Lf(y) ⊂ +∞⋂ k=0 Lf(y k). Theo định lí 2.1.2 suy ra điều phải chứng minh. Hệ quả 2.1.2. [2] Cho {xk}k≥0, {yk}k≥0 là các dãy được tính từ thuật toán 2.1. Nếu f là giả đơn điệu và hoặc {xk}k≥0 hoặc {yk}k≥0 bị chặn thì {xk}k≥0 hội tụ đến nghiệm của bài toán cân bằng. Chứng minh Nếu {xk}k≥0 bị chặn thì {yk}k≥0 cũng bị chặn (theo chứng minh mệnh đề 2.1.3). Giả sử {yk}k≥0 bị chặn và theo giả thiết f là giả đơn điệu nên suy ra +∞⋂ k=0 Lf(y k) 6= ∅. Theo định lí 2.1.2 suy ra điều phải chứng minh.  2.2. Phương pháp đạo hàm tăng cường giải bài toán cân bằng Phương pháp đạo hàm tăng cường lần đầu tiên được Korpelevich đề xuất để giải bài toán tìm điểm yên ngựa, sau đó được phát triển cho bài toán bất 25 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn đẳng thức biến phân. Phương pháp đạo hàm tăng cường giải bài toán cân bằng là sự mở rộng của nguyên lí bài toán cân bằng phụ. Nhưng ở phương pháp đạo hàm tăng cường cho phép giải các bài toán không cần giả thiết đơn điệu mạnh cho hàm f mà chỉ yêu cầu hàm này thoả mãn điều kiện Lipschitz. Trước tiên ta định nghĩa bài toán cân bằng phụ. Định nghĩa 2.2.1. [2] Cho L : K ìK → R và  > 0, ta xét bài toán cân bằng phụ sau: Tìm x∗ ∈ K sao cho : f(x∗, y) + L(x∗, y) ≥ 0, ∀y ∈ K (2.21) Mệnh đề 2.2.1. [2] Cho f : K ìK → R với f(x, x) = 0,∀x ∈ K và cho x∗ ∈ K. Giả sử f(x∗, .) : K → R là hàm lồi khả vi. Cho L : KìK → R là hàm lồi, khả vi, không âm trên tập lồi K theo biến thứ hai y (∀x ∈ K) và thoả mãn: a, L(x, x) = 0,∀x ∈ K; b, ∇yL(x, x) = 0,∀y ∈ K. Khi đó, x∗ ∈ K là nghiệm của bài toán cân bằng khi và chỉ khi nó là nghiệm của bài toán cân bằng phụ (2.21). Chứng minh (⇒) Do x∗ ∈ K là nghiệm của bài toán cân bằng nên f(x∗, y) ≥ 0 với ∀y ∈ K. Ta có  > 0 ⇒ f(x∗, y) ≥ 0,∀y ∈ K, ∀x∗ ∈ K. Vì L : K ìK → R là hàm lồi, khả vi, không âm trên tập lồi K thoả mãn: a, L(x, x) = 0,∀x ∈ K; b, ∇yL(x, x) = 0,∀y ∈ K. nên L(x∗, y) ≥ 0,∀x∗, y ∈ K ⇒ f(x∗, y) + L(x∗, y) ≥ 0,∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán cân bằng phụ. (⇐) Cho x∗ ∈ K là nghiệm của bài toán cân bằng phụ, ta sẽ chứng minh x∗ ∈ K cũng là nghiệm của bài toán cân bằng. Do x∗ ∈ K là nghiệm của bài toán cân bằng phụ nên nó cũng là nghiệm 26 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn tối ưu của bài toán: min y∈K {f(x∗, y) + L(x∗, y)}. Mặt khác, ta có f(x∗, y) + L(x∗, y) ≥ 0,∀y ∈ K, ⇒ f(x∗, x∗) + L(x∗, x∗) = 0. Ta có x∗ ∈ K là nghiệm tối ưu của bài toán min y∈K {f(x∗, y) + L(x∗, y)}. ⇔ 〈∇yf(x∗, x∗) +∇yL(x∗, x∗), y − x∗〉 ≥ 0,∀y ∈ K. Theo giả thiết, ∇yL(x, x) = 0,∀y ∈ K nên〈 ∇yf(x∗, x∗), y − x∗ 〉 ≥ 0,∀y ∈ K. ⇔ 〈∇yf(x∗, x∗), y − x∗〉 ≥ 0,∀y ∈ K. >0⇔ 〈∇yf(x∗, x∗), y − x∗〉 ≥ 0,∀y ∈ K. Do K là hàm lồi và theo tính chất lồi khả vi của f(x∗, .) : K → R nên theo định nghĩa ta có: f(x∗, y) ≥ f(x∗, x∗) + 〈∇yf(x∗, x∗), y − x∗〉,∀y ∈ K. ⇒ f(x∗, y) ≥ f(x∗, x∗) = 0,∀y ∈ K. Vậy x∗ ∈ K là nghiệm của bài toán cân bằng, mệnh đề được chứng minh. Chú ý Nếu G : K → R là hàm lồi mạnh, khả vi và L(x, y) = G(y)− G(x)− 〈∇G(x), y − x〉,∀x, y ∈ K. (2.22) thì hàm L thoả mãn các tính chất của mệnh đề 2.2.1. Hệ quả 2.2.1. [2] x∗ ∈ K là nghiệm của bài toán cân bằng khi và chỉ khi nó là nghiệm tối ưu của bài toán tối ưu: min y∈K {f(x∗, y) + L(x∗, y)}. Hệ quả 2.2.2. [2] Cho f : K ìK → R với f(x, x) = 0,∀x ∈ K. Giả sử f(x∗, .) : K → R là hàm lồi, khả vi và  > 0. Khi đó, x∗ ∈ K là nghiệm của bài toán cân bằng khi và chỉ khi x∗ ∈ K là nghiệm của bài toán cân bằng phụ (2.21) và hàm L được định nghĩa theo (2.22).. Nhận xét ? x∗ ∈ K là nghiệm của bài toán cân bằng khi và chỉ khi nó là nghiệm của 27 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn bài toán tối ưu: min y∈K {ξf(x∗, y) + G(y)− G(x∗)− 〈∇G(x∗), y − x∗〉}. Hay min y∈K {ξf(x∗, y) + G(y)− 〈∇G(x∗), y〉}. ? Do G là hàm lồi mạnh nên nghiệm của bài toán: min y∈K {ξf(x∗, y) + G(y)− 〈∇G(x∗), y〉} nếu tồn tại là duy nhất. Trong toàn phần này nếu không nói gì thêm ta giả sử f(x, .) đóng, lồi và khả dưới vi phân trên K, với ∀x ∈ K. Sau đây ta đưa ra thuật toán giải bài toán cân bằng phụ. Thuật toán 2.2 [2] Bước 0: Lấy x0 ∈ K,  > 0 và k := 0; Bước 1: Giải bài toán: min y∈K {f(xk, y) + G(y)− 〈OG(xk), y − xk〉}. (2.22a) có nghiệm tối ưu duy nhất yk. Nếu yk = xk thì thuật toán dừng và kết luận xk là nghiệm của bài toán cân bằng. Trái lại, ta chuyển sang bước 2. Bước 2: Giải bài toán: min y∈K {f(yk, y) + G(y)− 〈OG(xk), y − xk〉}. (2.22b) tìm nghiệm duy nhất xk+1. Bước 3: Lấy k := k + 1 và quay lại bước 1. Bổ đề dưới đây chỉ ra rằng nếu thuật toán 2.2 kết thúc tại bước lặp k nào đó thì ta tìm được nghiệm của bài toán cân bằng. Bổ đề 2.2.1. [6] Nếu thuật toán kết thúc tại điểm lặp xk thì xk là nghiệm của bài toán cân bằng. 28 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứng minh Nếu xk = yk thì do f(x, x) = 0 nên ta có: f(xk, yk) + G(yk)− G(xk)− 〈OG(xk), yk − xk〉} = 0. Do yk = xk là nghiệm của (2.22a), ta có: 0 = f(xk, yk) + G(yk)− G(xk)− 〈OG(xk), yk − xk〉} ≤ f(xk, y) + G(y)− G(xk)− 〈OG(xk), y − xk〉}, ∀y ∈ K. Từ mệnh đề 2.2.1 suy ra xk là nghiệm của bài toán cân bằng.  Ta kí hiệu K∗ là tập nghiệm của bài toán cân bằng và Kd là tập nghiệm của bài toán đối ngẫu (2.1). Định lí sau chỉ ra tính hội tụ của thuật toán. Định lý 2.2.1. [6] Giả sử rằng: i, G lồi mạnh với hệ số β > 0 và khả vi liên tục trên tập mở Ω ⊇ K. ii, Tồn tại hằng số c1 và c2 > 0 thoả mãn: f(x, y) + f(y, x) ≥ f(x, z)− c1 ‖ y − x ‖2 −c2 ‖ z − y ‖2 ∀x, y, z ∈ K. (2.23) Khi đó: a, Với mọi x∗ ∈ Kd, thì l(xk)−l(xk+1) ≥ (β 2 −c1 ) ‖ yk−xk ‖2 +(β 2 −c2 ) ‖ xk+1−yk ‖2 (2.24) với l(y) := G(x∗)− G(y)− 〈∇G(y), x∗ − y〉, ∀y ∈ K. b, Giả sử f là nửa liên tục dưới trên K ì K, f(., y) là nửa liên tục trên trên K và 0 <  < min { β 2c1 , β 2c2 } , thì dãy {xk} bị chặn và mọi điểm tụ của nó là nghiệm của bài toán cân bằng. Hơn thế, nếu Kd = K∗ (trong trường hợp này f là giả đơn điệu trên K) thì {xk} hội tụ tới nghiệm của bài toán cân bằng. Chứng minh a, Lấy x∗ ∈ Kd bất kì. Theo định nghĩa của hàm l và cho xk, xk+1 ∈ K, 29 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn ta có: l(xk)− l(xk+1) = G(xk+1)− G(xk) + 〈∇G(xk+1), x∗ − xk+1〉 − 〈∇G(xk), x∗ − xk〉 = G(xk+1)− G(xk) + 〈∇G(xk+1)−∇G(xk), x∗ − xk+1〉 − 〈∇G(xk), xk+1 − xk〉. (2.25) Ta có xk+1 là nghiệm của bài toán: min y∈K {f(yk, y) + G(y)− G(xk)− 〈∇G(xk), y − xk〉}, nếu và chỉ nếu 0 ∈ ∂2 { f(yk, xk+1)+G(xk+1)−G(xk)−〈∇G(xk), xk+1−xk〉}+NK(xk+1). với NK(x) là nón pháp tuyến của K tại x ∈ K. Do f(yk, .) là khả dưới vi phân và G là lồi mạnh, khả vi trên K nên theo định lí Moreau-Rockafella ∃w ∈ ∂2f(yk, xk+1) thoả mãn:〈∇G(xk+1)−∇G(xk), y − xk+1〉 ≥ 〈w, xk+1 − y〉, y ∈ K. Mặt khác ta có:〈∇G(xk+1)−∇G(xk), y − xk+1〉 ≥ f(yk, xk+1)− f(yk, y), ∀y ∈ K. Nếu x∗ = y thì bất đẳng thức trên có dạng:〈∇G(xk+1)−∇G(xk), x∗ − xk+1〉 ≥ f(yk, xk+1)− f(yk, x∗). Do x∗ là nghiệm của bài toán (2.1) nên f(yk, x∗) ≤ 0. Vì vậy〈∇G(xk+1)−∇G(xk), x∗ − xk+1〉 ≥ f(yk, xk+1). (2.26) Từ (2.23) với x = xk, y = yk và z = xk+1, khi đó (2.26) được viết:〈∇G(xk+1)−∇G(xk), x∗ − xk+1〉 ≥ f(xk, xk+1)− f(xk, yk) −  c1 ‖ yk − xk ‖2 −  c2 ‖ xk+1 − yk ‖2 . (2.27) 30 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Từ bước 1 của thuật toán 2.2 ta có yk là nghiệm của bài toán: min y∈K {f(xk, y) + G(y)− G(xk)− 〈∇G(xk), y − xk〉}, nên có 0 ∈ ∂2 { f(xk, yk) + G(yk)− G(xk)− 〈∇G(xk), yk − xk〉}+ NK(yk). Tương tự ta thấy rằng f(xk, y)− f(xk, yk) ≥ 〈∇G(yk)−∇G(xk), yk − y〉, y ∈ K. Với y = xk+1 ta có: f(xk, xk+1)− f(xk, yk) ≥ 〈∇G(yk)−∇G(xk), yk − xk+1〉. (2.28) Từ (2.25), (2.27), (2.28) ta suy ra l(xk)− l(xk+1) ≥ G(xk+1)− G(xk)− 〈∇G(xk), xk+1 − xk〉 + 〈∇G(yk)−∇G(xk), yk − xk+1〉 −  c1 ‖ yk − xk ‖2 − c2 ‖ xk+1 − yk ‖2 = G(xk+1)− G(xk)− 〈∇G(xk), yk − xk〉 + 〈∇G(yk), yk − xk+1〉 −  c1 ‖ yk − xk ‖2 − c2 ‖ xk+1 − yk ‖2 = [G(xk+1)− G(yk)− 〈∇G(yk), xk+1 − yk〉] + [G(yk)− G(xk)− 〈∇G(xk), yk − xk〉] −  c1 ‖ yk − xk ‖2 − c2 ‖ xk+1 − yk ‖2 . (2.29) Vì G lồi mạnh với hệ số β nên với mọi x, y ta có: G(y)− G(x)− 〈∇G(x), y − x〉 ≥ β 2 ‖ y − x ‖2, ∀x, y ∈ K. (2.30) Từ (2.29), (2.30) và ∀k ≥ 0 ta có: l(xk)− l(xk+1) ≥ (β 2 −  c1 ) ‖ yk − xk ‖2 +(β 2 −  c2 ) ‖ xk+1 − yk ‖2 . (2.31) 31 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Ta có điều phải chứng minh. b, Từ giả thiết 0 <  < min { β 2c1 , β 2c2 } , ta có: β 2 −  c1 > 0, β 2 −  c2 > 0. Vì vậy từ bất đẳng thức (2.31) ta có khẳng định sau: l(xk)− l(xk+1) ≥ (β 2 −  c1 ) ‖ yk − xk ‖2≥ 0, ∀k. (2.32) Do đó, dãy {l(xk)k≥0} là dãy không tăng. Nó bị chặn dưới bởi 0 nên nó hội tụ đến l∗.Trong (2.32) cho k chạy từ 0 đến m và cộng lại ta có: (β − c1) m∑ k=0 ‖ yk − xk ‖2≤ l(x0)− l(xk+1), ∀m ≥ 0. Dãy {l(xk)}k≥0 hội tụ, cho m →∞ từ bất đẳng thức cuối có: ∞∑ k=0 ‖ yk − xk ‖2< ∞. Từ đó kéo theo: lim k→+∞ ‖ yk − xk ‖= 0. (2.33) Do G là β−lồi mạnh và từ định nghĩa của l(xk) ta có thể viết: 0 ≤ β 2 ‖ x∗ − xk ‖2≤ l(xk), ∀k Vậy {l(xk)} hội tụ và dãy {xk}k≥0 bị chặn nên nó có ít nhất một điểm tụ. Gọi x ∈ K là điểm tụ và {xki}i≥0 là dãy con của {xk} nên có: lim i→+∞ xki = x. Từ (2.33) ta có lim i→+∞ yki = x. Quay lại bước 1 của thuật toán 2.2, ta có: f(xki, y) + G(y)− G(xki)− 〈∇G(xki), y − xki〉 ≥ f(xki, yki) + G(yki)− G(xki)− 〈∇G(xki), yki − xki〉, ∀y ∈ K. 32 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Vì f là nửa liên tục dưới trên K ìK, f(., y) là nửa liên tục trên trên K và f(x, x) = 0, cho i → +∞ ta có; f(x, y) + G(y)− G(x)− 〈∇G(x), y − x〉 ≥ 0, ∀y ∈ K, với x là nghiệm của bài toán 2.22 và L(x, y) = G(y)−G(x)〈∇G(x), y−x〉. Theo mệnh đề 2.2.1 thì x là nghiệm của bài toán cân bằng. Giả sử rằng Kd = K∗, ta khẳng định dãy {xk}k≥0 hội tụ đến x. Thật vậy, theo định nghĩa của l(xk) với x∗ = x ∈ Kd, có l(x) = 0. Vì vậy, do G là β− lồi mạnh nên ta có thể viết: l(xk)− l(x) = G(x)−G(xk)−〈∇G(xk), xk−x〉 ≥ β 2 ‖ xk−x ‖2, ∀k ≥ 0. (2.34) Mặt khác, do {l(xk)}k≥0 không tăng và l(xki) → l(x), ta có l(xk) → l(x) khi k → +∞. Vì vậy, từ (2.34) suy ra lim k→+∞ xk = x ∈ K∗.  Chú ý Điều kiện (2.23) không đủ để suy ra f là liên tục. Trong thực tế, nếu f(x, y) = ϕ(y)−ϕ(x) thì rõ ràng (2.21) luôn đúng với ∀c1 ≥ 0, c2 ≥ 0 và hàm ϕ tuỳ ý. Cho K là tập lồi đa diện dạng: K := {x ∈ Rn : Ax ≤ b}. (2.35) và hàm f : K ìK → R ∪ {+∞} có dạng: f(x, y) := 〈 F (x) + Qy + q, y − x〉, (2.36) với F : K → Rn, Q ∈ Rnìn là ma trận đối xứng xác định dương và q ∈ Rn. Do Q là đối xứng nửa xác định dương, f(x, .) là lồi với mọi x ∈ K. Ta sẽ minh hoạ thuật toán 2.2 cho lớp bài toán cân bằng này. Trước tiên ta có một số kết quả sau: Bổ đề 2.2.2. [5] Nếu f : K → Rn là τ−đơn điệu mạnh trên K. Khi đó: a, f đơn điệu trên K khi τ =‖ Q ‖. b, f là (τ− ‖ Q ‖)−đơn điệu mạnh trên K khi τ >‖ Q ‖. 33 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chứng minh Từ định nghĩa của hàm f ta có: f(x, y) + f(y, x) = 〈 Q(y − x), y − x〉− 〈F (y)− F (x), y − x〉. (2.37) Mặt khác, 〈 Q(y − x), y − x〉 ≤‖ Q ‖‖ y − x ‖2 . (2.38) Do F là τ−đơn điệu mạnh trên K, tức là〈 F (y)− F (x), y − x〉 ≥ τ ‖ y − x ‖2, Từ (2.37), (2.38) suy ra f(x, y) + f(y, x) ≤ 0, khi τ =‖ Q ‖. Vậy f đơn điệu trên K khi τ =‖ Q ‖. Khi τ >‖ Q ‖ từ (2.37), (2.38) ta suy ra f(x, y)+f(y, x) ≤‖ Q ‖‖ y−x ‖2 −τ ‖ y−x ‖2= −(τ− ‖ Q ‖) ‖ y−x ‖2 . Vậy f là (τ− ‖ Q ‖)− đơn điệu mạnh trênK khi τ >‖ Q ‖.  Bổ đề 2.2.3. [5] Nếu F là liên tục L−Lipschitz trên K, tức là ‖ F (y)− F (x) ‖≤ L ‖ y − x ‖ ∀x, y ∈ K, thì f thoả mãn tiêu chuẩn kiểu Lipschitz (2.23), tức là ta có: f(x, y) + f(y, z) ≥ f(x, z)− c1 ‖ y − x ‖2 −c2 ‖ z − y ‖2 ∀x, y, z ∈ K, với c1 > 0, c2 > 0 thoả mãn: 2 √ c1c2 ≥ L+ ‖ Q ‖ . Chứng minh Với mọi x, y, z ∈ K ta có: f(x, y) + f(y, z)− f(x, z) = 〈F (y)− F (x), z = y〉+ 〈Q(y − z), y − x〉, Theo bất đẳng thức Cauchy-Schwartz, ta có:〈 Q(y − z), y − x〉 ≥ − ‖ Q ‖‖ z − y ‖‖ y − x ‖ . và 〈 F (y)− F (x), z − y〉 ≥ − ‖ F (y)− F (x) ‖‖ z − y ‖ . 34 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Do F là L− Lipschitzs, ta có thể viết: − ‖ F (y)− F (x) ‖‖ z − y ‖≥ −L ‖ y − x ‖‖ z − y | . Do vậy ta suy ra f(x, y) + f(y, z)− f(x, z) ≥ −(L+ ‖ Q ‖) ‖ y − x ‖‖ z − y ‖ . Vì vậy, theo giả thiết có: −(L+ ‖ Q ‖) ‖ y − x ‖‖ z − y ‖≥ −c1 ‖ y − x ‖2 −c2 ‖ z − y ‖2 . Suy ra f(x, y) + f(y, z) ≥ f(x, z)− c1 ‖ y − x ‖2 −c2 ‖ z − y ‖2 .  • Trường hợp đặc biệt, khi F là đơn ánh và F (x) = Px, P ∈ Rnìn, thì hàm f được định nghĩa bởi (2.36) dạng f(x, y) = 〈 Px + Qy + q, y − x〉, (2.39) Ta giả sử rằng ma trận P,Q được chọn thoả mãn Q là đối xứng xác định dương và Q− P là nửa xác định âm. Khi đó, f thoả mãn một số tính chất sau đây: i, f đơn điệu, f(., y) liên tục và f(x, .) khả vi trên tập lồi K. ii, Với mọi x, y, z ∈ K ta có: f(x, y) + f(y, z) ≥ f(x, z)− c1 ‖ z − y ‖2 −c2 ‖ y − x ‖2, (2.40) với c1 = c2 = 1 2 ‖ P −Q ‖ . Thật vậy, với mọi x, y, z ∈ K, do Q− P là nửa xác định âm nên ta có: f(x, y) + f(y, x) = 〈 (Q− P )(y − x), y − x〉 ≤ 0. Do đó, f là đơn điệu trên K. Rõ ràng, f(x, .) khả vi, do Q đối xứng nửa xác định dương nên f(x, .) lồi với mọi x. 35 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Từ ii, ta thấy rằng, với mọi x, y, z ∈ K có: f(x, y) + f(y, z)− f(x, z) = = 〈 Px + Qy + q, y − x〉+ 〈Py + Qz + q, z − y〉− 〈Px + Qz + q, z − x〉 = 〈 Px + Qy, y − x〉+ 〈Py + Qz, z − y〉− 〈Px + Qz, z − x〉 + 〈 q, y − x + z − y − (z − x)〉 = 〈 Px + Qy, y − x〉+ 〈Py + Qz, z − y〉− 〈Px + Qz, z − x〉 = 〈 Px, y − x− (z − x)〉+ 〈Qz, z − y − (z − x)〉+ 〈Qy, y − x〉+ + 〈 Py, z − y〉 = 〈 Px, y − z〉+ 〈Qz, x− y〉+ 〈Qy, y − x〉+ 〈Py, z − y〉 = 〈 P (y − x), z − y〉+ 〈Q(z − y), x− y〉 = 〈 P (y − x), z − y〉+ 〈QT (x− y), z − y〉 = 〈 P (y − x), z − y〉+ 〈Q(x− y), z − y〉 doQ = QT = 〈 (P −Q)(y − x), z − y〉. Từ đó suy ra: f(x, y) + f(y, z)− f(x, z) = 〈(P −Q)(y − x), z − y〉 ≥ −2‖ P −Q ‖ 2 ‖ y − x ‖‖ z − y ‖ ≥ −‖ P −Q ‖ 2 ‖ y − x ‖2 −‖ P −Q ‖ 2 ‖ z − y ‖2 Theo cách đặt, c1 = c2 = 1 2 ‖ P −Q ‖, ta suy ra (2.40). Ví dụ 2.2.1. [5] áp dụng thuật toán 2.2 với hàm chính quy hoá bậc hai G(x) := 12 ‖ x ‖2 để giải bài toán cân bằng. Trong đó, f(x, y) := 〈 Px−Qy + q, y − x〉 và K := {x ∈ Rn : Ax ≤ b}. Trong trường hợp này, theo thuật toán tại bước 1 ta có bài toán con: min y∈K {f(x, y) + 1 2 ‖ y − x ‖2}. 36 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Theo (2.39) f(x, .) là hàm lồi toàn phương, nên bài toán con có thể giải trên MATLAB Optimization Toolbox. Với n = 5 và ma trận P,Q có dạng: Q =  1.6 1 0 0 0 1 1.6 0 0 0 0 0 1.5 1 0 0 0 1 1.5 0 0 0 0 0 2  ; P =  3.1 2 0 0 0 2 3.6 0 0 0 0 0 3.5 2 0 0 0 2 3.3 0 0 0 0 0 3  Với q = (1,−2,−1, 2,−1)T , K = { x ∈ R5 : 5∑ i=1 xi ≥ −1,−5 ≤ xi ≤ 5, i = 1, . . . , 5 } , c1 = c2 = 1 2 ‖ Q − P ‖= 1.4525,  = 12c1 = 0.7262, x0 = (1, 3, 1, 1, 2)T và ζ = 10−3 ta có: k xk1 x k 2 x k 3 x k 4 x k 5 0 1.00000 3.00000 1.00000 1.00000 2.00000 1 -0.34415 1.59236 0.68742 -0.15427 0.63458 2 -0.67195 1.10393 0.65016 -0.57872 0.30562 3 -0.73775 0.92351 0.66742 -0.74459 0.22567 4 -0.74236 0.85342 0.68785 -0.81261 0.20624 5 -0.73668 0.82486 0.70195 -0.84184 0.20152 6 -0.73168 0.81276 0.71030 -0.85493 0.20037 7 -0.72864 0.80747 0.71491 -0.86100 0.20009 8 -0.72700 0.80511 0.71737 -0.86389 0.20002 9 -0.72617 0.80403 0.71865 -0.86529 0.20001 10 -0.72576 0.80354 0.71931 -0.86598 0.20000 Nghiệm xấp xỉ sau 10 bước lặp là: x10 = (−0.72576, 0.80354, 0.71931,−0.86598, 0.20000)T . 37 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Nếu chọn P =  3.1 2.0 0.0 0.0 0.0 2.0 3.6 0.0 0.0 0.0 0.0 0.0 3.5 2.0 0.0 0.0 0.0 2.0 3.3 0.0 0.0 0.0 0.0 0.0 2.0  Khi đó giá trị riêng của ma trận Q− P là: {−0.7192,−2.7808, 2.9050,−0.8950, 0.0000} Theo i, của bổ đề 2.2.2 có f đơn điệu. Trong trường hợp này, máy tính tính được: k xk1 x k 2 x k 3 x k 4 x k 5 0 1.00000 3.00000 1.00000 1.00000 2.00000 1 -0.34006 1.59892 0.69395 -0.14884 0.69814 2 -0.67118 1.10637 0.65254 -0.57720 0.36476 3 -0.73773 0.92446 0.66833 -0.74422 0.27939 4 -0.74245 0.85380 0.68821 -0.81255 0.25753 5 -0.73676 0.82503 0.70210 -0.84185 0.25193 6 -0.73172 0.81283 0.71037 -0.85495 0.25049 7 -0.72866 0.80751 0.71494 -0.86102 0.25013 8 -0.72701 0.80512 0.71738 -0.86390 0.25003 9 -0.72618 0.80404 0.71866 -0.86530 0.25001 10 -0.72577 0.80354 0.71932 -0.86599 0.25000 và tính được nghiệm xấp xỉ là x10 = {−0.72577, 0.80354, 0.71932,−0.86599, 0.25000}T với ζ = 10−3. Kết luận chương Chương này giới thiệu về phương pháp chiếu và phương pháp đạo hàm tăng 38 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn cường giải bài toán cân bằng. Đồng thời, ta xét một ví dụ minh hoạ việc ứng dụng phương pháp đạo hàm tăng cường vào giải bài toán cân bằng. 39 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Chương 3 Phương pháp hàm đánh giá Một phương pháp hiệu chỉnh cơ bản để giải bài toán cân bằng là phương pháp hàm đánh giá. Tức là, ta quy việc giải bài toán cân bằng về việc giải bài toán cực trị. Cách tiếp cận theo hàm đánh giá được nghiên cứu và áp dụng rộng rãi để giải bài toán cân bằng. Chương này trình bày cơ sở lí thuyết và thuật toán hiệu chỉnh bài toán cân bằng theo phương pháp hàm đánh giá của Auslender và Fukushima. Nội dung chủ yếu của chương được tham khảo trong [2], [9]. Chúng ta vẫn xét bài toán cân bằng: Tìm x∗ ∈ K sao cho f(x∗, y) ≥ 0, ∀y ∈ K, (1.1) trong đó, f : K ìK → R là một hàm thoả mãn f(x, x) = 0, ∀x ∈ K. Như ta đã biết (chương 1), bài toán cân bằng (1.1) tương đương với nhiều bài toán quan trọng khác như: bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán bù,... Bổ đề sau đây cho ta dạng minimax của bài toán cân bằng (1.1). Bổ đề 3.0.4. [2] Cho f : K ìK → R với f(x, x) = 0,∀x ∈ K. Khi đó, các mệnh đề sau là tương đương: a, ∃x∗ ∈ K sao cho f(x∗, y) ≥ 0, ∀y ∈ K. b, min x∈K { sup y∈K [− f(x, y)]} = 0. c, x∗ ∈ K là nghiệm của bài toán: min y∈K f(x∗, y). Chứng minh (a⇒ b) Theo giả thiết ta có f(x, x) = 0,∀x ∈ K. ⇒ inf y∈K f(x, y) ≤ 0,∀x ∈ K 40 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn ⇒ sup x∈K { inf y∈K f(x, y)} ≤ 0. Mặt khác, có x∗ ∈ K nên ta suy ra được sup x∈K { inf y∈K f(x, y)} ≥ inf y∈K f(x∗, y). Theo phần a, ta lại có f(x∗, y) ≥ 0, ∀y ∈ K ⇒ inf y∈K f(x∗, y) ≥ 0 ⇒ 0 ≤ inf y∈K f(x∗, y) ≤ sup x∈K { inf y∈K f(x, y)} ⇒ max x∈K { inf y∈K f(x, y)} = sup x∈K { inf y∈K f(x, y)} = 0 Vậy min x∈K {sup y∈K [−f(x, y)]} = 0. (b⇒ a) Do min x∈K {sup y∈K [−f(x, y)]} = 0 ⇒ ∃x∗ ∈ K : sup y∈K [−f(x∗, y)] = min x∈K {sup y∈K [−f(x, y)]} = 0 ⇒ −f(x∗, y) ≤ 0,∀y ∈ K ⇒ f(x∗, y) ≥ 0,∀y ∈ K. (c⇔ a) Do x∗ ∈ K là nghiệm của bài toán min y∈K f(x∗, y) ⇔ f(x∗, y) ≥ f(x∗, x∗) = 0 (do f(x, x) = 0,∀x ∈ K), ∀y ∈ K ⇔ f(x∗, y) ≥ 0,∀y ∈ K.  Nhận xét Theo bổ đề trên thì x∗ ∈ K là nghiệm của bài toán cân bằng (1.1) khi và chỉ khi nó là nghiệm của bài toán tối ưu: min x∈K { sup y∈K [− f(x, y]}. (3.1) Xuất phát từ nhận xét trên, người ta đã đưa ra khái niệm hàm đánh giá và hướng tới việc xây dựng thuật toán hàm đánh giá giải bài toán cân bằng. Định nghĩa 3.0.2. [9] Cho K là tập đóng của Rn. Khi đó, hàm g : K → R được gọi là hàm đánh giá của bài toán cân bằng nếu và chỉ nếu: a, g(x) ≥ 0, ∀x ∈ K, b, x∗ ∈ K, g(x∗) = 0 ⇔ x∗ là nghiệm của bài toán cân bằng. Nhận xét ? Từ định nghĩa 3.0.2 ta thấy hàm: g(x) := sup y∈K [−f(x, y)] (3.2) 41 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn là hàm đánh giá của bài toán cân bằng (1.1). ? Đối với bài toán bất đẳng thức biến phân, ta có hàm đánh giá: g(x) := sup y∈K {− 〈T (x), y − x〉} = sup y∈K 〈 T (x), x− y〉 (3.3) hàm đánh giá (3.3) gọi là hàm đánh giá A.Auslender [6]. Trong trường hợp tổng quát hàm đánh giá này nhìn chung không khả vi. Vấn đề xây dựng hàm đánh giá khả vi, liên tục cho bài toán bất đẳng thức biến phân đã được đề xuất đầu tiên bởi M.Fukushima [8] và được phát triển tiếp theo bởi D.L.Zhu và P.Marcotte. D.L.Zhu và P.Marcotte đã chứng minh được rằng: g(x) := max y∈K {〈 T (x), x− y〉− L(x, y)} (3.4) là hàm đánh giá khả vi, liên tục cho bài toán bất đẳng thức biến phân, với điều kiện L : K ì K → R là một hàm không âm, khả vi liên tục và lồi mạnh trên tập lồi K theo biến y và thoả mãn: a,L(x, x) = 0, ∀x ∈ K, b,∇yL(x, x) = 0, ∀y ∈ K. Trong trường hợp đặc biệt, L(x, y) := 12 〈 x − y,M(x − y)〉 với M là ma trận đối xứng xác định dương cấp n, thì đó chính là hàm đánh giá được chỉ ra bởi Fukushima [9]. 3.1. Hàm đánh giá A.Auslender Nhìn chung, hàm đánh giá Auslender thường không khả vi [9]. Do đó, để có thể áp dụng phương pháp hàm đánh giá giải bài toán cân bằng ta cần các điều kiện để một hàm đánh giá là khả vi liên tục. Mệnh đề sau đây sẽ đưa ra điều kiện để một hàm đánh giá có dạng (3.2) là khả vi liên tục và cho công thức tường minh để tính đạo hàm của nó. 42 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Mệnh đề 3.1.1. [2] Giả sử rằng f(x, .) : K → R là hàm lồi mạnh với ∀x ∈ K, khả vi với biến x và ∇xf(., .) liên tục trên K ìK. Khi đó, g(x) := sup y∈K {−f(x, y)} là hàm đánh giá khả vi liên tục của bài toán cân bằng và đạo hàm của nó được cho bởi công thức: ∇g(x) := ∇xf(x, y(x)), (3.5) trong đó, y(x) := argminy∈Kf(x, y). Chứng minh Do f(., .) lồi mạnh với biến y, nên tồn tại duy nhất điểm cực tiểu y(x) của bài toán: min y∈K f(x, y) Theo định lí 4.3.3 của B.Bank, ta suy ra được y(x) là nửa liên tục trên tại x theo nghĩa Berge và là hàm đơn trị tại y(x). Do đó suy ra y(x) liên tục tại x. Lại do ∇xf(., .) liên tục trên KìK, từ định lí 1.7 chương 4 của Auslender [6] ta có: ∇g(x) := −∇xf(x, y(x)) Do tính liên tục của∇xf(., .) và y(x) nên∇g(x) liên tục tại x.  Thuật toán sau đây được xây dựng dựa vào việc cực tiểu hàm đánh giá g cho ở dạng (3.2). Thuật toán 3.1 [9] Cho g(x) := sup y∈K {−f(x, y)}. Bước 1 Cho k = 0, x0 ∈ K. Bước 2 Cho xk+1 = xk + tkd k với k = 1, 2, . . . trong đó: dk := y(xk)− xk y(xk) là nghiệm của bài toán tối ưu: 43 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn min y∈K f(xk, y) và tk là nghiệm của bài toán: min y∈K {g(xk + tdk)} Bước 3 Nếu ‖ xk+1 − xk ‖≤ à với à > 0 thì thuật toán dừng. Ngược lại, thay k bởi k + 1 và quay lại bước 2. • Nhắc lại rằng, dk là hướng giảm của hàm đánh giá g tại xk nếu:〈∇g(xk), dk〉 < 0. Ta cần chứng minh dk = y(xk)− xk là hướng giảm của hàm đánh giá g tại xk. Để khẳng định điều đó ta cần giả thiết thêm:〈5x f(x, y) +5yf(x, y), y − x〉 ≥ 0, ∀x, y ∈ K. (3.6) Giả thiết (3.6) thoả mãn trong trường hợp bài toán bất đẳng thức biến phân: f(x, y) = 〈 T (x), y − x〉 nếu ∇T (x) là ma trận xác định dương với mọi x ∈ K. Mệnh đề 3.1.2. [11] Giả sử rằng giả thiết của mệnh đề 3.1.1 là đúng và giả thiết (3.6) thoả mãn. Khi đó, d(x) := y(x)− x là hướng giảm của hàm đánh giá g tại x ∈ K, với điều kiện y(x) 6= x. Chứng minh Ta thấy rằng x∗ là nghiệm của bài toán cân bằng khi và chỉ khi y(x∗) = x∗. Mặt khác y(x) là nghiệm của bài toán: min y∈K {f(x, y)} 44 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn và f(x, .) lồi mạnh nên bất đẳng thức sau luôn đúng:〈∇yf(x, y(x)), z − y(x)〉 > 0, ∀z ∈ K, z 6= y(x) (3.7) Đặt z := x ta có: 〈∇yf(x, y(x)), x− y(x)〉 > 0 điều này tương đương với:〈∇yf(x, y(x)), y(x)− x〉 < 0 Kết hợp với (3.6) ta có: 0 > 〈∇yf(x, y(x)), y(x)− x〉− 〈∇xf(x, y(x)), y(x)− x〉 Theo công thức đạo hàm ta có: ∇g(x) = −∇xf(x, y(x)), ta suy ra được: 〈∇g(y), y − x〉 < 0. Tức là, d(x) = y(x)− x là hướng giảm của g tại x.  Định lí sau đây chỉ ra tính hội tụ của dãy điểm được sinh từ thuật toán 3.1. Định lý 3.1.1. [9] ChoK là tập lồi và compact của Rn. Giả sử rằng f(x, .) là hàm lồi chặt (với biến y) ∀x ∈ K, khả vi theo biến x và ∇xf liên tục trên K ìK. Hơn nữa, giả thiết (3.6) thoả mãn. Khi đó, với ∀x0 ∈ K, dãy {xk}k∈N được tìm từ thuật toán 3.1 là thuộc K và mọi điểm tụ của dãy {xk}k∈N đều là nghiệm của bài toán cân bằng. Chứng minh Vì K là tập lồi và 0 ≤ tk ≤ 1, nên {xk}k∈N ⊂ K. Hàm d(x) = y(x)− x liên tục trên K do y(x) liên tục. Ta lại có ánh xạ: U(x, d) = { y : y = x + tkd, g(x + tkd) = min t∈[0,1] g(x + td) } là đóng khi hàm g là hàm liên tục. Do đó, dãy {xk}k∈N được xây dựng bởi xk+1 = U(xk, d(xk)) là đóng [10]. 45 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Theo định lí hội tụ của Zangwill suy ra bất kì điểm tụ nào của dãy {xk}k∈N được tìm từ thuật toán 3.1 là nghiệm của bài toán cân bằng.  Mệnh đề 3.1.3. [9] Giả sử rằng K là tập lồi và compact của Rn. Giả sử:〈∇xf(x, y) +∇yf(x, y), y − x〉 ≥ à ‖ x− y ‖2, ∀x, y ∈ K (3.8) thoả mãn với à > 0. Khi đó,〈∇g(x), d(x)〉 ≤ −à ‖ d(x) ‖2 trong đó, d(x) := y(x)− x. Nhận xét Trong thuật toán 3.1, việc giải bài toán: min y∈K { g(xk + tdk) } để tìm tk đôi khi rất phức tạp. Để khắc phục nhược điểm này ta đưa ra thuật toán 3.2 để giải bài toán cân bằng trong trường hợp hàm đánh giá g được cho bởi (3.2) và hàm f thoả mãn điều kiện (3.8). Thuật toán 3.2 [9] Cho g(x) := sup y∈K {−f(x, y)}. Bước 1 Cho k = 0, x0 ∈ K. Bước 2 Nếu g(xk) = 0, thì lấy x∗ = xk và thuật toán dừng. Trái lại, ta tiếp tục thực hiện bước 3. Bước 3 Cho xk+1 = xk + tkd k với k = 1, 2, . . . trong đó: dk := y(xk)− xk. Chọn số nguyên không âm m nhỏ nhất thoả mãn: g(xk)− g(xk + αmdk) ≥ tαm ‖ dk ‖2 với αm = tk; t, α ∈ [0, 1]. Bước 4 Nếu ‖ xk+1 − xk ‖≤ à với à > 0 thì thuật toán dừng. Trái lại, thay k bởi k + 1 và quay lại bước 2. 46 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Định lí sau đây khẳng định sự hội tụ của dãy điểm được sinh từ thuật toán 3.2. Định lý 3.1.2. [9] Cho {xk}k∈N là dãy được tính từ thuật toán 3.2. Giả sử K là tập lồi và compact của Rn, f(x, .) lồi mạnh với ∀x ∈ K và giả sử (3.8) thoả mãn với à > 0 và t < à/2. Khi đó, với mọi x0 ∈ K, dãy {xk}k∈N ⊂ K và hội tụ đến nghiệm của bài toán cân bằng. Chứng minh Do tính lồi của tập K và với mọi tk ∈ [0, 1] nên ta suy ra {xk}k∈N ⊂ K. Lại do tính compact của tập K nên từ dãy {xk}k∈N ta có thể trích ra được một dãy con {xkn}kn∈N, dãy này hội tụ đến điểm x∗. Ta sẽ chứng minh y(x∗) = x∗ vì thế nên x∗ là nghiệm của bài toán cân bằng. Cho d(x) := y(x)−x, vì y(x) liên tục (xem chứng minh của mệnh đề 3.1.1) nên suy ra d(x) liên tục. Vì vậy, ta có thể khẳng định d(xkn) → d(x∗) := d∗ và g(xkn) → g(x∗) := g∗. Ta có: g(xk)− g(xk+1) ≥ tαk ‖ dk ‖2, Do đó, αkn ‖ d(xkn) ‖2→ 0, vậy {αkn} ⊆ {αk}. Nếu αkn > γ > 0, γ ∈ R, ∀k ∈ R thì ‖ d(xkn) ‖→ 0 nên y(x∗) = x∗. Trái lại, giả sử tồn tại dãy {αkp} ⊆ {αkn}, αkp → 0. Ta có, g(xkp)− g(xkp + αkpd(xkp) αkp < t ‖ d(xkp) ‖2, (3.9) trong đó, αkp = αkp/α. Cho (3.9) qua giới hạn với kp → 0, do αkp → 0 và g khả vi liên tục nên suy ra: −〈∇g(x∗), d∗〉 ≤ t ‖ d∗ ‖2, (3.10) 47 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Mệnh đề 3.1.3 ta có: −〈∇g(x∗), d∗〉 ≥ à ‖ d∗ ‖2 . Vì t < à/2 nên ‖ d∗ ‖= 0, từ đó suy ra y(x∗) = x∗.  3.2. Hàm đánh giá M.Fukushima ở phần trên Auslender đã xây dựng thuật toán hàm đánh giá giải bài toán cân bằng khi f(x, .) lồi mạnh. Nhưng không phải lúc nào giả thiết về tính lồi mạnh cũng được thoả mãn. Chẳng hạn, bài toán bất đẳng thức biến phân khi f(x, .) là hàm tuyến tính. Để khắc phục nhược điểm này Fukushima đã chuyển bài toán cân bằng về bài toán cân bằng phụ và đưa ra thuật toán hàm đánh giá giải bài toán cân bằng. Định lý 3.2.1. [2] Giả sử f(x, .) : K → R là hàm lồi với ∀x ∈ K, khả vi với biến x và ∇xf(., .) liên tục trên K ìK. Cho L(., .) không âm, khả vi liên tục trên K ì K, lồi mạnh với biến y, ∀x ∈ K thoả mãn: a, L(x, x) = 0, ∀x ∈ K, b, ∇yL(x, x) = 0, ∀x ∈ K. Khi đó, g(x) := max y∈K {−f(x, y)− L(x, y)} (3.11) là hàm đánh giá khả vi liên tục của bài toán cân bằng và đạo hàm của nó được cho bởi công thức: ∇g(x) := −∇xf(x, y(x))−∇xL(x, y(x)) (3.12) trong đó, y(x) := arguminy∈K{f(x, y) + L(x, y)}. Chứng minh Từ bổ đề 3.0.5 và hệ quả 2.2.1 (chương 2), ta suy ra bài toán cân bằng tương đương với bài toán cân bằng phụ sau: min y∈K {f(x∗, y) + L(x∗, y)}. 48 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Lấy  = 1 và áp dụng mệnh đề 3.1.1 cho bài toán cân bằng phụ ta suy ra điều phải chứng minh.  Nhận xét Khi f(x, y) := 〈 T (x), y − x〉 thì g(x) := sup y∈K {−f(x, y)− L(x, y)} là hàm đánh giá cho bài toán bất đẳng thức biến phân. áp dụng thuật toán 3.1 cho bài toán cân bằng ta có thuật toán cho bài toán cân bằng phụ. Thuật toán 3.3 [9] Cho g(x) := max y∈K {−f(x, y)− L(x, y)}. Bước 1 Cho k = 0, x0 ∈ K. Bước 2 Cho xk+1 = xk + tkd k với k = 1, 2, . . . trong đó, dk = y(xk)− xk y(xk) là nghiệm của bài toán tối ưu: min y∈K {f(xk, y) + L(xk, y)}, và tk là nghiệm của bài toán: min y∈K {g(xk + tdk)}. Bước 3 Nếu ‖ xk+1 − xk ‖≤ à với à > 0 thì thuật toán dừng. Trái lại, thay k bởi k + 1 và quay lại bước 2. Trong thuật toán 3.3 thay thế giả thiết (3.6) của thuật toán 3.1 bởi điều kiện sau:〈∇xf(x, y)+∇xL(x, y)+∇yf(x, y)+∇yL(x, y), y−x〉 ≥ 0, ∀x, y ∈ K. (3.13) Dễ thấy rằng nếu ta giả thiết ∇xL(x, y) + ∇yL(x, y) = 0, ∀x, y ∈ K thì giả thiết (3.13) chính là giả thiết (3.6). Định lí sau chỉ ra tính hội tụ của dãy điểm được sinh bởi thuật toán 3.3. 49 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Định lý 3.2.2. [2] Cho K là tập lồi và compact của tập Rn. Giả sử rằng f(x, .) là hàm lồi ∀x ∈ K, khả vi với biến x và ∇xf liên tục trên K ìK. Cho L(., .) : K ìK → R không âm, khả vi liên tục trên K ìK, L(x, .) lồi chặt với ∀x ∈ K và thoả mãn: a, L(x, x) = 0, ∀x ∈ K, b, ∇yL(x, x) = 0, ∀x ∈ K. Hơn nữa, giả sử điều kiện (3.13) thoả mãn. Khi đó, với mọi điểm x0 ∈ K, dãy {xk}k∈N được tìm từ thuật toán 3.3 là thuộc K và hội tụ tới nghiệm của bài toán cân bằng. Chứng minh Theo mệnh đề 3.0.5, bài toán cân bằng tương đương với bài toán cân bằng phụ. Lấy  = 1 và áp dụng định lí 3.2.1 cho bài toán cân bằng phụ ta suy ra điều phải chứng minh.  Nhận xét Chúng ta nhận thấy rằng điều kiện lồi mạnh của hàm f(x, .) trên K trong thuật toán 3.2 làm hạn chế phạm vi ứng dụng. Điều kiện này có thể bỏ được nếu ta thay thế giả thiết (3.8) bởi giả thiết sau [11]:〈∇xf(x, y)+∇xL(x, y)+∇yf(x, y)+∇yL(x, y), y−x〉 ≥ à ‖ x−y ‖2 . (3.14) Thuật toán sẽ trình bày sau đây có thể áp dụng ngay cả trong trường hợp f(x, .) là hàm lồi, nhưng không nhất thiết là lồi mạnh [9]. Thuật toán 3.4 [9] Cho g(x) := max y∈K {−f(x, y)− L(x, y)}. Bước 1 Cho k = 0, x0 ∈ K. Bước 2 Nếu g(xk) = 0 thì thuật toán dừng. Trái lại ta tiếp tục thực hiện bước 3. Bước 3 Cho xk+1 = xk + tkd k với k = 1, 2, . . . trong đó: dk := y(xk)− xk. Chọn số nguyên không âm m nhỏ nhất thoả mãn: 50 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn g(xk)− g(xk + αmdk) ≥ tαm ‖ dk ‖2 với αm = tk; t, α ∈ [0, 1]. Bước 4 Nếu ‖ xk+1 − xk ‖≤ à với à > 0 thì thuật toán dừng. Trái lại, thay k bởi k + 1 và quay lại bước 2. Sự hội tụ của dãy điểm được sinh từ thuật toán 3.4 được khẳng định bởi hệ quả (của định lí 3.1.2) sau: Hệ quả 3.2.1. [9] Cho {xk} là dãy được tìm từ thuật toán 3.4. Giả sử rằng K là tập lồi và compact của Rn và giả thiết (3.14) thoả mãn với à > 0 và t < à/2. Khi đó, với mọi x0 ∈ K dãy {xk} ⊂ K và hội tụ tới nghiệm của bài toán cân bằng. Người ta chứng minh được rằng có thể giảm nhẹ điều kiện về tính compact của tập chấp nhận được K trong trường hợp hàm f đơn điệu mạnh và ∇xL liên tục Lipschitz trên K [11]. Mệnh đề sau cho phép ta đánh giá sai số toàn cục khi giải bài toán cân bằng theo hàm đánh giá g trong trường hợp f đơn điệu mạnh. Mệnh đề 3.2.1. [9] Cho f đơn điệu mạnh trên K với hệ số b. Khi đó, g(x) ≥ b ‖ x− x∗ ‖2, ∀x ∈ K (3.15) với x∗ là nghiệm của bài toán cân bằng. Chứng minh Vì với ∀y ∈ K ta có g(x) ≥ −f(x, y). Khi đó dựa vào giả thiết về tính đơn điệu mạnh theo hệ số b của hàm f và tính chất f(x, x) = 0, ∀x ∈ K ta có: g(x) ≥ −f(x∗, x)− f(x, x∗) + f(x, x∗) ≥ b ‖ x− x∗ ‖2 +f(x, x∗) ≥ b ‖ x− x∗ ‖2 .  51 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Ta có thể mở rộng kết quả nêu trong mệnh đề 3.2.1 đối với hàm đánh giá g := maxy∈K {− f(x, y)−L(x, y)} và cần xét thêm điều kiện về tính liên tục Lipschitz cho hàm ∇yL(x, y). Mệnh đề 3.2.2. [11] Cho f đơn điệu mạnh trên K với hệ số b, L(x, .) lồi và ∇yL(x, .) liên tục Lipschitz với hệ số L < 2b, ∀x ∈ K. Khi đó, g(x) ≥ (b− L/2) ‖ x− x∗ ‖2, ∀x ∈ K (3.16) với x∗ là nghiệm của bài toán cân bằng. Chứng minh Với ∀x, y ∈ K có g(x) ≥ −f(x, y)− G(x, y). Do đó, với x∗ = y có g(x) ≥ −f(x∗, x)− L(x∗, x)− f(x, x∗) + f(x, x∗) ≥ b ‖ x− x∗ ‖2 +f(x, x∗)− L(x∗, x). Có g(x) ≥ b ‖ x− x∗ ‖2 −G(x∗, x). (3.17) Do ∇yL(x, .) liên tục Lipschitz nên bất đẳng thức sau đúng L(x∗, x) = L(x∗, x)− L(x, x) ( do L(x, x) = 0) ≤ (L/2) ‖ x∗ − x ‖2, ∀x ∈ K. Kết hợp với (3.17) có g(x) ≥ (b− L/2) ‖ x− x∗ ‖2, ∀x ∈ K.  Kết luận chương Chương này đã trình bày lí thuyết hàm đánh giá giải bài toán cân bằng. Dựa vào lí thuyết hàm đánh giá, Auslender và Fukushima đã đưa ra các thuật toán giải bài toán cân bằng thông qua bài toán cực tiểu có ràng buộc một hàm khả vi liên tục tương ứng. 52 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Kết luận Như đã trình bày ở trên, bài toán cân bằng (1.1) là bài toán tổng quát vì có nhiều bài toán quen thuộc như: bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán cân bằng Nash,... đều có thể đưa về bài toán cân bằng. Bài toán cân bằng có thể được nghiên cứu và tiếp cận theo những cách khác nhau. Luận văn này nghiên cứu phương pháp chiếu, phương pháp gradient tăng cường và phương pháp hàm đánh giá giải bài toán cân bằng. Những nội dung chính được trình bày trong luận văn bao gồm: • Dạng toán học của bài toán cân bằng và một số bài toán ứng dụng quen thuộc mà có thể chuyển về bài toán cân bằng. • Trình bày phương pháp chiếu và đạo hàm tăng cường giải bài toán cân bằng. • Trình bày phương pháp hàm đánh giá giải bài toán cân bằng. Nghĩa là, sử dụng lí thuyết hàm đánh giá để đưa việc giải bài toán cân bằng về việc giải bài toán cực tiểu một hàm đánh giá theo phương pháp hướng giảm trên tập ràng buộc. Trong thời gian tới, tác giả mong muốn có thể nghiên cứu sâu hơn về bài toán cân bằng để có thể đạt được một số kết quả riêng về lĩnh vực này. Tác giả mong muốn nhận được sự giúp đỡ và chỉ dẫn các thày cô giáo cùng các bạn bè đồng nghiệp để đạt được những kết quả đáng kể trong hướng nghiên cứu này. 53 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn Tài liệu tham khảo [1] Lê Dũng Mưu (1998), Nhập môn các phương pháp tối ưu, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội. [2] Nguyen Van Hien (2002), Lecture Notes on Equilibrium Problems, Na- mur, Belgium. [3] Nguyễn Thị Bạch Kim (2008), Giáo trình Các Phương pháp Tối ưu Lý thuyết và Thuật toán, Nhà xuất bản Bách Khoa -Hà Nội. [4] PGS.TS Đỗ Văn Lưu - PGS.TS Phan Huy Khải (2000), Giải tích lồi, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội. [5] D.Quoc Tran, M.Le Dung, Van Hien Nguyen (2008), "Extragradient Algorithms Extended to Equilibrium Problems", Optimization. [6] A.Auslender (1976), Opitimization-Méthodes numériques, Masson, Paris. [7] E.Blum andW.Oettli (1994), "FromOpitimization to Variational Inqual- ities to Equilibrium Problems", The Mathematics Student 63, pp.134-145. [8] M.Fukushima (1992), "Equivalent Differentiable Opitimization Prob- lems and Descent Methods for Asymmetric VariationalInquality Prob- lems", Mathematical Programming 53, pp. 99-110. [9] G.Mastroeni (2003), "Gap Function for Equilibrium Problems", Journal of Gloal Opitimization 27, pp. 411-426. [10] D.L.Zhu and P.Marcotte (1994), "An Extended Descent Framework for Variational Inequalities", Journal of Opitimization Theory and Appli- cations 80, pp. 349-366. 54 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn