ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————–
NGÔ DUY TOẢN
THUẬT TOÁN TÁCH LIONS-MERCIER VÀ
PHƯƠNG PHÁP LUÂN HƯỚNG TÌM KHÔNG ĐIỂM CỦA TỔNG HAI TOÁN TỬ ĐƠN ĐIỆU
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2016
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————–
NGÔ DUY TOẢN
THUẬT TOÁN TÁCH LIONS-MERCIER VÀ PHƯƠNG PHÁP LUÂN HƯỚNG TÌM KHÔNG ĐIỂM CỦA TỔNG HAI TOÁN TỬ ĐƠN ĐIỆU
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12
GIÁO VIÊN HƯỚNG DẪN GS.TS. NGUYỄN BƯỜNG
THÁI NGUYÊN - 2016
i
Mục lục
Bảng ký hiệu ii
Mở đầu 1
Chương 1. Không gian Hilbert và toán tử đơn điệu cực đại 3
1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . . 1.2 Toán tử đơn điệu cực đại . . . . . . . . . . . . . . . . . . . . 3 8
Chương 2. Thuật toán tách Lions–Mercier và phương pháp luân hướng tìm không điểm của tổng hai toán tử đơn điệu
cực đại 16
2.1 Phương pháp tách . . . . . . . . . . . . . . . . . . . . . . . 16 2.1.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . . . 16
2.1.2 Triển khai phương pháp . . . . . . . . . . . . . . . . 20 2.2 Mối quan hệ của phương pháp ngược từng phần . . . . . . 24 2.2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.2 Mối quan hệ với thuật toán tách Lions–Mercier . . . 26 2.3 Phương pháp luân hướng . . . . . . . . . . . . . . . . . . . . 27 2.3.1 Nguồn gốc của phương pháp luân hướng . . . . . . . 27
2.3.2 Mối liên hệ với phương pháp tách . . . . . . . . . . . 28
Kết luận 32
Tài liệu tham khảo 33
ii
Bảng 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
trong bảng dưới đây:
tập số thực
không gian véc tơ n, m chiều tương ứng không gian Hilbert thực không gian liên hợp của H
R Rn, Rm H H∗ C[a, b] conv C tập các hàm thực lien tục trên [a, b] bao lồi của tập C
conv C A∗ A bao lồi đóng của tập C toán tử liên hợp của toán tử A toán tử mở rộng của toán tử A
dom A gra A domf miền xác định của toán tử A đồ thị của toán tử A miền hữu hiệu của hàm f
tập trên đồ thị của hàm f tập tất cả không điểm của A, A−1(0) toán tử giải của toán tử T
hình nón chuẩn tắc ứng với tập lồi C tập rỗng hàm chỉ trên C
epif zer(A) Jr,T NC ∅ δC(.) V ⊥ bù vuông góc của không gian con V
1
Mở đầu
Cho A và B là hai toán tử đơn điệu cực đại trong không gian Hilbert
H, C := A + B. Nội dung của đề tài luận văn nghiên cứu bài toán tìm không điểm của toán tử C trên cơ sở kết quả của J. Eckstein [4].
Để giải bài toán này, J. Eckstein [4] đưa vào toán tử đơn điệu cực đại Sλ,A,B mà tập không điểm của nó xấp xỉ tập không điểm của A + B. Trong trường hợp B là nón chuẩn tắc của một không gian con tuyến tính thì Sλ,A,B trùng với ngược từng phần của toán tử Spingarn (xem [12], [13]). Ngoài ra, khi r = 1 thì toán tử giải (I + rSλ,A,B)−1 của Sλ,A,B là toán tử G(λ) của Lions–Mercier [6]. Vì vậy, thuật toán Lions–Mercier thực sự là thuật toán điểm gần kề ứng dụng cho toán tử Sλ,A,B. Ngoài ra, J. Eckstein [4] cũng chỉ ra rằng kỹ thuật của Spingarn cho cực tiểu phiếm hàm lồi trên không gian con tuyến tính thực chất là một trường hợp riêng trong cách tiếp cận của Lions–Mercier. Đồng thời thuật toán Lions–Mercier mở rộng
thuật toán luân hướng trong qui hoạch lồi đã được chỉ ra bởi Gabay [5] và thuật toán luân hướng cũng là một ví dụ của thuật toán điểm gần kề.
Mục đích của đề tài luận văn là trình bày lại kết quả của J. Eckstein [4]
về mối quan hệ giữa một số thuật toán tìm không điểm của toán tử đơn điệu cực đại: thuật toán điểm gần kề được đưa ra bởi Martinet [7], sau đó được phát triển bởi Rockafellar [10]; phương pháp Lions–Mercier tìm
không điểm của tổng hai toán tử đơn điệu cực đại [6]; phương pháp ngược từng phần của Spingarn cho toán tử đơn điệu cực đại [12], [13]. Nội dung của đề tài luận văn được viết trong hai chương:
Chương 1: "Không gian Hilbert và toán tử đơn điệu cực đại". Chương này giới thiệu về không gian Hilbert trên trường số thực và một số kiến
2
thức cơ bản về giải tích lồi. Tiếp theo là giới thiệu về toán tử đơn điệu cực đại và định nghĩa bài toán tìm không điểm của toán tử.
Chương 2: "Thuật toán tách Lions–Mercier và phương pháp luân hướng
tìm không điểm của tổng hai toán tử đơn điệu cực đại". Chương này nghiên cứu một số phương pháp tìm không điểm của tổng hai toán tử đơn điệu cực đại, chỉ ra phương pháp Lion–Mercier thực chất là trường hợp đặc biệt
của thuật toán điểm gần kề, đồng thời nêu nguồn gốc của phương pháp luân hướng và đưa ra mối quan hệ với thuật toán tách.
Luận văn này được hoàn thành tại Trường Đại học Khoa học - Đại học
Thái Nguyên dưới sự hướng dẫn tận tình của GS. TS. Nguyễn Bường, tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy, người đã người dành nhiều thời gian và tâm huyết để hướng dẫn tận tình, giúp đỡ tôi trong quá trình
học tập, nghiên cứu và viết bản luận văn này.
Tôi cũng xin chân thành cảm ơn Lãnh đạo Trường Đại học Khoa học – Đại học Thái Nguyên, Ban chủ nhiệm khoa Toán – Tin cùng toàn thể các
thầy cô trong và ngoài trường đã giảng dạy giúp tác giả trau dồi thêm rất nhiều kiến thức phục vụ cho việc học tập và nghiên cứu của bản thân. Tác giả xin gửi lời cảm ơn chân thành đến các thầy cô.
Cuối cùng tác giả xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tác giả trong quá trình học tập, nghiên cứu và làm luận văn.
Xin chân thành cảm ơn!
Thái Nguyên, tháng 6 năm 2016
Học viên
Ngô Duy Toản
3
Chương 1
Không gian Hilbert và toán tử đơn
điệu cực đại
Chương này trình bày một số khái niệm và tính chất cơ bản của không gian Hilbert thực H, giới thiệu về toán tử đơn điệu cực đại, định nghĩa
không điểm để phục vụ cho chương sau. Các kiến thức của chương được tổng hợp từ tài liệu [7], [10].
1.1 Không gian Hilbert
Định nghĩa 1.1.1 Cho H là không gian tuyến tính xác định trên trường số thực R. Một tích vô hướng trong H là một ánh xạ h·, ·i : H × H → R
thỏa mãn các tính chất sau:
i. hx, xi ≥ 0, ∀x ∈ H và hx, xi = 0 khi và chỉ khi x = 0,
ii. hx, yi = hy, xi , ∀x, y ∈ H,
iii. hx + y, zi = hx, zi + hy, zi , ∀x, y, z ∈ H,
iv. hαx, yi = α hx, yi , ∀x, y ∈ H, ∀α ∈ R.
Số thực hx, yi được gọi là tích vô hướng của hai véctơ x và y. Cặp (H, h·, ·i) gọi là không gian tiền Hilbert.
Định lý 1.1.2 (Bất đẳng thức Cauchy–Schwarz) Trong không gian tiền Hilbert H, ∀x, y ∈ H ta luôn có bất đẳng thức sau:
|hx, yi|2 ≤ hx, xi.hy, yi.
4
Chứng minh. Với y = 0 bất đẳng thức hiển nhiên đúng.
Giả sử y 6= 0 khi đó ∀λ ∈ R ta có:
hx + λy, x + λyi > 0,
nghĩa là
hx, xi + λhy, xi + λhx, yi + |λ|2hy, yi > 0.
ta được hx, xi− > 0 hay |hx, yi|2 ≤ hx, xi.hy, yi. Chọn λ = − hx, yi hy, yi |hx, yi|2 hy, yi
(cid:3) Bất đẳng thức được chứng minh.
Dấu bằng trong bất đẳng thức Schwarz xảy ra khi và chỉ khi x và y
phụ thuộc tuyến tính. Mối quan hệ giữa khái niệm chuẩn và tích vô hướng được thể hiện qua nhận xét sau:
Nhận xét 1.1.3 Mọi không gian tiền Hilbert H là không gian tuyến tính định chuẩn, với chuẩn được xác định:
hx, xi, x ∈ H. kxk =
p Bất đẳng thức Schwarz được viết lại:
|hx, yi| ≤ kxk.kyk.
Định nghĩa 1.1.4 Cho X là không gian định chuẩn, dãy {xn} ⊂ X gọi là dãy cơ bản nếu:
kxn − xmk = 0. lim m,n→∞
Nếu trong X mọi dãy cơ bản đều hội tụ, tức là kxn − xmk → 0 kéo theo sự tồn tại x0 ∈ X sao cho xn → x0 thì X được gọi là không gian đủ.
n
Định nghĩa 1.1.5 Không gian tiền Hilbert đầy đủ gọi là không gian Hilbert.
k=1 P
Ví dụ 1.1.6 Trong Rn, x = (x1, x2..., xn) , y = (y1, y2..., yn) ∈ Rn, ta đưa vào tích vô hướng hx, yi = xkyk
5
n
n
do đó
kxk2 = hx, xi = |xk|2. xkxk =
Xk=1 Xk=1
Khi đó Rn là không gian Hilbert.
b
Ví dụ 1.1.7 Trong không gian C[a, b] tập tất cả các hàm thực liên tục trên [a, b]. Xét tích vô hướng:
hx, yi = x(t)y(t)dt, x(t), y(t) ∈ C[a, b].
Za
Khi đó:
|x(t)| là không gian Banach i. Không gian C[a,b] với chuẩn kxk = max a6t6b
1/2
b
nên C[a, b] là không gian Hilbert;
a R
không là không ii. Không gian C[a,b] với chuẩn kxk = |x(t)|2dt !
gian Banach do đó C[a, b] không là không gian Hilbert.
Định nghĩa 1.1.8 Tập A ⊂ H gọi là tập lồi nếu ∀x1, x2 ∈ A và mọi số thực t ∈ [0, 1] ta đều có
tx1 + (1 − t)x2 ∈ A.
Nhận xét 1.1.9 Theo định nghĩa, tập ∅ là tập lồi.
Ví dụ 1.1.10 Các tập sau đây đều là tập lồi: Rn, ∅, {x} , hình cầu đóng, hình cầu mở, các nửa không gian đóng, nửa không gian mở.
Định nghĩa 1.1.11 Cho C ⊂ H. Bao lồi của C là giao của tất cả các tập con lồi của H chứa C, ký hiệu là conv C. Bao lồi đóng của C là tập con lồi đóng nhỏ nhất của H chứa C, ký hiệu là conv C.
Định nghĩa 1.1.12 Tập A ⊆ Rn được gọi là nón có đỉnh tại gốc O nếu:
∀x ∈ A, ∀λ > 0 ⇒ λx ∈ A.
6
A ⊆ Rn được gọi là nón có đỉnh tại x0 nếu A − x0 có đỉnh tại O. Nón A gọi là nón lồi nếu tập A là lồi.
Định nghĩa 1.1.13 Cho tập lồi S ⊆ Rn, hàm f : S → (−∞, +∞) được gọi là:
i. Hàm lồi trên S nếu với mọi số thực 0 ≤ λ ≤ 1, ∀x, y ∈ S, ta có:
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y);
ii. Hàm lồi chặt trên S nếu với mọi số thực 0 ≤ λ ≤ 1, ∀x, y ∈ S, x 6= y
ta có:
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y);
iii. Hàm f được gọi là hàm lõm (lõm chặt) trên S nếu −f là lồi (lồi chặt)
trên S;
iv. Hàm f được gọi là tuyến tính afin trên S nếu f vừa lồi vừa lõm trên S. Một hàm afin trên Rn có dạng f (x) = ha, xi + α với a ∈ Rn, như vậy ∀x, y ∈ Rn, ∀λ ∈ [0, 1] ta có:
f (λx + (1 − λ)y) = λf (x) + (1 − λ)f (y).
Tuy nhiên, hàm afin không lồi chặt hay lõm chặt.
Nếu H là không gian Hilbert thì H cũng là không gian định chuẩn, không gian liên hợp của H là H∗ = L(H, K). Định lý sau đây nêu lên đặc trưng của phiếm hàm tuyến tính liên tục trên không gian Hilbert H.
Định lý 1.1.14 Với mỗi véctơ a cố định thuộc không gian Hilbert H, hệ thức:
∀x ∈ H f (x) = hx, ai, (1.1)
xác định một phiếm hàm tuyến tính liên tục f (x) trên không gian Hilbert
7
H với
kf (x)k = kak. (1.2)
Ngược lại với bất kì phiếm hàm tuyến tính liên tục f (x) nào trên không
gian Hilbert H cũng đều có thể biểu diễn một cách duy nhất dưới dạng (1.1), trong đó a là một véctơ của H thỏa mãn (1.2).
Định lý 1.1.14 cho phép thiết lập tương ứng một - một giữa các phiếm hàm tuyến tính liên tục f trên H và các véctơ a ∈ H. tương ứng đó là phép đẳng cự tuyến tính, cho nên nếu ta đồng nhất phiếm hàm f với véctơ a
sinh ra nó thì không gian Hilbert H có thể đồng nhất được với không gian liên hợp H∗ của nó.
Cho A là toán tử tuyến tính liên tục trên không gian Hilbert H, với mỗi
y ∈ H cố định ta xét phiếm hàm x∗ : H → R xác định như sau:
∀x ∈ H. x∗(x) = hAx, yi,
Dễ thấy x∗ là phiếm hàm tuyến tính, liên tục trên H nên theo Định lý 1.1.14 về dạng tổng quát của phiếm hàm tuyến tính liên tục, tồn tại duy nhất y∗ ∈ H để:
∀x ∈ H. hAx, yi = hx, y∗i,
Định nghĩa 1.1.15 Cho A là toán tử trong không gian Hilbert H, ánh xạ A∗ : H → H được xác định như sau:
A∗y = y∗, ∀y ∈ H
trong đó
hAx, yi = hx, y∗i = hx, A∗yi.
Được gọi là toán tử liên hợp của toán tử A.
Nhận xét 1.1.16 Toán tử liên hợp A∗ nếu tồn tại là duy nhất.
Định nghĩa 1.1.17 Dãy (xn)n ∈ H được gọi là:
8
i. Hội tụ mạnh đến x0 ∈ H nếu nó hội tụ theo chuẩn, tức là:
kxn − x0k = 0, lim n→∞
xn = x0; kí hiệu xn → x0 hay lim n→∞
ii. Hội tụ yếu đến x ∈ H nếu ∀y ∈ H ta có:
hxn, yi = hx, yi, lim n→∞
kí hiệu xn ⇀ x khi n → ∞.
Định nghĩa 1.1.18 Hàm f xác định trên tập lồi C ⊂ Rn được gọi là lồi mạnh, nếu với ∀x, y ∈ C, ∀λ ∈ [0, 1], tồn tại hệ số t > 0, t ∈ R, ta có:
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − λ(1 − λ)tkx − yk2.
Định nghĩa 1.1.19 Cho hàm f : S → (−∞, +∞), S ⊂ Rn, các tập: domf = {x ∈ S : f (x) < +∞} gọi là miền hữu hiệu của hàm f ; epif = {(x, α) ∈ S × R : f (x) ≤ α} gọi là tập trên đồ thị của hàm f.
Hàm f là lồi khi và chỉ khi epif là tập lồi.
Định nghĩa 1.1.20 Hàm f được gọi là chính thường (proper), nếu domf 6= ∅ và f (x) > −∞, ∀x ∈ S.
Cho C ⊂ Rn là tập lồi, C 6= ∅. Ta có một số ví dụ về hàm lồi như sau:
hx, xi, x ∈ Rn; i. Hàm chuẩn Euclid : kxk =
p kx − yk. ii. Hàm khoảng cách từ điểm x ∈ Rn tới C : dC(x) = inf y∈C
Định nghĩa 1.1.21 Cho H là không gian Hilbert, X là tập con khác rỗng của H. Khi đó X được gọi là tập compact nếu mọi dãy {xn} ⊂ H đều chứa dãy con hội tụ đến một điểm x0 ∈ X nào đó.
1.2 Toán tử đơn điệu cực đại
Cho hai tập hợp X, Y ta có một số định nghĩa sau.
9
Định nghĩa 1.2.1 Cho X, Y là hai tập con bất kì của không gian Hilbert H, ánh xạ F từ không gian X vào không gian Y là đơn trị nếu ứng với
mỗi phần tử x ∈ X, xác định duy nhất một phần tử F (x) = y ∈ Y và ta kí hiệu là:
F : X → Y.
Ánh xạ F là đa trị từ không gian X vào không gian Y nếu ứng với mỗi
phần tử x ∈ X, thì F (x) là một tập con của không gian Y (có thể là tập rỗng) và ta kí hiệu là:
F : X → 2Y .
Nhận xét 1.2.2 Ánh xạ đơn trị là một trường hợp riêng của ánh xạ đa trị.
Định nghĩa 1.2.3
i. Nếu F là ánh xạ đơn trị thì ánh xạ ngược F −1 : Y → X được định
nghĩa như sau:
F −1(y) = {x ∈ X : F (x) = y},
ii. Nếu F là ánh xạ đa trị thì ánh xạ ngược F −1 : 2Y → X được định
nghĩa như sau:
F −1(y) = {x ∈ X : y ∈ F (x)},
iii. Cho hai ánh xạ T : X → Y và R : Y → Z, hợp của chúng là RT hoặc
R ◦ T là
RT = {(x, z) | ∃y ∈ Y : (x, y) ∈ T, (y, z) ∈ R},
vì vậy
Ry. (RT )x =
[y∈T x
Ví dụ 1.2.4 Xét phương trình đa thức:
an + an−1x + · · · + a1xn−1 + xn = 0, ai ∈ R.
10
Quy tắc cho tương ứng mỗi điểm a ∈ Rn với tập nghiệm của phương trình trên, ký hiệu là F (a) cho ta một ánh xạ đa trị F : Rn → 2C.
Định nghĩa 1.2.5 Nếu Y là không gian véctơ thực, ta có một số các khái niệm sau:
cA = {(x, cy) | (x, y) ∈ A}, ∀c ∈ R, A : X → Y
A + B = {(x, y + z) | (x, y) ∈ A, (x, z) ∈ B}, ∀A, B : X → Y.
Định nghĩa 1.2.6 Một không điểm của A là x ∈ X bất kì sao cho 0 ∈ Ax. Tập tất cả các không điểm của A, được kí hiệu là zer(A).
Định nghĩa 1.2.7 Toán tử A : H → H được gọi là đơn điệu nếu:
hA(x) − A(y), x − yi > 0, ∀x, y ∈ H.
Định nghĩa 1.2.8 Cho toán tử đa trị A : H → 2H. Khi đó:
dom A = {x ∈ H|Ax 6= ∅} là miền xác định của A,
gra A = {(x, u) ∈ H × H|u ∈ Ax} là đồ thị của A.
Toán tử A là đơn điệu nếu:
hx − y, u − vi > 0, ∀(x, u), (y, v) ∈ gra A.
Ví dụ 1.2.9 Cho toán tử đơn trị A xác định trên tập số thực R như sau:
A(x) = x, ∀x ∈ R.
Khi đó, A là toán tử đơn điệu vì với ∀x, y ∈ R ta có:
hA(x) − A(y), x − yi = hx − y, x − yi = (x − y)2 > 0.
Định nghĩa 1.2.10 Toán tử đa trị A : H → 2H được gọi là toán tử đơn điệu cực đại nếu toán tử A là đơn điệu và đồ thị gra A của A không chứa trong đồ thị của toán tử đơn điệu khác trong H.
11
Ví dụ 1.2.11 Xét toán tử Ti : R → 2R, i = 1, 2 cho bởi công thức:
T1(x) = 1 nếu x ≥ 0 ∅ nếu x < 0 (
và
∀x ∈ R. T2(x) = 1,
Dễ thấy T1, T2 đều là các toán tử đơn điệu. Nhưng T1 không phải là toán tử đơn điệu cực đại vì gra T1 chứa thực sự trong gra T2.
Mệnh đề 1.2.12 Cho toán tử đơn điệu A : H → 2H. Khi đó, A là toán tử đơn điệu cực đại khi và chỉ khi ∀(a, b) ∈ H × H, nếu:
hb − u, a − xi > 0, ∀(x, u) ∈ gra A
thì b ∈ A(a).
Chứng minh. Giả sử A là toán tử đơn điệu cực đại mà b /∈ A(a). Ta mở rộng toán tử A thành toán tử A bằng cách:
A(a) = A(a) ∪ {b}.
Suy ra
gra A gra A
′
mâu thuẫn với giả thiết.
′
Ngược lại, giả sử b ∈ A(a). Xét toán tử đơn điệu bất kì A có:
′
. gra A ⊆ gra A
Nếu (a, b) ∈ gra A thì:
′
hb − u, a − xi > 0, ∀(x, u) ∈ gra A,
⊆ gra A. Nghĩa là A là (cid:3) suy ra b ∈ A(a) ⇒ (a, b) ∈ gra A. Nghĩa là gra A toán tử đơn điệu cực đại. Mệnh đề được chứng minh.
12
Nếu A, B là đơn điệu thì A + B là đơn điệu. Tuy nhiên nếu A, B là đơn điệu cực đại thì A + B không phải lúc nào cũng đơn điệu cực đại. Điều kiện để A + B là đơn điệu cực đại là
ri(dom A) ∩ ri(dom B) 6= ∅.
Bổ đề 1.2.13 Cho toán tử đơn điệu A trên H, A là đơn điệu cực đại khi và chỉ khi im(I + A)= H.
Bổ đề 1.2.14 Cho số thực r > 0, A là toán tử trên H. Khi đó zer(A) = zer(rA), và A là đơn điệu (cực đại) khi và chỉ khi rA là đơn điệu (cực đại).
Sau đây là mối tương ứng giữa họ các toán tử đơn điệu cực đại và một
lớp toán tử không giãn chặt có miền xác định trên H.
Định nghĩa 1.2.15 Toán tử K trên H được gọi là không giãn nếu
kx′ − xk >k y′ − y k ∀(x, y), (x′, y′) ∈ K.
Bổ đề 1.2.16 Mọi toán tử không giãn là đơn trị.
Chứng minh. Cho (x, y1), (x, y2) ∈ K, 0 =k x − x k>k y1 − y2 k, suy ra (cid:3) y1 = y2.
Định nghĩa 1.2.17 K là không giãn chặt nếu
hx′ − x, y′ − yi > k y′ − y k2 ∀(x, y), (x′, y′) ∈ K.
Bổ đề 1.2.18 Mọi toán tử không giãn chặt là đơn điệu và không giãn. Vì vậy chúng là đơn trị.
Chứng minh. Cho K là toán tử không giãn chặt. Vì
hx′ − x, y′ − yi > k y′ − y k2 ∀(x, y), (x′, y′) ∈ K,
nên K là đơn điệu.
13
Một khái niệm tương đương về toán tử không giãn chặt được đưa ra
như sau:
k y′ − y k2 6 k x′ − x k2 − k (x′ − y′) − (x − y) k2 ∀(x, y), (x′, y′) ∈ K.
Mối quan hệ tương đương này có thể kiểm tra bằng cách tính toán trực tiếp. Từ dạng này có thể suy ra K là không giãn, và theo Bổ đề 1.2.16 thì (cid:3) K là đơn trị.
Định nghĩa 1.2.19 Bài toán điểm bất động trên K là tìm phần tử x∗ ∈ H sao cho Kx∗ = x∗.
Một lược đồ tự nhiên là phép lặp xk+1 = ⋄Kxk, xuất phát từ điểm x0 nào đó thuộc H. Nếu w là điểm bất động bất kì của K, thì từ Bổ đề 1.2.18
2
ta có
2 6 k xk − w k
2 − k xk+1 − xk k
k xk+1 − w k ∀k > 0.
Suy ra khoảng cách giữa xk và những điểm bất động là không tăng, và k xk+1 − xk k −→ 0. Vì vậy, nếu tồn tại điểm bất động thì dãy xk phải là giới nội. Từ đó, phụ thuộc vào các điều kiện của bài toán đặt ra người ta có thể sử dụng kết luận trên để suy ra tính hội tụ của dãy xk đến điểm bất động của K, thông thường trong tôpô yếu. Trong không gian hữu hạn chiều, sự hội tụ được đảm bảo.
Định nghĩa 1.2.20 Cho toán tử đơn điệu cực đại T và số thực r > 0, ta định nghĩa toán tử giải Jr,T của T là (I + rT )−1.
Mệnh đề 1.2.21 Toán tử T trên H là đơn điệu khi và chỉ khi J1,T = (I + T )−1 là không giãn chặt. T là đơn điệu cực đại khi và chỉ khi (I + T )−1 là không giãn chặt và có miền xác định đầy đủ.
Chứng minh. Ta có
(x, y) ∈ T ⇔ (x + y, x) ∈ (I + T )−1 hx′ − x, y′ − yi > 0 ⇔ hx′ − x + y′ − y, x′ − xi > k x′ − x k2.
14
Suy ra kết luận thứ nhất.
Mặt khác, theo Bổ đề 1.2.13, T là cực đại khi và chỉ khi im(I + T ) = H. Điều này đúng khi và chỉ khi toán tử (I + T )−1 có miền xác định đầy đủ. (cid:3) Điều này xác minh cho kết luận thứ 2.
Hệ quả 1.2.22 Toán tử K là không giãn chặt khi và chỉ khi K −1 − I là đơn điệu. K là không giãn chặt với miền xác định đầy đủ khi và chỉ khi K −1 − I là đơn điệu cực đại.
Hệ quả 1.2.23 Hàm số từ T 7−→ (I + T )−1 là song ánh giữa họ M (H) các toán tử đơn điệu cực đại trên H và họ F (H) các toán tử không giãn chặt trên H.
Hệ quả 1.2.24 Cho T là toán tử đơn điệu cực đại bất kì và số thực r > 0, toán tử giải Jr,T = (I + rT )−1 là không giãn chặt (do đó là đơn trị) và có miền xác định đầy đủ.
Chứng minh. Theo Bổ đề 1.2.14, rT là đơn điệu cực đại do đó (I + rT )−1 (cid:3) là không giãn chặt và có miền xác định đầy đủ.
Bổ đề 1.2.25 Cho toán tử đơn điệu cực đại T , số thực r > 0, và x ∈ H, 0 ∈ T x khi và chỉ khi Jr,T (x) = {x}.
Chứng minh. Bằng cách tính trực tiếp, Jr,T = {(x + ry, x) | (x, y) ∈ T }. Vì vậy
0 ∈ T x ⇔ (x, 0) ∈ T ⇔ (x, x) ∈ Jr,T
(cid:3) vì Jr,T là đơn trị nên phần chứng minh được kết thúc.
Quan sát này đưa ta đến việc xây dựng xấp xỉ không điểm của toán tử
T [7]. Xuất phát ∀r > 0 và x0 ∈ H ta tính
xk+1 = Jr,T (xk) = (I + rT )−1xk.
Rockafellar [10] đã chứng minh và phân tích thuật toán này (gọi là thuật toán điểm gần kề): lấy dãy {rk} các số thực dương, bị chặn dưới bởi 0, x0 ∈ H tùy ý, ta thực hiện phép lặp
15
xk+1 = Jrk,T (xk) = (I + rkT )−1xk.
Mệnh đề 1.2.26 Cho T là toán tử đơn điệu cực đại. Nếu zer(T ) 6= ∅, thì dãy {xk} sinh ra bởi thuật toán điểm gần kề là giới nội và hội tụ yếu đến không điểm của T . Nếu zer(T ) = ∅ thì {xk} không giới nội.
Điều quan trọng cần lưu ý rằng thuật toán bất kì tạo bởi dãy lặp xk+1 = Kxk, ở đây K là toán tử không giãn chặt với miền xác định đầy đủ, có thể xem xét như là một phần ứng dụng của thuật toán điểm gần kề với toán tử đơn điệu cực đại K −1 − I, và {rk} cố định bằng 1.
Bài toán cơ bản ta xét trong chương sau là tìm không điểm của toán tử
đơn điệu A + B, ở đây A và B là toán tử đơn điệu cực đại.
16
Chương 2
Thuật toán tách Lions–Mercier và
phương pháp luân hướng tìm không
điểm của tổng hai toán tử đơn điệu
cực đại
Chương này trình bày thuật toán tách Lions–Mercier và phương pháp
luân hướng tìm không điểm của tổng hai toán tử đơn điệu cực đại. Mục 2.1 mô tả phương pháp tách và cách triển khai phương pháp này. Mục 2.2 giới thiệu phương pháp ngược từng phần và mối liên hệ với phương pháp
tách Lions–Mercier. Mục 2.3 trình bày về phương pháp luân hướng và nêu mối liên hệ với phương pháp tách. Các kiến thức của chương được tổng hợp từ các tài liệu [2]–[13].
2.1 Phương pháp tách
2.1.1 Mô tả phương pháp
Xét bài toán tìm không điểm của tổng hai toán tử đơn điệu cực đại A và B trong không gian Hilbert H. Trong trường hợp đặc biệt A + B là toán
tử đơn điệu cực đại, người ta cũng có thể sử dụng thuật toán điểm gần kề cho A + B. Tuy nhiên điểm cần lưu ý trong trường hợp này là Jr,A+B khó tính toán, cho nên cách tiếp cận này là không thực tế. Thay vào đó ta dùng cách tiếp cận tách ra Jλ,A và Jλ,B, trong đó λ > 0 là một số thực
17
dương nào đó.
Dựa vào phân tích trên thay cho việc tìm không điểm của A + B ta
phân tích tìm (u, b) ∈ B, (v, a) ∈ A sao cho
v = u;
a = −b.
Với mọi số thực λ > 0 ta có hệ phương trình tương đương là
u − v = 0;
v + λa = u − λb.
Một cách để xác định u, b, v và a là tìm không điểm của toán tử
, (v + λb, u − v) | (u, b) ∈ B, (v, a) ∈ A, v + λa = u − λb Sλ,A,B =
o
n và có thể viết dưới dạng
. (v + λb, u − v) | (u, b) ∈ B, (v, λ−1(u − v) − b) ∈ A Sλ,A,B =
n o
Ta gọi Sλ,A,B là thuật toán tách ứng với A và B. Chọn v + λb là phần tử đầu tiên trong cặp của Sλ,A,B. Hơn nữa, ta sẽ thấy trong Mệnh đề 2.1.2, Sλ,A,B là đơn điệu cực đại nếu A và B là đơn điệu cực đại.
Tập không điểm của Sλ,A,B và A + B không phải lúc nào cũng bằng
nhau, nhưng có mối quan hệ mật thiết với nhau. Ta có kết quả sau.
Mệnh đề 2.1.1 Ta luôn có
zer(Sλ,A,B) = {u + λb | b ∈ Bu, −b ∈ Au}
⊆ {u + λb | u ∈ zer(A + B), b ∈ Bu}.
Chứng minh. Cho S = Sλ,A,B và Z = {u + λb | b ∈ Bu, −b ∈ Au}. Ta chỉ ra rằng zer(S) = Z.
18
Thật vậy, lấy z ∈ zer(S). Khi đó tồn tại u, b, v ∈ H sao cho
v + λb = z, u − v = 0, (u, b) ∈ B và (v, λ−1(u − v) − b) ∈ A.
Điều kiện này dẫn đến
u + λb = z, (u, b) ∈ B và (u, −b) ∈ A.
Do đó, z ∈ Z.
Ngược lại, nếu z ∈ Z thì
z = u + λb, b ∈ Bu và − b ∈ Au.
Đặt u = v, ta nhận thấy (z, 0) ∈ S. Cuối cùng, bao hàm thức
b ∈ Bu} Z ⊆ {u + λb | u ∈ zer(A + B),
(cid:3) vì b ∈ Bu và −b ∈ Au dẫn đến u ∈ zer(A + B).
Ký hiệu S = Sλ,A,B.
Mệnh đề 2.1.2 Nếu A và B là hai toán tử đơn điệu cực đại thì S = Sλ,A,B cũng là toán tử đơn điệu cực đại.
Chứng minh. Đầu tiên ta chứng minh S là đơn điệu. Thật vậy, cho u, b, v, u′, b′, v′ ∈ H sao cho
(u, b) ∈ B, (v, λ−1(u − v) − b) ∈ A, (u′, b′) ∈ B, (v′, λ−1(u′ − v′) − b′) ∈ A.
Khi đó
h(v′ + λb′) − (v + λb), (u′ − v′) − (u − v)i
= λh(v′ + λb′) − (v + λb), λ−1(u′ − v′) − b′ − λ−1(u − v) + bi
19
+ λh(v′ + λb′) − (v + λb), b′ − bi
= λh(v′ − v), λ−1(u′ − v′) − b′ − λ−1(u − v) + bi
+ λ2hb′ − b, λ−1(u′ − v′) − b′ − λ−1(u − v) + bi + λhv′ − v, b′ − bi + λ2hb′ − b, b′ − bi = λhv′ − v, λ−1(u′ − v′) − b′ − λ−1(u − v) + bi
+ λhb′ − b, u′ − ui − λhb′ − b, v′ − vi − λ2hb′ − b, b′ − bi + λhv′ − v, b′ − bi + λ2hb′ − b, b′ − bi
= λhv′ − v, λ−1(u′ − v′) − b′ − λ−1(u − v) + bi + λhb′ − b, u′ − ui.
Theo tính chất đơn điệu của hai toán tử A và B, hai số hạng ở dòng cuối cùng là không âm, vì vậy ta nhận được
h(v′ + λb′) − (v + λb), (u′ − v′) − (u − v)i ≥ 0,
vậy S là đơn điệu.
Theo Bổ đề 1.2.13, ta sẽ đi chứng minh im(I + S) = H. Vì A và B là đơn điệu cực đại, nên λA và λB là đơn điệu cực đại, vì vậy im(I + λA) =
im(I + λB) = H. Lấy w ∈ H bất kỳ, khi đó tồn tại u sao cho
u + λb = w và (u, b) ∈ B.
Hơn nữa, tồn tại v sao cho
v + λa = u − λb và (v, a) ∈ A.
Khi đó a = λ−1(u − v) − b, vì vậy ta có thể thay u, b, v vào biểu thức xác định S để nhận được
(I + S)(v + λb) ∋ u − v + v + λb = u + λb = w.
(cid:3) Mệnh đề được chứng minh.
Từ trên, ta thấy có thể xấp xỉ không điểm u của A + B bởi thuật toán điểm gần kề (với dãy số dương bất kỳ {rk} giới nội và bị chặn dưới bởi
20
0) cho Sλ,A,B để nhận được dãy {zk} hội tụ (yếu) đến không điểm z của Sλ,A,B. Vì toán tử giải (I + λB)−1 = Jλ,B được xấp xỉ như một ánh xạ 1 − 1, liên tục Lipschitz, vì vậy dãy {uk} = {Jλ,B(zk)} hội tụ (yếu) đến không điểm u = Jλ,B(z) của A + B. Ta gọi quá trình này là thuật toán tách. Rõ ràng, Sλ,A,B là cực đại nếu A và B là cực đại, ngay cả khi A + B không là cực đại.
2.1.2 Triển khai phương pháp
Để thực hiện thuật toán tách, ta phải tính giá trị của (I + rS)−1 tại
một điểm bất kì. Phần tính toán được xét như sau
(I + rS)−1 = ((1 − r)v + ru + λb, v + λb) | (u, b) ∈ B,
n . (v, λ−1(u − v) − b) ∈ A
o
Vì vậy, để tính (I + rS)−1(z), ta phải tìm (u, b) ∈ B và (v, a) ∈ A sao cho
(1 − r)v + ru + λb = z, a = λ−1(u − v) − b.
Nói cách khác, ta xét bài toán tìm u, v ∈ H sao cho
z − (ru + (1 − r)v) ∈ λB, −z + ((1 + r)u − rv) ∈ λA.
Điều này không làm cho bài toán trở nên dễ dàng hơn. Cụ thể, nó không làm giảm bớt khó khăn so với việc tính Jr,A+B tại điểm z bất kì mà ta đang tránh. Từ so sánh đó, đi tìm (u, b) ∈ B sao cho (u, λ−1(z − u) − b) ∈ A.
Trong thuật toán tách khi cố định r = 1, ta chỉ đi tìm
(u, b) ∈ B sao cho u + λb = z
và
(v, a) ∈ A sao cho v + λa = u − λb.
Những điều kiện (u, b) ∈ B, u + λb = z xác định duy nhất u = Jλ,B(z) và b = λ−1(z − u) độc lập với v. Khi u đã biết thì v xác định duy nhất từ u = Jλ,A(u − λb). Do đó, ta có phân tích trong việc tính J1,S = (I + S)−1
21
được thay thế một cách riêng biệt trong đánh giá của Jλ,A = (I + λA)−1 và Jλ,B = (I + λB)−1. Khi r = 1 thực chất đó là phép phân hoạch. Spingarn [13] cũng đã công nhận sự việc trên, nhưng với điều kiện hạn chế hơn. Không làm mất tính tổng quát, ta giả sử dãy rk = 1 với mọi k, trừ trường hợp đặc biệt để áp dụng cho các thuật toán tách. Phần tiếp theo, ta chỉ ra rằng với sự hạn chế đó, thuật toán tách tương ứng với phương pháp Lions–Mercier trong [6].
B
(u, b)
(v, b)
1 2 (A + B)
z
v + λb
A
(u, -b)
(v, 1
λ (u − v) − b) = (v, a)
Tính (u, v)
−1
Tính v v + λb = (I + S)
(z)
−1
(z)
Hình 2.1: Tính (I + S)
Hình 2.1 minh họa cho việc tính (I + λS)−1(z).
Tính (u, b) xem như tìm giao điểm của B với đường có hệ số góc −1/λ đi qua điểm có tọa độ (z, 0). Sau đó để tính v, ta di chuyển điểm có tọa
22
độ (u, b) đến điểm có tọa độ (u, −b), và tìm giao điểm đường thẳng đi qua (u, −b) có hệ số góc −1/λ với A. Cuối cùng tính v + λb được mô tả là dựng một đường thẳng đứng tới điểm có tọa độ (v, b) và kẻ đường chéo tới trục
nằm ngang.
Từ phân tích tính (I + S)−1(z) sang việc tính (u, b) ∈ B và (v, a) ∈ A được tiến hành luân phiên trong thuật toán tách. Dãy {z}k được tạo thành sao cho
zk+1 = (I + S)−1(zk), với thành phần {uk + λbk},
trong đó (uk, bk) ∈ B là cặp duy nhất trong B sao cho uk + λbk = zk. Do đó ta nhận được mô tả sau đây của thuật toán:
(B1) Bắt đầu từ (uk, bk) ∈ B, tính (vk, ak) ∈ A sao cho
vk + λak = uk − λbk.
(B2) Tìm (uk+1, bk+1) ∈ B sao cho
uk+1 + λbk+1 = vk + λbk.
Ta có thể xem (B1) như một bước vẽ hình, trong đó tính giá trị của toán tử J1,S được nhắc lại, và (B2) như là một bước biểu diễn lại trong đó biến đầu ra của (B1) thành uk+1 + λbk+1 thuận lợi hơn, trong đó (uk+1, bk+1) ∈ B. Lưu ý rằng khó có thể tạo ra bước lặp (B1)-(B2) tại điểm bất kì (u0, b0) ∈ H × H, khi (u0, b0 không thuộc B. Bởi vì (u1, b1) sẽ phải thuộc B khi thực hiện (B2), khi đó thuật toán trở nên đúng đắn.
Hình 2.3 cho ta mô tả khác của thuật toán tách, trong đó không điểm của A + B chính là những điểm mà toán tử B và toán tử −A = (−1)A (nói chung không đơn điệu) cắt nhau.
23
B
(uk, bk)
(uk+1, bk+1)
(vk, bk)
1 2 (A + B)
A
(uk, −bk)
(vk, ak)
(vk, ak)
(uk+1, bk+1)
Hình 2.2: Thuật toán tách
24
(vk, bk)
B
(uk+1, bk+1)
−1/λ
(uk, bk)
1/λ
(vk, −ak)
-A
Hình 2.3: Mô tả khác của thuật toán tách
2.2 Mối quan hệ của phương pháp ngược từng phần
2.2.1 Giới thiệu
Ta xét trường hợp đặc biệt: Cho tập lồi C ⊆ H, và nón pháp tuyến NC
ứng với tập C là
. (x, y)|x ∈ C, hx′ − x, yi ≤ 0 ∀x′ ∈ C NC(x) :=
n o
Ta biết rằng NC là toán tử đơn điệu cực đại, và là ánh xạ dưới vi phân của hàm chỉ lồi:
nếu x ∈ C δC(x) = +∞ nếu x /∈ C. 0
Giả sử V là không gian con tuyến tính của H. Khi đó NV = V × V ⊥. Cho w ∈ H bất kì, ký hiệu phép chiếu của w lên V và V ⊥ tương ứng là wV và wV ⊥. Xét trường hợp B = NV. Khi đó bài toán tìm không điểm của A + B trở thành tìm (u, v) ∈ A sao cho u ∈ V và −v ∈ V ⊥, hay u ∈ V và v ∈ V ⊥. Trong trường hợp này ta có
. (v + λb, u − v)|u ∈ V, b ∈ V ⊥, (v, λ−1(u − v) − b) ∈ A Sλ,A,B =
n o
25
Cho (v, a) ∈ A bất kỳ, nghiệm duy nhất để
u ∈ V, b ∈ V ⊥ λ−1(u − v) − b = a,
là
u = (v + λa)V, b = −(λ−1z + a)V ⊥.
Khi đó
S = {(zV − λaV ⊥, λaV − zV ⊥)|(z, a) ∈ A}.
Với mọi toán tử đơn điệu cực đại T và tập con V, Spingarn [12]-[13] định nghĩa ngược từng phần:
TV = (xV + yV ⊥, yV + xV ⊥)|(x, y) ∈ T . ) (
Do đó, ngoại trừ sự khác nhau về dấu, S là ngược từng phần (λA)V của λA. Ứng dụng chính của ngược từng phần là tìm (x, y) ∈ T sao cho x ∈ V, y ∈ V ⊥. Cho T = A đây là bài toán mà ta đã xét. Để chỉ ra điều đó, Spingarn gợi ý áp dụng thuật toán điểm gần kề để xấp xỉ không điểm z của TV, khi đó chiếu z lên V và V ⊥ tương ứng, được x và y. Spingarn không xét tham số λ nhưng do tính đóng của V tích vô hướng nó làm cho không có sự khác nhau khi cho T = A hoặc T = λA; trong trường hợp sau ta làm đơn giản y bởi 1/λ để được kết quả cuối cùng. Về bản chất cùng một lí do, sự khác nhau về dấu giữa S và (λA)V là không ảnh hưởng. Dễ dàng chỉ ra rằng Jλ,B là toán tử chiếu lên V, vì vậy thuật toán tách mang lại các phương pháp tương tự như Spingarn gợi ý, ngoại trừ sự khác biệt
về dấu được ghi nhận từ trước. Phương pháp qui hoạch ngẫu nhiên của Rockafellar và Wets [11] trùng với thuật toán tách, λ xuất hiện và không
có sự khác nhau về dấu.
26
2.2.2 Mối quan hệ với thuật toán tách Lions–Mercier
Lions và Mercier [6] đưa ra thuật toán tìm không điểm của toán tử
A + B: bắt đầu với điểm tùy ý v0 ∈ H, thực hiện phép lặp
vk+1 = Gλ(vk),
trong đó
Gλ = Jλ,A(2Jλ,B − I) + I − Jλ,B.
Chú ý rằng toán tử này được gọi là G(λ) trong [6]. Ta có kết quả sau.
Mệnh đề 2.2.1 Ta luôn có
Gλ = (I + Sλ,A,B)−1.
Chứng minh. Bằng tính toán trực tiếp, đầu tiên ta chú ý
Jλ,A = {(y + λa, y)|(y, a) ∈ A}
Jλ,B = {(x + λb, x)|(x, b) ∈ B}.
Do đó,
2Jλ,B − I = {(x + λb, x − λb)|(x, b) ∈ B}
Jλ,A(2Jλ,B − I) = {(x + λb, y)|(x, b) ∈ B, (y, a) ∈ A, y + λa = x − λb} Jλ,A(2Jλ,B − I) = {(x + λb, y)|(x, b) ∈ B, (y, λ−1(x − y) − b ∈ A)}
Gλ = Jλ,A(2Jλ,B − I) + I − Jλ,B
= {(x + λb, y + λb)|(x, y) ∈ B, (y, λ−1(x − y) − b) ∈ A}.
Khi đó
−1 − I = {(y + λb, x − y)|(x, y) ∈ B, (y, λ−1(x − y) − b) ∈ A} = Sλ,A,B,
Gλ
(cid:3) mệnh đề được chứng minh.
Do đó, phương pháp Lions–Mercier đơn giản là thuật toán tách áp dụng cho A và B, rk = 1, với mọi k. Vì vậy phương pháp Lions–Mercier thực
27
chất là trường hợp đặc biệt của thuật toán điểm gần kề. Trên thực tế, đầu tiên ta xây dựng Sλ,A,B bằng việc kết hợp những nhận xét của phần 1.2 với chứng minh của Lions và Mercier rằng Gλ là không giãn chặt.
2.3 Phương pháp luân hướng
2.3.1 Nguồn gốc của phương pháp luân hướng
Ta sẽ chứng minh phương pháp luân hướng cho qui hoạch lồi là một
trường hợp đặc biệt của thuật toán tách.
Xét dạng tổng quát của qui hoạch lồi được giới thiệu bởi Rockafellar
trong [8]:
x∈Rn{f (x) + g(M x)},
(P) min
trong đó M là ma trận thực cỡ m × n, và f : Rn −→ (−∞, +∞], g : Rm −→ (−∞, +∞] là hàm lồi đóng chặt. Mở rộng cho không gian Hilbert tổng quát, ta sẽ hạn chế cho Rn và Rm, theo tiêu chuẩn tích trong, làm cho đại số tuyến tính đơn giản hơn. Ta có thể viết lại bài toán (P) như
sau:
{f (x) + g(z)} (P’) min s.t.
M x = z x ∈ Rn z ∈ Rm.
Khi đó, bài toán đối ngẫu với (P’) là
φ(p)
max s.t. p ∈ Rm,
trong đó
(x,z)∈Rn+m{f (x) + g(z) + p⊤(M x − z)}
φ(p) = inf
28
{g(z) + p⊤z} = inf x {f (x) + p⊤M x} − inf z
= −f ∗(−M ⊤p) − g∗(p),
ở đây ∗ kí hiệu cho phép toán liên hợp lồi. Đối ngẫu của (P) có thể viết
p∈Rm{f ∗(−M ⊤p) + g∗(p)}.
(D) min
Phương pháp nhân cho qui hoạch lồi thực chất là một cách thực hiện thuật toán điểm gần kề giống như áp dụng với toán tử đơn điệu cực đại
∂[f ∗ ◦ (−M ⊤) + g∗].
Khi ta kết hợp ma trận và ánh xạ đa trị, nghĩa là các ma trận được xem như ánh xạ tuyến tính đơn trị tương ứng; ví dụ M được hiểu là {(x, M x)|x ∈ Rn}.
2.3.2 Mối liên hệ với phương pháp tách
Bây giờ ta sẽ chứng minh những điều kiện chính qui đã biết, phương
pháp luân hướng thực chất là một cách thực hiện phương pháp tách giống như áp dụng với toán tử đơn điệu cực đại:
A = ∂[f ∗ ◦ (−M ⊤)] và B = ∂g∗ = (∂g)−1.
Nói cách khác, nó là thuật toán điểm gần kề với r = 1 áp dụng cho toán tử đơn điệu cực đại:
S = Sλ,∂[f ∗◦(−M ⊤)],∂g∗.
Cần chú ý rằng trong một số trường hợp ngoại lệ đây có thể không phải
là cách tiếp cận hợp lí để giải quyết bài toán (D), lí do là trong khi
∂[f ∗ ◦ (−M ⊤) + g∗] ⊇ ∂[f ∗ ◦ (−M ⊤)] + ∂g∗
luôn đúng, đẳng thức có thể không xảy ra trừ khi một số những điều kiện bổ xung được thỏa mãn. Do đó có thể hiểu rằng tập nghiệm của (D), zer(∂[f ∗ ◦ (−M ⊤) + g∗]), có thể khác rỗng, nhưng S không có không điểm.
29
Giả sử:
∂[f ∗ ◦ (−M ⊤) + g∗] = ∂[f ∗ ◦ (−M ⊤)] + ∂g∗ = A + B.
Khi đó, zer(S) khác rỗng khi và chỉ khi bài toán (D) có nghiệm.
Ta cũng giả sử rằng im(M ⊤) ∩ ri(domf ∗) 6= ∅, do đó
A = ∂[f ∗ ◦ (−M ⊤)] = −M ◦ ∂f ∗ ◦ (−M ⊤) = −M ◦ (∂f )−1 ◦ (−M ⊤).
Phương pháp luân hướng được tiến hành như sau: bắt đầu với điểm tùy
2
ý z0, p0 ∈ Rm và sau đó thực hiện các bước lặp
kM x − zkk } xk+1 = arg min
x∈Rn{f (x) + (pk)⊤M x + λ x∈Rm{g(z) − (pk)⊤z − 2
λ 2 2 kM xk+1 − zk } zk+1 = arg min
pk+1 = pk + λ(M xk+1 − zk+1).
Mệnh đề 2.3.1 Cho các dãy {xk}, {pk}, {zk} được định nghĩa bởi phương pháp luân hướng ở trên. Khi đó với mọi k > 1,
pk+1 + λzk+1 = (I + Sλ,∂[f ∗◦(−M ⊤)],∂g∗)−1(pk + λzk).
Chứng minh. Dạng chi tiết của toán tử A là:
A = −M ◦ (∂f )−1 ◦ (−M ⊤) = {(u, −M w)|(w, −M ⊤u) ∈ ∂f }.
Dạng chi tiết của toán tử B là:
B = {(u, b)|(b, u) ∈ ∂g}.
Từ bước tối giản x, với mọi k > 0,
0 ∈ ∂f (xk+1) + M ⊤pk + λM ⊤(M xk+1 − zk) ⇔ (xk+1, −M ⊤(pk + λ(M xk+1 − zk))) ∈ ∂f ⇒ (pk + λ(M xk+1 − zk), −M xk+1) ∈ A.
30
Từ bước tối giản z, cũng tương tự như vậy,
0 ∈ ∂g(zk+1) − pk + λ(zk+1 − M xk+1) ⇔ (zk+1, pk + λ(M xk+1 − zk+1)) = (zk+1, pk+1) ∈ ∂g ⇔ (pk+1, zk+1) ∈ B.
Ta có
(I + S)−1 = {(u + λb, v + λb)|(u, b) ∈ B, (v, λ−1(u − v) − b) ∈ A}.
Với mọi k > 1, thực hiện các phép thay thế sau:
u = pk b = zk v = pk + λ(M xk+1 − zk).
Do k > 1, ta có (u, b) = (pk, zk) ∈ B từ phân tích trong bước tối giản z. Như vậy
λ−1(u − v) − b = λ−1(pk − (pk + λ(M xk+1 − zk))) − zk = −M xk+1 (v, λ−1(u − v) − b) = (pk + λ(M xk+1 − zk), −M xk+1).
Ta đã biết phần tử của A có được từ phân tích trong bước tối giản x. Do đó sự thay thế là hợp lí, và ta kết luận rằng (I + S)−1 bao gồm
(u + λb, v + λb) = (pk + λzk, pk + λM xk+1) = (pk + λzk, pk+1 + λzk+1).
(cid:3) Chứng minh được hoàn thành.
Do đó, tại mỗi bước lặp trừ bước đầu tiên, phương pháp luân hướng về
cơ bản thực hiện các tính toán tương tự như phương pháp tách áp dụng cho toán tử đơn điệu cực đại A và B. Chú ý rằng phần tử cực tiểu x thực hiện tại "bước vẽ hình" (B1), trong khi đó điểm cực tiểu z và cập nhật p
được thực hiện tại "bước biểu diễn lại" (B2). Kết luận của Mệnh đề 2.3.1 có thể không đúng khi k = 0.
Theo lý thuyết của thuật toán điểm gần kề, ta được đảm bảo (ít nhất
31
Thuật toán điểm gần kề
Thuật toán tách
Lions-Mercier
Phương pháp ngược từng phần
Phương pháp luân hướng của tích
Rockafellar-Wets
Hình 2.4: Đường nét liền biểu thị mối liên hệ được thiết lập trong bản báo cáo này, đường nét đứt biểu thị mối quan hệ đã được biết đến.
là trong không gian hữu hạn chiều, sự hội tụ yếu và hội tụ mạnh là trùng nhau) rằng dãy {pk + λzk} là hội tụ. Từ toán tử Jλ,B = (I + λB)−1 là không giãn, nên nó liên tục (Lipschitz), suy ra dãy {Jλ,B(pk + λzk)} cũng hội tụ. Dãy này giống với dãy {pk}, có thể ngoại trừ phần tử đầu tiên trong nó. Do đó, ta có thể kết luận rằng dãy {pk} và {zk} bị chặn và hội tụ, với {pk} hội tụ tới nghiệm của bài toán (D). Từ đây, ta có thể dùng các chứng minh hội tụ thông thường cho phương pháp luân hướng.
32
Kết luận
Đề tài luận văn đã trình bày thuật toán Lions–Mercier và phương pháp
luân hướng tìm không điểm của toán tử đơn điệu cực đại trong không gian Hilbert thực. Cụ thể:
(1) Giới thiệu khái niệm và một số tính chất cơ bản của không gian Hilbert
thực và toán tử đơn điệu cực đại;
(2) Trình bày phương pháp tách Lions–Mercier, phương pháp luân hướng
tìm không điểm của tổng hai toán tử đơn điệu cực đại;
(3) Nêu mối liên hệ giữa phương pháp luân hướng, phương pháp tách và phương pháp điểm gần kề tìm không điểm của toán tử đơn điệu cực
đại.
Điểm quan trọng đó là qui tắc phân hoạch của phần 2.1 cho các thuật
toán của Lions–Mercier, phương pháp phân hoạch của Spingarn [13], và phương pháp luân hướng của tích.
Câu hỏi thú vị cho hướng nghiên cứu tiếp theo của đề tài là liệu còn có
thể có được sự hội tụ nếu thay đổi các tham số λ từ phép lặp đến số lần lặp của thuật toán tách?
33
Tài liệu tham khảo
Tiếng Việt
[1] Hoàng Tụy, Hàm thực và Giải tích hàm, NXB Đại học Quốc gia Hà
Nội, (2003).
Tiếng Anh
[2] Bertsekas D., Tsitsiklis J. (1989), Parallel and Distributed Computa-
tion: Numerical Methods (Englewood Cliffs: Prentice-Hall).
[3] Brézis H. (1973), Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert (Amsterdam: North- Hol- land).
[4] Eckstein J.(1988), "The Lions-Mercier splitting algorithm and the al- ternating direction method are instances of the proximal point algo-
rithm", Report LIDS-P-1769, Laboratory for Information and Deci- sion Sciences.
[5] Gabay D. (1983), "Applications of the Method of Multipliers to Vari- ational Inequalities". In M. Fortin, R. Glowinski, editors, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value
Problems (Amsterdam: North-Holland).
[6] Lions P. L., Mercier B. (1979), "Splitting Algorithms for the Sum
of Two Nonlinear Operators". SIAM Journal on Numerical Analysis, 16(6): 964-979.
[7] Martinet B. (1972), "Determination Approchee d’un Point Fixe d’une Application Pseudo-Contractante. Cas de l’Application prox",
34
Comptes Rendus de l’Academie des Sciences, Paris, Sdrie A, 274: 163-165.
[8] Rokafellar R.T. (1970), Convex Analysis (Princeton: Princeton Uni-
versity Press).
[9] Rokafellar R.T. (1970), "On the Maximality of Sums of Nonlinear
Monotone Operators", Transactions of the American Mathematical Society, 149: 75-88.
[10] Rokafellar R.T. (1976), "Monotone Operators and the Proximal Point Algorithm", SIAM Journal on Control and Optimization, 14(5): 877- 898.
[11] Rokafellar R.T., Wets R.J.B. (1987), Scenarios and Policy Aggregation
in Optimization under Uncertainty, Working paper WP-87-119, Inter- national Institute for Applied Systems Analysis, Laxenberg, Austria.
[12] Spingarn J.E. (1983), "Partial Inverse of a Monotone Operator", Ap-
plied Mathematics and Optimization, 10: 247-265.
[13] Spingarn J.E. (1985), "Application of the Method of Partial Inverses to Convex Programming: Decomposition", Mathematical Programming, 32: 199-233.
