ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THỊ MINH HIẾU
BÀI TOÁN CÂN BẰNG
VỚI SONG HÀM GIẢ ĐƠN ĐIỆU MẠNH
Chuyên ngành: Toán ứng dụng
Mã số:
60 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
GS. TSKH. LÊ DŨNG MƯU
Thái Nguyên - 2015
i
Mục lục
Lời cảm ơn
iii
Danh sách ký hiệu
iv
Mở đầu
1
1
Bài toán cân bằng
2
1.1
Bài toán cân bằng và các trường hợp riêng . . . . . . . . . . .
2
1.1.1
Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2
Bài toán điểm bất động Brouwer . . . . . . . . . . . .
3
1.1.3
Bài toán bất đẳng thức biến phân tổng quát . . . . . . .
4
1.1.4
Bài toán cân bằng Nash . . . . . . . . . . . . . . . . .
5
1.2
Định nghĩa về tính đơn điệu, giả đơn điệu mạnh của song hàm .
7
1.3
Sự tồn tại nghiệm của bài toán cân bằng . . . . . . . . . . . . .
9
2
Thuật toán chiếu giải bài toán cân bằng giả đơn điệu mạnh
2.1
Thuật toán chiếu cho bài toán cân bằng giả đơn điệu mạnh
2.2
Các thuật toán và tốc độ hội tụ của chúng
13
. . 13
. . . . . . . . . . . 17
2.2.1
Thuật toán hội tụ tuyến tính . . . . . . . . . . . . . . . 17
2.2.2
Thuật toán không cần biết các hằng số Lipschitz . . . . 23
2.2.3
Thuật toán không có điều kiện Lipschitz . . . . . . . . 25
ii
2.3
Ví dụ áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Kết luận và Đề nghị
33
Tài liệu tham khảo
34
iii
Lời cảm ơn
Luận văn này được thực hiện và hoàn thành tại Trường Đại học Khoa học Đại học Thái Nguyên. Em xin bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy
GS. TSKH Lê Dũng Mưu (Viện Toán học, Viện Hàn lâm Khoa học và Công
nghệ Việt Nam), người đã trực tiếp hướng dẫn tận tình và động viên em trong
suốt thời gian nghiên cứu và viết luận văn vừa qua.
Tôi cũng xin gửi lời cảm ơn chân thành và sâu sắc tới các thầy, cô trong khoa
Toán - Tin, Trường Đại học Khoa học - Đại học Thái Nguyên đã giảng dạy và
giúp đỡ tác giả trong suốt quá trình học tập tại trường.
Xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp và các thành viên trong
lớp cao học Toán ứng dụng K7A đã luôn quan tâm, động viên, giúp đỡ tôi trong
thời gian học tập và quá trình làm luận văn.
Mặc dù có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu xót và
hạn chế, rất mong nhận được sự đóng góp quý báu của quý thầy, cô cùng toàn
thể bạn đọc.
NGUYỄN THỊ MINH HIẾU
Học viên Cao học Toán K7A,
Trường Đại học Khoa học - Đại học Thái Nguyên
iv
Danh sách ký hiệu
Trong toàn luận văn, ta dùng những ký hiệu với các ý nghĩa xác định dưới
đây:
N
tập số tự nhiên
R
tập hợp các số thực
H
không gian Hilbert
ha, bi
tích vô hướng của vectơ a và b
∂f (x) dưới vi phân của hàm f tại x
PC (x) hình chiếu (theo chuẩn) của x lên tập C
1
Mở đầu
Bài toán cân bằng hay còn gọi là bất đẳng thức Ky Fan là một đề tài hiện
nay đang được quan tâm nghiên cứu, do bài toán này có nhiều ứng dụng trong
các lĩnh vực khác nhau. Hơn nữa nhiều bài toán quan trọng như bài toán tối ưu,
bất đẳng thức biến phân, điểm bất động Brouwer, bài toán cân bằng Nash trong
trò chơi không hợp tác đều có thể mô tả dưới bài toán cân bằng.
Một trong những hướng nghiên cứu được quan tâm nhiều là các phương
pháp giải thông thường. Để xây dựng được các phương pháp giải, người ta phải
có những điều kiện đặt lên song hàm của bài toán, một điều kiện thường được
sử dụng là tính đơn điệu của song hàm.
Bản luận văn này nhằm mục đích tổng hợp những kiến thức cơ bản nhất về
bài toán cân bằng. Luận văn nghiên cứu bài toán cân bằng với song hàm giả
đơn điệu mạnh. Cụ thể luận văn đề cập tới sự tồn tại nghiệm của bài toán cân
bằng giả đơn điệu mạnh, hơn nữa luận văn còn giới thiệu một số thuuật toán để
giải bài toán đơn điệu mạnh. Cuối cùng giới thiệu một mô hình sản xuất điện.
Thái Nguyên, tháng 05 năm 2015
Nguyễn Thị Minh Hiếu
Học viên Cao học Toán K7A
Chuyên ngành Toán ứng dụng
Trường Đại học Khoa học - Đại học Thái Nguyên
Email:
[email protected]
2
Chương 1
Bài toán cân bằng
Trong chương này chúng ta giới thiệu bài toán cân bằng và trình bày một số
trường hợp riêng điển hình của bài toán này. Tiếp đến ta khảo sát một số tính
chất của đơn điệu, đặc biệt là song hàm giả đơn điệu mạnh. Cuối chương xét
đến sự tồn tại duy nhất nghiệm của bài toán cân bằng với song hàm giả đơn điệu
mạnh. Các kết quả của chương này được tổng hợp từ các tài liệu [1], [2], [3], [4],
[5], [6], [7].
1.1
Bài toán cân bằng và các trường hợp riêng
Cho H là không gian Hilbert thực với Tôpô yếu được xác định bởi tích vô
hướng h.i ứng với chuẩn k.k. Giả sử C là tập lồi đóng khác rỗng trong không
gian Hilbert H và một song hàm f : C × C → R thỏa mãn f (x, x) = 0 với
mọi x ∈ C . Một hàm f như vậy gọi là song hàm cân bằng.
Chúng ta xét bài toán cân bằng được định nghĩa như sau:
Tìm x∗ ∈ C sao cho f (x∗ , x) ≥ 0, ∀x ∈ C.
(EP)
Bài toán này lần đầu tiên được đưa ra vào năm 1955 bởi H. Nikaido, K.
Isoda nhằm tổng quát hóa bài toán cân bằng Nash trong trò chơi không hợp tác
và vào năm 1972, được Ky Fan giới thiệu năm 1972 và thường được gọi là bất
3
đẳng thức Ky Fan.
Bài toán (EP ) còn được đặt tên là bài toán cân bằng bởi tác giả L. D Muu
và W. Oettli năm 1992, E. Blum và W. Oettli giới thiệu năm 1994;
Bài toán cân bằng (EP ) bao gồm một số bài toán như: bài toán tối ưu hóa,
điểm yên ngựa, bất đẳng thức biến phân, điểm bất động và mô hình cân bằng
Nash trong lý thuyết trò chơi không hợp tác v.v...
1.1.1
Bài toán tối ưu
Xét bài toán min {ϕ (x) : x ∈ C}. Đặt
f (x, y) = ϕ (y) − ϕ (x).
Khi đó
ϕ (x) ≤ ϕ(y), ∀y ∈ C ⇔ f (x, y) ≥ 0, ∀y ∈ C
Vậy bài toán tối ưu trên là một trường hợp riêng của bài toán (EP ).
1.1.2
Bài toán điểm bất động Brouwer
Giả sử C ⊂ H là một tập lồi compact khác rỗng và ánh xạ đơn trị F : C →
C . Khi đó bài toán điểm bất động có dạng sau:
Tìm x∗ ∈ C sao cho x∗ = F (x∗ ).
Đặt
f (x, y) = hx − F (x), y − xi , ∀x, y ∈ C.
Khi đó bài toán (F P ) trở thành bài toán cân bằng (EP ).
(FP)
4
Tổng quát hơn, bài toán điểm bất động của ánh xạ đa trị (M F P ) là bài toán:
Tìm x∗ ∈ C sao cho x∗ ∈ F (x∗ ),
với F : C → 2C là ánh xạ đa trị có giá trị lồi compact khác rỗng.
Khi đó, x∗ ∈ C là nghiệm của bài toán (M F P ) khi và chỉ khi x∗ là
nghiệm của bài toán cân bằng (EP ).
1.1.3
Bài toán bất đẳng thức biến phân tổng quát
n
Cho T : C → 2R là ánh xạ nửa liên tục sao cho T (x) là tập compact, lồi
∀x ∈ C . Khi đó, bài toán bất đẳng thức biến phân tổng quát được phát biểu
như sau:
Tìm x∗ ∈ C, ξ ∗ ∈ T (x) sao cho hξ ∗ , y − xi ≥ 0, ∀y ∈ C.
(1.1)
Nếu ta đặt
f (x, y) := max hξ, y − xi , ∀x, y ∈ C
ξ∈T (x)
thì bài toán cân bằng (EP ) tương đương với bài toán bất đẳng thức biến phân
tổng quát.
Thật vậy, vì x∗ ∈ C là nghiệm của bài toán (1.1) nên ta có:
hξ ∗ , y − x∗ i ≥ 0, ∀y ∈ C, ξ ∗ ∈ T (x∗ ).
Mặt khác theo cách đặt ta được:
f (x∗ , y) = ∗max∗ hξ ∗ , y − x∗ i ≥ 0, ∀y ∈ C.
ξ ∈T (x )
Vậy x∗ ∈ C là nghiệm của bài toán (EP ). Ngược lại, cho x∗ ∈ C là nghiệm
của bài toán (EP ), nghĩa là
5
f (x∗ , y) ≥ 0, ∀y ∈ C.
Theo cách đặt ta có:
f (x∗ , y) = ∗max∗ hξ ∗ , y − x∗ i ≥ 0, ∀y ∈ C.
ξ ∈T (x )
Vậy x∗ ∈ C là nghiệm của bài toán (1.1). Nếu T là ánh xạ đơn trị thì bài toán
bất đẳng thức biến phân tổng quát là bài toán bất đẳng thức biến phân sau:
Tìm x∗ ∈ C sao cho hT (x∗ ) , y − x∗ i ≥ 0, ∀y ∈ C.
(1.2)
Nếu ta đặt f (x, y) := hT (x), y − xi , ∀x, y ∈ C thì với cách lập luận tương
như trên bài toán (1.2) tương đương với bài toán cân bằng (EP ).
1.1.4
Bài toán cân bằng Nash
(i) Cho I = {1, 2, ..., p} là tập chỉ số hữu hạn (tập p-người chơi);
(ii) Ki là tập lồi khác rỗng của Rni (tập chiến lược của người chơi thứ i);
(iii) Hàm fi : K1 × .... × Kp → R cho trước (hàm tổn thất của người chơi
thứ i khi vi phạm, chiến lược của người chơi ∀i ∈ I ).
Cho x = (x1 , x2 , ..., xp ) ∈ K1 × .... × Kp và y = (y1 , y2 , ..., yp ) ∈ K1 ×
.... × Kp . Ta định nghĩa vectơ x [yi ] ∈ K1 × .... × Kp như sau:
xj ∀j 6= i
x [yi ]j =
y ∀j = i
j
đặt K = K1 × .... × Kp .
Khi đó, bài toán cân bằng Nash được phát biểu như sau:
Tìm x∗ ∈ K sao cho fi (x∗ ) ≤ fi (x∗ [yj ]) , ∀i ∈ I, ∀y ∈ K
(1.3)
6
Điểm thỏa mãn (1.3) gọi là điểm cân bằng Nash. Về ý nghĩa kinh tế, điểm cân
bằng Nash nói lên rằng bất kỳ đối thủ nào chọn phương án ra khỏi điểm cân
bằng trong khi các đối thủ còn lại vẫn giữ phương án điểm cân bằng thì đối thủ
ra khỏi điểm cân bằng sẽ bị thua thiệt.
Nếu ta đặt f : K × K → R là hàm số xác định bởi
f (x, y) :=
p
P
(fi (x [yi ]) − fi (x))
i=1
với mọi ∀x, y ∈ K , thì bài toán cân bằng Nash (1.3) tương đương với bài toán
cân bằng (EP).
Thật vậy, giả sử x∗ ∈ K là nghiệm của bài toán cân bằng (1.3), khi đó
fi (x∗ ) ≤ fi (x∗ [yi ]) , ∀i ∈ I, ∀yi ∈ Ki
⇔ fi (x∗ [yi ]) −fi (x∗ ) ≥ 0, ∀i ∈ I, ∀yi ∈ Ki
p
P
⇔
(fi (x∗ [yi ]) −fi (x∗ )) ≥ 0, ∀y ∈ K.
i=1
Theo định nghĩa của f , ta có
f (x∗ , y) ≥ 0, ∀y ∈ K.
Vậy x∗ ∈ K là nghiệm của (EP)
Ngược lại, giả sử x∗ ∈ K là nghiệm của (EP) nhưng không là nghiệm của
(1.3). Khi đó, ta có:
f (x∗ , y) ≥ 0, ∀y ∈ K.
Theo định nghĩa của f , ta có:
n
P
(fi (x∗ [yi ]) −fi (x∗ )) ≥ 0, ∀y ∈ K.
i=1
Vì x∗ ∈ K không là nghiệm của (1.3), nên tồn tại i0 ∈ I sao cho
7
fi0 (x∗ ) > fi0 (x∗ [yi ]) , ∀yi ∈ Ki .
Lấy x∗ [yi ] = x∗ , ∀j 6= i0 , ta có
fi0 (x∗ ) = fi0 (x∗ [yi ]) , ∀j 6= i0 .
Kết hợp với hai điều kiện trên ta suy ra rằng
n
P
(fi (x∗ [yi ]) −fi (x∗ )) < 0, ∀y ∈ K.
i=1
Điều này mâu thuẫn với giả thiết.
Vậy x∗ ∈ K là nghiệm của bài toán (1.3).
1.2
Định nghĩa về tính đơn điệu, giả đơn điệu mạnh của
song hàm
Ta ký hiệu PC - toán tử chiếu theo chuẩn lên tập C lồi đóng, tức là:
PC (x) ∈ C : kx − PC (x)k ≤ kx − yk , ∀y ∈ C.
Bổ đề 1.1. Giả sử C là một tập lồi đóng khác rỗng trong H.
(i) PC (x) là duy nhất và được xác định với mọi x;
(ii) π=PC (x) khi và chỉ khi hx − π, y − πi ≤ 0, ∀y ∈ C;
(iii) kPC (x) − PC (y)k2 ≤ kx − yk2 − kPC (x) − x + y − PC (y)k2 , ∀x, y ∈ C.
Định nghĩa 1.1. Một song hàm f : C × C → R được gọi là
(i) Đơn điệu mạnh trên C với hệ số β > 0 nếu
f (x, y) + f (y, x) ≤ −βky − xk2 , ∀x, y ∈ C;
(ii) Đơn điệu trên C nếu
8
f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C;
(iii) Giả đơn điệu mạnh trên C với hệ số β > 0 nếu
f (x, y) ≥ 0 ⇒ f (y, x) ≤ −βky − xk2 , ∀x, y ∈ C;
(iv) Giả đơn điệu trên C nếu
f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C.
Chú ý rằng một song hàm giả đơn điệu mạnh có thể không đơn điệu
Từ định nghĩa cho thấy (i) ⇒ (ii) ⇒ (iv) và (i) ⇒ (iii) ⇒ (iv) nhưng
không có sự liên hệ giữa (ii) và (iii). Ngoài ra, nếu f là đơn điệu mạnh (tương
ứng giả đơn điệu) với hệ số β > 0, thì nó là đơn điệu mạnh (tương ứng giả đơn
điệu) với hệ số β 0 cho mọi 0 < β 0 ≤ β
Sau đây là một ví dụ cho song hàm giả đơn điệu mạnh. Giả sử
f (x, y) := (R − kxk) g (x, y) , Br := {x ∈ H : kxk ≤ r} ,
khi g là một đơn điệu mạnh trên Br với hệ số β > 0, ví dụ g (x, y) =
hx, y − xi , và R > r > 0. Ta thấy rằng f là giả đơn điệu mạnh trên Br .
Thực vậy, giả sử rằng f (x, y) ≥ 0, từ x ∈ Br ta có g (x, y) ≥ 0. Với hàm
g , β - đơn điệu mạnh trên Br , g (x, y) ≤ −βkx − yk2 , ∀x, y ∈ Cr .
Từ định nghĩa của f và y ∈ Br kéo theo
f (y, x) = (R − kyk) g (y, x) ≤ −β (R − kyk) kx − yk2 ≤
−β (R − r) kx − yk2 .
Vì vậy f là đơn điệu mạnh trên Br với hệ số β (R − r) .
Giả thiết sau đây sẽ được sử dụng cho song hàm f : C × C → R
(A1) f (., y) là nửa liên tục trên C cho mỗi y ∈ C;
9
(A2) f (x, .) là đóng, lồi và dưới khả vi trên C cho mỗi x ∈ C;
(A2a) f (x, .) là đóng, lồi trên C cho mỗi x ∈ C.
Điều kiện kiểu Lipschitz sau đây sẽ được sử dụng ở phần tiếp theo.
∃L1 , L2 : f (x, y) + f (y, z) ≥ f (x, z) − L1 kx − yk2 −
− L2 ky − zk2 , ∀x, y, z ∈ C. (1.4)
Rõ ràng với bài toán cực tiểu minx∈cϕ(x) , song hàm f (x, y) := ϕ (y) − ϕ (x)
có tính chất (1.4) với hàm ϕ bất kỳ được định nghĩa trên C .
Với F : C → H, cho bất đẳng thức biến phân
f (x, y) := hF (x) , y − xi
nếu F là Lipschitz trên C với hằng số L > 0, thì cho một số bất kỳ µ > 0 ta có
f (x, y) + f (y, z) ≥ f (x, z) −
Lµ
2 kx
f thỏa mãn điều kiện Lipschitz với L1 =
1.3
L
− yk2 − 2µ
ky − zk2 , ∀x, y, z ∈ C,
Lµ
2
và L2 =
L
2µ .
Sự tồn tại nghiệm của bài toán cân bằng
Bổ đề 1.2. Giả sử f : C × C → R ∪ {∞} là một song hàm cân bằng sao cho
f (., y) là bán liên tục trên với mỗi y ∈ C và f (x, .) là lồi với mọi x ∈ C . Nếu
ít nhất một trong những giả thiết dưới đây thỏa mãn:
(i) C là compact;
(ii) Tồn tại một tập hợp W compact khác rỗng sao cho mỗi x ∈ C\W có
một y ∈ C ∩ W với f (x, y) < 0;
thì bài toán cân bằng (EP) có một nghiệm.
10
Trong những kết quả dưới đây, chúng ta cần các điều kiện về song hàm f :
(A1 ) với mỗi x ∈ C, y ∈ C , hàm f (x, .) lồi chính thường (không nhất
thiết khả dưới vi phân) và hàm f (., y) là nửa liên tục trên C .
(A2 ) f là β - giả đơn điệu mạnh trên C .
Kết quả sau đây nói về sự tồn tại nghiệm của bài toán cân bằng giả đơn điệu
mạnh.
Định lí 1.1. Giả sử rằng f là giả đơn điệu mạnh trên C , khi đó dưới giả thiết
(A1 ), (A2 ) bài toán (EP ) có một nghiệm duy nhất.
Chứng minh. Theo Bổ đề 1.2 ta chỉ cần chứng minh điều kiện bức sau đây:
Tồn tại hình cầu đóng B sao cho:
(∀x ∈ C\B, ∃y ∈ C ∩ B : f (x, y) < 0).
(C0)
Thực vậy, nếu trái lại, với mọi hình cầu đóng Br bao O với bán kính r, có
xr ∈ C\Br sao cho f (x, y) ≥ 0, ∀y ∈ C ∩ Br .
Cố định r0 > 0, thì với mọi r > r0 , có tồn tại xr ∈ C\Br sao cho
f xr , y 0 ≥ 0 với y 0 ∈ C ∩ Br .
Do đó, từ f là β - giả đơn điệu mạnh, chúng ta có:
2
f y 0 , xr + β
xr − y 0
≤ 0, ∀r
(1.5)
Mặt khác, do f y 0 , . là lồi chính thường, tồn tại x0 ∈ C sao cho ∂2 f y 0 , x0 6=
φ, tại x0 .
Lấy w∗ ∈ ∂2 f y 0 , x0 , theo định nghĩa của dưới vi phân ta có:
∗
w , x − x0 + f y 0 , x0 ≤ f y 0 , x , ∀x.
11
Với x = xr ta được:
f (y 0 , xr ) + βkxr − y 0 k2 ≥ f (y 0 , x0 ) + w∗ , xr − x0 + βkxr − y 0 k2
≥ f (y 0 , x0 ) − kw∗ kkxr − x0 | + βkxr − y 0 k2 .
2
Do r → ∞, từ kxr k → ∞, ta thu được f y 0 , xr + β
xr − y 0
→ ∞,
mâu thuẫn với (1.5). Vì vậy điều kiện bức (C0) phải đúng. Theo Bổ đề 1.2, bài
toán (EP ) có nghiệm.
Toán tử F : C → H là được gọi là giả đơn điệu mạnh trên C với hệ số
β > 0, nếu:
hF (x) , y − xi ≥ 0 ⇒ hF (y) , y − xi ≥ βky − xk2 , ∀x, y ∈ C.
Ta áp dụng định lý trên với bất đẳng thức biến phân
Tìm x∗ ∈ C : hF (x∗ ) , y − x∗ i ≥ 0 , ∀y ∈ C,
(VI)
Định nghĩa song hàm f theo công thức
f (x, y) := hF (x), y − xi
(1.6)
Rõ ràng x∗ là một nghiệm của (1.6) khi và chỉ khi nó là một nghiệm của bài
toán (EP) với f xác định bởi (1.6).
Khi đó f là giả đơn điệu mạnh nếu F là giả đơn điệu mạnh.
Thật vậy, giả sử f (x, y) ≥ 0 theo (1.6), ta có
hF (x) , y − xi ≥ 0
nhưng do F là β− đơn điệu mạnh nên
hF (y) , x − yi ≤ −βky − xk2
Theo (1.6) thì f (x, y) = hF (y) , x − yi .
12
Hệ quả 1.1. Giả sử rằng F là liên tục và giả đơn điệu mạnh trên C. Khi đó bài
toán bất đẳng thức biến phân (VI) có một nghiệm duy nhất.
13
Chương 2
Thuật toán chiếu giải bài toán cân bằng giả
đơn điệu mạnh
Trong chương này chúng ta trình bày thuật toán chiếu cho bài toán cân bằng
giả đơn điệu mạnh, đặc biệt là ba thuật toán và tốc độ hội tụ của chúng:
Thuật toán 1: Thuật toán tuyến tính hội tụ yêu cầu biết được hệ số Lipschitz
của song hàm.
Thuật toán 2: Thuật toán không cần biết hằng số Lipschitz.
Thuật toán 3: Thuật toán không có điều kiện Lipschitz.
Các kiến thức trong chương này chủ yếu được tham khảo ở trong các tài liệu
[3], [4], [6], [7].
2.1
Thuật toán chiếu cho bài toán cân bằng giả đơn điệu
mạnh
Cho ε ≥ 0, chúng ta gọi một điểm xε ∈ C một ε - nghiệm tới bài toán (EP).
Nếu f (xε , y) ≥ −ε cho mọi y ∈ C . Bổ đề sau sẽ được sử dụng trong phần
chứng minh của định lý hội tụ dưới đây.
Bổ đề 2.1. Giả sử rằng {ak }∞
k=0 là một dãy vô hạn các số dương thỏa mãn:
ak+1 ≤ ak + ξk ∀k,
14
với
P∞
k=0 ξk
< ∞. Khi đó dãy {ak } là hội tụ.
Thuật toán
Bước 1. (Chọn một điểm xuất phát và độ dài bước). Lấy x1 ∈ C , chọn sai
số ε > 0 và một dãy các số dương {σk } sao cho
∞
X
σk = ∞,
k=1
∞
X
σk2 < +∞.
(2.1)
k=1
Bước 2. (Tìm một hướng chuyển động) Tìm g k ∈ H sao cho
f xk , y + g k , xk − y ≥ −σk , ∀y ∈ C.
(2.2)
a) Nếu g k = 0 và σk ≤ ε, kết thúc: xk là 1 ε - nghiệm;
b) Chuyển qua bước 3.
Bước 3. (Phép chiếu) Lấy xk+1 := PC xk − σk g k và quay trở lại Bước 2
với k được thay bởi k + 1.
Định lí 2.1. Giả sử rằng giả thiết (A1 ) và (A2 ) là thỏa mãn. Khi đó ta có:
(i) Nếu thuật toán kết thúc ở Bước 2, thì xk là một ε - nghiệm và
k+1
2
2
2
x
− x∗
≤ (1 − 2βσk )
xk − x∗
+ 2σk2 + σk2
g k
, ∀k;
(2.3)
(ii) Nếu thuật toán không kết thúc và g k giới nội thì dãy xk hội tụ mạnh
tới nghiệm duy nhất x∗ của (EP ).
Chứng minh. (i) Nếu thuật toán kết thúc ở Bước 2, thì g k = 0 và σk ≤ ε.
Khi đó, từ (2.2), f xk , y ≥ −σk ≥ −ε với ∀y ∈ C . Như vậy, xk là một ε nghiệm.
Từ xk+1 = PC xk − σk g k , ta có
k+1
2
2
x
− x∗
≤
xk − σk g k − x∗
15
2
2
=
xk − x∗
− 2σk g k , xk − x∗ + σk2
g k
.
(2.4)
Áp dụng (2.2) với y = x∗ ta thu được:
f xk , x∗ + g k , xk − x∗ ≥ −σk ;
điều này kéo theo:
− g k , xk − x∗ ≤ f xk , x∗ + σk .
(2.5)
Khi đó từ (2.4) ta được:
k+1
2
2
2
x
− x∗
≤
xk − x∗
+ 2σk f xk , x∗ + σk + σk2
g k
.
(2.6)
Do x∗ là nghiệm, f xk , x∗ ≥ 0, nên theo tính chất β− giả đơn điệu mạnh của
f ta có:
2
f xk , x∗ ≤ −β
xk − x∗
.
Kết hợp bất đẳng thức cuối cùng với (2.6) chúng ta thu được:
k+1
2
2
2
x
− x∗
≤
xk − x∗
− 2βσk kxk − x∗ k2 + 2σk2 + σk2
g k
2
= (1 − 2βσk ) kxk − x∗ k2 +2σk2 + σk2
g k
.
(2.7)
(ii) Giả sử rằng bây giờ thuật toán không kết thúc và dãy g k là bị chặn. Vậy
có một số thực c sao cho
g k
≤ c < ∞, ∀k. Thì (2.7) có thể viết như sau:
k+1
2
x
− x∗
≤ (1 − 2βσk ) kxk − x∗ k2 +c0 σk2
=kxk − x∗ k2 − λk kxk − x∗ k2 + c0 σk2 ,
(2.8)
P
2
đặt λk := 2βσk , c0 := 2 + c. Từ ∞
k=1 σk < ∞, nên theo Bổ đề 2.1.1, dãy
n
o
xk − x∗
2 hội tụ. Lấy tổng theo bất đẳng thức (2.8) từ 1 tới k + 1 ta được:
k
k
X
X
k+1
1
j
∗
2
∗
2
∗
2
x
−x
≤ x −x
−
λj x − x
+ c0
σj2 ,
j=2
j=2