Tóm tắt Luận án tiến sĩ Toán học: Một số phương pháp giải bài toán chấp nhận tách suy rộng liên quan đến bài toán cân bằng

Chia sẻ: Trần Văn Ha | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

47
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án được nghiên cứu với mục tiêu nhằm Đề xuất một thuật toán dưới đạo hàm giải bài toán chấp nhận tách với toán tử chuyển là tựa tuyến tính và chứng minh sự hội tụ của nó. Thuật toán được áp dụng cho mô hình Nash–Cournot có ràng buộc chung, cụ thể là dùng để tính toán thử nghiệm giải mô hình sản xuất điện thỏa mãn tỉ lệ của các loại điện trên nhiều số liệu khác nhau được tạo ngẫu nhiên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Toán học: Một số phương pháp giải bài toán chấp nhận tách suy rộng liên quan đến bài toán cân bằng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM NGUYỄN THỊ THANH HUYỀN MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CHẤP NHẬN TÁCH SUY RỘNG LIÊN QUAN ĐẾN BÀI TOÁN CÂN BẰNG Chuyên ngành: Toán Giải tích Mã số: 9 46 01 02 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC THÁI NGUYÊN–NĂM 2020
Công trình được hoàn thành tại: Trường Đại học Sư phạm - Đại học Thái Nguyên, Thái Nguyên. Người hướng dẫn khoa học: GS.TSKH. Lê Dũng Mưu Phản biện 1:................................................................... Phản biện 2: .................................................................. Phản biện 3:................................................................... Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp trường họp tại: Trường Đại học Sư phạm, Đại học Thái Nguyên. Vào hồi ... giờ ... ngày ... tháng ... năm 2019
Mở đầu Bài toán cân bằng, còn được gọi là bất đẳng thức Ky Fan, được nghiên cứu trong luận án này có thể phát biểu một cách đơn giản như sau: Cho C là một tập lồi, đóng, khác rỗng trong không gian Rn và f : C×C → R là một song hàm thỏa mãn f (x, x) = 0, với mọi x ∈ C (song hàm có tính chất này thường được gọi là song hàm cân bằng). Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C. EP(C, f ) Bất đẳng thức trên được H. Nikaido và K. Isoda sử dụng lần đầu tiên vào năm 1955 trong khi nghiên cứu trò chơi không hợp tác. Năm 1972, Ky Fan gọi là bất đẳng thức minimax và ông đã đưa ra các kết quả về sự tồn tại nghiệm của bài toán này. Thuật ngữ bài toán cân bằng được sử dụng lần đầu tiên bởi GS. L.D. Muu và W. Oettli năm 1992. Bài toán cân bằng bao hàm nhiều lớp 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 điểm bất động Kakutani, bài toán cân bằng Nash trong lý thuyết trò chơi không hợp tác, bài toán cân bằng véctơ, bài toán cân bằng tập... Các bài toán này, một số được trình bày bởi GS. L.D. Muu và W. Oettli, sau đó được E. Blum và W. Oettli giới thiệu thêm trong công trình của mình vào năm 1994, gần đây được giới thiệu khá đầy đủ trong cuốn sách chuyên khảo của G. Bigi và các cộng sự. Ngoài ra, bài toán cân bằng còn được mở rộng sang các bài toán cân bằng véctơ, bài toán cân bằng tập, chẳng hạn bởi các tác giả P.H. Sach, N.X. Tan, T.X.D. Ha, D.V. Luu,... và cuốn chuyên khảo của G. Kassay. Trong vài chục năm trở lại đây, bài toán cân bằng được nghiên cứu cả về tính chất định tính và các phương pháp giải. Về tính chất định tính, sự tồn tại nghiệm của bài toán cân bằng được 1
khảo sát bởi các tác giả M. Bianchi, R. Pini, G. Bigi, L.D. Muu, A. Iusem, G. Kassay, W. Sosa... Sự ổn định nghiệm, cấu trúc của tập nghiệm được nghiên cứu bởi L.Q. Anh, P.Q. Khanh, L.D. Muu và một số tác giả khác. Hướng nghiên cứu về phương pháp giải có thể nói là được quan tâm nhiều hơn, chẳng hạn bởi P.K. Anh, L.D. Muu, D. Aussel, J. Contreras, B.V. Dinh, N.V. Quy, P.N. Anh, A. Iusem, D.V. Hieu, P. Santos, S. Scheimberg, L.Q. Thuy, T.N. Hai,... Do bài toán cân bằng bao hàm nhiều bài toán quan trọng, khó giải như là những trường hợp riêng, nên không hy vọng có một thuật toán hiệu quả để giải bài toán cân bằng tổng quát. Vì thế người ta đã nghiên cứu các phương pháp giải bài toán cân bằng với những giả thiết nhất định. Các giả thiết thông thường hay được dùng là một tính chất đơn điệu nào đó và tính lồi, khả dưới vi phân theo biến thứ hai của song hàm f . Một số tiếp cận về phương pháp giải bài toán cân bằng có thể được chia ra như sau: • Phương pháp điểm bất động cho ánh xạ co, hoặc không giãn, không giãn suy rộng dựa trên nguyên lý bài toán phụ. Nguyên lý bài toán phụ cho bài toán cân bằng EP (C, f ) liên quan đến bài toán cân bằng dưới đây Tìm x ∈ C : fα (x, y) := f (x, y) + αM (x, y) ≥ 0, ∀y ∈ C EP (C, fα ) trong đó α > 0, và M (được gọi là hàm khoảng cách Bregman) có tính chất (M1) Xác định trên toàn không gian, hàm M (x, .) lồi mạnh, khả vi và ∇M (x, x) = 0 với mọi x ∈ C . Nguyên lý bài toán phụ được G. Cohen đề xuất lần đầu tiên cho bài toán tối ưu và bài toán bất đẳng thức biến phân lần lượt vào năm 1980 và 1988. Đến năm 2003, nguyên lý này đã được mở rộng cho bài toán cân bằng bởi G. Mastroeni. • Phương pháp hàm đánh giá (gap function). Ý tưởng chính của phương pháp hàm đánh giá là chuyển việc giải bài toán cân bằng về bài toán tối 2
ưu. Hai loại hàm đánh giá cơ bản là hàm đánh giá Auslender và hàm đánh giá Fukushima được định nghĩa lần lượt như sau gA (x) = − min{f (x, y) : y ∈ C} gF (x) = − min{f (x, y) + αM (x, y) : y ∈ C}, trong đó α > 0 và song hàm M có tính chất đã nêu ở trên. Như đã biết, x ∈ C , gA (x) = 0, hoặc gF (x) = 0 khi và chỉ khi x là nghiệm của bài toán EP (C, f ). Chú ý rằng bài toán quy hoạch lồi xác định gA (x) có thể không tồn tại nghiệm, và nếu có nghiệm thì nghiệm có thể không duy nhất. Tuy nhiên bài toán xác định gF (x), do M (x, .) lồi mạnh, nên luôn tồn tại duy nhất nghiệm. • Phương pháp hiệu chỉnh Tikhonov và điểm gần kề (proximal point). Các phương pháp này nhằm mục đích chuyển việc giải bài toán đặt không chỉnh, ví dụ các bài toán không duy nhất nghiệm, và/hoặc nghiệm không phụ thuộc liên tục vào các dữ kiện ban đầu về việc giải các bài toán đặt chỉnh. Để đảm bảo tính duy nhất nghiệm, người ta thường dùng một song hàm hiệu chỉnh và một tham số hiêụ chỉnh để xây dựng bài toán phụ có duy nhất nghiệm phụ thuộc tham số hiệu chỉnh, và nghiệm duy nhất này sẽ hội tụ đến một nghiệm của bài toán ban đầu, khi tham số hiệu chỉnh tiến tới giá trị nhất định. Các phương pháp hiệu chỉnh này đã được sử dụng một cách hiệu quả cho bài toán tối ưu, bất đẳng thức biến phân, phương trình toán tử, bao hàm thức đơn điệu và gần đây cho bài toán cân bằng đơn điệu, giả đơn điệu. Trong phương pháp hiệu chỉnh Tikhonov bài toán hiệu chỉnh, với hàm hiệu chỉnh khoảng cách, được cho như sau: fT (x, y) := f (x, y) + hx − xg , y − xi, trong đó > 0 là tham số hiệu chỉnh, còn xg đóng vai trò như lời giải dự đoán. Trong phương pháp điểm gần kề, điểm dự đoán xg thay đổi ở 3
mỗi bước lặp k và hàm hiệu chỉnh có dạng fP (x, y) := f (x, y) + chx − xk , y − xi, với c > 0. Với giả thiết f đơn điệu trên C , thì fT và fP đơn điệu mạnh trên C . Do đó, với các giả thiết thông thường về tính liên tục của song hàm, bài toán cân bằng hiệu chỉnh EP (C, fT ) và EP (C, fP ) có duy nhất nghiệm phụ thuộc vào các tham số hiệu chỉnh và hội tụ đến một nghiệm của bài toán ban đầu khi tiến dần đến 0, đối với hiệu chỉnh Tikhonov, còn đối với hiệu chỉnh điểm gần kề thì c tiến về một số hữu hạn. • Phương pháp chiếu và chiếu tăng cường (extragradient method). Phương pháp chiếu cơ bản (tức là chiếu một lần) cho bài toán cân bằng có thể không hội tụ, ngay cả khi song hàm f là đơn điệu. Do đó, năm 1997, S. Flam và A. Antipin đã dùng phương pháp chiếu tăng cường (chiếu hai lần) với hàm khoảng cách Bregman cho bài toán cân bằng. Năm 2011, N. Langenberg mở rộng kết quả của Flam và Antipin. Sau đó, nhiều tác giả đã dùng phương pháp chiếu tăng cường giải bài toán cân bằng với các giả thiết khác nhau đặt lên song hàm f . Trong phương pháp chiếu tăng cường, ở mỗi bước lặp k , phải giải hai bài toán tối ưu α xk = argmin{f (xk , y) + ky − xk k2 : y ∈ C}; 2 α xk+1 = argmin{f (xk , y) + ky − xk k2 : y ∈ C}. 2 Với các giả thiết thông thường, dãy điểm lặp xác định như trên sẽ hội tụ về một nghiệm của bài toán EP (C, f ). Đối với bài toán cân bằng có tính chất đơn điệu mạnh hơn, như đơn điệu mạnh, giả đơn điệu mạnh, đơn điệu mạnh ngược, para-đơn điệu (paramonotone), thì chỉ cần dùng phương pháp chiếu cơ bản (một lần chiếu), chẳng hạn xem P. Santos và S. Scheimberg. Một bài toán khác liên quan nhiều đến luận án này là bài toán chấp nhận 4
tách (Split feasibility problem). Bài toán chấp nhận tách được Y. Censor và T. Elfving giới thiệu lần đầu tiên vào năm 1994 cho mô hình bài toán ngược. Sau đó được C. Byrne ứng dụng vào năm 2002 cho bài toán phục hồi và tái tạo hình ảnh y tế. Gần đây, bài toán này còn được Y. Censor ứng dụng trong mô hình điều khiển cường độ xạ trị trong điều trị ung thư. Trong không gian hữu hạn chiều, bài toán chấp nhận tách có thể mô tả như sau: Cho C và Q là các tập lồi khác rỗng trong không gian Rn và Rm tương ứng, và A : Rn → Rm là toán tử tuyến tính bị chặn (được gọi là toán tử chuyển). Bài toán chấp nhận tách được phát biểu: Tìm x ∈ C sao cho Ax ∈ Q. (SFP). Trong trường hợp hai không gian là trùng nhau và A là toán tử đồng nhất, thì bài toán chấp nhận tách trở về bài toán chấp nhận lồi (convex feasibility problem) là tìm x ∈ C ∩ Q. Kí hiệu Γ là tập nghiệm của bài toán chấp nhận tách (SFP), Γ = {x ∈ C : Ax ∈ Q} = C ∩ A−1 Q, thì do C, Q là các tập lồi đóng, nên Γ là tập lồi, đóng và là giao của hai tập lồi đóng C và A−1 Q. Như vậy bài toán chấp nhận tách có thể xem như một trường hợp đặc biệt của bài toán chấp nhận lồi. Trong những năm gần đây, việc giải bài toán chấp nhận tách được nhiều người quan tâm nghiên cứu, đặc biệt là trong trường hợp C và/hoặc Q được cho như là tập nghiệm của các bài toán nào đó, ví dụ tập điểm bất động, tập nghiệm của bài toán tối ưu lồi, bất đẳng thức biến phân, và tổng quát hơn là của bài toán cân bằng. Có hai phương pháp cơ bản để giải bài toán chấp nhận tách là phương pháp chiếu (lần lượt hoặc song song). Các thuật toán chiếu này lấy ý tường từ các phương pháp chiếu của C.J. Karzmark và của V. Neumann. Phương pháp thứ hai giải bài toán chấp nhận tách là chuyển bài toán chấp nhận tách về bài toán tối ưu lồi. Do đó các phương pháp của quy hoạch toán học có thể áp dụng để giải bài toán chấp nhận 5
tách. Điều khó khăn ở đây chính là việc tính giá trị cũng như đạo hàm của hàm mục tiêu. Cần phải nói thêm rằng các thuật toán đã có chỉ áp dụng cho trường hợp A là toán tử tuyến tính, lý do chính là các thuật toán dựa trên phương pháp chiếu đòi hỏi phải tính được hoặc toán tử chuyển vị A∗ hoặc toán tử nghịch đảo A−1 , trong khi đó với phương pháp dựa trên bài toán tối ưu, thì hàm 1 mục tiêu 2λ k(I − PQ )(Ax)k2 chỉ lồi và khả vi khi A là tuyến tính. Do tính khả vi của hàm mục tiêu nên bài toán cực tiểu hàm này tương đương với bài toán bất đẳng thức biến phân đơn điệu. Một vấn đề được đặt ra là nghiên cứu thuật toán giải bài toán chấp nhận tách với toán tử chuyển không phải là tuyến tính với C và/hoặc Q không được cho tường minh, ví dụ như là tập nghiệm của bài toán cân bằng, hoặc các trường hợp riêng của nó. Trong luận án, chúng tôi xét bài toán chấp nhận tách cho hai trường hợp: Trường hợp đầu là bài toán chấp nhận tách với C là tập nghiệm của bài toán cân bằng và Q là tập nghiệm của bài toán quy hoạch lồi. Đối với bài toán này chúng tôi đề xuất một thuật toán chiếu một lần giải bài toán cân bằng kết hợp với phương pháp chiếu giải bài toán quy hoạch lồi bằng cách sử dụng ánh xạ gần kề của hàm mục tiêu. Bài toán chấp nhận tách thứ hai được xét trong luận án là bài toán trong đó toán tử chuyển không nhất thiết là tuyến tính mà là một phép biến đổi được cho bởi các hàm số tựa tuyến tính. Một thuật toán dựa trên phương pháp tối ưu cho bài toán tựa lồi, sử dụng dưới đạo hàm Clarke đã được đề xuất. Sự hội tụ của thuật toán đã được chứng minh. Bản luận án, ngoài phần mở đầu, kết luận, danh mục các công trình đã công bố của tác giả có liên quan đến luận án và danh mục tài liệu tham khảo, luận án gồm 3 chương. Các kết quả chính được trình bày trong các Chương 2 và Chương 3. Chương 1 trình bày các kiến thức bổ trợ, nhắc lại các kết quả về phép chiếu mêtric, tập lồi, hàm lồi, hàm tựa lồi, song hàm đơn điệu, bài toán cân 6
bằng và một số bài toán liên quan, bài toán chấp nhận tách và một số bổ đề dùng để chứng minh cho các kết quả chính ở các chương sau. Trong Chương 2 chúng tôi trình bày thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii giải bài toán chấp nhận tách liên quan đến bài toán cân bằng và bài toán tối ưu lồi. Một mô hình cân bằng sản xuất điện với chi phí môi trường thấp nhất đã được trình bày ở chương này cùng với các tính toán thử nghiệm khi giải mô hình theo thuật toán đã đề xuất. Chương 3 trình bày thuật toán dưới đạo hàm giải bài toán chấp nhận tách với toán tử chuyển là tựa tuyến tính và chứng minh sự hội tụ. Cuối chương giới thiệu một mô hình cân bằng Nash có ràng buộc chung và hai ví dụ khác và được so sánh với một kết quả đã có của Santos và Scheimberg đề xuất vào năm 2017. Các kết quả chính của luận án được công bố trong 2 bài báo đăng trên các tạp chí thuộc danh mục ISI là: Mathematical Methods of Operations Research và Journal of Global Optimization. 7
Chương 1 Một số kiến thức chuẩn bị Trong chương này, chúng tôi trình bài một số khái niệm cơ bản cần thiết và một số bổ đề bổ trợ sẽ được dùng ở các chương tiếp theo. Nội dung của chương được chia thành năm phần. Phần đầu trình bày một số khái niệm và kết quả cơ bản của giải tích lồi, hai phần tiếp theo trình bày bài toán cân bằng và một số bài toán liên quan và bài toán chấp nhận tách, phần thứ tư nhắc lại một số phương pháp lặp cơ bản. Phần cuối của chương trình bày một số kết quả bổ trợ để chứng minh sự hội tụ của các thuật toán ở các chương sau. 1.1. Các khái niệm và kết quả cơ bản 1.2. Bài toán cân bằng và một số bài toán liên quan 1.3. Bài toán chấp nhận tách 1.4. Một số phương pháp lặp cơ bản 1.5. Các bổ đề bổ trợ 8
Chương 2 Thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii giải bài toán chấp nhận tách Trong chương này, chúng tôi trình bày thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii giải bài toán chấp nhận tách liên quan đến bài toán cân bằng và bài toán tối ưu lồi. Kết quả của chương này được viết dựa trên nội dung bài báo (1) đăng trên tạp chí Mathematical Methods of Operations Research nằm trong Danh sách các công trình của tác giả liên quan đến luận án. 2.1. Mô tả bài toán và sự hội tụ Cho C, Q là các tập lồi đóng khác rỗng trong không gian Rn , Rm tương ứng; A : Rn → Rm là toán tử tuyến tính. Xét bài toán chấp nhận tách: Tìm x∗ ∈ C sao cho Ax∗ ∈ Q. Khi C và/hoặc Q là các tập nghiệm của các bài toán bất đẳng thức biến phân hoặc tập nghiệm của bài toán điểm bất động, bài toán này đã được xét bởi một số tác giả, chẳng hạn T.V. Anh, Y. Shehu, J. Tang. Chúng tôi xét bài toán chấp nhận tách trong trường hợp C là tập nghiệm của bài toán cân bằng para-đơn điệu trong không gian Rn và Q là tập nghiệm của bài toán tối ưu lồi trong không gian Rm . Xét bài toán (SEO) sau đây: Tìm x∗ ∈ K : f (x∗ , y) ≥ 0 ∀y ∈ K và g(Ax∗ ) ≤ g(u) ∀u ∈ Rm , 9
trong đó K là tập con lồi đóng trong không gian Rn , A : Rn → Rm là toán tử tuyến tính và g là hàm lồi nửa liên tục dưới, chính thường trên không gian Rm . Các giả thiết sau cần thiết cho sự hội tụ của thuật toán. (A1) Với mỗi x ∈ K , f (x, x) = 0 và f (x, .) là lồi, nửa liên tục dưới trên K . (A2) ∂2 f (x, x) bị chặn trên mỗi tập con bị chặn bất kì của K , trong đó ∂2 f (x, x) kí hiệu -dưới vi phân của hàm lồi f (x, .) tại x, tức là ∂2 f (x, x) := {p ∈ Rn |hp, y − xi + f (x, x) ≤ f (x, y) + , ∀y ∈ Rn }. (A3) f là giả đơn điệu trên K đối với mỗi nghiệm của (EP ), tức là f (x, x∗ ) ≤ 0 với mỗi x ∈ K , x∗ ∈ Sol(EP ), và thỏa mãn điều kiện para-đơn điệu x∗ ∈ Sol(EP ), y ∈ K, f (x∗ , y) = f (y, x∗ ) = 0 ⇒ y ∈ Sol(EP ). (A4) Với mỗi x ∈ K , f (., x) là nửa liên tục trên trên K . Nhận xét 2.1 Khi = 0 thì ∂2 f (x, x) chính là dưới vi phân của song hàm f (x, .) theo biến thứ hai tại x hay ∂2 f (x, x). Thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii được mô tả như sau. Thuật toán 2.1 Lấy các tham số dương δ , ξ và các dãy số thực {ak }, {δk }, {βk }, {k }, {ρk } thỏa mãn các điều kiện: 0 < a < ak < b < 1; 0 < ξ ≤ ρk ≤ 4 − ξ, ∀k ∈ N; (2.1) δk > δ > 0, βk > 0, k ≥ 0, ∀k ∈ N; (2.2) 1 lim ak = ; (2.3) k→+∞ 2 ∞ ∞ X βk X = +∞, βk2 < +∞; (2.4) δk k=1 k=1 ∞ X βk k < +∞. (2.5) δk k=1 10
Bước 0: Chọn x1 ∈ K và cho k := 1. Bước k: Có xk ∈ K , lấy gk ∈ ∂2k f (xk , xk ) và xác định βk αk = trong đó γk = max{δk , kgk k}. γk Tính yk = PK (xk − αk gk ), tức là hyk − xk + αk gk , x − yk i ≥ 0 ∀x ∈ K. Lấy   0 nếu ∇h(y ) = 0, k µk := (2.6)  ρ h(yk ) nếu ∇h(y ) 6= 0 k k∇h(yk )k2 k và tính zk = PK (yk − µk AT (I − proxλg )(Ayk )). Tính xk+1 = ak xk + (1 − ak )zk . Nhận xét 2.2 Nếu chọn k = 0, thì xk = yk và h(xk ) = 0, suy ra xk là một nghiệm. Dựa theo cách này, ta sẽ gọi xk là -nghiệm nếu k ≤ và kxk − yk k ≤ , |h(xk )| ≤ . Các bổ đề sau cần thiết để chứng minh sự hội tụ của thuật toán. Gọi S là tập nghiệm của bài toán (SEO) và z ∈ S . Bổ đề 2.1 Nếu ∇h(yk ) 6= 0 thì bất đẳng thức sau đúng 2 2 h2 (yk ) kzk − zk ≤ kyk − z|| − ρk (4 − ρk ) . (2.7) k∇h(yk )k2 Bổ đề 2.2 Cho z ∈ S . Khi đó, với mỗi k sao cho ∇h(yk ) 6= 0, ta có 2 2 h2 (yk ) kxk+1 − zk ≤ kxk − z|| − (1 − ak )ρk (4 − ρk ) k∇h(yk )k2 +2(1 − ak )αk f (xk , z) + Ak , (2.8) 11
và với mỗi k sao cho ∇h(yk ) = 0, kxk+1 − zk2 ≤ kxk − z||2 + 2(1 − ak )αk f (xk , z) + Ak , (2.9) trong đó Ak = 2(1 − ak )(αk k + βk2 ). Tiếp theo là định lý hội tụ cho Thuật toán 2.1. Định lí 2.1 Giả sử bài toán (SEO) có nghiệm và các giả thiết (A1)- (A4) được thỏa mãn. Khi đó, dãy {xk } sinh bởi Thuật toán 2.1 hội tụ tới nghiệm của bài toán (SEO). 2.2. Ví dụ minh họa Trong mục này, chúng tôi xét bài toán chấp nhận tách với C là tập nghiệm của bài toán cân bằng và Q là tập nghiệm của bài toán tối ưu lồi. Bây giờ chúng tôi xét một ứng dụng của bài toán này cho mô hình cân bằng bán độc quyền Nash–Cournot trong bài toán sản xuất điện. Mô hình bài toán cân bằng trong sản xuất điện đã được nghiên cứu bởi một số tác giả. Trong mô hình này, ta giả sử có n nhà máy, mỗi nhà máy thứ i có Ii máy phát điện. Đặt x là véctơ trong đó tọa độ xj là lượng điện sinh bởi máy phát j . Giả sử giá pi (s) là hàm affin, giảm theo s với s = N P j=1 xj trong đó N là số tất cả các máy phát điện, tức là pi (s) = α − βi s. Khi đó lợi nhuận thu được P P bởi nhà máy thứ i được cho bởi fi (x) = pi (s)( j∈Ii xj ) − j∈Ii cj (xj ), trong đó cj (xj ) là hàm chi phí để sản xuất lượng điện xj bởi máy phát thứ i. Giả sử Ki ⊆ R là tập chiến lược của nhà máy thứ i, tức là điều kiện P j∈Ii xj ∈ Ki phải được thỏa mãn với mọi i. Khi đó tập chiến lược của mô hình là K := K1 × K2 ... × Kn . Mỗi nhà máy tìm kiếm lợi nhuận cực đại bằng cách chọn mức sản xuất tương thích dưới căn cứ sản lượng của các nhà máy khác là tham số đầu vào. Một cách tiếp cận chung cho mô hình này là dựa trên khái niệm cân bằng Nash. 12
Chúng tôi nhắc lại rằng x∗ ∈ K = K1 × K2 × · · · × Kn là một điểm cân bằng Nash của mô hình nếu fi (x∗ ) ≥ fi (x∗ [xi ]) ∀xi ∈ Ki , ∀i = 1, 2, . . . , n, trong đó x∗ [xi ] là véctơ thu được từ x∗ bằng cách thay x∗i bởi xi . Đặt f (x, y) := ψ(x, y) − ψ(x, x) với n X ψ(x, y) := − fi (x[yi ]), (2.10) i=1 thì bài toán tìm điểm cân bằng Nash của mô hình có thể đưa về bài toán x∗ ∈ K : f (x∗ , x) ≥ 0 ∀x ∈ K. (EP ) Chúng tôi mở rộng mô hình cân bằng này bằng cách thêm một giả thiết rằng để sản xuất điện thì các nhà máy phải sử dụng nguyên vật liệu. Kí hiệu al,j là số lượng vật liệu l (l = 1, ..., m) cho việc sản xuất một đơn vị điện bởi máy phát j (j = 1, ..., N ). Đặt A là ma trận với các phần tử là al,j . Khi đó hàng l của véctơ Ax là số lượng vật liệu l cho việc sản xuất x. Sử dụng vật liệu cho sản xuất có thể làm ô nhiễm môi trường và mỗi nhà máy phải trả phí môi trường. Giả sử g(Ax) là toàn bộ phí môi trường cho việc sản xuất x. Nhiệm vụ đặt ra bây giờ là tìm một sản lượng x∗ sao cho nó là điểm cân bằng Nash với phí môi trường thấp nhất. Bài toán này có thể đưa về dạng Tìm x∗ ∈ K : f (x∗ , x) ≥ 0 ∀x ∈ K, g(Ax∗ ) ≤ g(Ax) ∀x ∈ K. (SEP ) Giả sử với mỗi j , hàm chi phí cj và phí môi trường g là các hàm lồi tăng. Các giả thiết lồi ở đây có nghĩa là hàm chi phí sản xuất và phí môi trường cho việc sản xuất một đơn vị điện tăng khi số lượng điện tăng. Dưới giả thiết lồi, ta thấy bài toán (EP) với hàm f cho bởi (2.10) có thể đưa về dạng Tìm x∗ ∈ K : hB˜1 x∗ − a¯, x − x∗ i + ϕ(x) − ϕ(x∗ ) ≥ 0 ∀x ∈ K, (2.11) 13
trong đó ¯ := (α, α, ..., α)T a     β1 0 0 ... 0 0 β1 β1 ... β1     0 β2 0 ... 0   , B˜1 :=  β2 0 β2 ... β2   B1 :=   ... ,  ... ... ... ...    ... ...  ... ... ...   0 0 0 0 βn βn βn βn ... 0 N X T ϕ(x) := x B1 x + cj (xj ). j=1 Chú ý rằng khi cj là các hàm lồi khả vi với mỗi j , thì bài toán (2.11) có thể quy về bài toán bất đẳng thức biến phân sau Tìm x∗ ∈ K : hB˜1 x∗ − a¯ + ∇ϕ(x∗ ), x − x∗ i ≥ 0, ∀x ∈ K. (2.12) Chúng tôi thử nghiệm Thuật toán 2.1 với hàm chi phí cho bởi 1 cj (xj ) = pj x2j + qj xj , pj > 0. 2 Với hàm chi phí này, thì toán tử trong bài toán (2.12) là toán tử para-đơn điệu. Lấy các dãy tham số là 7 βk = , k = 0, δk = 3, γk = max{3, ||gk ||} ∀k 2(k + 1) và giải mô hình với các cỡ khác nhau, 10 bài toán mỗi cỡ. Thuật toán được chạy thực hiện bằng Matlab 7.8 trên máy tính Ram 8GB core i7. Các bài toán con được giải bằng MATLAB Optimization Toolbox bằng công cụ QUADPROG cho các hàm bậc hai nửa xác định dương g(u) := 1/2uT Du + dT u. Các kết quả tính toán được trình bày trong Bảng 2.1. Các trục ngang và trục dọc biểu thị số bước lặp trung bình k , thời gian CPU (giây) trung bình và error1 := ||x − y||, error2 := h(x), tương ứng. Các 14
tham số βj , pj , qj , với mọi j = 1, . . . , n, được sinh ngẫu nhiên trong khoảng (0,1], [1,3], [1,3] tương ứng, các ma trận A, D và véctơ d được sinh ngẫu nhiên trong khoảng [-2,30]. Bảng 2.1. Thuật toán 2.1 size N Prob. Iter CPU-times(s) Error 1 Error 2 6 10 1654 51.13 9.9996.10−5 1.1.10−6 10 10 19793 622.09 9.7011.10−5 7.8.10−4 20 10 25690 1282.10 9.9801.10−5 0.0565 30 10 32001 1059.12 9.9504.10−5 0.3283 −5 50 10 67344 3213.47 9.8034.10 2.9610 15
Chương 3 Thuật toán dưới đạo hàm giải bài toán chấp nhận tách phi tuyến và ứng dụng cho mô hình cân bằng Nash có ràng buộc Trong chương này, chúng tôi trình bày một thuật toán mới giải bài toán chấp nhận tách (NSEP) và xét một ứng dụng của bài toán này cho mô hình cân bằng Nash có ràng buộc. Cụ thể, bài toán xét ở đây có dạng Tìm x ∈ K sao cho f (x, y) ≥ 0, ∀y ∈ K thỏa mãn F (x) ∈ Q, trong đó F là toán tử tựa tuyến tính. Kết quả của chương này được viết dựa trên nội dung bài báo (2) đăng trên tạp chí Journal of Global Optimization nằm trong Danh mục công trình của tác giả liên quan đến luận án. 3.1. Mô tả bài toán Xét bài toán chấp nhận tách như sau: Tìm z ∈ K sao cho f (z, u) ≥ 0, ∀u ∈ K và F (z) ∈ Q, (N SEP ) 6 K ⊆ Rn là tập lồi, f : K × K → R, ∅ = trong đó ∅ = 6 Q ⊆ Rm và F : Rn → Rm là toán tử tựa tuyến tính được xác định bởi các hàm tựa tuyến tính. 16
3.2. Thuật toán và sự hội tụ Giả sử bài toán (N SEP ) có nghiệm và thỏa mãn các giả thiết sau. Giả thiết (B1) Q = Q1 × Q2 × · · · × Qm trong đó Qi là một tập con lồi của R với mỗi i = 1, 2, . . . , m; (B2) F = (F1 , F2 , . . . , Fm ) trong đó Fi : Rn → R là tựa tuyến tính, tức là, F vừa tựa lồi vừa tựa lõm và khả vi trên một tập mở chứa K . (B3) Với mỗi x ∈ K , song hàm f (x, .) là hàm lồi, khả dưới vi phân, f (., x) nửa liên tục trên trên một tập lồi mở chứa K và f (x, x) = 0 với mỗi x ∈ K. (B4) Song hàm f giả đơn điệu trên K đối với tập nghiệm Sol(EP ) của bài toán (EP ), tức là f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0 ∀x ∈ Sol(EP ), y ∈ K. Kí hiệu Sol(EP ) là tập nghiệm của bài toán cân bằng: Tìm z ∈ K sao cho f (z, u) ≥ 0 ∀u ∈ K. (EP ) Khi đó, dưới giả thiết (B1), (B2), bài toán (N SEP ) có thể đưa về dạng min max |(I − PQi )(Fi (x))|2 , (OP ) x∈C i=1,2,...,m với C là tập nghiệm của (EP). Với mỗi x ∈ K , đặt pi (x) = |(I − PQi )(Fi (x))|2 , p(x) = max pi (x), i=1,...,m I(x) : = {i : pi (x) = p(x)}. Bổ đề sau chỉ ra hàm pi (x) và p(x) là các hàm tựa lồi. 17
Bổ đề 3.1 Giả sử các giả thiết (B1) và (B2) thỏa mãn. Khi đó, các mệnh đề sau đúng i) Hàm pi tựa lồi và khả vi trên K ; ii) Hàm p tựa lồi trên K . Thuật toán cho bài toán (NSEP) được mô tả như sau: Thuật toán 3.1 Lấy số dương δ và các dãy số thực {δk }, {βk }, {k } thỏa mãn các điều kiện δk > δ > 0, βk > 0, k ≥ 0, ∀k ∈ N; (3.1) ∞ ∞ X X βk k k < +∞, < +∞; (3.2) δk k=1 k=1 ∞ ∞ X βk X = +∞, βk2 < +∞; (3.3) δk k=1 k=1 Bước 0: Lấy x1 ∈ K và đặt k := 1. Bước k: Có xk ∈ K . Lấy gk ∈ ∂2k f (xk , xk ) và xác định βk αk = trong đó γk = max{δk , kgk k}. γk Tính yk = PK (xk − αk gk ). Nếu ∇pi (yk ) = 0 ∀i ∈ I(yk ) thì lấy bhk = 0; Ngược lại, lấy 0 6= hk ∈ co {∇pi (yk ), i ∈ I(yk )} và đặt h hk = k . b khk k Tính xk+1 = PK (yk − αkb hk ), tăng k bởi 1 và quay lại bước k . Nhận xét 3.1 (i) Nếu k = 0, xk = yk và p(xk ) = 0, thì xk là một nghiệm chính xác. Vì vậy, xk được gọi là một − nghiệm nếu k ≤ , ||xk − yk || ≤ và p(xk ) ≤ . 18