Luận án Phương pháp hàm phạt cho bài toán bất đẳng thức biến phân

huyển sang Bước k với k := k + 1. a2) Nếu x(k) /∈ D, đặt b := tk và tk := (a+b)/2. Đặt k := k+1 và quay lại Bước k. b) Nếu ||y(j) − PK(y(j) − λf (tk)(y(j)))|| > εk, chuyển sang Bước k2. • Bước k2: Tính y(j+1/2) := PK(y (j) − ηf (tk)(y(j))), y(j+1) := PK(y (j) − ηf (tk)(y(j+1/2))). Gán j := j + 1 và quay lại Bước k1. Trên đây PK(x) là hình chiếu của x lên K. Khi K có hình dạng đặc biệt, ta có thể tính PK(x) dễ dàng nhờ vào một công thức hiển (xem phần 1.2). Từ Định lý 1.3.1 và Định lý 1.4.2, vì εk → 0, ta có kết quả sau. 1.5.1 Định lí. Giả sử f là một ánh xạ đơn điệu trên miền lồi đóng K ⊃ D, P là một hàm phạt lồi khả vi của D. Hơn nữa giả sử P bị chặn dưới trên K, f và ∇P liên tục Lipschitz trên K. Gọi {x(k)} là dãy sinh bởi Thuật toán 3. Khi đó, một điểm giới hạn bất kỳ của {x(k)} là nghiệm của bài toán ban đầu VIP(D,f). Chứng minh. Không giảm tổng quát, vì nếu cần cho qua dãy con, ta có thể giả sử x (k) ∗ → x∗, 25 và x(k) → x¯, khi k → +∞. Theo Định lý 1.4.2 ta có x∗ là một nghiệm của bài toán ban đầu VIP(D,f). Mặt khác, theo phương pháp chiếu hai lần và do εk > 0 nên vòng lặp j sẽ kết thúc sau một số hữu hạn bước và tại bước lặp cuối cùng của vòng lặp j, ta có y(j) = x(k) thỏa mãn ‖x(k) − x(k)∗ ‖ ≤ εk. Qua giới hạn, do x (k) ∗ → x∗, x(k) → x¯, và εk → 0, ta được ‖x∗ − x¯‖ ≤ 0. Từ đó suy ra x¯ = x∗. Do x∗ là nghiệm của VIP(D,f), x¯ cũng là một nghiệm của VIP(D,f). 1.6 Ví dụ 1.6.1 Ví dụ. Xét D = {x ∈ Rn : g(x) ≤ 0} ∩K, trong đó K = {x = (x1, x2, . . . , xn)T ∈ Rn : 0 ≤ xi ≤ ai , i = 1, 2, . . . , n}, ai = 5 + i 3i− 1, g(x) = 1 n2 ∑ i exi − e 5 + n− 1 n2 . 26 Dễ thấy g(x) là một hàm lồi trên Rn. Chọn hàm P (x) ≡ g(x) trên Rn. Khi đó, P (x) ≤ 0, x ∈ D,P (x) > 0, x ∈ K \D. Ta sẽ bao D bởi K, do đó P là một hàm phạt của D. Hơn nữa, ∇P (x) = 1 n2 (ex1, ex2, . . . , exn)T . Do đó, ∇P (x) liên tục Lipschitz trên D với hằng số Lipschitz e6/n2. Ngoài ra, dễ thấy ∇P (x) còn đơn điệu mạnh với hằng số đơn điệu 1/n2. Do đó nếu f đơn điệu thì f (t) sẽ đơn điệu mạnh. Ánh xạ f được lấy theo mô hình Nash ([28]). f(x) = H(x)− p(σx)e− p′(σx)x, trong đó e = (1, . . . , 1)T ∈ Rn, σx = 〈x, e〉 = ∑ j xj, H(x) = (α1x1 + β1, . . . , αnxn + βn) T , với αi, βi, i = 1, . . . , n lấy ngẫu nhiên trong khoảng [0, 10]. Hàm p(t) được cho bởi p(t) = γ t+ 1 , trong đó γ lấy ngẫu nhiên trong khoảng [0, 15]. Ta có f chọn như trên là ánh xạ đơn điệu (tham khảo [28]). Ngoài ra, f liên tục Lipschitz với hằng số Lipschitz Ln = √ 2(α2 + 4n2γ2), trong đó α = max i αi. 27 Thật vậy, giả sử f = (f1, f2, . . . , fn), ta có fi(x) = αixi + βi − γ 1 + ∑ j xj + γxi (1 + ∑ j xj) 2 . Do đó fi(x)− fi(y) = αi(xi − yi) + γ ( 1 1 + ∑ j yj − 1 1 + ∑ j xj + xi (1 + ∑ j xj) 2 − yi (1 + ∑ j yj) 2 ) . Đặt N = 1 1 + ∑ j yj − 1 1 + ∑ j xj , Ni = xi (1 + ∑ j xj) 2 − yi (1 + ∑ j yj) 2 , và Mi = N +Ni. Ta có fi(x)− fi(y) = αi(xi − yi) + γMi. Do đó ( fi(x)− fi(y) )2 ≤ 2((αi(xi − yi))2 + (γMi)2). (1.6) Ta có M2i = (N +Ni) 2 ≤ 2(N2 +N2i ). (1.7) N2 = (∑ j(xj − yj) )2( (1 + ∑ j yj)(1 + ∑ j xj) )2 ≤ n ∑ j(xj − yj)2 1 = n‖x− y‖2. (1.8) Ta ước lượng N2i = ( xi (1 + ∑ j xj) 2 − yi (1 + ∑ j yj) 2 )2 . 28 Đặt ϕi(x) = xi (1 + ∑ r xr) 2 . Theo công thức số gia hữu hạn, tồn tại c ∈ [x,y] sao cho ϕi(x)− ϕi(y) = ∑ j ∂ϕi ∂xj (c)(xj − yj). Do đó N2i = ( ϕi(x)− ϕi(y) )2 = (∑ j ∂ϕi ∂xj (c)(xj − yj) )2 , trong đó ∂ϕi ∂xj (c) =  −2ci (1 + ∑ r cr) 3 =: Pi, j 6= i, 1 + ∑ r cr − 2ci (1 + ∑ r cr) 3 =: Qi, j = i. Ta suy ra N2i = ( Pi ∑ j 6=i (xj − yj) +Qi(xi − yi) )2 ≤ ( |Pi| ∑ j 6=i |xj − yj|+ |Qj||xi − yi| )2 . Hơn nữa, vì ci ≥ 0 ta có |Pi| = ∣∣∣ −2ci (1 + ∑ j cj) 3 ∣∣∣ = 2ci (1 + ∑ j cj) 3 ≤ 2ci (1 + ∑ j cj) 2 ≤ 2ci 2 ∑ j cj ≤ 1. 29 Bây giờ xét |Qi| = |1 +∑j cj − 2ci| (1 + ∑ j cj) 3 . Nếu ci ≤ 1, ta có |Qi| = (1− ci) + ∑ j 6=i cj (1 + ∑ j cj) 3 ≤ 1 + ∑ j cj (1 + ∑ j cj) 3 = 1 (1 + ∑ j cj) 2 ≤ 1. Nếu ci > 1, ta có (1 + ∑ j cj) 3 > (1 + ∑ j cj) 2 = 1 + 2 ∑ j cj + ( ∑ j cj) 2 ≥ 1 + 3 ∑ j cj = |1 + ∑ j cj|+ |2 ∑ j cj| ≥ |1 + ∑ j cj|+ |2ci| ≥ |1 + ∑ j cj − 2ci|. Do đó trong trường hợp này ta cũng có |Qi| ≤ 1. Tóm lại ta luôn có |Pi| ≤ 1, 30 và |Qi| ≤ 1. Do vậy, N2i ≤ (∑ j 6=i |xj − yj|+ |xi − yi| )2 = (∑ j |xj − yj| )2 ≤ n ∑ j |xj − yj|2 = n‖x− y‖2. (1.9) Kết hợp (1.6), (1.7), (1.8), và (1.9) ta có( fi(x)− fi(y) )2 ≤ 2(α2i (xi − yi)2 + γ2M2i ) ≤ 2(α2i (xi − yi)2 + 2γ2(N2 +N2i ) ≤ 2(α2i (xi − yi)2 + 2γ2(n‖x− y‖2 + n‖x− y‖2)) = 2 ( α2i (xi − yi)2 + 4nγ2‖x− y‖2 ) . Cuối cùng ta có ‖f(x)− f(y)‖2 = ∑ i ( fi(x)− fi(y) )2 ≤ 2 (∑ i α2i (xi − yi)2 + 4nγ2 ∑ i ‖x− y‖2 ) ≤ 2(α2‖x− y‖2 + 4n2γ2‖x− y‖2) = 2(α2 + 4n2γ2)‖x− y‖2, trong đó α = max i αi. Như vậy, ‖f(x)− f(y)‖ ≤ Ln‖x− y‖, 31 trong đó Ln = √ 2(α2 + 4n2γ2). Như vậy, ví dụ này thỏa mãn các giả thiết của Định lý 1.5.1. Do đó, dãy sinh bởi Thuật toán 3 có tính chất bất kỳ điểm giới hạn nào của dãy đó đều là một nghiệm của bài toán ban đầu. Chúng tôi đã cài đặt Thuật toán 3 dùng ngôn ngữ C và kết quả số được mô tả dưới đây. Sai số cho phép của thuật toán chiếu là ε = 10−6. Bảng I γ\n 5 10 20 5 [15 - 18] - 1s [15 - 28] - 1s [13 - 24] - 8s 10 [17 - 25] - 1s [15 - 25] - 3s [10 - 24] - 9s 15 [19 - 25] - 2s [14 - 24] - 5s [14 - 22] - 12s Bảng II γ\n 30 40 50 5 [13 - 15] - 10s [15 - 25] - 28s [10 - 24] - 70s 10 [15 - 22] - 50s [12 - 22] - 60s [13 - 21] - 210s 15 [17 - 22] - 90s [13 - 21] - 225s [13 - 20] - 420s Dữ liệu trong hai bảng trên được đọc như sau. Chẳng hạn lấy ô nằm ở hàng 3, cột 3, bảng 1, tương ứng với n = 10 và γ = 10 : thuật toán chạy mất 3 giây để đến được vòng lặp thứ 25 (giải hết bài toán phạt thứ 25), trong đó, các vòng lặp từ 15 đến 25 cho cùng một nghiệm xk (tính đến 6 chữ số thập phân). Ta xét hai ví dụ tiếp theo, trong đó hàm phạt P sẽ được lấy theo công thức (1.4). Xét D = {x = (x1, x2)T ∈ R2 : g1(x) ≤ 0, g2(x) ≤ 0}, 32 trong đó g1(x) = x2− x1− 1, g2(x) = −x2 + x21− 1 là các hàm lồi trên R2. Bây giờ ta xét hai ví dụ ứng với hai ánh xạ f khác nhau. 1.6.2 Ví dụ. Giả sử f(x) = ( x1 + x2 x2 + e x2 4 − 1 ) . Có thể nhận thấy (0, 0)T là một nghiệm của bài toán trên và là nghiệm duy nhất, do f đơn điệu mạnh. Ta lấy P theo (1.4). P (x) = [max{0, x2 − x1 − 1}]2 + [max{0,−x2 + x21 − 1}]2 =  0, x ∈ D, (x2 − x1 − 1)2, x ∈ (I), (x2 − x1 − 1)2 + (−x2 + x21 − 1)2, x ∈ (II), (−x2 + x21 − 1)2, x ∈ (III). Chú ý rằng D là miền nằm dưới đường thẳng x2 = x1 + 1 và nằm trên đường cong x2 = x 2 1 − 1, (I) là miền nằm trên cả đường thẳng và đường cong, (II) nằm trên đường thẳng và dưới đường cong, (III) nằm dưới cả đường thẳng và đường cong. Hai giao điểm của đường thẳng và đường cong là (−1, 0) và (2, 3). Do 33 đó có thể bao D bởi hình hộp K = {x = (x1, x2) ∈ R2 : −1 ≤ x1 ≤ 2, −1 ≤ x2 ≤ 3}. Không khó để thấy rằng f liên tục Lipschitz trên K với hằng số Lipschitz l = √ 4.4, do đó tf (t > 0) liên tục Lipschitz với hằng số Lipschitz lt = t √ 4.4. Hơn nữa, f đơn điệu mạnh trên K với hằng số đơn điệu α = 1 2 . Do đó tf (t > 0) có hằng số đơn điệu αt = t 2 . Ta có ∇P (x) =  0 0  , x ∈ D,−2(x2 − x1 − 1) 2(x2 − x1 − 1)  , x ∈ (I),−2(x2 − x1 − 1) + 4x1(−x2 + x21 − 1) 2(x2 − x1 − 1)− 2(−x2 + x21 − 1)  , x ∈ (II),4x1(−x2 + x21 − 1) −2(−x2 + x21 − 1)  , x ∈ (III) liên tục Lipschitz trên K với hằng số Lipschitz 69. Do đó f (t) liên tục Lipschitz trên K với hằng số Lipschitz Lt = 69 + t √ 4.4, 34 và có hằng số đơn điệu αt = t 2 . Trước hết, ta dùng phương pháp hàm phạt đưa bài toán trên về dãy các bài toán VIP(K,f (t)). Với mỗi t > 0, áp dụng phương pháp chiếu hai lần, ta chọn độ dài bước η thỏa mãn 0 < η < 1 Lt = 1 69 + t √ 4.4 . Do đó, có thể chọn η = 0.9t 69 + t √ 4.4 . Dùng Thuật toán 3, với độ chính xác (của thuật toán chiếu) 10−12, t0 = 1, ngay từ vòng lặp đầu tiên (của thuật toán phạt), với kết quả lấy đến 9 chữ số thập phân, ta được kết quả (0, 0)T . Có thể nhận thấy tk tiến ra ∞ nhanh chóng và kết quả ở mỗi bước lặp (của thuật toán phạt) đều cho ra nghiệm (0, 0)T (đúng đến 10 hoặc 11 chữ số thập phân). Chương trình chạy tới vòng lặp thứ 1000 chỉ sau 3 giây. Kết quả trên được giải thích như sau. Do ∇P ≡ 0 trên D (P chọn theo (1.4), nên nếu nghiệm của VIP(K,f (t)) nằm trong D thì đó cũng là nghiệm của bài toán ban đầu VIP(D,f). Trong trường hợp t∗ = ∞, vì t0 0, nên theo Bổ đề 1.4.1, S(t0) ⊂ D. Do đó, nghiệm của bài toán phạt ứng với t0 cũng chính là nghiệm của bài toán ban đầu. Điều đó giải thích tại sao nghiệm của bài toán ban đầu lại được tìm ra ngay sau bước lặp đầu tiên. 1.6.3 Ví dụ. Lấy f(x) = ( x1 + x2 + 10 x2 + e x2 + 10 ) . Chú ý rằng ở đây f không có nghiệm trên miền D. Tuy vậy, f vẫn đơn điệu mạnh và liên tục Lipschitz với cùng hằng số như ở ví dụ trước. Với 35 độ chính xác (của phương pháp chiếu) là 10−10, t0 = 1, x(0) = (1, 1)T , sau đây là kết quả của vòng lặp 24 đến vòng lặp 28. Bảng III Số bước lặp k x(k) tk 889881606 24 (−0.437337405102318,−0.808736590634006)T 0.0000001192 1779680342 25 (−0.437337404356388,−0.808736293018647)T 0.0000000596 3560253327 26 (−0.437337403855591,−0.808736144322769)T 0.0000000298 7128665016 27 (−0.437337403701826,−0.808736069890305)T 0.0000000149 14205655551 28 (−0.437337403325762,−0.808736032935760)T 0.0000000075 Cột đầu tiên cho biết số bước lặp mà thuật toán chiếu thực hiện để giải bài toán phạt. Có thể thấy là tk → 0, nghĩa là t∗ = 0. Trong trường hợp t∗ = 0, từ Bổ đề 1.4.1, nghiệm x(k) của bài toán phạt ứng với tk luôn nằm ngoài miền D và một điểm giới hạn bất kỳ của một dãy {x(k)} với x(k) ∈ S(tk) và tk → t∗ là một nghiệm của VIP(D,f). Có thể nhận thấy là nghiệm của những bước cuối cùng xấp xỉ thuộc miền D với sai số khoảng 10−8, nhưng vẫn nằm ngoài D. Điều này phù hợp với kết luận của Bổ đề 1.4.1. Kết luận Chương 1 Trong chương này, luận án đã giải quyết được những vấn đề sau. - Kết hợp phương pháp hàm phạt và phương pháp chiếu để đưa ra một thuật toán hoàn chỉnh giải bài toán bất đẳng thức biến phân VIP(D,f), với f là ánh xạ đơn điệu và liên tục Lipschitz, D là một miền lồi đóng khác rỗng của Rn. Với phương pháp này, trở ngại chính của phương pháp chiếu được khắc phục. - Áp dụng thuật toán này cho một số ví dụ cụ thể để minh họa các kết quả đã có trong phần lý thuyết. CHƯƠNG 2 HÀM PHẠT CHO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN VECTOR YẾU Phương pháp hàm phạt thường được sử dụng để đưa một bài toán có ràng buộc, gọi là bài toán ban đầu, về một dãy các bài toán không ràng buộc, gọi là các bài toán phạt, sao cho một dãy nghiệm của các bài toán phạt hội tụ về một nghiệm của bài toán ban đầu. Đã có nhiều nghiên cứu về cách thức áp dụng phương pháp hàm phạt để giải các bài toán bất đẳng thức biến phân (tham khảo chẳng hạn [38, 23, 39, 1, 51]). Tuy nhiên, theo hiểu biết của chúng tôi, cho tới nay chưa có công trình nghiên cứu nào về việc áp dụng phương pháp hàm phạt cho bài toán bất đẳng thức biến phân vector yếu. Trong chương này chúng tôi nghiên cứu mối quan hệ giữa tập nghiệm S(t) của bài toán phạt WVVIP(K,F (t)), khi t→ +∞, với tập nghiệm S của bài toán ban đầu WVVIP(D,F ). Chúng tôi chứng minh được rằng với một số giả thiết nhất định, các bài toán phạt luôn có ít nhất một nghiệm. Hơn nữa, một dãy nghiệm của các bài toán phạt luôn có ít nhất một điểm giới hạn và một điểm giới hạn bất kỳ của dãy này sẽ là nghiệm của bài toán ban đầu WVVIP(D,F ). Các ký hiệu, định nghĩa sau đây sẽ được sử dụng trong hai chương còn lại của luận án. Với x = (x1, . . . , xk) T ∈ Rk, 36 37 và y = (y1, . . . , yk) T ∈ Rk, ta dùng các ký hiệu sau x < y⇐⇒xi < yi, ∀i = 1, . . . , p, x 6< y⇐⇒∃i : xi ≥ yi. Tích vô hướng của x và y định nghĩa như sau 〈x,y〉 = k∑ i=1 xiyi. Với mỗi y = (y1, . . . , yk) T ∈ Rk, ký hiệu ‖y‖ là chuẩn Euclide của y, tức là ‖y‖ = √√√√ k∑ i=1 y2i . Ký hiệu Rk+ = {x = (x1, . . . , xk)T ∈ Rk : xi ≥ 0, i = 1, . . . , k}. Giả sử D là một tập con khác rỗng của Rk. Giả sử F : Rk → Rr×k là một ánh xạ liên tục với miền giá trị là một tập các ma trận thực kích thước r×k. Bài toán bất đẳng thức biến phân vector yếu với ràng buộc trên D được định nghĩa như sau WVVIP(D,F ) : Tìm x ∈ D sao cho F (x)(y − x) 6< 0,∀y ∈ D. Nếu D = Rk, WVVIP(D,F ) được gọi là một bài toán bất đẳng thức biến phân vector yếu không ràng buộc. Bài toán WVVIP(D,F ) dĩ nhiên là một trường hợp tổng quát của bài toán VIP(D,f) xét ở Chương 1 vì khi r = 1 nó trở thành bài toán bất 38 đẳng thức biến phân vô hướng. Hơn nữa bài toán bất đẳng thức biến phân vector yếu bao hàm nhiều bài toán quan trọng khác như một trường hợp riêng, trong đó có bài toán tối ưu vector lồi. Về bài toán bất đẳng thức biến phân vector yếu có thể tham khảo các tài liệu [16, 6, 4, 3, 31, 12, 17]. Gọi F i : Rk → Rk, i = 1, . . . , r là các ánh xạ thành phần của F , nghĩa là F i(x) là hàng thứ i của ma trận F (x). Ta có F (x)(y − x) = (〈F 1(x),y − x〉, . . . , 〈F r(x),y − x〉)T . Do đó x ∈ D là một nghiệm của WVVIP(D,F ) nếu và chỉ nếu với mọi y ∈ D ta có (〈F 1(x),y − x〉, . . . , 〈F r(x),y − x〉)T 6< 0, hay nói cách khác là tồn tại chỉ số i sao cho 〈F i(x),y − x〉 ≥ 0. 2.1 Điều kiện đủ cho sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu Chúng tôi nhắc lại một điều kiện đủ cho sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu được đưa ra trong [6]. Trước hết chúng ta cần một vài định nghĩa. 2.1.1 Định nghĩa ([6]). Ánh xạ F : Rk → Rr×k được gọi là đơn điệu trên Rk nếu với mọi x,y ∈ Rk ta có (F (y)− F (x))(y − x) ≥ 0, hay nói cách khác, các ánh xạ thành phần F i đều đơn điệu, nghĩa là 〈F i(y)− F i(x),y − x〉 ≥ 0, với mọi i = 1, . . . , r. 39 2.1.2 Định nghĩa ([6]). Ánh xạ F : Rk → Rr×k được gọi là thỏa mãn điều kiện bức yếu trên D ⊂ Rk nếu tồn tại s ∈ Rr+ và a ∈ D sao cho 〈sTF (y),y − a〉 → +∞ khi ‖y‖ → +∞, y ∈ D. Chen và Yang [6] đã đưa ra điều kiện đủ sau đây cho sự tồn tại nghiệm của WVVIP(D,F ). 2.1.3 Định lí ([6]). Giả sử D 6= ∅ là một tập con lồi đóng của Rk, và F : Rk → Rr×k là một ánh xạ liên tục và đơn điệu trên Rk. Giả sử rằng 1. D bị chặn, hoặc 2. F thỏa mãn điều kiện bức yếu trên D. Khi đó WVVIP(D,F ) có nghiệm. 2.2 Bài toán phạt Trong mục này ta xây dựng các bài toán phạt và thiết lập điều kiện đủ để các bài toán đó có nghiệm. Trước hết, ta có định nghĩa sau đây cho hàm phạt ngoài của một tập D ⊂ Rk. 2.2.1 Định nghĩa. Cho D là một tập con khác rỗng của Rk. Hàm P : Rk → R được gọi là một hàm phạt (ngoài) của D nếu nó thỏa mãnP (x) = 0, x ∈ D,P (x) > 0, x /∈ D. (2.1) Ta luôn chọn P sao cho P không những là hàm lồi mà còn khả vi. Ví dụ, nếu D được cho bởi D = {x ∈ Rk : gj(x) ≤ 0, j = 1, . . . ,m}, (2.2) 40 trong đó gj : Rk → R, j = 1, . . . ,m là các hàm liên tục, ta có thể lấy P (x) = m∑ j=1 [ max{0, gj(x)} ]2 . (2.3) Như đã chứng minh trong mục 1.4, P chọn như trên không những lồi và khả vi trên Rk, mà còn thỏa mãn (2.1). Do tính chất của hàm lồi (tham khảo [45], Hệ quả 25.5.1), nếu P là lồi và khả vi thì ∇P (x) liên tục trên Rk. Hơn nữa, 〈∇P (x),y − x〉 ≤ P (y)− P (x), với mọi x và y trong Rk. Ta định nghĩa bài toán phạt như sau. Đặt Qi := ∇P, và Q : Rk → Rr×k, với các hàm thành phần Qi : Rk → Rk, i = 1, . . . , r. Cố định một tập K ⊃ D. Với t > 0 ta xét bài toán phạt sau đây WVVIP(K,F (t)) : Tìm x(t) ∈ K sao cho (F (t)(x(t)))(y − x(t)) 6< 0, với mọi y ∈ K, trong đó F (t) := F + tQ. 2.2.2 Định nghĩa. Ánh xạ f : Rk → Rk được gọi là thỏa mãn điều kiện D-bức trên K nếu tồn tại a ∈ D sao cho 〈f(y),y − a〉 → +∞ khi ‖y‖ → +∞, y ∈ K. 2.2.3 Ví dụ. Ánh xạ F : R2 → R2 cho bởi F (y) = (y1 + y2, y2 + ey2/4 − 1)T , thỏa mãn điều kiện D-bức trên R2 với mọi tập con D chứa 41 gốc tọa độ (0, 0) của R2. Thật vậy, 〈F (y),y − 0〉 = (y1 + y2)y1 + (y2 + ey2/4 − 1)y2 = (y21 + y1y2 + y 2 2) + (e y2/4y2 − y2) → +∞, khi ‖y‖ → +∞. 2.2.4 Định nghĩa. Ánh xạ F : Rk → Rr×k được gọi là thỏa mãn điều kiện D-bức trên K nếu tồn tại s ∈ Rr+ và a ∈ D sao cho 〈sTF (y),y − a〉 → +∞ khi ‖y‖ → +∞, y ∈ K. Hiển nhiên khi r = 1 thì hai định nghĩa trên là như nhau vì ta có thể lấy s = 1. Bổ đề sau đây chỉ ra một điều kiện đủ để cả bài toán ban đầu và bài toán phạt có nghiệm. 2.2.5 Bổ đề. Giả sử D 6= ∅ là một tập con lồi đóng của Rk và F : Rk → Rr×k là một ánh xạ liên tục, đơn điệu và thỏa mãn điều kiện D-bức trên K. Khi đó WVVIP(D,F ) có nghiệm. Hơn nữa, với mọi t > 0, bài toán phạt WVVIP(K,F (t)) cũng có nghiệm. Chứng minh. Vì F thỏa mãn điều kiện D-bức trênK, nó cũng thỏa mãn điều kiện bức yếu trên D nếu D không bị chặn. Do đó theo Định lý 2.1.3, WVVIP(D,F ) có nghiệm. Bây giờ ta chứng minh rằng WVVIP(K,F (t)) cũng có nghiệm. Hiển nhiên F (t) là ánh xạ liên tục. Hơn nữa F (t) đơn điệu trên Rk. Ta cần chứng minh rằng với mọi x,y ∈ Rk, vector (F (t)(y)− F (t)(x))(y − x) có các tọa độ không âm. Thật vậy (F (t)(y)− F (t)(x))(y − x) = (F (y) + tQ(y)− F (x)− tQ(x))(y − x) = (F (y)− F (x))(y − x) + t(Q(y)−Q(x))(y − x). 42 Chú ý rằng số hạng thứ nhất luôn không âm, nghĩa là tất cả các tọa độ của nó đều không âm. Tọa độ thứ i của số hạng thứ hai được biến đổi như sau t〈Qi(y)−Qi(x),y − x〉 = −t〈∇P (y),x− y〉 − t〈∇P (x),y − x〉 ≥ −t(P (x)− P (y))− t(P (y)− P (x)) = 0. Chú ý rằng trong bất đẳng thức thứ hai ta sử dụng giả thiết P là hàm lồi. Do vậy tất cả các tọa độ của số hạng thứ hai đều không âm. Do đó F (t) đơn điệu trên Rk. Chúng ta còn phải chứng minh rằng F (t) thỏa mãn điều kiện bức yếu trên K. Thật vậy, tồn tại s ∈ Rr+ và a ∈ D sao cho 〈sTF (y),y − a〉 → +∞ khi ‖y‖ → +∞,y ∈ K. Ta có 〈sTF (t)(y),y − a〉 = 〈sT (F (y) + tQ(y)),y − a〉 = 〈sTF (y),y − a〉+ t〈sTQ(y),y − a〉. Xét số hạng thứ hai sau khi chia cho t. Vì Q(y)(y − a) = (〈Q1(y),y − a〉, . . . , 〈Qr(y),y − a〉), ta có 〈sTQ(y),y − a〉 = ∑ i si〈Qi(y),y − a〉 = ∑ i si〈∇P (y),y − a〉 ≥ ∑ i si(P (y)− P (a)) = ∑ i siP (y). 43 Tổng cuối cùng là không âm, vì si ≥ 0 và P (y) ≥ 0. Vì F thỏa mãn điều kiện D-bức trên K, ta có 〈sTF (y),y − a〉 → +∞ khi ‖y‖ → +∞,y ∈ K. Do vậy ta suy ra 〈sTF (t)(y),y − a〉 → +∞ khi ‖y‖ → +∞,y ∈ K. Do đó F (t) thỏa mãn điều kiện bức yếu trên K với mọi t > 0. Theo Định lý 2.1.3, bài toán phạt WVVIP(K,F (t)) có nghiệm. 2.2.6 Ví dụ. Ta lấy miền D như trong Ví dụ 1.6.2 D = {x = (x1, x2)T ∈ R2 : x2 − x1 − 1 ≤ 0,−x2 + x21 − 1 ≤ 0}, và K = R2. Hình 2.1: Miền ràng buộc D của WVVIP(D,F ) Lấy P theo (2.3). P (x) = [max{0, x2 − x1 − 1}]2 + [max{0,−x2 + x21 − 1}]2 =  0, x ∈ D, (x2 − x1 − 1)2, x ∈ (I), (x2 − x1 − 1)2 + (−x2 + x21 − 1)2, x ∈ (II), (−x2 + x21 − 1)2, x ∈ (III). 44 Ánh xạ F : R2 → R2×2 được cho bởi F (x) = ( x1 + x2 x2 + e x2/2 − 2 x1 + 2x2 x1 + 3x2 + e x2 − 1 ) . Khi đó với mọi x,y ∈ Rk ta có 〈F 1(y)− F 1(x),y − x〉 = (y1 − x1)2 + (y2 − x2)(y1 − x1) + (y2 − x2)2 + (ey2/2 − ex2/2)(y2 − x2) ≥ 0, và 〈F 2(y)− F 2(x),y − x〉 = (y1 − x1)2 + 3(y2 − x2)(y1 − x1) + 3(y2 − x2)2 + (ey2 − ex2/2)(y2 − x2) ≥ 0. Do đó F đơn điệu trên R2. Hơn nữa F thỏa mãn điều kiện D-bức trên K = R2. Thật vậy, chọn a = 0 ∈ D và s = (1, 1)T , ta có 〈sTF (y),y − a〉 = 〈F 1(y) + F 2(y),y〉 = 2y21 + 4y1y2 + 4y 2 2 + e y2/2y2 + e y2y2 − 3y2 → +∞, khi ‖y‖ → +∞. Như vậy các miền D, K = R2 và ánh xạ F định nghĩa như trên thỏa mãn tất cả các giả thiết của Bổ đề 2.2.5. Do đó, cả WVVIP(D,F ) và WVVIP(K,F (t)) (t > 0) tương ứng với D, K và F này đều có nghiệm. 2.3 Các định lý hội tụ Ký hiệu S và S(t) tương ứng là các tập nghiệm của WVVIP(D,F ) và WVVIP(K,F (t)). Giả sử {tn}n là một dãy số thực dương tăng đơn điệu tới +∞ khi n→ +∞. 45 2.3.1 Bổ đề. Giả sử x(n) ∈ S(tn) với mọi n ∈ N, {x(nm)}m là một dãy con hội tụ của {x(n)}n và limm→+∞ x(nm) = x. Khi đó x ∈ D. Chứng minh. Ta chứng minh bằng phản chứng. Giả sử x 6∈ D, ta có P (x) > 0 và do đó P (x) > ε với ε > 0 nào đó. Lấy y bất kỳ thuộc D. Vì x(nm) là một nghiệm của (WVVIP)tnm , tồn tại chỉ số inm sao cho 〈F (tnm)inm (x(nm)),y − x(nm)〉 ≥ 0. Vì inm ∈ {1, 2, . . . , r}, tồn tại một dãy vô hạn các chỉ số {inmk}k nhận cùng một giá trị, chẳng hạn inmk = 1, với mọi k ∈ N. Để đơn giản hóa ký hiệu ta giả sử inm = 1 với mọi m ∈ N. Do đó với mọi m ∈ N ta có 〈F (tnm)1 (x(nm)),y − x(nm)〉 ≥ 0. (2.4) Mặt khác vì P (x(nm))→ P (x) > ε, với mọi m đủ lớn ta có P (x(nm)) > ε. Do vậy 〈F (tnm)1 (x(nm)),y − x(nm)〉 = 〈F 1(x(nm)),y − x(nm)〉 + tnm〈∇P (x(nm)),y − x(nm)〉 ≤ 〈F 1(x(nm)),y − x(nm)〉 + tnm(P (y)− P (x(nm))) = 〈F 1(x(nm)),y − x(nm)〉 − tnmP (x(nm)) < 〈F 1(x(nm)),y − x(nm)〉 − εtnm → 〈F 1(x),y − x〉 −∞ = −∞, khi m→ +∞. Điều này mâu thuẫn với (2.4). Định lý sau đây chỉ ra rằng nếu một dãy các nghiệm của các bài toán phạt hội tụ về một điểm x thì x là một nghiệm của bài toán ban đầu 46 WVVIP(D,F ). Chú ý rằng nếu tồn tại n ∈ N sao cho x(n) ∈ S(tn)∩D thì dễ thấy x(n) cũng là một nghiệm của WVVIP(D,F ). 2.3.2 Định lí. Giả sử rằng x(n) ∈ S(tn) với mọi n ∈ N. Khi đó một điểm giới hạn bất kỳ của dãy {x(n)}n sẽ là một nghiệm của WVVIP(D,F ). Chứng minh. Giả sử x là một điểm giới hạn của dãy {x(n)}n. Gọi {x(nm)}m là dãy con của {x(n)}n hội tụ về x. Theo Bổ đề 2.3.1, ta có x ∈ D. Giả sử phản chứng rằng x không phải là nghiệm của WVVIP(D,F ). Khi đó tồn tại y ∈ D thỏa mãn 〈F i(x),y − x〉 < 0 với mọi i = 1, . . . , r. Vì x(nm) là một nghiệm của (WVVIP)tnm , với y nói trên, tồn tại một chỉ số inm thỏa mãn 〈F (tnm)inm (x(nm)),y − x(nm)〉 ≥ 0. Vì inm ∈ {1, 2, . . . , r}, tồn tại một dãy vô hạn các chỉ số {inmk}k nhận cùng một giá trị, chẳng hạn inmk = 1, với mọi k ∈ N. Để đơn giản hóa ký hiệu ta giả sử rằng dãy {inm}m tự nó thỏa mãn tính chất này, nghĩa là inm = 1 với mọi m ∈ N. Do vậy với mọi m ∈ N ta có 〈F (tnm)1 (x(nm)),y − x(nm)〉 ≥ 0. (2.5) Vì 〈F 1(x),y − x〉 < 0, ta suy ra rằng 〈F 1(x),y − x〉 < −ε, với ε > 0 nào đó. Sử dụng tính liên tục của F và giả thiết x(nm) → x, ta suy ra với mọi m đủ lớn〈 F 1(x (nm)),y − x(nm) 〉 < −ε. Do đó, sử dụng tính chất P (x(nm)) ≥ 0, 47 và tnm > 0, với mọi m ∈ N, với mọi m đủ lớn ta có 〈F (tnm)1 (x(nm)),y − x(nm)〉 = 〈 F 1(x (nm)),y − x(nm) 〉 + tnm 〈 ∇P (x(nm)),y − x(nm) 〉 ≤ 〈 F 1(x (nm)),y − x(nm) 〉 + tnm(P (y)− P (x(nm))) = 〈 F 1(x (nm)),y − x(nm) 〉 − tnmP (x(nm)) < −ε. Điều này mâu thuẫn với (2.5). 2.3.3 Định nghĩa. Ánh xạ F : Rk → Rr×k được gọi là thỏa mãn điều kiện D-bức mạnh trên K nếu tất cả các ánh xạ thành phần của nó thỏa mãn điều kiện D-bức trên K với cùng một vector a, nghĩa là tồn tại a ∈ D sao cho với mọi j = 1, . . . , r, 〈F j(y),y − a〉 → +∞, khi ‖y‖ → +∞,y ∈ K. Dễ thấy với ánh xạ F và các miền D và K = R2 định nghĩa trong Ví dụ 2.2.6 thì F thỏa mãn điều kiện D-bức mạnh trên K. Hiển nhiên nếu F thỏa mãn điều kiện D-bức mạnh trên K, thì F cũng thỏa mãn điều kiện D-bức trên K. Tuy nhiên, điều ngược lại không phải lúc nào cũng đúng. Ví dụ, xét miền D = {0}, K = R2, và F (x) = ( x1 + x2 x2/4 x1 x2 ) . 48 Chọn s = (1, 1)T . Vì 〈sTF (y),y − 0〉 = 〈F 1(y) + F 2(y),y〉 = 2y21 + y1y2 + 5 4 y22 → +∞, khi ‖y‖ → +∞, ta kết luận rằng F thỏa mãn điều kiện D-bức trên R2. Mặt khác, vì 〈F 1(y),y − 0〉 = (y1 + y2/2)2 = 0, với mọi y = (y1,−2y1)T , với y1 → +∞, ta suy ra F 1 thậm chí không thỏa mãn điều kiện D-bức trên R2. Do vậy F thỏa mãn điều kiện D-bức trên R2, nhưng không thỏa mãn điều kiện D-bức mạnh trên R2. 2.3.4 Định lí. Cho D 6= ∅ là một tập con lồi đóng của Rk và F : Rk → Rr×k là một ánh xạ liên tục, đơn điệu, đồng thời thỏa mãn điều kiện D-bức mạnh trên K. Giả sử x(n) ∈ S(tn) với mọi n ∈ N. Khi đó dãy {x(n)}n có ít nhất một điểm giới hạn và bất kỳ một điểm giới hạn nào của dãy này là một nghiệm của WVVIP(D,F ). Chứng minh. Chú ý rằng vì F cũng thỏa mãn điều kiện D-bức trên K, theo Bổ đề 2.2.5, S(tn) 6= ∅ với mọi n ∈ N, do đó dãy {x(n)}n nêu trong định lý được xác định đúng đắn. Ta sẽ chứng minh rằng dãy {x(n)}n bị chặn, nghĩa là tồn tại một hình cầu B nào đó với bán kính hữu hạn, có tâm là gốc tọa độ, sao cho x(n) ∈ B với mọi n ∈ N. Giả sử a là vector hằng trong Định nghĩa 2.3.3. Với mỗi t > 0, gọi B(t) là hình cầu đóng bé nhất, tâm tại gốc tạo độ 0, thỏa mãn tính chất sau: với mọi y /∈ B(t) và mọi j = 1, . . . , r, ta có 〈F (t)j (y),y − a〉 > 0, hay nói cách khác, 〈F j(y),y − a〉+ t〈∇P (y),y − a〉 > 0. 49 Vì mỗi F j thỏa mãn điều kiện D-bức trên K và 〈∇P (y),y − a〉 ≥ P (y)− P (a) = P (y) ≥ 0, ta suy ra với mọi t > 0, B(t) có bán kính hữu hạn. Ta sẽ chứng minh bằng phản chứng rằng S(t) ⊆ B(t) với mọi t > 0. Thật vậy, giả sử y ∈ S(t)\B(t), khi đó theo định nghĩa của B(t), với mọi j = 1, . . . , r ta có 〈F (t)j (y),y − a〉 > 0. Từ đó ta suy ra 〈F (t)j (y),a−y〉 < 0 với mọi j = 1, . . . , r. Điều này mâu thuẫn với giả thiết y ∈ S(t). Mặt khác ta sẽ chứng minh rằng nếu t′ > t, thì B(t′) ⊆ B(t). Thật vậy, với mọi y /∈ B(t), ta có 〈F j(y),y − a〉+ t〈∇P (y),y − a〉 > 0, kéo theo 〈F j(y),y − a〉+ t′〈∇P (y),y − a〉 > 0, (2.6) với mọi j = 1, . . . , r. Theo định nghĩa B(t′) là hình cầu nhỏ nhất thỏa mãn tính chất: với mọi y /∈ B(t′) bất đẳng thức (2.6) được thỏa mãn. Do đó B(t′) bị chứa trong B(t). Cuối cùng, vì {tn}n là dãy đơn điệu tăng ta có B(t1) ⊇ B(t2) ⊇ · · · ⊇ B(tn) ⊇ · · · Do đó, với mọi n ∈ N, x(n) ∈ S(tn) ⊆ B(tn) ⊆ B(t1). Vì B(t1) có bán kính hữu hạn, ta kết luận rằng dãy {x(n)}n bị chặn. Do vậy, theo nguyên lý Bolzano-Weierstrass dãy này có ít nhất một điểm giới hạn. Khẳng định rằng mỗi điểm giới hạn của {x(n)}n là một nghiệm của WVVIP(D,F ) được suy ra trực tiếp từ Định lý 2.3.2. 50 Kết luận Chương 2 Trong chương này, luận án đã giải quyết được những vấn đề sau. - Xây dựng mô hình bài toán phạt cho bài toán bất đẳng thức biến phân vector yếu và chứng minh rằng một điểm giới hạn bất kỳ của một dãy các nghiệm của các bài toán phạt chính là một nghiệm của bài toán ban đầu. - Chứng minh được rằng nếu miền D là lồi đóng, ánh xạ F đơn điệu và thỏa mãn tính chất bức, thì các bài toán phạt đều có nghiệm. Hơn nữa, bất kỳ dãy nghiệm nào của các bài toán phạt đều bị chặn, do đó có ít nhất một điểm giới hạn, và đó chính là một nghiệm của bài toán bất đẳng thức biến phân vector yếu ban đầu. CHƯƠNG 3 HÀM PHẠT CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU Phương pháp hàm phạt áp dụng cho bài toán tối ưu phi tuyến đã được nghiên cứu một cách khá kỹ lưỡng (tham khảo chẳng hạn [56, 14, 43, 7]). Phương pháp hàm phạt áp dụng cho bài toán tối ưu đa mục tiêu cũng đã được nghiên cứu trong một vài công trình gần đây (tham khảo [52, 21, 22, 34]). Trong [34], Liu và Feng đã chứng minh rằng nếu x là một điểm giới hạn của một dãy các nghiệm Pareto yếu của các bài toán phạt và x chấp nhận được (nghĩa là x ∈ D), thì x là một nghiệm Pareto yếu của bài toán ban đầu. Tính chấp nhận được của x là một giả thiết trong các kết quả của [34]. Trong chương này, chúng tôi sử dụng hàm phạt ngoài và chứng minh được các kết quả sau: (1) nếu x là một điểm giới hạn của một dãy các nghiệm Pareto yếu của các bài toán phạt thì x là chấp nhận được; (2) một điểm x như thế sẽ là một nghiệm của bài toán ban đầu; (3) với một số giả thiết đặt lên f , mọi bài toán phạt sẽ có ít nhất một nghiệm Pareto yếu và mỗi dãy nghiệm Pareto yếu của các bài toán phạt sẽ có ít nhất một điểm giới hạn, điểm giới hạn đó chính là một nghiệm của bài toán tối ưu đa mục tiêu ban đầu. 51 52 3.1 Điều kiện đủ cho sự tồn tại nghiệm của bài toán tối ưu đa mục tiêu Cho D là một tập con lồi đóng khác rỗng của Rk. Ta xét bài toán tối ưu đa mục tiêu với ràng buộc trên D sau đây MOP(D,f) : min x∈D f(x) = (f1(x), . . . , fr(x)), trong đó fi : Rk → R, i = 1, . . . , r là các ánh xạ xác định trên Rk. D được gọi là miền ràng buộc của MOP(D,f). Nếu x ∈ D thì x được gọi là một điểm chấp nhận được của MOP(D,f). Nếu D = Rk thì MOP(D,f) được gọi là bài toán tối ưu đa mục tiêu không ràng buộc. 3.1.1 Định nghĩa. Vector x ∈ D được gọi là một nghiệm Pareto yếu của MOP(D,f) nếu không tồn tại y ∈ D nào thỏa mãn f(y) < f(x). Do đó, x ∈ D là một nghiệm Pareto yếu MOP(D,f) nếu và chỉ nếu với mọi y ∈ D luôn tồn tại một chỉ số i sao cho fi(y) ≥ fi(x). Định lý sau đây thiết lập mối quan hệ giữa nghiệm Pareto yếu của một bài toán tối ưu đa mục tiêu và nghiệm của bài toán bất đẳng thức biến phân vector yếu tương ứng, dựa trên giả thiết về tính lồi và khả vi của hàm mục tiêu. 3.1.2 Định lí ([5]). Giả sử f là một ánh xạ lồi và khả vi, nghĩa là mỗi ánh xạ thành phần fi của f là lồi và khả vi. Khi đó x là một nghiệm Pareto yếu của MOP(D,f) nếu và chỉ nếu x là một nghiệm của WVVIP(D,f ′), trong đó f ′ là đạo hàm của f . Các kết quả sau đây về sự tồn tại nghiệm của bài toán tối ưu đa mục tiêu sẽ được sử dụng về sau trong chương này. 53 3.1.3 Định lí ([30]). Giả sử f lồi và khả vi. Hơn nữa giả sử rằng D không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈D 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Khi đó MOP(D,f) có một nghiệm Pareto yếu. Kết hợp Định lý 3.1.2, Định lý 3.1.3, và Định lý 2.1.3 ta thu được kết quả sau cho sự tồn tại nghiệm của bài toán tối ưu đa mục tiêu. 3.1.4 Hệ quả. Giả sử f lồi và khả vi. Giả sử thêm rằng một trong các điều kiện dưới đây thỏa mãn 1. D bị chặn, 2. D không bị chặn và ∇f thỏa mãn điều kiện bức yếu trên D, nghĩa là tồn tại một vector s ∈ Rr+ và một vector a ∈ D sao cho lim ‖y‖→+∞, y∈D r∑ i=1 si〈∇fi(y),y − a〉 = +∞, 3. D không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈D 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Khi đó MOP(D,f) có nghiệm Pareto yếu. Chứng minh. Do tính lồi của fi, ta có ∇fi liên tục và đơn điệu (Hệ quả 25.5.1, [45]). Gọi F : Rk → Rr×k là ánh xạ với các ánh xạ thành phần ∇fi, i = 1, . . . , r. Khi đó hiển nhiên F liên tục và đơn điệu. Nếu D bị chặn, theo Định lý 2.1.3, WVVIP(D,F ) có một nghiệm x. Sử dụng Định lý 3.1.2, ta suy ra rằng x cũng là một nghiệm Pareto yếu của MOP(D,f). 54 Giả sử rằng D không bị chặn. Nếu tính chất thứ hai thỏa mãn, ta có F thỏa mãn điều kiện bức yếu trên D. Do đó, theo Định lý 2.1.3, WVVIP(D,F ) có một nghiệm x. Sử dụng Định lý 3.1.2, ta suy ra x là một nghiệm Pareto yếu của MOP(D,f). Nếu tính chất thứ ba thỏa mãn, theo Định lý 3.1.3, MOP(D,f) có một nghiệm Pareto yếu. 3.2 Bài toán phạt Trong mục này ta sẽ xây dựng các bài toán phạt cho MOP(D,f). Cố định một tập K ⊃ D. Với t > 0 ta định nghĩa bài toán phạt như sau MOP(K,f (t)) : min x∈K f (t) = (f (t) 1 , . . . , f (t) r ), trong đó f (t) i = fi + tP , i = 1, . . . , r, với P là hàm phạt của D. Trong trường hợp miền K là Rk thì bài toán phạt không có ràng buộc nào. Tiếp theo ta nghiên cứu sự tồn tại nghiệm của các bài toán phạt MOP(K,f (t)). 3.2.1 Bổ đề. Giả sử f : Rk → Rr là lồi và khả vi. Hơn nữa giả thiết rằng một trong các điều kiện sau đây thỏa mãn 1. K bị chặn, 2. K không bị chặn và tồn tại các vector s ∈ Rr+ và a ∈ D sao cho lim ‖y‖→+∞, y∈K r∑ i=1 si〈∇fi(y),y − a〉 = +∞, 3. K không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈K 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Khi đó MOP(K,f (t)) có một nghiệm Pareto yếu. 55 Chứng minh. Hiển nhiên f (t) i = fi + tP lồi và khả vi. Nếu K bị chặn, theo Hệ quả 3.1.4, MOP(K,f (t)) có một nghiệm Pareto yếu. Giả sử rằng điều kiện thứ hai thỏa mãn. Ta có r∑ i=1 si〈∇f (t)i (y),y − a〉 = r∑ i=1 si〈∇fi(y),y − a〉+ t r∑ i=1 si〈∇P (y),y − a〉 ≥ r∑ i=1 si〈∇fi(y),y − a〉+ t(P (y)− P (a)) ≥ r∑ i=1 si〈∇fi(y),y − a〉 → +∞, khi ‖y‖ → +∞,y ∈ K. Trong bất đẳng thức thứ hai ta sử dụng tính chất P (y) ≥ 0 và P (a) = 0 vì a ∈ D. Do đó, theo Hệ quả 3.1.4 MOP(K,f (t)) có một nghiệm Pareto yếu. Giả sử điều kiện thứ ba thỏa mãn. Với mỗi i = 1, . . . , r ta có 〈∇f (t)i (y),y − a〉 = 〈∇fi(y),y − a〉+ t〈∇P (y),y − a〉 ≥ 〈∇fi(y),y − a〉+ t(P (y)− P (a)) ≥ 〈∇fi(y),y − a〉. Do đó lim ‖y‖→+∞, y∈K 〈∇f (t)i (y),y − a〉 > 0. Theo Hệ quả 3.1.4, ta kết luận rằng MOP(K,f (t)) có một nghiệm Pareto yếu. 3.3 Các định lý hội tụ Ký hiệu S và S(t) tương ứng là các tập nghiệm của MOP(D,f) và MOP(K,f (t)). Lấy {tn}n là một dãy các số thực dương tăng đơn điệu tới +∞ khi n→ +∞. 56 3.3.1 Bổ đề. Giả sử f liên tục và x(n) ∈ S(tn) với mọi n ∈ N. Giả sử rằng x là một điểm giới hạn của dãy { x(n) } n . Khi đó x ∈ D. Chứng minh. Ta chứng minh bổ đề này bằng phương pháp phản chứng. Giả sử x là giới hạn của dãy con { x(nm) } m của { x(n) } n và x /∈ D. Khi đó P (x) > 0 và do vậy P (x) > ε với ε > 0 nào đó. Lấy y ∈ D bất kỳ. Vì x(nm) ∈ S(tnm), tồn tại inm sao cho f (tnm) inm (y) ≥ f (tnm)inm (x(nm)). Vì inm ∈ {1, 2, . . . , r}, tồn tại một dãy vô hạn {inm`}` các chỉ số có cùng một giá trị, chẳng hạn inm` = 1, với mọi ` ∈ N. Để đơn giản ký hiệu, ta giả sử inm = 1 với mọi m ∈ N. Do đó với mọi m ∈ N f (tnm) 1 (y) ≥ f (tnm)1 (x(nm)). (3.1) Vì P (x(nm))→ P (x) > ε, với mọi m đủ lớn ta có P (x(nm)) > ε. Do vậy với m đủ lớn f (tnm) 1 (x (nm))− f (tnm)1 (y) = f1(x(nm))− f1(y) + tnm(P (x(nm))− P (y)) ≥ f1(x(nm))− f1(y) + tnmε → f1(x)− f1(y) +∞ = +∞, as m→ +∞. Điều này mâu thuẫn với (3.1). Chú ý rằng ở đây P (y) = 0 vì y ∈ D. Định lý sau đây chứng tỏ rằng nếu một dãy các nghiệm Pareto yếu của các bài toán phạt hội tụ tới một điểm x thì x là một nghiệm Pareto yếu của bài toán ban đầu. Để ý rằng nếu tồn tại n ∈ N sao cho x(n) ∈ S(tn) ∩D, dễ thấy x(n) cũng là một nghiệm của MOP(D,f). 3.3.2 Định lí. Giả sử rằng f liên tục và x(n) ∈ S(tn) với mọi n ∈ N. Khi đó một điểm giới hạn bất kỳ của dãy { x(n) } n sẽ là một nghiệm Pareto yếu của MOP(D,f). 57 Chứng minh. Ta giả sử rằng x là một điểm giới hạn của dãy { x(n) } n . Gọi { x(nm) } m là dãy con của { x(n) } n hội tụ tới x. Theo Bổ đề 3.3.1, x ∈ D. Giả sử phản chứng rằng x /∈ S. Khi đó tồn tại y ∈ D thỏa mãn fi(y) < fi(x), i = 1, . . . , r. Vì x(nm) ∈ S(tnm), tồn tại inm sao cho f (tnm) inm (y) ≥ f (tnm)inm ( x(nm) ) . Vì inm ∈ {1, 2, . . . , r}, tồn tại một dãy vô hạn các chỉ số { inm` } ` nhận cùng một giá trị, chẳng hạn inm` = 1, với mọi ` ∈ N. Để đơn giản ký hiêu, ta lại giả sử rằng chính dãy { inm } m thỏa mãn tính chất này, tức là inm = 1 với mọi m ∈ N. Do đó với mọi m ∈ N đủ lớn ta có f (tnm) 1 (y) ≥ f (tnm)1 ( x(nm) ) . (3.2) Vì f1(y) 0 nào đó. Vì x(nm) → x khi m→ +∞, với m đủ lớn ta có f1(y)− f1 ( x(nm) ) < −ε. Do vậy với m đủ lớn f (tnm) 1 (y)− f (tnm)1 ( x(nm) ) = f1(y)− f1 ( x(nm) ) + tnm ( P (y)− P(x(nm))) < −ε− tnmP ( x(nm) ) ≤ −ε. Điều này mâu thuẫn với (3.2). 3.3.3 Định lí. Giả sử f : Rk → Rr lồi và khả vi. Giả sử thêm rằng một trong các điều kiện sau đây thỏa mãn 1. K bị chặn, 58 2. K không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈K 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Giả sử x(n) ∈ S(tn) với mọi n ∈ N. Khi đó dãy { x(n) } n có ít nhất một điểm giới hạn và mỗi điểm giới hạn của dãy này là một nghiệm Pareto yếu của MOP(D,f). Chứng minh. Trước hết để ý rằng theo Bổ đề 3.2.1, ta có S(tn) 6= ∅. Do đó dãy { x(n) } n nêu trong định lý luôn tồn tại. Nếu K bị chặn thì dãy { x(n) } n ⊆ K cũng bị chặn. Do đó theo nguyên lý Bolzano-Weierstrass, dãy này sẽ có ít nhất một điểm giới hạn. Khẳng định rằng điểm giới hạn này là một nghiệm Pareto yếu của MOP(D,f) được suy ra trực tiếp từ Định lý 3.3.2. Bây giờ giả sử rằng K không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈K 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Ta chỉ cần chứng tỏ rằng dãy { x(n) } n bị chặn là đủ. Với t > 0, gọi B(t) là hình cầu đóng nhỏ nhất của Rk tâm tại gốc tọa độ sao cho với mọi y /∈ B(t) và với mọi i = 1, . . . , r, ta có〈∇f (t)i (y),y − a〉 > 0, hay nói cách khác〈∇fi(y),y − a)〉+ t〈∇P (y),y − a〉 > 0. Vì 〈∇fi(y),y − a)〉 > 0 khi ‖y‖ đủ lớn, và t 〈∇P (y),y − a〉 ≥ t(P (y)− P (a)) ≥ 0, 59 ta suy ra B(t) có bán kính hữu hạn. Tiếp theo, ta chứng minh rằng S(t) ⊆ B(t). Thật vậy, giả sử phản chứng rằng tồn tại y ∈ S(t)\B(t). Khi đó theo định nghĩa của B(t), với mọi i = 1, . . . , r ta có 〈∇f (t)i (y),y − a〉 > 0, hay nói một cách tương đương,〈∇f (t)i (y),a− y〉 < 0, i = 1, . . . , r. Do đó y không phải là một nghiệm của WVVIP(K, (f (t))′). Theo Định lý 3.1.2, ta suy ra rằng y /∈ S(t), mâu thuẫn. Do vậy S(t) ⊆ B(t). Mặt khác, với t′ > t, ta có B(t′) ⊆ B(t). Thật vậy, với mọi y /∈ B(t) và với mọi i = 1, . . . , r, ta có〈∇fi(y),y − a)〉+ t〈∇P (y),y − a〉 > 0, kéo theo 〈∇fi(y),y − a)〉+ t′〈∇P (y),y − a〉 > 0, (3.3) vì 〈∇P (y),y − a〉 ≥ P (y)− P (a) ≥ 0. Theo định nghĩa, B(t′) là hình cầu đóng nhỏ nhất sao cho với mọi y /∈ B(t′), bất đẳng thức (3.3) thỏa mãn với mọi i = 1, . . . , r. Do đó B(t′) là một tập con của B(t). Cuối cùng, vì {tn}n đơn điệu tăng, ta có B(t1) ⊇ B(t2) ⊇ · · · ⊇ B(tn) ⊇ · · · Do đó với mọi n ∈ N ta có x(n) ∈ S(tn) ⊆ B(tn) ⊆ B(t1). Vì bán kính của B(t1) là hữu hạn, ta kết luận rằng dãy { x(n) } n bị chặn. 60 3.3.4 Ví dụ. Xét D = {x = (x1, x2)T ∈ R2 : x2 − x1 − 1 ≤ 0,−x2 + x21 − 1 ≤ 0}. Hình 3.1: Miền ràng buộc D Lấy P theo (2.3) P (x) = [max{0, x2 − x1 − 1}]2 + [max{0,−x2 + x21 − 1}]2 =  0, x ∈ D, (x2 − x1 − 1)2, x ∈ (I), (x2 − x1 − 1)2 + (−x2 + x21 − 1)2, x ∈ (II), (−x2 + x21 − 1)2, x ∈ (III). Cho f(x) = (f1(x), f2(x)), trong đó f1(x) = x21 2 + x22 2 + x1x2 + 2e x2/2 − 2x2, f2(x) = e x1 + x21 − x1 + x22 2 + 1. Dễ thấy f định nghĩa như trên là lồi và khả vi trên R2. Lấy K = R2 và a = 0 ∈ D. Khi đó ta có 〈∇f1(y),y〉 = (y1 + y2)2 + y2ey2/2 − 2y2, 〈∇f2(y),y〉 = 2y21 + y22 + y1ey1 − y1, 61 hiển nhiên là các số dương khi ‖y‖ → +∞. Do đó, theo Định lý 3.3.3 một dãy bất kỳ các nghiệm Pareto yếu của các bài toán phạt MOP(K,f (tn)), n = 1, 2, . . . sẽ có ít nhất một điểm giới hạn và mọi điểm giới hạn của dãy đó là một nghiệm Pareto yếu của MOP(D,f). Kết luận Chương 3 Trong chương này, luận án đã giải quyết được những vấn đề sau. - Nghiên cứu mối quan hệ giữa tập các nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu ban đầu và các tập nghiệm Pareto yếu của các bài toán phạt tương ứng. - Chứng minh được rằng nếu miền D là lồi đóng, ánh xạ f lồi, khả vi và thỏa mãn tính chất bức, thì các bài toán phạt đều có nghiệm Pareto yếu. Hơn nữa, bất kỳ dãy nghiệm Pareto yếu nào của các bài toán phạt đều bị chặn, do đó có ít nhất một điểm giới hạn và đó chính là một nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu ban đầu. Định lý 3.3.2 chứng minh rằng một điểm giới hạn bất kỳ của dãy các nghiệm Pareto yếu của các bài toán phạt là một nghiệm Pareto yếu của bài toán ban đầu, chỉ cần giả thiết về tính liên tục của hàm mục tiêu f . Ta không yêu cầu f lồi hoặc khả vi trong định lý này. Tuy nhiên, Định lý 3.3.3 đòi hỏi những tính chất đó của f . Một vài công trình gần đây đã nghiên cứu nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu với các giả thiết được giảm nhẹ cho f , chẳng hạn, khi f không lồi và không khả vi (tham khảo [27, 30, 46]). Dựa trên những kết quả này, ta cũng có thể giảm nhẹ các giả thiết đặt lên hàm f nêu trong Định lý 3.3.3. 62 KẾT LUẬN VÀ KIẾN NGHỊ 1 Kết luận Luận án nghiên cứu phương pháp hàm phạt áp dụng cho bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân vector yếu và bài toán tối ưu đa mục tiêu. Kết quả chính của luận án như sau. 1. Đưa ra thuật toán kết hợp hai phương pháp hàm phạt và phương pháp chiếu để giải bài toán bất đẳng thức biến phân. Thuật toán kết hợp đã khắc phục được nhược điểm cơ bản của phương pháp chiếu là sự khó khăn khi tính hình chiếu của một điểm lên một miền lồi bất kỳ và tận dụng được ưu điểm của thuật toán này là khối lượng tính toán nhỏ, thuật toán đơn giản. Thuật toán được minh họa bởi các ví dụ trong trường hợp hai chiều và nhiều chiều, kết quả giải số của các ví dụ được phân tích và so sánh. 2. Xây dựng mô hình hàm phạt để giải bài toán bất đẳng thức biến phân vector yếu. Chứng minh được các kết quả hội tụ cơ bản của phương pháp. 3. Nghiên cứu áp dụng phương pháp hàm phạt để tìm nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu. Chứng minh được các kết quả hội tụ cơ bản của phương pháp. Cải tiến các kết quả nêu trong [34]. Kết quả chính của luận án được công bố trong [37], [35] và [36]. 2 Kiến nghị Thời gian tới, chúng tôi mong muốn tiếp tục nghiên cứu những vấn đề sau. 1. Nghiên cứu thêm về tính hiệu quả và tốc độ hội tụ của thuật toán 63 kết hợp phương pháp hàm phạt và phương pháp chiếu cho bài toán bất đẳng thức biến phân. 2. Giảm nhẹ các giả thiết nêu trong các điều kiện đủ đã thiết lập trong Chương 2 và Chương 3. Trước hết là nghiên cứu kỹ hơn các điều kiện đủ này trong trường hợp hàm mục tiêu là không trơn và không đơn điệu. 3. Nghiên cứu mở rộng phương pháp hàm phạt cho các dạng tổng quát hơn của bài toán bất đẳng thức biến phân vector. DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA NGHIÊN CỨU SINH LIÊN QUAN ĐẾN LUẬN ÁN 1. Đậu Xuân Lương (2003), “Ánh xạ tự bức và ứng dụng vào bất đẳng thức biến phân,” Thông báo khoa học – Các ngành khoa học tự nhiên, Trường Đại học Vinh. 2. D. X. Luong and L. D. Muu (2010), “Combining the projection meth- ods and the penalty function method to solve the variational inequal- ities with monotone mappings”, Int. J. Optim. Theory Methods Appl., 2(2), pp. 124–137. 3. D. X. Luong (2010), “Penalty functions for the vector variational inequality problem”, submitted to Acta Mathematica Vietnamica for publication. 4. D. X. Luong and T. V. An (2010), “Penalty functions for the mul- tiobjective optimization problem”, J. Math. Sci. Adv. Appl., 6(1), pp. 177–192. TÀI LIỆU THAM KHẢO [1] Alber Y. I. (1995), “The penalty method for variational inequali- ties with nonsmooth unbounded operators in banach space”, Numer. Funct. Anal. Optim., 16(9&10), 1111–1125. [2] Chen G. Y. (1988), “Vector variational inequality and vector opti- mization”, Lecture Notes in Econom. and Math. Systems, 285, 408–416. [3] Chen G. Y. (1992), “Existence of solutions for a vector variational inequality: An extension of the Hartman-Stampacchia theorem”, J. Optim. Theory Appl., 74, 445–456. [4] Chen G. Y. and Craven B. D. (1990), “A vector variational inequality and optimization over an efficient set”, ZOR-Meth. Models Oper. Res., 34, 1–12. [5] Chen G. Y. and Craven B. D. (1994), “Existence and continuity of solutions for vector optimization”, J. Optim. Theory Appl., 81(3), 459–468. [6] Chen G. Y. and Yang X. Q. (1990), “The vector complementary prob- lem and its equivalences with the weak minimal element in ordered spaces”, J. Math. Anal. Appl., 153, 136–158. [7] Cominetti R. and Dussault J. P. (1994), “Stable exponential-penalty algorithm with superlinear convergence”, J. Optim. Theory Appl., 83(2), 285–309. 64 65 [8] Dafermos S. C. (1980), “Traffic equilibria and variational inequali- ties”, Transportation Science, 14(1), 42–54. [9] Dafermos S. C. (1990), “Exchange price equilibria and variational inequalities”, Math. Program., 46, 391–402. [10] Dafermos S. C. (1990), “Exchange price equilibria and variational inequalities”, Math. Program., 46(3), 391–402. [11] Dafermos S. C. and McKelvey S. C. (1992), “Partitionable variational inequalities with applications to network and economic equilibria”, J. Optim. Theory Appl., 73(2), 243–268. [12] Daniilidis A. and Hadjisavvas N. (1996), “Existence theorems for vec- tor variational inequalities”, Bull. Austral. Math. Soc., 54, 473–481. [13] Edgeworth F. Y. (1881), Mathematical Psychics, Kegan Paul, Lon- don, England. [14] Evans J. P. and Gould F. J. (1974), “An existence theorem for penalty function theory”, SIAM J. Control., 12, 505–516. [15] Facchiney F. and Pang J.-S. (2003), Finite Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Op- erations Research and Financial Engineering. [16] Giannessi F. (1980), “Theorems of alternative, quadratic programs and complementary problems”, 151–186, in Variational inequality and complementary problems, edited by Cottle R. W., Giannessi F. and Eds J.-L. Lions, Wiley, New York. [17] Giannessi F. (2000), Vector Variational Inequalities and Vector Equilibria, Kluwer Academic Publishers. [18] Goh C. J. and Yang X. Q. (1999), “Vector equilibrium problem and vector optimization”, European J. Oper. Res., 116(3), 615–628. 66 [19] Goh C. J. and Yang X. Q. (2000), “Scalarization methods for vector variational inequality”, in Vector variational inequalities and vector equilibria, edited by Giannessi F., Kluwer Acadamic Publishers. [20] Hartman P. and Stampacchia G. (1966), “On some nonlinear elliptic differential functional equations”, Acta Mathematica, 115, 153–188. [21] Huang X. Q. and Yang X. Q. (2002), “Nonlinear Lagrangian for mul- tiobjective optimization and applications to duality and exact penal- ization”, SIAM J. Optim., 13(3), 675–692. [22] Huang X. Q., Yang X. Q. and Teo K. L. (2006), “Convergence analysis of a class of penalty methods for vector optimization problems with cone constraints”, J. Global Optim., 36(4), 637–652. [23] Ito K. and Kunisch K. (1990), “An augmented Lagrangian technique for variational inequalities”, Appl. Math. Optim., 21(1), 223–241. [24] Jahn J. (2004), Vector Optimization: Theory, Applications, and Extensions, Springer Verlag, New York. [25] Jofre A., Rockafellar R. T. and Wets R. J-B. (2005), “A varia- tional inequality scheme for determining an economic equilibrium”, in Variational Analysis and Applications, edited by Giannessi F. and Maugeri A., Kluwer Acadamic Publishers. [26] Jofré A., Rockafellar R. T. and Wets R. J-B. (2007), “Variational Inequalities and Economic Equilibrium”, Math. Oper. Res., 32(1), 32–50. [27] Kazmi K. R. (1996), “Existence of solutions for vector optimization”, Appl. Math. Lett., 9, 19–22. 67 [28] Konnov I. V. (2001), “Combined relaxation methods for variational inequalities”, Lecture Notes in Economics and mathematical Sys- tems, 495. [29] Konnov I. V. (2007), Equilibium Models and Variational Inequali- ties, Elsevier B. V., Amsterdam. [30] Lee G. M. and Kim D. S. (1994), “Existence of Solutions for vector optimization problems”, J. Optim. Theory Appl., 81(3), 459–468. [31] Lee G. M., Kim D. S., Lee B. S. and Cho S. J. (1993), “Generalized vector variational inequalities and fuzzy extensions”, Appl. Math. Lett., 6, 47–51. [32] Lions J. L. and Stampacchia G. (1967), “Variational inequalities”, Comm. Pure Appl. Math., 20, 493–519. [33] Liu G. P., Yang J. B. andWhidborne J. F. (2002),Multiobjective Op- timization and Control, Research Studies Press Ltd, Baldock United Kingdom. [34] Liu S. and Feng E. (2010), “The exponential penalty function method for multiobjective programming problems”, Optim. Methods Softw., 25(5), 667–675. [35] Luong D. X. (2010), “Penalty functions for the vector variational inequality problem”, Submitted to Acta Mathematica Vietnamica for publication. [36] Luong D. X. and An T. V. (2010), “Penalty functions for the mul- tiobjective optimization problem”, J. Math. Sci. Adv. Appl., 6(1), 177–192. [37] Luong D. X. and Muu L. D. (2010), “Combining the projection meth- ods and the penalty function method to solve the variational inequal- 68 ities with monotone mappings”, Int. J. Optim. Theory Methods Appl., 2(2), 124–137. [38] Muu L. D. (1989), “An augmented penalty function method for solv- ing a class of variational inequalities”, U.S.S.R. Comput. Math. and Math. Phys., 26(6), 117–122. [39] Muu L. D. (1992), “On a Lagrangian penalty function method for nonlinear programming problems”, Appl. Math. Optim., 25(1), 1–9. [40] Nagurney A. (1989), “Migration Equilibrium and Variational Inequal- ities”, Econom. Lett., 31(1), 109–112. [41] Nagurney A. (1999), Network Economics: A Variational Inequality Approach, Edition 2, Springer Series in Advances in Computational Economics. [42] Nagurney A. and Dafermos S. C. (1984), “General spatial economic equilibrium problem”, Oper. Res., 32, 1069–1086. [43] Nguyen V. H. and Strodiot J. J. (1979), “On the convergence rate for a penalty function method of exponential type”, J. Optim. Theory Appl., 27(4), 495–508. [44] Pareto V. (1906), Manual of Political Economy, Societa Editrice Libraria, Milano, Italy. [45] Rockafellar R. T. (1970), Convex Analysis, Princeton Univ. Press, Princeton, New Jersey. [46] Santos L. B., Ruiz-Garzon G., Rojas-Medar M. A. and Rufian-Lizana A. (2008), “Existence of weakly efficient solutions in nonsmooth vec- tor optimization”, Appl. Math. Comput., 200(2), 547–556. [47] Smith M. J. (1979), “The existence, uniqueness and stability of traffic equilibria”, Transportation Science, 13B, 295–304. 69 [48] Stadler W. (1979), “A survey of multicriteria optimization or the vector maximum problem, part I: 1776–1960”, J. Optim. Theory Appl., 29(1), 1–52. [49] Stadler W. (1988), Multicriteria Optimization in Engineering and in the Sciences, Springer Verlag, New York. [50] Stampacchia G. (1964), “Formes bilineares coercives sur les ensembles convexes”, Comptes Rendus Academie Sciences Paris, 258, 4413– 4416. [51] Tang Y. C. and Liu L. W. (2010), “The penalty method for a new system of generalized variational inequlities”, Int. J. Math. Math. Sci., 25(2010), 1–9. [52] White D. J. (2002), “Multiobjective programming and penalty func- tions”, J. Optim. Theory Appl., 13(3), 675–692. [53] Yang X. Q. (1993), “Vector complimentary and minimal element problems”, J. Optim. Theory Appl., 77, 483–495. [54] Yang X. Q. (1993), “Vector variational inequality and its duality”, Nonlinear Anal., 21(11), 869–877. [55] Yang X. Q. and Goh C. J. (1997), “On vector variational inequality: applications to vector traffic equilibria”, J. Optim. Theory Appl., 95, 431–443. [56] Zangwill W. I. (1969), Nonlinear Programming: A Unified Ap- proach, Prentice Hall, Englewood Cliffs, NJ.