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

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 Korpelev._.