Tóm tắt Luận văn Thạc sĩ Khoa học: Một tiếp cận tối ưu hai cấp cho hiệu chỉnh bài toán cân bằng giả đơn điệu

Chia sẻ: Na Na | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

51
lượt xem 5
download

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

Luận văn nghiên cứu và trình bày một số phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu và thông qua bài toán tối ưu hai cấp để tìm điểm giới hạn của các quỹ đạo nghiệm hiệu chỉnh. Sau đây là tóm tắt của luận vă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 văn Thạc sĩ Khoa học: Một tiếp cận tối ưu hai cấp cho hiệu chỉnh bài toán cân bằng giả đơn điệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- NGUYỄN THỊ THANH HẢI MỘT TIẾP CẬN TỐI ƯU HAI CẤP CHO HIỆU CHỈNH BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU LUẬN VĂN THẠC SỸ KHOA HỌC Hà Nội – Năm 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- NGUYỄN THỊ THANH HẢI MỘT TIẾP CẬN TỐI ƯU HAI CẤP CHO HIỆU CHỈNH BÀI TOÁN CÂN BẰNG GIẢ ĐƠN ĐIỆU Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.01.12 LUẬN VĂN THẠC SỸ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. LÊ DŨNG MƯU Hà Nội – Năm 2015
Mục lục Lời cảm ơn 3 Mở đầu 4 1 Kiến thức chuẩn bị 6 1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.1 Không gian tuyến tính định chuẩn. . . . . . . . . . . . . . . . 6 1.1.2 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Tập lồi, nón lồi, hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.2 Nón lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2.3 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Bài toán cân bằng 9 2.1 Bài toán cân bằng và các khái niệm . . . . . . . . . . . . . . . . . . . 9 2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.2 Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Các trường hợp riêng của bài toán cân bằng . . . . . . . . . . . . . . 12 2.2.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Sự tồn tại nghiệm của bài toán cân bằng . . . . . . . . . . . . . . . . 12 3 Hiệu chỉnh dựa trên tối ưu hai cấp 14 3.1 Hiệu chỉnh bài toán cân bằng giả đơn điệu . . . . . . . . . . . . . . . 14 3.1.1 Phương pháp hiệu chỉnh Tikhonov . . . . . . . . . . . . . . . 14 3.1.2 Phương pháp điểm gần kề . . . . . . . . . . . . . . . . . . . 15 3.2 Thuật toán giải . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2.1 Mô tả thuật toán . . . . . . . . . . . . . . . . . . . . . . . . 18 3.2.2 Tính hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . 19 1
MỤC LỤC Kết luận chung 24 Tài liệu tham khảo 25 2
LỜI CẢM ƠN Qua luận văn này em xin bày tỏ lòng kính trọng và biết ơn sâu sắc đến Thầy GS.TSKH Lê Dũng Mưu, người đã tận tình chỉ bảo, hướng dẫn, giúp đỡ em trong suốt quá trình học tập, nghiên cứu và hoàn thiện luận văn này. Tác giả xin trân trọng cám ơn Ban Giám hiệu, Phòng Đào tạo sau đại học đặc biệt là quý thầy cô trong Khoa Toán - Cơ - Tin học Trường Đại học Khoa học Tự nhiên - Đại học Quốc gia Hà Nội đã tạo điều kiện thuận lợi cho em hoàn thành khóa học này. Tác giả xin gửi lời cám ơn chân thành tới gia đình, đồng nghiệp, các anh chị, bạn bè trong lớp cao học khóa 2013 - 2015 đã luôn động viên, khích lệ tác giả cố gắng trong suốt khóa học để luôn đạt được kết quả học tập cao nhất. Em xin chân thành cảm ơn! 3
MỞ ĐẦU Lớp các bài toán cân bằng đang ngày càng được áp dụng nhiều vào các lĩnh vực trong cuộc sống như kinh tế, xã hội,... Chính vì vậy mà ngày càng được các nhà khoa học quan tâm, nghiên cứu. Hơn nữa, bài toán cân bằng còn là sự mở rộng của lớp các bài toán khác như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán cân bằng Nash, bài toán điểm yên ngựa,... Mô hình chung cho bài toán cân bằng là Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0 với mọi y ∈ C (EP(C, f )) trong đó H là không gian Hilbert, C ⊆ H là một tập lồi và f : C ×C → R ∪ {+∞} là một song hàm. Bài toán hiệu chỉnh được xây dựng bằng cách thay song hàm ban đầu bằng song hàm fε := f + εg, trong đó ε, g lần lượt là tham số hiệu chỉnh và song hàm hiệu chỉnh, thông thường ta chọn g là một song hàm đơn điệu mạnh. Luận văn nghiên cứu và trình bày một số phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu và thông qua bài toán tối ưu hai cấp để tìm điểm giới hạn của các quỹ đạo nghiệm hiệu chỉnh. Dựa trên ý tưởng của phương pháp hiệu chỉnh Tikhonov, trong [4] các tác giả đã đưa ra phương pháp hiệu chỉnh với bài toán hiệu chỉnh như sau Tìm x ∈ C sao cho fk (x, y) := f (x, y) + εk g(x, y) ≥ 0 với mọi y ∈ C, trong đó εk > 0 là tham số hiệu chỉnh, g(x, y) là một song hàm đơn điệu mạnh gọi là song hàm hiệu chỉnh. Năm 1970 Martine đưa ra phương pháp điểm gần kề cho bài toán bất đẳng thức biến phân đơn điệu và sau này được mở rộng bởi Rockafellar (1976) cho toán tử đơn điệu cực đaị. Bài toán hiệu chỉnh có dạng Tìm xk ∈ C sao cho fk (xk , y) := f (xk , y) + ck hxk − xk−1 , y − xk i ≥ −δk với mọi y ∈ C, trong đó ck > 0, δk > 0 lần lượt là các tham số hiệu chỉnh và sai số cho trước. Sự khác biệt giữa hai phương pháp này là ở phương pháp hiệu chỉnh điểm gần kề tại 4
MỞ ĐẦU mỗi bước lặp bài toán hiệu chỉnh phụ thuộc vào điểm lặp ở bước trước và tham số hiệu chỉnh ck 6→ 0 khi k → ∞. Nội dung của luận văn gồm ba chương • Chương 1: Kiến thức chuẩn bị. • Chương 2: Bài toán cân bằng. • Chương 3: Hiệu chỉnh dựa trên tối ưu hai cấp. Chương 1 trình bày một số kiến thức cơ sở như không gian tuyến tính, không gian Hilbert; các kiến thức về giải tích lồi như tập lồi, nón lồi, hàm lồi; các khái niệm về sự hội tụ yếu, hội tụ mạnh, hàm nửa liên tục trên, nửa liên tục dưới. Chương 2 phát biểu bài toán cân bằng, một số trường hợp có thể đưa về bài toán cân bằng và sự tồn tại nghiệm của bài toán. Chương 3 trình bày phương pháp hiệu chỉnh bài toán cân bằng giả đơn điệu, thuật toán tiếp cận dựa trên bài toán tối ưu hai cấp và sự hội tụ của thuật toán. Mặc dù đã có nhiều cố gắng, song do thời gian và trình độ còn hạn chế nên luận văn khó tránh khỏi những thiếu sót. Vì vậy em rất mong nhận được sự góp ý của các thầy cô và các bạn để luận văn được hoàn thiện hơn. Hà Nội, ngày 28 tháng 09 năm 2015 Tác giả Nguyễn Thị Thanh Hải 5
Chương 1 Kiến thức chuẩn bị Chương này chúng ta nhắc lại một số kiến thức về không gian tuyến tính, không gian Hilbert, tập lồi, nón lồi, hàm lồi; các khái niệm về sự hội tụ yếu, hội tụ mạnh, hàm nửa liên tục trên, nửa liên tục dưới. Các kiến thức này được lấy ra từ các tài liệu [1], [2]. 1.1 Không gian Hilbert 1.1.1 Không gian tuyến tính định chuẩn. Định nghĩa 1.1.1. Cho X là một không gian tuyến tính thực. Một chuẩn trên X, kí hiệu là k.k, là một ánh xạ k.k : X → R thỏa mãn các tính chất sau 1. kxk ≥ 0, ∀x ∈ X; kxk = 0 ⇔ x = 0; 2. kαxk = |α|kxk, ∀x ∈ X, α ∈ R; 3. kx + yk ≤ kxk + kyk, ∀x, y ∈ X. Khi đó (X, k.k) được gọi là không gian tuyến tính định chuẩn. Định nghĩa 1.1.2. Cho X là không gian tuyến tính thực, X được gọi là không gian tiền Hilbert nếu với mọi x, y ∈ X, xác định một tích vô hướng, kí hiệu là hx, yi, thỏa mãn các tính chất 1. hx, yi = hy, xi, ∀x, y ∈ X; 2. hx + y, zi = hx, zi + hy, zi, ∀x, y, z ∈ X; 3. hαx, yi = αhx, yi, ∀x, y ∈ X, α ∈ R; 4. hx, xi ≥ 0, ∀x ∈ X; hx, xi = 0 ⇔ x = 0. 6
Chương 1. Kiến thức chuẩn bị 1.1.2 Không gian Hilbert Định nghĩa 1.1.3. Cho X là không gian định chuẩn. Dãy {xn } ⊆ X được gọi là dãy cơ bản trong X nếu lim kxn − xm k = 0. n,m→∞ Nếu trong X, mọi dãy cơ bản đều hội tụ, tức là kxn − xm k → 0 kéo theo sự tồn tại xo ∈ X sao cho xn → xo thì X được gọi là không gian đủ. Định nghĩa 1.1.4. Không gian tiền Hilbert và đủ được gọi là không gian Hilbert. Trong luận văn này ta thống nhất kí hiệu H là một không gian Hilbert trên trường số thực. 1.2 Tập lồi, nón lồi, hàm lồi 1.2.1 Tập lồi Định nghĩa 1.2.1. Một tập C ⊆ H được gọi là một tập lồi nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là C lồi khi và chỉ khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λ x + (1 − λ )y ∈ C. 1.2.2 Nón lồi Định nghĩa 1.2.2. Tập C được gọi là nón nếu với mọi λ > 0 và với mọi x ∈ C suy ra λ x ∈ C. Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi. Định nghĩa 1.2.3. Cho C 6= 0/ (không nhất thiết lồi) và y là một vectơ bất kỳ, đặt dC (y) := inf kx − yk. x∈C Ta nói dC (y) là khoảng cách từ y đến C. Nếu tồn tại π ∈ C sao cho dC (y) = kπ − yk, thì ta nói π là hình chiếu của y trên C, kí hiệu pC (y). Theo định nghĩa trên ta thấy rằng, hình chiếu pC (y) của y trên C sẽ là nghiệm của bài toán tối ưu 1 min{ kx − yk2 |x ∈ C}. x 2 7
Chương 1. Kiến thức chuẩn bị 1.2.3 Hàm lồi Định nghĩa 1.2.4. 1. Cho 0/ 6= C ⊆ H lồi và f : C → R ∪ {+∞}. Ta nói f là hàm lồi trên C nếu f λ x + (1 − λ )y ≤ λ f (x) + (1 − λ ) f (y) ∀x, y ∈ C, ∀λ ∈ [0, 1]. 2. Hàm f : H → R ∪ {+∞} được gọi là lồi chặt trên C nếu f λ x + (1 − λ )y < λ f (x) + (1 − λ ) f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1). 3. Hàm f : H → R ∪ {+∞} được gọi là lồi mạnh trên C với hệ số η nếu với mọi x, y ∈ C và với mọi λ ∈ (0, 1) 1 f λ x + (1 − λ )y ≤ λ f (x) + (1 − λ ) f (y) − ηλ (1 − λ )kx − yk2 . 2 4. Hàm f được gọi là hàm lõm trên C nếu − f là hàm lồi trên C. 8
Chương 2 Bài toán cân bằng Chương này chúng ta nhắc lại các khái niệm về song hàm cân bằng, toán tử cân bằng và phát biểu bài toán cân bằng. Một số bài toán có thể đưa về dạng bài toán cân bằng và sự tồn tại nghiệm của bài toán. Các kiến thức này được tham khảo từ các tài liệu [2], [3]. 2.1 Bài toán cân bằng và các khái niệm Trong kinh tế và nhiều lĩnh vực khác bài toán cân bằng có nhiều ý nghĩa quan trọng. Hơn nữa, bài toán là sự mở rộng của nhiều bài toán khác như bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán cân bằng Nash, bài toán điểm yên ngựa,... Vì vậy mà lớp các bài toán cân bằng được nhiều nhà toán học quan tâm, nghiên cứu. 2.1.1 Phát biểu bài toán Định nghĩa 2.1.1. Giả sử C ⊆ H là một tập lồi, đóng, khác rỗng và f : H × H → R ∪ {+∞} thỏa mãn f (x, x) = 0 với mọi x ∈ C. Khi đó ta gọi hàm f là một song hàm cân bằng trên C. Cho f là một song hàm cân bằng trên C. Ta xét bài toán Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C. (EP(C, f )) Ta kí hiệu bài toán này là EP(C, f ) và gọi là bài toán cân bằng, tập nghiệm của nó được kí hiệu là S(C, f ). 2.1.2 Các khái niệm Định nghĩa 2.1.2. Song hàm f : H × H → R ∪ {+∞} được gọi là 9
Chương 2. Bài toán cân bằng 1. đơn điệu mạnh trên C với hệ số γ > 0 nếu f (x, y) + f (y, x) ≤ −γkx − yk2 , ∀x, y ∈ C; 2. đơn điệu trên C nếu f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C; 3. giả đơn điệu trên C nếu f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C. Từ định nghĩa trên ta suy ra: 1) ⇒ 2) ⇒ 3). Điều ngược lại chưa chắc đã đúng.Thật vậy, để làm rõ vấn đề này ta xét một số ví dụ sau. Ví dụ 2.1.1. Xét song hàm f (x, y) = εhx, y − xi, ∀x, y ∈ H , trong đó ε > 0. Với hằng số γ > 0 nào đó thỏa mãn γ ≤ ε ta có f (x, y) + f (y, x) = εhx, y − xi + εhy, x − yi; = εh−x + y, x − yi; = −εkx − yk2 ≤ −γkx − yk2 . Chứng tỏ f là song hàm đơn điệu mạnh trên H . Do γ > 0 nên từ đẳng thức f (x, y) + f (y, x) ≤ −γkx − yk2 ta suy ra f (x, y) + f (y, x) ≤ 0 ∀x, y ∈ H , chứng tỏ f là đơn điệu trên H . Giả sử f (x, y) ≥ 0 với mọi x, y ∈ H . Khi đó, do f (x, y) + f (y, x) ≤ 0, suy ra f (y, x) ≤ − f (x, y) ≤ 0, ∀x, y ∈ H . Vậy f là song hàm giả đơn điệu. 10
Chương 2. Bài toán cân bằng Ví dụ 2.1.2. Cho không gian Hilbert thực ∞ H = l2 := x = (x1 , x2 , ..., xi , ...) := ∑ |xi |2 < +∞, ∀xi ∈ R . i=1 Tích vô hướng và chuẩn trên H tương ứng được xác định bởi ∞ p hx, yi := ∑ xi yi , kxk := hx, xi i=1 với mọi x = (x1 , x2 , ..., xi , ...) = (x1 , xb) ∈ H , y = (y1 , y2 , ..., yi , ...) = (y1 , yb) ∈ H , trong đó xb := (x2 , ..., xi , ...), yb := (y2 , ..., yi , ...). Kí hiệu ∞ p hb x, ybi := ∑ xi yi , kb xk := hb x, xbi. i=2 √ Xét tập C = {x ∈ H : kxk ≤ 2} và hàm f : C ×C → R được cho bởi f (x, y) = (2 − kb xk)hb x, yb− xbi. Nhận thấy, tập nghiệm của bài toán EP(C, f ) là Ce := S(C, f ) = {(x1 , 0, ..., 0, ...) : x1 ∈ R)}. Với x, y ∈ C ta có 2 − kb xk > 0 và 2 − kb yk > 0. Do đó f (x, y) = (2 − kb xk)hb x, yb− xbi ≥ 0; ⇒ hb x, yb− xbi ≥ 0; ⇒ hb y, xb− ybi ≤ 0; ⇒ f (y, x) = (2 − kb yk)hb y, xb− ybi ≤ 0. Chứng tỏ f là song hàm giả đơn điệu trên C. √ Lấy x = (0, 1, 0, ..., 0, ...), y = (0, 2, 0, ..., 0, ...) ∈ C. Khi đó √ xb = (1, 0, ..., 0, ...), yb = ( 2, 0, ..., 0, ...) và √ kb xk = 1, kb yk = 2. Nhận thấy √ √ √ √ f (x, y) + f (y, x) = (2 − 1) × 1 × ( 2 − 1) + (2 − 2) × 2 × (1 − 2) √ √ = ( 2 − 1) × (2 2 − 1) > 0. Vậy, f không đơn điệu trên C. 11
Chương 2. Bài toán cân bằng 2.2 Các trường hợp riêng của bài toán cân bằng 2.2.1 Bài toán tối ưu Cho hàm số ϕ : C → R. Xét bài toán tối ưu Tìm x∗ ∈ C sao cho ϕ(x∗ ) ≤ ϕ(y), ∀y ∈ C. (OP) Đặt f (x, y) := ϕ(y) − ϕ(x). Rõ ràng f (x, x) = ϕ(x) − ϕ(x) = 0. Vậy f là một song hàm cân bằng. Khi đó bài toán tối ưu (OP) tương đương với bài toán Tìm x∗ ∈ C sao cho ϕ(y) − ϕ(x∗ ) ≥ 0, ∀y ∈ C hay Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C. Đây chính là bài toán cân bằng. 2.3 Sự tồn tại nghiệm của bài toán cân bằng Trong mục này chúng ta sẽ xét tới sự tồn tại nghiệm của bài toán cân bằng trong các trường hợp compact và trường hợp có điều kiện bức. Ta xét sự tồn tại nghiệm của bài toán cân bằng dựa trên các giả thiết sau đây Cho C ⊆ H là một tập lồi, đóng, khác rỗng và f : H × H → R ∪ {+∞} Giả thiết (A1 ) f (., y) là hàm nửa liên tục trên, yếu trên H đối với mỗi y ∈ C; (A2 ) f (x, .) là hàm lồi, nửa liên tục dưới yếu trên H và khả vi trên dom f (x, .) đối với mỗi x ∈ C; (A3 ) Tồn taị một tập compact B ⊂ H và một vectơ y0 ∈ B ∩C sao cho f (x, y0 ) < 0 ∀x ∈ C \ B. Giả thiết (A3 ) còn được gọi là điều kiện bức. Ta xét định lý sau. Định lý 2.3.1. (Ky Fan’theorem). Giả sử C là một tập lồi đóng, khác rỗng trong không gian Hilbert H và f : C ×C → R ∪ {+∞} là một song hàm cân bằng xác định trên C. Nếu f thỏa mãn giả thiết A1 và f (x, .) là tựa lồi trên C với mỗi x ∈ C cố định. Khi đó nếu C là tập compact hoặc điều kiện bức (A3 ) được thỏa mãn thì bài toán EP(C, f ) có nghiệm. 12
Chương 2. Bài toán cân bằng Mệnh đề 2.3.1. 1. Nếu hàm f đơn điệu mạnh trên C và thỏa mãn các giả thiết (A1 ), (A2 ), thì EP(C, f ) có nghiệm duy nhất. 2. Nếu hàm f thỏa mãn các giả thiết (A1 ), (A2 ) và giả đơn điệu trên C thì nghiệm của EP(C, f ) là một tập lồi, đóng yếu. 3. Nếu hàm f thỏa mãn các giả thiết (A1 ), (A2 ) và (A3 ) thì tập nghiệm của EP(C, f ) là khác rỗng. Mệnh đề 2.3.2. Giả sử f thỏa mãn các giả thiết (A1 ) và (A2 ). Xét các mệnh đề sau 1. Tồn tại một véctơ y0 ∈ C sao cho L(y0 , f ) := {x ∈ C : f (x, y0 ) ≥ 0} là một tập bị chặn. 2. Tồn tại một hình cầu đóng B ⊆ H và một vectơ y0 ∈ C ∩ B sao cho f (x, y0 ) < 0, ∀x ∈ C \ B. 3. Tập nghiệm S(C, f ) của bài toán EP(C, f ) là khác rỗng và compact yếu. Khi đó 1) ⇒ 2) ⇒ 3). Hơn nữa nếu f là giả đơn điệu trên C thì S(C, f ) là lồi và tập L> (y0 , f ) : {x ∈ C : f (x, y0 ) > 0} là rỗng với mọi y0 ∈ S(C, f ). 13
Chương 3 Hiệu chỉnh dựa trên tối ưu hai cấp Trong chương này chúng ta sẽ nghiên cứu hai phương pháp hiệu chỉnh cho bài toán cân bằng giả đơn điệu đó là phương pháp Tikhonov và phương pháp điểm gần kề. Thuật toán và tính hội tụ của thuật toán hiệu chỉnh dựa trên bài toán tối ưu hai cấp. Các kết quả được lấy ra từ các tài liệu [3], [4], [5], [6], [7]. 3.1 Hiệu chỉnh bài toán cân bằng giả đơn điệu 3.1.1 Phương pháp hiệu chỉnh Tikhonov Xét bài toán cân bằng Tìm x∗ ∈ C sao cho f (x∗ , y) ≥ 0, ∀y ∈ C, trong đó C là một tập lồi đóng trong H , f : C ×C → R là một song hàm giả đơn điệu trên C. Khi đó bài toán hiệu chỉnh được xây dựng như sau. Tìm x ∈ C sao cho (EPδ (C, fε )) fε (x, y) := f (x, y) + εhx − xg , y − xi ≥ −δ , ∀y ∈ C trong đó g(x, y) là một song hàm đơn điệu mạnh được gọi là song hàm hiệu chỉnh, ε > 0 là tham số hiệu chỉnh. Kí hiệu Sδ (C, fε ) là tập nghiệm của bài toán EPδ (C, fε ). Ta xét bổ đề sau Bổ đề 3.1.1. Giả sử f là giả đơn điệu trên C. Khi đó với mọi ε > 0, δ ≥ 0, x ∈ S(C, f ), x(ε) ∈ Sδ (C, fε ) và xg ∈ C, ta có δ 1. kxg − x(ε)k2 + kx(ε) − xk2 ≤ kxg − xk2 + 2 , ε r ! x + xg x − xg δ 2. Sδ (C, fε ) ⊂ B 0, + + ∩C, 2 2 ε 14
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp x − xg r x − xg 2 δ 3. kx(ε) − xg k ≤ + + , 2 2 ε trong đó kí hiệu B(x, r) là hình cầu đóng tâm x, bán kính r. Ví dụ 3.1.1. Ta xét song hàm giả đơn điệu được xác định như ở Ví dụ 2.1.3 Xét bài toán hiệu chỉnh Tìm xk ∈ C sao cho (EP(C, fεk )) fεk (xk , y) := f (xk , y) + εk hxk − xg , y − xk i ≥ −δk , ∀y ∈ C, trong đó xg = (x1g , x2g , ..., xig , ...) ∈ C là nghiệm dự đoán của bài toán EP(C, f ); {εk }, {δk } δk là hai dãy số dương đơn điệu giảm về 0 thỏa mãn → 0 khi k → ∞, và εk fεk (xk , y) = (2 − kb xk , yb− xbk i + εk (x1k − x1g )(y1 − x1k ) + εk hb xk k)hb xk − xbg , yb− xbk i = εk (x1k − x1g )(y1 − x1k ) + εh(2 − kb xk k + εk )b xk − εk xbg , yb− xbk i. Ta nhận thấy, nếu x1k = x1g , (2 − kb xk − εk xbg = 0 xk k + εk )b được thỏa mãn thì xk = (x1k , xbk ) là một nghiệm của bài toán EP(C, fεk ). xk k + εk )b Từ đẳng thức (2 − kb xk − εk xbg = 0 ta suy ra √ k εk xbg ε 2 0 ≤ kbx k= ≤ √ . 2 − kbxk k + εk 2 − 2 + εk Do khi k → ∞ thì εk → 0 nên √ k ε kk 2 0 ≤ limk→+∞ kb x −b 0k = limk→+∞ kb x k ≤ lim √ k→+∞ 2 − 2 + εk ⇒ limk→+∞ kb xk − b 0k = 0. Điều này chứng tỏ xbk hội tụ mạnh về b 0. Do đó, xk hội tụ mạnh về x∗ := (x1g , b 0) = (x1g , 0, ..., 0, ...) ∈ C. e Hơn nữa, x∗ là nghiệm duy nhất của bài toán cân bằng đơn điệu mạnh EP(C, e g) với g(x, y) := (x1 − x1g )(y1 − x1 ) + hb x − xbg , yb− xbi ≥ 0. 3.1.2 Phương pháp điểm gần kề Trong phần này chúng ta sẽ nghiên cứu phương pháp điểm gần kề cho bài toán cân bằng giả đơn điệu. Kết quả hội tụ của phương pháp này cho thấy phương pháp điểm 15
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp gần kề cũng có thể sử dụng cho bài toán cân bằng giả đơn điệu. Tuy nhiên, khác với phương pháp hiệu chỉnh Tikhonov, ở phương pháp này, tại mỗi bước lặp, bài toán hiệu chỉnh phụ thuộc vào điểm lặp ở bước trước và tham số hiệu chỉnh ck > 0 không cần dần đến 0. Xuất phát từ một điểm x0 ∈ C cho trước, tại mỗi bước lặp k = 1, 2, ... xét bài toán hiệu chỉnh Tìm xk ∈ C sao cho fk (xk , y) := f (xk , y) + ck hxk − xk−1 , y − xk i ≥ −δk , ∀y ∈ C trong đó tham số ck > 0 và sai số δk ≥ 0 cho trước. Ta gọi nghiệm của bài toán hiệu chỉnh trên là δk − nghiệm và kí hiệu tập tất cả các δk − nghiệm là Sδk (C, fk ). Gọi dãy {xk } với xk ∈ Sδk (C, fk ) là một quỹ đạo xấp xỉ gần kề. Định lý sau đây sẽ chỉ ra rằng, đối với bài toán cân bằng giả đơn điệu, mặc dù bài toán hiệu chỉnh không có duy nhất nghiệm nhưng mọi quỹ đạo xấp xỉ đều có cùng một giới hạn. Định lý 3.1.1. Giả sử f là giả đơn điệu trên C thỏa mãn các giả thiết (A1), (A2) và bài toán EP(C, f ) là có lời giải. Lấy {ck } và {δk } là hai dãy số dương sao cho δk ck ≤ c < +∞, ∀k, và ∑∞k=1 c < +∞. Khi đó k 1. Đối với mỗi k ∈ N tập nghiệm Sδk (C, fk ) khác rỗng, đóng và bị chặn đều. Khi đó ta có δk kxk−1 − xk k2 + kxk − xk2 ≤ kxk−1 − xk2 + 2 , (3.3) ck trong đó x ∈ S(C, f ), xk ∈ Sδk (C, fk ). 2. Xét dãy {xk } bất kỳ, trong đó xk chọn tùy ý trong tập Sδk (C, fεk ), hội tụ yếu đến một nghiệm của bài toán EP(C, f ). Hơn nữa, nếu {xk } có một điểm hội tụ mạnh, khi đó toàn bộ dãy sẽ hội tụ mạnh đến một nghiệm của bài toán EP(C, f ) ban đầu. Định lý 3.1.2. Giả sử C ⊆ Rn là một tập lồi, đóng, khác rỗng, f là giả đơn điệu trên C, f (., y) là nửa liên tục trên với mỗi y ∈ C, f (x, .) là nửa lên tục dưới và lồi với mỗi x ∈ C, bài toán cân bằng EP(C, f ) có nghiệm. Lấy {ck }, {δk } là hai dãy số dương sao δk cho ck < c < +∞ và ∑∞ k=1 c < +∞. Khi đó k 1. Với mọi k, tập δk -nghiệm của bài toán EP(C, fk ) là khác rỗng và compact. 2. Mọi dãy {xk }, với xk là một δk -nghiệm của bài toán EP(C, fk ) đều hội tụ mạnh tới các nghiệm của bài toán EP(C, f ). 16
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp Nhận xét. Các kết quả trên đã chỉ ra rằng, mọi quỹ đạo của thuật toán điểm gần kề đều có chung một điểm giới hạn yếu. Tuy nhiên việc tìm điểm giới hạn này là một việc khó do sự hội tụ là không mạnh và các kết quả trên không chỉ ra được điểm giới hạn này. Để làm rõ điều này ta xét ví dụ sau. Ví dụ 3.1.2. Xét song hàm cân bằng giả đơn điệu trong Ví dụ 2.1.3. Ta xét bài toán hiệu chỉnh Tìm xk ∈ C sao cho (3.1.1) fk (xk , y) := f (xk , y) + ck hxk − xk−1 , y − xk i ≥ −δk , ∀y ∈ C, trong đó x0 = xg = (x1g , x2g , ..., xig , ...) là điểm xuất phát của dãy lặp, đóng vai trò là nghiệm dự đoán của bài toán EP(C, f ); {ck }, {δk } là hai dãy số không âm sao cho δk ck ≤ c < +∞ với mọi k ∈ N và ∑∞ k=1 < +∞. Khi đó ck fk (xk , y) = (2 − kb xk k)hb xk , yb− xbk i + ck (x1k − x1k−1 )(y1 − x1k ) + ck hb xk − xbk−1 , yb− xbk i, = ck (x1k − x1k−1 )(y1 − x1k ) + ck h(2 − kb xk k + ck )b xk − ck xbk−1 , yb− xbk i. Nhận thấy, nếu x1k = x1k−1 , (2 − kb xk − ck xbk−1 = 0 xk k + ck )b được thỏa mãn thì xk = (x1k , xbk ) là một nghiệm của bài toán EP(C, fk ) và ta có c xbk−1 √ k c k 2 xk k = 0 ≤ kb ≤ √ . 2 − kbk x k + ck 2 − 2 + ck Tuy nhiên, khác với phương pháp hiệu chỉnh Tikhonov, khi cho k → ∞ thì ck 6→ 0 do đó, từ ước lượng trên ta không suy ra được dãy {xk } hội tụ mạnh đến một nghiệm cụ thể nào của bài toán EP(C, f ) mà chỉ có thể kết luận được rằng dãy này bị chặn, hội tụ yếu về một nghiệm nào đó của bài toán ban đầu. 3.2 Thuật toán giải Như chúng ta đã biết, đối với bài toán cân bằng đơn điệu, nhờ tính đơn điệu mạnh của các bài toán hiệu chỉnh, các thuật toán hiệu chỉnh Tikhonov và điềm gần kề có thể dẫn đến những phương pháp giải chấp nhận được. Còn đối với bài toán cân bằng giả đơn điệu, các bài toán hiệu chỉnh nói chung là không đơn điệu mạnh, thậm chí không giả đơn điệu, vì vậy các phương pháp giải đòi hỏi tính đơn điệu không thể áp dụng 17
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp được. Trong trường hợp này, các điểm giới hạn là điểm chiếu của các nghiệm dự đoán xg trên tập nghiệm của bài toán EP(C, f ). Các điểm giới hạn này có thể thu được dựa vào bài toán tối ưu hai cấp min{kx − xg k2 với x ∈ S(C, f )}. (BO) 3.2.1 Mô tả thuật toán Như ta đã biết, khi f là giả đơn điệu trên C, tập nghiệm S(C, f ) của bài toán EP(C, f ) là một tập lồi. Do đó (BO)là bài toán tìm cực tiểu của một hàm chuẩn trên một tập lồi. Giả sử tập nghiệm S(C, f ) của bài toán EP(C, f ) là khác rỗng và f là liên tục yếu, giả đơn điệu trên C. Xét một song hàm L : H × H → R thỏa mãn các điều kiện sau (B1 )L(x, x) = 0, ∃β > 0 : L(x, y) ≥ β2 kx − yk2 , ∀x, y ∈ C; (B2 )L là liên tục yếu, L(x, .) là khả vi, lồi mạnh trên H với mọi x ∈ C và ∇2 L(x, x) = 0 với mọi x ∈ H . Ta xét bổ đề sau Bổ đề 3.2.1. Giả sử f thỏa mãn các giả thiết (A1 ), (A2 ) và L thỏa mãn giả thiết (B1 ), (B2 ). Khi đó, với mọi ρ > 0, các mệnh đề sau đây là tương đương 1. x∗ là nghiệm của bài toán cân bằng; 1 2. x∗ ∈ C : f (x∗ , y) + L(x∗ , y) ≥ 0, ∀y ∈ C; ρ 1 3. x∗ = argmin{ f (x∗ , y) + L(x∗ , y) : y ∈ C}. ρ Thuật toán. Chọn ρ > 0 và η ∈ (0, 1). Khởi đầu với x1 := xg ∈ C (xg có vai trò như là một nghiệm dự đoán). Nếu x1 ∈ S(C, f ), thì x1 là một nghiệm của bài toán tối ưu (BO), ngược lại ta thực hiện phép lặp đối với k theo các bước sau. Bước 1. Giải các bài toán quy hoạch lồi mạnh 1 min{ f (xk , y) + L(xk , y) : y ∈ C} (CP(xk )) ρ để tìm nghiệm duy nhất yk . Nếu yk = xk , chọn uk := xk và chuyển đến Bước 3. Ngược lại chuyển sang Bước 2 18