ĐẠ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ị
. . . . . . . . . . 1.1 Không gian Hilbert
6 6 6 7 7 7 7 8 . . . . . . . . . . . . . . . . . 1.1.1 Không gian tuyến tính định chuẩn. . . 1.1.2 Không gian Hilbert . . . . . . . . . 1.2 Tập lồi, nón lồi, hàm lồi . . . . . . . 1.2.1 Tập lồi . . . 1.2.2 Nón lồi 1.2.3 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Bài toán cân bằng
Phát biểu bài toán . . 2.1.1 2.1.2 Các khái niệm . 2.1 Bài toán cân bằng và các khái niệm . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Bài toán tối ưu . . . . . . . . .
9 9 . . 9 . . 9 . . . . 12 . . 12 . 12 . . . . 2.2 Các trường hợp riêng của 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 Hiệu chỉnh dựa trên tối ưu hai cấp
3.1.1 3.1.2
3.2 Thuật toán giải . . . .
. . . . . . . .
1
14 . . 14 . . 14 . . 15 . . 17 . . 18 . . 19 3.1 Hiệu chỉnh bài toán cân bằng giả đơn điệu . Phương pháp hiệu chỉnh Tikhonov . . Phương pháp điểm gần kề . . . . . . 3.2.1 Mô tả thuật toán . . . 3.2.2 Tính hội tụ của thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MỤC LỤC
Kết luận chung 24
2
Tài liệu tham khảo 25
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.
3
Em xin chân thành cảm ơn!
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
(cid:26)Tìm x ∈ C sao cho
fk(x, y) := f (x, y) + εkg(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
(cid:26)Tìm xk ∈ C sao cho
fk(xk, y) := f (xk, y) + ck(cid:104)xk − xk−1, y − xk(cid:105) ≥ −δk với mọi y ∈ C,
4
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
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 (cid:54)→ 0 khi k → ∞.
• 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.
Nội dung của luận văn gồm ba chương
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ả
5
Nguyễn Thị Thanh Hải
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à (cid:107).(cid:107), là một ánh xạ
(cid:107).(cid:107) : X → R
thỏa mãn các tính chất sau
1. (cid:107)x(cid:107) ≥ 0, ∀x ∈ X; (cid:107)x(cid:107) = 0 ⇔ x = 0;
2. (cid:107)αx(cid:107) = |α|(cid:107)x(cid:107), ∀x ∈ X, α ∈ R;
3. (cid:107)x + y(cid:107) ≤ (cid:107)x(cid:107) + (cid:107)y(cid:107), ∀x, y ∈ X.
Khi đó (X, (cid:107).(cid:107)) đượ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à (cid:104)x, y(cid:105), thỏa mãn các tính chất
1. (cid:104)x, y(cid:105) = (cid:104)y, x(cid:105), ∀x, y ∈ X;
2. (cid:104)x + y, z(cid:105) = (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105), ∀x, y, z ∈ X;
3. (cid:104)αx, y(cid:105) = α(cid:104)x, y(cid:105), ∀x, y ∈ X, α ∈ R;
6
4. (cid:104)x, x(cid:105) ≥ 0, ∀x ∈ X; (cid:104)x, x(cid:105) = 0 ⇔ x = 0.
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
(cid:107)xn − xm(cid:107) = 0. lim n,m→∞
Nếu trong X, mọi dãy cơ bản đều hội tụ, tức là (cid:107)xn − xm(cid:107) → 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 (cid:54)= /0 (không nhất thiết lồi) và y là một vectơ bất kỳ, đặt
(cid:107)x − y(cid:107). dC(y) := inf 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) = (cid:107)π − y(cid:107), 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
7
(cid:107)x − y(cid:107)2|x ∈ C}. { min x 1 2
Chương 1. Kiến thức chuẩn bị
1.2.3 Hàm lồi
1. Cho /0 (cid:54)= C ⊆ H lồi và f : C → R ∪ {+∞}. Ta nói f là hàm
Định nghĩa 1.2.4. lồi trên C nếu
f (cid:0)λ x + (1 − λ )y(cid:1) ≤ λ 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 (cid:0)λ x + (1 − λ )y(cid:1) < λ 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)
f (cid:0)λ x + (1 − λ )y(cid:1) ≤ λ f (x) + (1 − λ ) f (y) − ηλ (1 − λ )(cid:107)x − y(cid:107)2. 1 2
8
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.
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
9
Định nghĩa 2.1.2. Song hàm f : H × H → R ∪ {+∞} được gọi là
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) ≤ −γ(cid:107)x − y(cid:107)2, ∀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) = ε(cid:104)x, y − x(cid:105), ∀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) = ε(cid:104)x, y − x(cid:105) + ε(cid:104)y, x − y(cid:105);
= ε(cid:104)−x + y, x − y(cid:105); = −ε(cid:107)x − y(cid:107)2 ≤ −γ(cid:107)x − y(cid:107)2.
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) ≤ −γ(cid:107)x − y(cid:107)2
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 .
10
Vậy f là song hàm giả đơn điệu.
Chương 2. Bài toán cân bằng
Ví dụ 2.1.2.
Cho không gian Hilbert thực
∞ ∑ i=1
|xi|2 < +∞, ∀xi ∈ R(cid:9). H = l2 := (cid:8)x = (x1, x2, ..., xi, ...) :=
Tích vô hướng và chuẩn trên H tương ứng được xác định bởi
∞ ∑ i=1
(cid:104)x, y(cid:105) := (cid:107)x(cid:107) := (cid:112)(cid:104)x, x(cid:105) xiyi,
y = (y1, y2, ..., yi, ...) = (y1, (cid:98)y) ∈ H , với mọi x = (x1, x2, ..., xi, ...) = (x1, (cid:98)x) ∈ H , trong đó
(cid:98)x := (x2, ..., xi, ...), (cid:98)y := (y2, ..., yi, ...).
Kí hiệu
∞ ∑ i=2
xiyi,
(cid:104)(cid:98)x, (cid:98)y(cid:105) := √ Xét tập C = {x ∈ H : (cid:107)x(cid:107) ≤ (cid:107)(cid:98)x(cid:107) := (cid:112)(cid:104)(cid:98)x, (cid:98)x(cid:105). 2} và hàm f : C ×C → R được cho bởi
f (x, y) = (2 − (cid:107)(cid:98)x(cid:107))(cid:104)(cid:98)x, (cid:98)y − (cid:98)x(cid:105).
Nhận thấy, tập nghiệm của bài toán EP(C, f ) là
(cid:101)C := S(C, f ) = {(x1, 0, ..., 0, ...) : x1 ∈ R)}.
Với x, y ∈ C ta có 2 − (cid:107)(cid:98)x(cid:107) > 0 và 2 − (cid:107)(cid:98)y(cid:107) > 0. Do đó f (x, y) = (2 − (cid:107)(cid:98)x(cid:107))(cid:104)(cid:98)x, (cid:98)y − (cid:98)x(cid:105) ≥ 0; ⇒ (cid:104)(cid:98)x, (cid:98)y − (cid:98)x(cid:105) ≥ 0; ⇒ (cid:104)(cid:98)y, (cid:98)x − (cid:98)y(cid:105) ≤ 0; ⇒ f (y, x) = (2 − (cid:107)(cid:98)y(cid:107))(cid:104)(cid:98)y, (cid:98)x − (cid:98)y(cid:105) ≤ 0.
√ y = (0, Chứng tỏ f là song hàm giả đơn điệu trên C. Lấy x = (0, 1, 0, ..., 0, ...), 2, 0, ..., 0, ...) ∈ C. Khi đó √ 2, 0, ..., 0, ...) (cid:98)x = (1, 0, ..., 0, ...), (cid:98)y = (
và √ 2. (cid:107)(cid:98)x(cid:107) = 1, (cid:107)(cid:98)y(cid:107) =
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.
11
Vậy, f không đơn điệu trên C.
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
(OP) Tìm x∗ ∈ C sao cho ϕ(x∗) ≤ ϕ(y), ∀y ∈ C.
Đặ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
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; 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
Tồn taị một tập compact B ⊂ H và một vectơ y0 ∈ B ∩C sao cho 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) (A2) với mỗi x ∈ C; (A3)
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.
12
Đị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.
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}
13
là rỗng với mọi y0 ∈ S(C, f ).
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.
(cid:26)Tìm x ∈ C sao cho (EPδ (C, fε)) fε(x, y) := f (x, y) + ε(cid:104)x − xg, y − x(cid:105) ≥ −δ , ∀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. (cid:107)xg − x(ε)(cid:107)2 + (cid:107)x(ε) − x(cid:107)2 ≤ (cid:107)xg − x(cid:107)2 + 2 δ ε
(cid:32) (cid:33)
14
∩C, 0, 2. Sδ (C, fε) ⊂ B (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) + (cid:114)(cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) + x + xg 2 x − xg 2 δ ε
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp
+ , 3. (cid:107)x(ε) − xg(cid:107) ≤ (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) + (cid:13) 2 (cid:13) (cid:13) (cid:114)(cid:13) (cid:13) (cid:13) x − xg 2 x − xg 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
(cid:26) Tìm xk ∈ C sao cho (EP(C, fεk)) fεk(xk, y) := f (xk, y) + εk(cid:104)xk − xg, y − xk(cid:105) ≥ −δk, ∀y ∈ C,
i , ...) ∈ C là nghiệm dự đoán của bài toán EP(C, f ); {εk}, {δk}
1, xg
2, ..., xg
trong đó xg = (xg
1) + εk(cid:104)(cid:98)xk − (cid:98)xg, (cid:98)y − (cid:98)xk(cid:105)
là hai dãy số dương đơn điệu giảm về 0 thỏa mãn → 0 khi k → ∞, và
1)(y1 − xk
= εk(xk fεk(xk, y) = (2 − (cid:107)(cid:98)xk(cid:107))(cid:104)(cid:98)xk, (cid:98)y − (cid:98)xk(cid:105) + εk(xk 1 − xg δk εk 1 − xg 1)(y1 − xk 1) + ε(cid:104)(2 − (cid:107)(cid:98)xk(cid:107) + εk)(cid:98)xk − εk(cid:98)xg, (cid:98)y − (cid:98)xk(cid:105).
1, (2 − (cid:107)(cid:98)xk(cid:107) + εk)(cid:98)xk − εk(cid:98)xg = 0
1 = xg xk 1, (cid:98)xk) là một nghiệm của bài toán EP(C, fεk).
Ta nhận thấy, nếu
được thỏa mãn thì xk = (xk Từ đẳng thức (2 − (cid:107)(cid:98)xk(cid:107) + εk)(cid:98)xk − εk(cid:98)xg = 0 ta suy ra
. 0 ≤ (cid:107)(cid:98)xk(cid:107) = (cid:13) (cid:13) (cid:13) ≤ (cid:13) (cid:13) (cid:13) 2 − √ 2 ε √ 2 + εk εk(cid:98)xg 2 − (cid:107)(cid:98)xk(cid:107) + εk
Do khi k → ∞ thì εk → 0 nên
k→+∞
1,(cid:98)0) = (xg
1, 0, ..., 0, ...) ∈ (cid:101)C. Hơn nữa, x∗ là nghiệm
εk √ 0 ≤ limk→+∞(cid:107)(cid:98)xk − (cid:98)0(cid:107) = limk→+∞(cid:107)(cid:98)xk(cid:107) ≤ lim 2 − √ 2 2 + εk
⇒ limk→+∞(cid:107)(cid:98)xk − (cid:98)0(cid:107) = 0. Điều này chứng tỏ (cid:98)xk hội tụ mạnh về (cid:98)0. Do đó, xk hội tụ mạnh về x∗ := (xg duy nhất của bài toán cân bằng đơn điệu mạnh EP( (cid:101)C, g) với
1)(y1 − x1) + (cid:104)(cid:98)x − (cid:98)xg, (cid:98)y − (cid:98)x(cid:105) ≥ 0.
g(x, y) := (x1 − xg
3.1.2 Phương pháp điểm gần kề
15
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
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
(cid:26)Tìm xk ∈ C sao cho
fk(xk, y) := f (xk, y) + ck(cid:104)xk − xk−1, y − xk(cid:105) ≥ −δ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.
k=1
δk ck
< +∞. Khi đó Đị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 ck ≤ c < +∞, ∀k, và ∑∞
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ó
, (cid:107)xk−1 − xk(cid:107)2 + (cid:107)xk − x(cid:107)2 ≤ (cid:107)xk−1 − x(cid:107)2 + 2 (3.3) δk 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.
k=1
δk ck
< +∞. Khi đó Đị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 cho ck < c < +∞ và ∑∞
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
16
tới các nghiệm của bài toán EP(C, f ).
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
1, xg
2, ..., xg
(cid:26) Tìm xk ∈ C sao cho (3.1.1) fk(xk, y) := f (xk, y) + ck(cid:104)xk − xk−1, y − xk(cid:105) ≥ −δk, ∀y ∈ C,
k=1
1 − xk−1 1
1) + ck(cid:104)(cid:98)xk − (cid:98)xk−1, (cid:98)y − (cid:98)xk(cid:105),
< +∞. Khi đó trong đó x0 = xg = (xg i , ...) 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 ck ≤ c < +∞ với mọi k ∈ N và ∑∞ δk ck
= ck(xk )(y1 − xk fk(xk, y) = (2 − (cid:107)(cid:98)xk(cid:107))(cid:104)(cid:98)xk, (cid:98)y − (cid:98)xk(cid:105) + ck(xk 1 − xk−1 1 )(y1 − xk 1) + ck(cid:104)(2 − (cid:107)(cid:98)xk(cid:107) + ck)(cid:98)xk − ck(cid:98)xk−1, (cid:98)y − (cid:98)xk(cid:105).
1 = xk−1 xk 1
Nhận thấy, nếu
, (2 − (cid:107)(cid:98)xk(cid:107) + ck)(cid:98)xk − ck(cid:98)xk−1 = 0
1, (cid:98)xk) là một nghiệm của bài toán EP(C, fk) và ta có
được thỏa mãn thì xk = (xk
ck √ . 0 ≤ (cid:107)(cid:98)xk(cid:107) = (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) ≤ 2 − √ 2 2 + ck ck(cid:98)xk−1 2 − (cid:107)(cid:98)xk(cid:107) + ck
Tuy nhiên, khác với phương pháp hiệu chỉnh Tikhonov, khi cho k → ∞ thì ck (cid:54)→ 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
17
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
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{(cid:107)x − xg(cid:107)2 với x ∈ S(C, f )}. (BO)
3.2.1 Mô tả thuật toán
2 (cid:107)x − y(cid:107)2, ∀x, y ∈ C;
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) ≥ β (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à ∇2L(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;
L(x∗, y) ≥ 0, ∀y ∈ C; 2. x∗ ∈ C : f (x∗, y) + 1 ρ
3. x∗ = argmin{ f (x∗, y) + L(x∗, y) : y ∈ C}. 1 ρ
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
L(xk, y) : y ∈ C} min{ f (xk, y) + (CP(xk)) 1 ρ
18
để 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
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp
Bước 2.(Qui tắc tìm kiếm theo tia Amijio) Tìm một số nguyên, không âm nhỏ nhất mk , m là một số nguyên, thỏa mãn
(3.11) zk,m := (1 − η m)xk + η myk,
f (zk,m, yk) + L(xk, yk) ≤ 0. (3.12) 1 ρ
Đặt ηk := η mk, zk := zk,mk, tính
(3.13) σk = uk := PC(xk − σkgk),
−ηk f (zk, yk) (1 − ηk)(cid:107)gk(cid:107)2 , trong đó gk ∈ ∂2 f (zk, zk), dưới đạo hàm của hàm lồi f (zk, .) tại zk. Bước 3. Xây dựng các nửa không gian
Ck := {y ∈ H : (cid:107)uk − y(cid:107)2 ≤ (cid:107)xk − y(cid:107)2};
Dk := {y ∈ H : (cid:104)xg − xk, y − xk(cid:105) ≤ 0}.
Bước 4. Đặt Bk = Ck ∩ Dk ∩C và tính xk+1 := PBk(xg). Nếu xk+1 ∈ S(C, f ), kết luận xk+1 là nghiệm của bài toán (BO). Ngược lại, tăng k lên 1 và lặp lại quá trình.
3.2.2 Tính hội tụ của thuật toán
Bổ đề và định lý sau cho thấy tính hội tụ mạnh của các dãy {xk}, {uk} trong thuật
toán trên.
Bổ đề 3.2.2. Từ các giả thiết của Bổ đề 3.2.1 ta có 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)
k (cid:107)gk(cid:107)2, ∀x∗ ∈ S(C, f ), ∀k.
(3.15) (cid:107)uk − x∗(cid:107)2 ≤ (cid:107)xk − x∗(cid:107)2 − σ 2
Định lý 3.2.1. Giả sử f là song hàm liên tục yếu, f(x,.) là lồi, khả dưới vi phân trên C với mọi x ∈ C và bài toán EP(C, f ) có nghiệm. Khi đó cả hai dãy {xk}, {uk} đều hội tụ tới nghiệm duy nhất của bài toán tối ưu hai cấp (BO).
Chứng minh.
Ta có S(C, f ) ⊆ Bk với mọi k. Thật vậy, từ Định lý 3.1.2 ta có
19
(cid:107)un − x∗(cid:107)2 ≤ (cid:107)xn − x∗(cid:107)2, ∀x∗ ∈ S(C, f ),
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp
do đó S(C, f ) ⊆ Ck. Ta chứng minh S(C, f ) ⊆ Dk bằng phương pháp qui nạp. Với k = 1 thì D1 = H nên S(C, f ) ⊆ D1. Giả sử S(C, f ) ⊆ Dk, tức là (cid:104)xg − xk, x∗ − xk(cid:105) ≤ 0 với mọi x∗ ∈ S(C, f ). Khi đó S(C, f ) ⊆ Bk = Ck ∩ Dk. Mặt khác theo định nghĩa xk+1 = PBk(xg) nên ta có (cid:104)x∗ − xk+1, xk+1 − xg(cid:105) ≤ 0, ∀x∗ ∈ S(C, f ),
hay
(cid:104)xk+1 − x∗, xg − xk+1(cid:105) ≤ 0, ∀x∗ ∈ S(C, f ).
Vậy S(C, f ) ⊆ Dk+1, suy ra S(C, f ) ⊆ Bk. Từ định nghĩa của Dk, ta có
xk = PDk(xg).
Do xk+1 ∈ Dk nên
(cid:107)xk − xg(cid:107) ≤ (cid:107)xk+1 − xg(cid:107), ∀k ∈ C. Hơn nữa, xk = PDk(xg) và S(C, f ) ⊂ Dk với mọi k nên ta có
(cid:107)xk − xg(cid:107) ≤ (cid:107)x∗ − xg(cid:107), ∀x∗ ∈ S(C, f ), ∀k. (3.20)
Do đó {xk} bị chặn. Do tính bị chặn của {xk} và (cid:107)xk − xg(cid:107) ≤ (cid:107)xk+1 − xg(cid:107) với mọi k nên limk (cid:107)xk − xg(cid:107) tồn tại. Ta chứng minh (cid:107)xk+1 − xk(cid:107) → 0 khi k → ∞..
Thật vậy, do xk ∈ Dk và xk+1 ∈ Dk, Dk là một tập lồi nên ta có
∈ Dk.
(cid:107)xg − xk(cid:107)2 ≤ (cid:13)
+ (cid:13) 2; (cid:13) (cid:13)xg − xk − xg 2
= kk+1 + xk 2 Mặt khác, xk = PDk(xg) nên theo tính chất lồi mạnh của hàm (cid:107)xg − .(cid:107)2 ta có xk+1 + xk (cid:13) 2; (cid:13) 2 xk+1 − xg 2 (cid:107)xg − xk+1(cid:107)2 + (cid:107)xk+1 − xk(cid:107)2. (cid:107)xg − xk(cid:107)2 − 1 2 1 4 = (cid:13) (cid:13) 1 2
Suy ra
(cid:107)xk+1 − xk(cid:107)2 ≤ (cid:107)xg − xk+1(cid:107)2 − (cid:107)xg − xk(cid:107)2. 1 2
Do lim (cid:107)xk − xg(cid:107) tồn tại nên ta suy ra (cid:107)xk+1 − xk(cid:107) → 0 khi k → ∞. Mặt khác, xk+1 ∈ Bk ⊆ Ck, từ định nghĩa của Ck ta có
20
(cid:107)uk − xk+1(cid:107) ≤ (cid:107)xk+1 − xk(cid:107).
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp
Do đó,
(cid:107)uk − xk(cid:107) ≤ (cid:107)uk − xk+1(cid:107) + (cid:107)xk+1 − xk(cid:107) ≤ 2(cid:107)xk+1 − xk(cid:107),
và (cid:107)xk+1 − xk(cid:107) → 0, tức là (cid:107)uk − xk(cid:107) → 0 khi k → ∞.
Sau đây ta sẽ chỉ ra rằng một điểm tụ yếu bất kỳ của dãy {xk} đều là một nghiệm của bài toán EP(C, f ). Thật vậy, lấy x là một điểm tụ yếu bất kỳ của dãy {xk}. Không mất tính chất tổng quát, ta giả sử xk (cid:42) x. Ta xét hai trường hợp Trường hợp 1. Việc tìm kiếm theo tia chỉ xảy ra ở hữu hạn điểm. Trong trường hợp này, theo thuật toán, uk = xk với mọi k vô hạn, do đó yk = xk là một nghiệm của bài toán EP(C, f ) với mọi k. Do vậy, trường hợp này luôn đúng. Trường hợp 2. Việc tìm kiếm theo tia xảy ra tại vô hạn điểm.
Khi đó ta trích ra một dãy con và giả thiết rằng việc tìm kiếm theo tia là thực hiện
được với mọi k. Ta xét hai khả năng
(a) limkηk > 0.
Do xk (cid:42) x và (cid:107)uk − xk(cid:107) → 0 nên uk (cid:42) x. Áp dụng công thức (3.15) với x∗ ∈ S(C, f ) ta thấy σk(cid:107)gk(cid:107)2 → 0. Do định nghĩa của σk nên ta có
− (cid:104)gk, yk − zk(cid:105) → 0. ηk 1 − ηk
Từ điều kiện limkηk > 0, giả sử (cid:104)gk, yk − zk(cid:105) → 0. Mặt khác từ giả thiết (B1) và qui tắc tìm kiếm Armijo ta có
(cid:107)xk − yk(cid:107)2 ≤ 0 ≤ L(xk, yk) ≤ −(cid:104)gk, yk − zk(cid:105) → 0. β 2ρ 1 2ρ
Do đó, (cid:107)xk − yk(cid:107) → 0. Do xk (cid:42) x nên yk (cid:42) x, trong đó yk là nghiệm của bài toán
(cid:110) f (xk, y) + (cid:111) . min L(xk, y) : y ∈ C (CP(Ck)) 1 ρ
Khi đó ta có thể viết lại như sau
f (xk, y) + L(xk, y) ≥ f (xk, yk) + L(xk, yk) ∀y ∈ C. 1 ρ 1 ρ
Cho k tiến ra vô cùng, do tính liên tục yếu của f và L nên
L(x, y) ≥ f (x, y) + L(x, y) ∀y ∈ C, f (x, y) + 1 ρ 1 ρ
21
điều này cho thấy y là nghiệm của bài toán CP(x). Do (cid:107)xk − yk(cid:107) → 0 và xk (cid:42) x, yk (cid:42) y nên suy ra x = y. Vậy theo Bổ đề 3.2.1 x là một nghiệm của bài toán EP(C, f ).
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp
(b) limk ηk = 0.
Trong trường hợp này dãy {yk} cũng bị chặn. Thật vậy, do yk là nghiệm của bài toán CP(xk), hàm mục tiêu là liên tục yếu, lồi mạnh và lời giải là không đổi. Theo Định lý Berge, ánh xạ xk → s(xk) := yk là liên tục yếu. Từ tính chất bị chặn của {xk} ta suy ra {yk} bị chặn, suy ra yk (cid:42) y.
Lập luận tương tự như trước ta được
f (x, y) + L(x, y) ≤ f (x, y) + L(x, y), ∀y ∈ C (3.21) 1 ρ 1 ρ
Mặt khác, do mk là số tự nhiên nhỏ nhất thỏa mãn quy tắc tìm kiếm theo tia Armijo nên
f (zk,mk−1, yk) + L(xk, yk) > 0. (3.22)
1 ρ Trong đó zk,mk−1 (cid:42) x khi k → ∞. Từ bất đẳng thức (3.22), do tính liên tục yếu của f và L ta thu được giới hạn
f (x, y) + L(x, y) ≥ 0. (3.23) 1 ρ
Thay y = x vào (3.21) ta được
f (x, y) + L(x, y) ≤ 0, 1 ρ
kết hợp với (3.23) ta được
f (x, y) + L(x, y) = 0. (3.24) 1 ρ
Từ (3.24) và
f (x, x) + L(x, x) = 0, 1 ρ
suy ra cả x, y đều là nghiệm của bài toán
(cid:110) f (x, y) + (cid:111) . min L(x, y) : y ∈ C 1 ρ
Do đó x = y, theo Bổ đề 3.2.1 x là nghiệm của bài toán EP(C, f ). Hơn nữa, từ điều kiện (cid:107)uk − xk(cid:107) → 0 ta có thể kết luận rằng, mọi điểm tụ yếu của {xk} đều là một nghiệm của bài toán EP(C, f ).
22
Ta cần chỉ ra {xk} hội tụ mạnh đến nghiệm duy nhất của bài toán hai cấp (BO). Nhận thấy mọi điểm tụ yếu của {xk} đều thuộc tập nghiệm S(C, f ). Gọi x∗ là một điểm tụ bất kỳ của dãy {xk}, s = PS(C, f )(xg). Khi đó, tồn tại dãy con {xk j} của dãy {xk} sao cho xk j → x∗ khi j → ∞.
Chương 3. Hiệu chỉnh dựa trên tối ưu hai cấp
Theo chứng minh trên ta có x∗ ∈ S(C, f ) và từ định nghĩa của s ta suy ra
sup(cid:107)xk − xg(cid:107) ≤ (cid:107)s − xg(cid:107). (cid:107)s − xg(cid:107) ≤ (cid:107)x∗ − xg(cid:107) = lim j (cid:107)xk j − xg(cid:107) ≤ lim k
Bất đẳng thức cuối xảy ra do xk+1 = PBk(xg) và s ∈ S(C, f ) ⊆ Bk với mọi k. Do đó
lim (cid:107)xk − xg(cid:107) = (cid:107)s − xg(cid:107) = (cid:107)x∗ − xg(cid:107).
23
(cid:3) Do x∗ ∈ S(C, f ), s = PS(C, f )(xg) và S(C, f ) là một tập lồi đóng nên hình chiếu của xg lên S(C, f ) là duy nhất, suy ra x∗ = s, do đó xk → s khi k → ∞ là nghiệm của bài toán (BO). Từ (cid:107)xk − uk(cid:107) → 0 ta có uk → Psxg.
KẾT LUẬN CHUNG
Luận văn đã trình bày các vấn đề chính sau đây - Các khái niệm về không gian tuyến tính định chuẩn, không gian tiền Hilbert,
không gian Hilbert, sự hội tụ yếu, hội tụ mạnh trong không gian Hilbert. - Các định nghĩa về tập lồi, nón lồi, hàm lồi và tính chất của hàm lồi. - Phát biểu bài toán cân bằng, sự tồn tại nghiệm của bài toán cân bằng. Trình bày một số trường hợp có thể đưa về bài toán cân bằng như bài toán tối ưu, 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.
24
- Trình bày phương pháp hiệu chỉnh Tikhonov và phương pháp điểm gần kề cho bài toán cân bằng giả đơn điệu, thuật toán hiệu chỉnh 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.
TÀI LIỆU THAM KHẢO
Tiếng Việt [1] Đỗ Văn Lưu, Giải tích hàm, (2009), NXB khoa học kỹ thuật, Hà Nội. [2] Lê Dũng Mưu, Nguyễn Văn Hiền, Nguyễn Hữu Điển (2015), Giáo trình giải
tích lồi ứng dụng, NXB ĐHQG Hà Nội.
Tiếng Anh [3] Bui V.Dinh, Pham G.Hung, Le D.Muu (2014), Bilevel optimization as a regu- larization approach to pseudomonotone equilibrium problems, Numerical Functional Analysis and Optimization. 35:539-563.
[4] Pham G. Hung, Le D. Muu (2011), The Tikhonov regularization extended to equilibrium problems involving pseudomontone bifunctions, Nonlinear Analysis 74:6121 – 6129.
[5] M. Bianchi and S. Schaible (1996), Generalized monotone bifunctions and
equilibrium problems, Journal of Optimization Theory and Applications. 90:31–43.
[6] G. Mastroeni (2003), On auxiliary priciple for equilibrium problems, Kluwer
Academic, Dordrecht, pp. 289–298.
[7] L. D. Muu (1984), Stability property of a class of variational inequality, Opti-
25
mization 15:347–351.
