Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Một số phương pháp giải bài toán cân bằng và ứng dụng....

Tài liệu Một số phương pháp giải bài toán cân bằng và ứng dụng.

.PDF
27
642
67

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ PHẠM MINH TUẤN MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CÂN BẰNG VÀ ỨNG DỤNG Chuyên ngành: Cơ sở toán học cho tin học Mã số: 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2017 Công trình được hoàn thành tại: VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ - BỘ QUỐC PHÒNG Người hướng dẫn khoa học: 1. PGS. TS Phạm Ngọc Anh 2. TS Nguyễn Mạnh Linh Phản biện 1: GS.TSKH Lê Dũng Mưu Phản biện 2: GS.TS Nguyễn Hữu Dư Phản biện 3: PGS.TS Nguyễn Bá Minh Luận án sẽ được bảo vệ trước Hội đồng chấm luận án cấp Viện, họp tại Viện KH&CNQS Vào hồi giờ ngày tháng năm 2016 Có thể tìm hiểu luận án tại thư viện: - Thư viện Viện Khoa học và Công nghệ quân sự - Thư viện Quốc gia Việt Nam 1 MỞ ĐẦU Trong những năm gần đây, bài toán cân bằng được đặc biệt quan tâm nghiên cứu cả trong lý thuyết và ứng dụng. Bài toán cân bằng bao hàm nhiều lớp bài toán quan trọng trong giait tích phi tuyến và tối ưu như bài toán cân bằng Nash, bất đẳng thức biến phân, bài toán bù phi tuyến, bài toán tối ưu (tối ưu véc tơ), bài toán điểm bất động, bài toán điểm yên ngựa và lý thuyết trò chơi. Hơn nữa nó hợp nhất các bài toán này với một cấu trúc rõ ràng tiện lợi cho việc nghiên cứu các bài toán phức tạp nảy sinh trong thực tiễn. Các nghiên cứu định tính đã thu được nhiều kết quả quan trọng. Các nghiên cứu về phương pháp giải cũng đã đạt được nhiều kết quả, tuy nhiên việc nghiên cứu giải bài toán cân bằng với những giả thiết phù hợp và hiệu quả hơn vẫn đang được tiếp tục nghiên cứu. Với các mô hình ứng dụng cụ thể các thuật toán giải bài toán cân bằng đều thực hiện được trên máy tính, trong đó, phần mềm Matlab là một công cụ hữu hiệu giải các bài toán tối ưu nói chung và các bài toán cân bằng nói riêng. Các phương pháp giải bài toán cân bằng có thể phân theo ba cách tiếp cận khác nhau. Hướng thứ nhất là sử dụng hàm đánh giá. Phương pháp này thay việc giải trực tiếp bài toán cân bằng bằng phương pháp dựa trên hàm đánh giá đưa bài toán cân bằng về bài toán tối ưu phù hợp. Sau đó sử dụng phương pháp tối ưu cục bộ để giải các bài toán tối ưu. Phương pháp hàm đánh giá xuất hiện trong toán học ứng dụng và tối ưu, và được sử dụng cho bài toán bất đẳng thức biến phân bởi Zhu và Marcotte. Mastroeni phát triển phương pháp này cho bài toán cân bằng. Cách tiếp cận thứ hai dựa trên nguyên lý bài toán phụ. Bài toán cân bằng được đưa về bài toán tương đương, được gọi là bài toán phụ, dễ giải hơn. Nguyên lý này được giới thiệu bởi Cohen cho bài toán tối ưu và sau đó ứng dụng cho bài toán bất đẳng thức biến phân. Mastroeni áp dụng phương pháp này cho bài toán cân bằng đơn điệu mạnh và liên tục kiểu Lipschitz. Cách tiếp thứ ba là phương pháp điểm gần kề. Phương pháp điểm gần kề được Martinet phát hiện để giải bài toán bất đẳng thức biến phân và sau đó được Rockafelar sử dụng để 2 tìm nghiệm bài toán tìm không điểm cho ánh xạ đơn điệu cực đại. Gần đây, nhiều nghiên cứu đã được phát triển cho bài toán cân bằng. Luận án "Một số phương pháp giải bài toán cân bằng và ứng dụng" đề xuất một số phương pháp mới giải bài toán cân bằng và đưa ra một số ví dụ minh họa cho mô hình cân bằng Nash-Cournot. Cấu trúc của luận án Luận án ngoài phần mở đầu, kết luận, tài liệu tham khảo được chia thành bốn chương: • Chương 1. Bài toán cân bằng • Chương 2. Phương pháp xấp xỉ trong • Chương 3. Phương pháp xấp xỉ ngoài • Chương 4. Phương pháp lặp egodic 3 Chương 1 BÀI TOÁN CÂN BẰNG Trong chương này, luận án nhắc lại định nghĩa bài toán cân bằng và một số tính chất đơn điệu, liên tục kiểu Lípchitz và một số phương pháp giải đã biết của bài toán cân bằng. Định nghĩa 1.1. Cho C là một tập con lồi, đóng, khác rỗng trong không gian Rn và song hàm f : C × C → R ∪ {+∞}. Bài toán cân bằng (Viết tắt, EP (f, C)) được định nghĩa như sau: Tìm x∗ ∈ C sao cho f (x∗ , x) ≥ 0, ∀x ∈ C. ở đó f (x, x) = 0 với mọi x ∈ C. song hàm thỏa mãn điều kiện này được gọi là song hàm cân bằng trên C. Định nghĩa dưới đây nhắc lại một số tính chất đơn điệu của song hàm cân bằng: Định nghĩa 1.2. Cho C là tập con lồi, đóng, khác rỗng trên Rn . Song hàm f : C × C → R ∪ {+∞}, được gọi là: (i) đơn điệu trên C, nếu f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; (ii) đơn điệu chặt trên C, nếu f (x, y) + f (y, x) < 0, ∀x, y ∈ C và x 6= y; (iii) giả đơn điệu trên C, nếu f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C; 4 (iv) đơn điệu mạnh trên C với hằng số γ > 0, nếu f (x, y) + f (y, x) ≤ −γkx − yk2 , ∀x, y ∈ C; (v) giả đơn điệu mạnh trên C với hằng số γ > 0, nếu f (x, y) ≥ 0 ⇒ f (y, x) ≤ −γkx − yk2 , ∀x, y ∈ C; (vi) liên tục kiểu Lipschitz trên C với hằng số c1 > 0, c2 > 0, nếu f (x, y) + f (y, z) ≥ f (x, z) − c1 kx − yk2 − c2 ky − zk2 , ∀x, y, z ∈ C, Từ định nghĩa, ta có: (iv) ⇒ (ii) ⇒ (i) ⇒ (iii); (iv) ⇒ (v) ⇒ (iii) . Một số phương pháp giải đã biết Phần này trình bày một số bài toán cân bằng EP (f, C) đã biết với các điều kiện của song hàm và tập ràng buộc phù hợp. Thuật toán 1.1. Phương pháp điểm gần kề Bước 0. Chọn k := 0, x0 ∈ C và β > 0. Bước 1. Tìm xk+1 ∈ C, sao cho f (xk+1 , y) + β xk+1 − xk , y − xk+1 ≥ 0, ∀y ∈ C. Bước 2. nếu xk+1 = xk thì Dừng. Ngược lại, k := k + 1 và quay lại Bước 1. Thuật toán 1.2. Phương pháp điểm bất động Bước 0. Chọn x0 ∈ C, k := 0. 5 Bước 1. Tìm xk+1 ∈ C là một nghiệm của bài toán dưới đây  min f (xk , y) : y ∈ C . Bước 2. nếu xk+1 = xk thì Dừng và xk là một nghiệm của EP (f, C). Ngược lại, k := k + 1 và quay lại Bước 1. Thuật toán 1.3. Phương pháp nguyên lý bài toán phụ Bước 0. Chọn x0 ∈ C, k = 0 và λ > 0. Bước 1. Tìm xk+1 ∈ C là một nghiệm của bài toán dưới đây  min λf (xk , y) + h(xk , y) : y ∈ C . Bước 2. nếu xk+1 = xk thì Dừng, xk là một nghiệm. Ngược lại, đặt k := k + 1 và quay lại Bước 1. Ở đó, h : C × C → R, sao cho (A1 .) h không âm và khả vi liên tục trên C × C, (A2 .) h(x, x) = 0 và ∇h(x, .)(x) = 0, ∀x ∈ C, (A3 .) h(x, .) lồi mạnh, ∀x ∈ C. Thuật toán 1.4. Phương pháp chiếu Bước 0. Chọn x0 ∈ C, k = 0. Bước 1. Tìm xk+1 ∈ C là một nghiệm của bài toán dưới đây  1 min λf (xk , y) + kxk − yk2 : y ∈ C . 2 Bước 2. nếu xk+1 = xk thì Dừng, xk là một nghiệm. Ngược lại, đặt k := k + 1 và quay lại Bước 1. 6 Thuật toán 1.6. Phương pháp đạo hàm tăng cường Bước 0. Chọn x0 ∈ C, k = 0, α ∈ (0, 1), ρ ∈ (0, 1), β > 0 và dãy số dương {γk }. Bước 1. Tìm y k là nghiệm của bài toán dưới đây:   1 k k 2 min βf (x , y) + ky − x k : y ∈ C . 2 nếu y k = xk , thì Dừng và xk là một nghiệm của EP (f, C). Ngược lại y k 6= xk , thực hiện Bước 2. Bước 2. Tìm m là số nguyên không âm nhỏ nhất sao cho f (z k,m , xk ) − f (z k,m , y k ) ≥ α k ky − xk k2 , β ở đó z k,m = (1 − ρm )xk + ρm y k . đặt z k := z k,m và thực hiện Bước 3. Bước 3. Chọn g k ∈ ∂f (z k , ·)(xk ), tính σk := f (z k , xk ) kg k k2 và xk+1 := P rC (xk − γk σk g k ). đặt k := k + 1 và quay lại Bước 1. 7 Chương 2 PHƯƠNG PHÁP XẤP XỈ TRONG Chương này trình bày hai phương pháp mới giải bài toán cân bằng. Thứ nhất là phương pháp chiếu cải tiến giải bài toán cân bằng giả đơn điệu mạnh. Thứ hai là phương pháp xấp xỉ trong giải bài toán giả đơn điệu không đòi hỏi điều kiện liên tục kiểu Lipschitz. 2.1.1 Phương pháp chiếu cải tiến Phần này trình bày một phương pháp mới để giải bài toán cân bằng giả đơn điệu mạnh. Ước lượng sai số nghiệm cho dãy lặp được sinh ra bởi thuật toán được xác định với một vài giả thiết. Một ví dụ minh họa được trình bày. 2.1 Thuật toán Cho  > 0. gọi điểm x̄ ∈ C là một -nghiệm của EP (f, C) nếu tồn tại x∗ ∈ Sol(f, C) sao cho kx̄ − x∗ k ≤ . Xét bài toán cân bằng với song hàm f is γ-giả đơn điệu mạnh và liên tục kiểu Lipschitz với các hằng số c1 > 0 và c2 > 0 trên C. Thuật toán 2.1. Chọn dãy số dương {λk } thỏa mãn các điều kiện sau: 0 < a ≤ λk ≤ b < 1 1 , c2 < γ,  > 0, δ = p . 2c1 1 + 2a(γ − c2 ) Bước 0: k = 0, Chọn x0 ∈ C. Bước 1: Giải bài toán lồi mạnh: x k+1 n o 1 k k 2 = argmin λk f (x , y) + ky − x k : y ∈ C . 2 8 (1 − δ) , thì kết thúc: xk+1 là -nghiệm δ của EP (f, C). Ngược lại, đặt k := k + 1 và quay lại Bước 1. Bước 2: Nếu kxk − xk+1 k < Định lý 2.1. Cho f : C × C → R là γ- giả đơn điệu mạnh trên C, liên tục kiểu Lipschiz với các hệ số c1 > 0 và c2 > 0. Với mỗi x ∈ C, f (x, ·) lồi khả dưới vi phân trên C. Thì Sol(f, C) có nghiệm duy nhất x∗ và [1 + 2λk (γ − c2 )]kxk+1 − x∗ k2 ≤ kxk − x∗ k2 , ∀k ≥ 0. Hơn nữa, dãy {xk } được sinh bởi Thuật toán 2.1. hội tụ tới nghiệm x∗ với sai số như sau: kxk+1 − x∗ k ≤ và kxk+1 − x∗ k ≤ δ k+1 0 kx − x∗ k 1−δ δ kxk − xk+1 k. 1−δ Hệ quả 2.1. Cho F : C → Rn là γ-đơn điệu mạnh và liên tục Lipschitz 2γ 1 với L > 0. Cho 0 < a ≤ λk ≤ b < 2 , δ = p và dãy L 1 + 2a (γ − L)  k x được xác định bởi x0 ∈ C, xk+1 := P rC (xk − λk F (xk )), ∀k ≥ 0.  thì xk hội tụ tới nghiệm x∗ của bài toán bất đẳng thức biến phân V I(F, C) với sai số: kxk+1 − x∗ k ≤ δ k+1 kx0 − x∗ k và kxk+1 − x∗ k ≤ δ kxk − xk+1 k. 1−δ 9 2.1.2 Ví dụ minh họa Ví dụ 2.1. n Xét now EP (f, C) với C = (x1 , x2 , x3 , x4 , x5 )T : x1 , x2 , x3 , x4 , x5 ∈ R+ , x1 + x2 + x3 + 2x4 + x5 ≤ 10, 2x1 + x2 − x3 + x4 + 3x5 ≤ 15, o x1 + x2 + x3 + x4 + 0.5x5 ≥ 4 ; f (x, y) = hAx + χn (y + x) + µ − α, y − xi − kx − yk2 . Ở đó  1 χ  A= χ χ χ χ 1 χ χ χ χ χ 1 χ χ χ χ χ 1 χ  χ χ  T T χ  , α = (α0 , · · · , α0 ) , µ = (µ1 , · · · , µn ) . χ 1 5×5 Ta có, f giả đơn điệu mạnh trên C × C với hằng số γ = 2. Dễ γ 1 dàng thấy f liên tục kiểu Lipschitz với các hằng số c1 ≥ + kAk và 2 5 γ 1 −4 0 c2 ≥ + kAk. Các tham số được chọn:  = 10 , x = (1, 2, 1, 1, 1)T ∈ 2 5 1 C, χ = 1, α0 = 2, µ = (3, 4, 5, 7, 6)T . Chọn c2 = τ + kAk = 1.8 và 2 1 = 0.2778, chọn λk = a = b = 0.2 c1 = 6.2. Từ 0 < a ≤ λk ≤ b < 2c1 với mọi k ≥ 0. thì δ = 0.9623. Nghiệm xấp xỉ sau 11 bước lặp là: x11 = (0.9467, 0.9447, 0.9426, 0.9405, 0.4510)T . 2.2. Phương pháp xấp xỉ trong Phần này trình bày một phương pháp xấp xỉ trong giải bài toán cân bằng, với song hàm giả đơn điệu, không đòi hỏi điều kiện liên tục kiểu Lipschitz, trên tập đa diện. Phương pháp này là sự kết hợp giữa việc sử dụng hàm xấp xỉ trong thay cho hàm dạng toàn phương trong 10 phương pháp bài toán phụ, kỹ thuật tìm đường kiểu Armijo và phương pháp siêu phẳng cắt. Chúng ta đã biết rằng, kỹ thuật xấp xỉ trong là một công cụ mạnh để phân tích và giải các bài toán tối ưu. Kỹ thuật này được sử dụng rộng rãi để giải các bất đẳng thức biến phân và các bài toán cân bằng trên tập hợp lồi đa diện, trong đó sử dụng hàm xấp xỉ trong d thay thế cho hàm h trong AuxEP (f, C), có dạng:    n X 1 xi x i xi  2 2  yi ln − + 1   2 kx − yk + µ yi yi yi i=1 d(x, y) =  nếu xi > 0 ∀i = 1, · · · , n,    +∞ nếu ∃i : xi 6 0, với µ ∈ (0, 1) và y ∈ Rn+ := {(x1 , · · · , xn )T ∈ Rn : xi > 0 ∀i = 1, · · · , n}. Phần này giải bài toán EP (f, C), với song hàm f và C thỏa mãn các điều kiện dưới đây: B1 . C = {x ∈ Rn : Ax ≤ b}, ở đó A là ma trận (p × n) (p > n, rankA = n), b ∈ Rp , và int(C) = {x : Ax < b} khác rỗng,C bị chặn. B2 . Với mỗi x ∈ C, f (x, ·) lồi và khả dưới vi phân trên C. B3 . f giả đơn điệu trên C. B4 . f liên tục trên C × C. B5 . Sol(f, C) 6= ∅. 2.2.1. Thuật toán Kí hiệu ai là các dòng của ma trận A, và li (x) = bi − hai , xi, 11 l(x) = (l1 (x), l2 (x), · · · , lp (x)), D(x, y) = d (l(x), l(y)). Khi đó đạo hàm ∇D(·, y) của D(·, y) tại x với mọi y ∈ C được xác định bởi   l(x) T , ∇D(·, y)(x) = −A l(x) − l(y) + µXy ln l(y) ở đó Xy = diag  (l1 (y), · · · , lp (y))  l(x) l1 (x) lp (x) và ln = ln , · · · , ln . l(y) l1 (y) lp (y) Thuật toán 2.2. Bước 0. Chọn x0 ∈ C, 0 < σ < β và γ ∈ (0, 1). 2kĀ−1 k2 Bước 1. Tính  y k := argmin f (xk , y) + βD(y, xk ) : y ∈ C , r(xk ) := xk − y k . nếu r(xk ) = 0 thì Dừng. Ngược lại, đặt z k := xk − γ mk r(xk ), ở đó mk là số nguyên không âm nhỏ nhất sao cho  f xk − γ mk r(xk ), y k ≤ −σkr(xk )k2 . Bước 2. Tính xk+1 := P rCk ∩Hk (x0 ), ở đó (  Ck = x ∈ C : f (z k , x) ≤ 0 ,  Hk = x ∈ Rn : x − xk , x0 − xk ≤ 0 . k := k + 1 và quay lại Bước 1. 12 Định lý 2.2. Giả sử các  k giả thiết (B1 ) − (B5 ) thỏa mãn, ∂f (x, ·)k nửa liên tục trên trên C, x được sinh bởi Thuật toán 2.2. và {x } ∈  int(C) với mọi k. thì xk hội tụ tới một nghiệm x∗ of EP (f, C), ở đó x∗ = P rSol(f,C) (x0 ). Định lý 2.3. Giả sử thỏa  k mãn các điều kiện (B1 )−(B4 ) và ∂fk (x, ·) nửa liên tục trên trên C, x được sinh bởi Thuật toán 2.2., x ∈ int(C) với mọi k và Sol(f, C) = ∅. thì, lim kxk − x0 k = +∞. k→∞ 2.2.2 Ví dụ minh họa Ví dụ 2.2. Xét the mô hình cân bằng Cournot-Nash (Moudafi, A: Proximal point algorithm extended to equilibrium problem). Bài toán EP (f, C) được xác định như sau: f (x, y) = hM (x + y) + hx, di B(x + y) + q, y − xi , ở đó  1 1  M = 0 3 3 2 0 0 3 4   5 1 2   6 9 0 3 4 3 , B =   0 1 1 2 0 1     1 3 3 2      , d = 0 0 q=     1 4 5 9 3 0 9 3 5 4 5 2 4 1 3 2 5 2 2 4 1 2 3 3  1 3  4 , 7 4 13 n và C = (x1 , x2 , x3 , x4 , x5 )T : x1 , x2 , x3 , x4 , x5 ∈ R+ , 4 ≤ x1 + 2x2 + x3 + 3x5 ≤ 12, 7 ≤ 5 X xi ≤ 15, i=1 o 6 ≤ x2 + x3 + 2x4 ≤ 13, 3 ≤ x2 + x3 ≤ 5. Dãy lặp được cho bởi Bảng 2.2. Bảng 2.2. Dãy lặp của Ví dụ 2.2. k 0 10 20 50 100 150 180 200 250 300 350 355 358 360 361 xk1 1 4.3842 4.4657 4.4901 4.4976 4.5001 4.5012 4.5106 4.5309 4.5370 4.5389 4.5395 4.5396 4.5397 4.5397 xk2 3 0.0001 00.0013 0.0017 0.0082 0.0099 0.0107 0.0142 0.0412 0.0494 0.0519 0.0526 0.0528 0.0529 0.0529 xk3 1 3.4633 3.1371 3.0404 3.0117 3.0031 3.0005 2.9716 2.9176 2.9013 2.8963 2.8948 2.8943 2.8942 2.8942 xk4 1 1.7683 1.9315 1.9796 1.9938 1.9979 1.9989 2.0071 2.0206 2.0247 2.0259 2.0263 2.0264 2.0264 2.0265 xk5 1 1.3842 1.4657 1.4898 1.4969 1.4990 1.4995 1.4965 1.4897 1.4877 1.4870 1.4868 1.4868 1.4868 1.4868 2.3 Kết luận Chương này trình bày hai thuật toán mới giải bài toán cân bằng. Thứ nhất là phương pháp chiếu cải giải bài toán giả đơn điệu mạnh. Thứ hai là phương pháp xấp xỉ trong giải bài toán giả đơn điệu liên tục kiểu Lipschitz. Hơn nữa, ở đây cũng đưa ra mối liên hệ giữa việc tồn tại nghiệm của bài toán cân bằng và sự hội tụ của dãy lặp của 14 thuật toán xấp xỉ trong. Một số ví dụ minh họa cũng được trình bày cho hai thuật toán đề xuất. Chương 3 PHƯƠNG PHÁP XẤP XỈ NGOÀI Trong chương này, chúng tôi đề xuất hai thuật toán xấp xỉ ngoài mới để giải bài toán cân bằng trên miền ràng buộc phi tuyến. Chiến lược ở đây là thay miền ràng ràng buộc của thuật toán đạo hàm tăng cường hiện thời bằng các đa diện. Thuật toán thứ nhất là cải tiến thuật toán đạo hàm tăng cường với điều kiện tối ưu tiệm cận và đòi hỏi song hàm cân bằng thỏa mãn điều kiện liên tục kiểu Lipschitz. Tiếp theo để tránh đòi hỏi này, chúng tôi kết hợp phương pháp đạo hàm tăng cường với phươngpháp tìm đường kiểu Armijo, đã được sử dụng trong việc giải bài toán bất đẳng thức biến phân. Hơn nữa, chúng tôi nghiên cứu sự hội tụ về nghiệm của thuật toán thứ nhất với điều kiện có sai số tính toán. Xét bài toán EP (f, C) với: C = {x ∈ Rn : ci (x) ≤ 0 ∀i = 1, 2, · · · , p} , ở đó ci là các hàm lồi, khả vi liên tục, và ∃x̄ ∈ Rn : ci (x̄) < 0, ∀i = 1, 2, · · · , p. Song hàm cân bằng f : Rn × Rn → R ∪ {+∞} thỏa mãn: (C1.) Với mỗi x ∈ Rn , f (x, ·) lồi, khả dưới vi phân trên Rn ; (C2.) Với mỗi x ∈ Rn , f (·, x) liên tục trên Rn ; (C3.) Sol(f, C) 6= ∅. 15 Đặt C(x) := {y ∈ Rn : ci (x) + h5ci (x), y − xi ≤ 0 ∀i = 1, 2, · · · , p}. 3.1 Phương pháp xấp xỉ ngoài Thuật toán 3.1  Bước 0. Chọn σ ∈ (0, 1), x0 ∈ Rn , βk ∈ 0,  1−σ 2 max {c1 , c2 } ∀k = 0, 1, ..., và lim inf βk > 0. k→∞ Bước 1. Giải bài toán lồi mạnh:   1 k 2 k k k y := argmin βk f (x , y) + ky − x k : y ∈ C(x ) . 2 (1) Đặt r(xk ) := y k − xk . nếu kr(xk )k = 0 thì Dừng. Ngược lại, thực hiện Bước 2. Bước 2. Giải bài toán lồi mạnh:   1 k 2 k k+1 k x := argmin βk f (y , y) + ky − x k : y ∈ C(x ) . 2 Đặt k := k + 1, quay lại Bước 1. Định lý 3.1. Cho f liên tục kiểu Lipschiz và điều kiện tối ưu tiệm cận sau được thỏa mãn Ω := ∞ \ k=1 Ωk = ∞ \  u ∈ Sol(f, C) : f (y k , u) ≤ 0 6= ∅. k=1   thì, dãy xk và y k hội tụ tới cùng một nghiệm x∗ của bài toán EP (f, C).  Chú ý 3.1. Với Ωk := u ∈ Sol(f, C) : f (y k , u) ≤ 0 , điều kiện Ω := ∞ \ k=1 Ωk 6= ∅ 16 được gọi là tối ưu tiệm cận của bài toán EP (f, C) được đề xuất bởi Iiduka và Yamada, Iusem và Sosa. Nó cũng là điều kiện chính quy cho thuật toán đạo hàm tăng cường lai ghép cho bài toán tựa cân bằng được Strodiot, Van và Hien sử dụng. 3.2 Phương pháp xấp xỉ ngoài tìm đường kiểu Armijo Thuật toán 3.2. Bước 0. Chọn σ > 0, x0 ∈ C, 0 < σ < β , và γ ∈ (0, 1). 2 Bước 1. Tính  β k 2 k y := argmin f (x , y) + ky − x k : y ∈ C(x ) , 2  k k r(xk ) = xk − y k . nếu r(xk ) = 0 thì Dừng. Ngược lại, Tìm số nguyên không âm nhỏ nhất mk sao cho  f xk − γ mk r(xk ), y k ≤ −σkr(xk )k2 . đặt z k := xk − γ mk r(xk ). Chọn w̄k ∈ ∂f (z k , ·)(z k ). Bước 2. Tính xk+1 := P rC∩Hk (xk ), ở đó  Hk = x ∈ Rn : w̄k , x − z k ≤ 0 . đặt k := k + 1, quay lại Bước 1. Định lý 3.2. Giả  ksử điều kiện tối ưu tiệm cận được thỏa mãn và dãy k C(x ) bị chặn, w̄ bị chặn bởi M > 0. thì, kx k+1 ∗ 2 k ∗ 2 − x k ≤ kx − x k − kx k+1 γ mk σ − ȳ k − M (1 − γ mk ) k 2  2 kr(xk )k4 ,  Thì dãy xk được sinh bởi Thuật toán 3.2. hội tụ tới một nghiệm của bài toán EP (f, C). 17 3.3 Sai số tính toán Trong phần này, chúng tôi xét sự hội tụ của Thuật toán 3.1. tới một nghiệm của bài toán EP (f, C), với lỗi trong tính toán. Giả sử tại mỗi bước lặp k, thuật toán 3.1. sinh ra các dãy {xk } và {y k } sao cho    1  k k k 2 k  ky − argmin βk f (x , y) + ky − x k : y ∈ C(x ) k ≤ , 2   1  k+1 k k 2 k  − argmin βk f (y , y) + ky − x k : y ∈ C(x ) k ≤ , kx 2 (2) với  > 0, phụ thuộc với mỗi máy tính. Trong trường hợp này, không thể có được các dãy {xk } và {y k } hội tụ về nghiệm của EP (f, C). Với mỗi τ > 0 kí hiệu Solτ là tập x̄ ∈ C sao cho kr(x̄)k ≤ τ . Mục đích ở đây là chỉ ra rằng các dãy được sinh bởi Lược đồ (2) hội tụ tới một nghiệm xấp xỉ thuộc Solτ . Kí hiệu các nghiệm chính xác của các bước là:   1 k 2 k k k (3) ŷ := argmin βk f (x , y) + ky − x k : y ∈ C(x ) , 2   1 k 2 k k+1 k x̂ := argmin βk f (ŷ , y) + ky − x k : y ∈ C(x ) , (4) 2   1 k 2 k k+1 k (5) x̄ := argmin βk f (y , y) + ky − x k : y ∈ C(x ) . 2 Gải sử các tham số và song hàm f thỏa mãn các điều kiện: (i) x∗ ∈ Sol(f, C),  ∈ (0, 1). (ii) σ1 > 0, σ2 > 0, |f (x, y)| ≤ σ2 , ∀x, y ∈ C(xk ) ⊂ B(x∗ , σ1 ) ∀k ≥ 0. (iii) f liên tục kiểu Lipschiz với các hằng số c1 > 0, c2 > 0 và đơn điệu trên B(x∗ , σ1 + σ2 + 1). (iv) 0 < 1 − 2(3c1 + c2 )βk , ∀k ≥ 0. 18 (v) Điều kiện tối ưu tiệm cận. (vi) (1 − 2c1 βi )¯2 − ᾱi > 0 ∀k, ở đó    p p 2 2 2  ᾱ :=  + α σ + δ α σ + δ + 2  +  k k 1 k k 1 k σ1 ,     7c1 βk αk := , (1 − 2c2 βk )(1 − 2(c2 + 3c1 )βk )    (σ2 + 6c1 2 )βk   . δk := (1 − 2c2 βk )(1 − 2(c2 + 3c1 )βk ) Định lý 3.3. Giả sử thỏa mãn các điều kiện (i) − (v) và 0 <  < ¯, một số dương 4σ12 , ∀i ≥ 0, K> (1 − 2c1 βi )¯2 − ᾱi ở đó ᾱi được định nghĩa bởi (6), và các dãy {xi } và {y i } được định nghĩa bởi Lược đồ (2). thì, tồn tại một số nguyên j ∈ [0, K] sao cho (a) kxj − y j k ≤ 2¯. (b) kxi − y i k > 2¯, ∀i = 0, 1, · · · , j − 1. (c) xj ∈ Sol3¯ . 3.4 Kết luận Để giải bài toán EP (f, C), tại các bước lặp k, hầu hết các thuật toán hiện nay giải bài toán trên tập lồi. Để thực hiện tính toán này trong một số trường hợp không đơn giản. Để khắc phục vấn đề này chúng tôi đã thay thế tập lồi nói chung bằng đa diện Ck tại mỗi bước lặp. Chúng tôi đã đề xuất hai phương pháp giải bài toán cân bằng với điều kiện liên tục kiểu Lipschiz hoặc không. Đầu tiên, chúng tôi đề xuất thuật toán xấp xỉ ngoài giải bài toán cân bằng với điều kiện tối ưu tiệm cận và đòi hỏi song hàm cân bằng liên tục kiểu Lipschiz. Để tránh điều kiện liên tục kiểu Lipschitz chúng tối đề xuât thuật toán xấp xỉ ngoài tìm kiếm theo tia kiểu Armijo.
- Xem thêm -

Tài liệu liên quan