i
Mục lục
Lời cảm ơn ii
Danh sách ký hiệu iii
Mở đầu 1
1 Một số vấn đề cơ bản 3
3 1.1 Không gian Hilbert và các vấn đề liên quan . . . . . . . .
11 1.2 Một số vấn đề về giải tích lồi . . . . . . . . . . . . . . . .
1.3 Toán tử đơn điệu, nghiệm của phương trình toán tử đơn
điệu và của bất đẳng thức biến phân trong không gian Hilbert 19
2 Phương pháp Dykstra lai ghép cho hai toán tử đơn điệu 27
2.1 Bài toán tìm giao điểm của hai không gian con đóng và
thuật toán Neumann . . . . . . . . . . . . . . . . . . . . . 27
2.2 Phương pháp Dykstra tìm không điểm của tổng hai toán tử
đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
40 Kết luận
41 Tài liệu tham khảo
ii
Lời cảm ơn
Để hoàn thành được luận văn một cách hoàn chỉnh, tôi luôn nhận được
sự hướng dẫn và chỉ bảo tận tình của GS.TS. Nguyễn Bường (Viện Công
nghệ Thông tin - Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Tôi
xin chân thành bày tỏ lòng biết ơn và xin gửi lời tri ân sâu sắc nhất đến
thầy.
Tôi xin chân thành cảm ơn Ban lãnh đạo khoa Toán - Tin, phòng Đào
tạo, quý thầy cô giảng dạy lớp cao học toán K7Y (01/2014–01/2016) trường
Đại học Khoa học – Đại học Thái Nguyên đã tận tình truyền đạt những kiến
thức quý báu và tạo điều kiện cho tôi trong quá trình học tập và nghiên cứu.
Tôi xin gửi lời cảm ơn chân thành nhất tới gia đình, bạn bè, đồng nghiệp
những người đã luôn động viên, hỗ trợ và tạo mọi điều kiện cho tôi trong
suốt quá trình học tập và thực hiện luận văn.
Trong quá trình thực hiện, mặc dù đã rất cố gắng luận văn không tránh
khỏi những thiếu sót. Tôi rất mong nhận được sự góp ý của các Thầy, các
Cô và các Độc giả quan tâm để luận văn được hoàn thiện hơn.
Xin trân trọng cảm ơn!
Thái Nguyên, 2015 Nguyễn Thị Hoàng Nguyên
Học viên Cao học Toán Khóa 01/2014–01/2016,
Trường ĐH Khoa học - ĐH Thái Nguyên
iii
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
trong bảng dưới đây:
R không gian số thực
H không gian Hilbert thực
X ∗ không gian đối ngẫu của X
phép chiếu trực giao của điểm x trên tập C PC(x)
(cid:104)x, y(cid:105) tích vô hướng của hai vectơ x và y
(cid:107)x(cid:107) chuẩn của vectơ x
xn → x xn hội tụ mạnh đến x
xn (cid:42) x xn hội tụ yếu x
x := y x được gán bằng y
spanC tổ hợp tuyến tính của C
∀ mọi
∃ tồn tại
∅ tập rỗng
Id ánh xạ đơn vị.
1
Mở đầu
Toán tử đơn điệu là một trong những công cụ được sử dụng nhiều và rất
có hiệu quả trong lĩnh vực toán ứng dụng chẳng hạn như bất đẳng thức biến
phân. Nó giúp ích cho việc nghiên cứu ánh xạ dưới gradient và gradient,
chứng minh sự tồn tại và duy nhất nghiệm cho rất nhiều các lớp bài toán cân
bằng, bài toán bất đẳng thức biến phân và bài toán tối ưu. Từ bài toán tìm
giao điểm của hai không gian con đóng đã được chứng minh bởi nhà toán
học Neumann trong thuật toán chiếu luân hướng cổ điển vào năm 1933. Và
sau này nhà toán học Dykstra sử dụng phép chiếu lên hai tập đóng lồi của
không gian Hilbert để xây dựng phép chiếu lặp lên giao của chúng.
Đề tài của luận văn là trình bày cách tiếp cận đối ngẫu để mở rộng thuật
toán của Dykstra nhằm xây dựng toán tử giải cho toán tử tổng hai toán tử
đơn điệu cực đại từ các toán tử giải đơn điệu.
Nội dung của luận văn được trình bày trong hai chương. Chương 1 giới
thiệu một số kiến thức cơ bản về không gian Hilbert thực, giải tích lồi, phép
chiếu trong không gian Hilbert, toán tử đơn điệu, nghiệm của phương trình
toán tử đơn điệu và nghiệm của bất đẳng thức biến phân trong không gian
Hilbert. Chương 2 gồm hai mục chính. Mục 2.1 nêu bài toán tìm giao điểm
của hai không gian con đóng. Mục 2.2 trình bày về phương pháp Dykstra
lai ghép cho hai toán tử đơn điệu cực đại.
Qua quá trình hoàn thành luận văn, tác giả nhận thấy rằng luận văn chỉ
thể hiện được một phần nhỏ các vấn đề được đề cập trong luận văn. Tuy
2
nhiên, thông qua việc trình bày luận văn tác giả được trau dồi những kiến
thức khởi đầu định hướng cho sự tiếp cận các vấn đề sau này.
Thái Nguyên, tháng 11 năm 2015
Nguyễn Thị Hoàng Nguyên
Học viên cao học toán khóa 01/2014 – 01/2016
Chuyên ngành Toán ứng dụng
Trường Đại học Khoa học - Đại học Thái Nguyên
3
Chương 1
Một số vấn đề cơ bản
Trong chương này chúng tôi nhắc lại một số kiến tức cơ bản của giải
tích hàm, giải tích lồi, toán tử đơn điệu và bài toán bất đẳng thức biến
phân, có liên quan đến nội dung nghiên cứu của đề tài. Các kiến thức trong
chương được tham khảo trong các tài liệu [1], [2], [3], [4], [6].
1.1 Không gian Hilbert và các vấn đề liên quan
Trong toàn bộ đề tài, chúng tôi chỉ đề cập đến không gian Hilbert thực,
với tích vô hướng (cid:104)., .(cid:105) và chuẩn ||.||. Phép chiếu lên tập con U đóng lồi
khác rỗng của H kí hiệu là PU và xn −→ x có nghĩa là dãy xn hội tụ mạnh
đến x.
1.1.1. Định nghĩa và ví dụ
Định nghĩa 1.1. Cho không gian tuyến tính H trên trường số thực R, ta gọi tích vô hướng trên không gian H là một ánh xạ đi từ tích Descartes H × H vào trường R ký hiệu (cid:104)., .(cid:105) thỏa mãn các điều kiện sau:
a) (cid:104)x, y(cid:105) = (cid:104)y, x(cid:105), ∀x, y ∈ H.
b) (cid:104)x + y, z(cid:105) = (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105), ∀x, y, z ∈ H.
c) (cid:104)αx, y(cid:105) = α(cid:104)x, y(cid:105), ∀x, y ∈ H, ∀α ∈ R.
4
d) (cid:104)x, x(cid:105) > 0 nếu x (cid:54)= 0 và (cid:104)x, x(cid:105) = 0 nếu x = 0.
Nhận xét 1.1. Từ định nghĩa ta suy ra
1) (cid:104)x, λy(cid:105) = λ(cid:104)y, x(cid:105), ∀x, y ∈ H;
2) (cid:104)x, y + z(cid:105) = (cid:104)x, y(cid:105) + (cid:104)x, z(cid:105), ∀x, y, z ∈ H;
Định nghĩa 1.2. Không gian tuyến tính H cùng với một tích vô hướng trên
nó được gọi là một không gian tiền Hilbert.
Định lí 1.1. (Bất đẳng thức Schwarz) Trong không gian tiền Hilbert H, với
mọi x, y ∈ H ta luôn có bất đẳng thức sau:
|(cid:104)x, y(cid:105)|2 ≤ (cid:104)x, x(cid:105)(cid:104)y, y(cid:105)
Chứng minh. Với mọi số thực α ta có
0 ≤ (cid:104)x − αy, x − αy(cid:105) = (cid:104)x, x(cid:105) − 2α(cid:104)x, y(cid:105) + α2(cid:104)y, y(cid:105)
(cid:3) Nên ∆ = |(cid:104)x, y(cid:105)|2 − (cid:104)x, x(cid:105)(cid:104)y, y(cid:105) ≤ 0. Hay |(cid:104)x, y(cid:105)|2 ≤ (cid:104)x, x(cid:105)(cid:104)y, y(cid:105).
Dấu đẳng thức trong bất đẳng thức xảy ra khi và chỉ khi x và y phụ
thuộc tuyến tính.
Định lí 1.2. Cho H là một không gian tiền Hilbert, khi đó H cũng là một
không gian tuyến tính định chuẩn với chuẩn được xác định bởi
||x|| = (cid:112)(cid:104)x, x(cid:105) với mọi x ∈ H. (1.1)
Chuẩn này được gọi là chuẩn cảm sinh từ tích vô hướng. Ta dễ dàng chứng minh được hàm số ||x|| = (cid:112)(cid:104)x, x(cid:105) với mọi x ∈ H, là một chuẩn trên H. Thật vậy, từ điều kiện d) ta có ||x|| > 0 nếu x (cid:54)= 0, ||x|| = 0 nếu x = 0.
5
Từ điều kiện a), c) ta suy ra ||λx|| = |λ|.||x||. Từ bất đẳng thức Schwarz và
cách định nghĩa chuẩn ta có
|(cid:104)x, y(cid:105)| ≤ ||x||.||y||. (1.2)
Từ đó
(cid:104)x + y, x + y(cid:105) = (cid:104)x, x(cid:105) + 2(cid:104)x, y(cid:105) + (cid:104)y, y(cid:105)
≤ ||x||2 + 2||x||.||y|| + ||y||2 = (||x|| + ||y||)2.
Suy ra ||x + y|| ≤ ||x|| + ||y||.
Định nghĩa 1.3. Nếu H là một không gian tiền Hilbert thực và đầy đủ đối
với chuẩn cảm sinh từ tích vô hướng xác định bởi (1.1) thì H được gọi là
không gian Hilbert thực.
n (cid:88)
Ví dụ 1.1. Rn là không gian Hilbert thực với tích vô hướng
k=1
(cid:104)x, y(cid:105) = xkyk
1
n (cid:88)
2 .
trong đó x = (x1, x1, ..., xn), y = (y1, y2, ..., yn) ∈ Rn và chuẩn cảm sinh
k=1
||x|| = (cid:112)(cid:104)x, x(cid:105) = ( x2 k)
∞ (cid:88)
Ví dụ 1.2. Không gian
n=1
|xn|2 < +∞} l2 = {x = {xn}n ∈ R :
n=1
là không gian Hilbert với tích vô hướng ∞ (cid:88) (cid:104)x, y(cid:105) = xnyn
1
n (cid:88)
n (cid:88)
trong đó x = (xn)n∈N , y = (yn)n∈N ∈ l2 và chuẩn cảm sinh
2 .
k=1
k=1
||x|| = (cid:112)(cid:104)x, x(cid:105) = |xk|2 = ( |xk|2) (cid:118) (cid:117) (cid:117) (cid:116)
6
a
Ví dụ 1.3. Gọi C[a,b] là tập tất cả các hàm giá trị thực liên tục trên khoảng đóng hữu hạn [a, b] ⊂ R. Trong C[a,b] xét tích vô hướng (cid:90) b (cid:104)x, y(cid:105) = x(t)y(t)dt, x(t), y(t) ∈ C[a,b].
Khi đó, không gian C[a,b] với chuẩn
1 2
a
(cid:90) b ||x|| = ( |x(t)|2dt)
là không gian tiền Hilbert.
1.1.2. Một số tính chất
Định lí 1.3. Giả sử (xn)n∈N , (yn)n∈N là hai dãy lần lượt hội tụ mạnh đến
x0, y0 trong không gian tiền Hilbert thực H, khi đó
(cid:104)xn, yn(cid:105) = (cid:104)x0, y0(cid:105). lim n→∞
yn = y0 trong không gian H. Ta xn = x0, lim n→∞
Chứng minh. Giả sử lim n→∞ (cid:104)xn, yn(cid:105) = (cid:104)x0, y0(cid:105) trong R. Thật vậy, ta có sẽ chứng minh cho lim n→∞
|(cid:104)xn, yn(cid:105) − (cid:104)x0, y0(cid:105)| = |(cid:104)xn, yn(cid:105) + (cid:104)xn, y0(cid:105) − (cid:104)xn, y0(cid:105) − (cid:104)x0, y0(cid:105)|
≤ |(cid:104)xn, yn − y0(cid:105)| + |(cid:104)xn − x0, y0(cid:105)|
≤ ||xn||.||yn − y0|| + ||xn − x0||.||y0||.
Vì dãy (xn)n∈N hội tụ trong H nên tồn tại M > 0 sao cho ||xn|| ≤ M với
mọi n ∈ N . Khi đó,
(cid:104)xn, yn(cid:105) = (cid:104)x0, y0(cid:105). lim n→∞
(cid:3)
Nhận xét 1.2. Từ định lý trên cho thấy tích vô hướng là một hàm số liên
tục trên H × H, nó cũng là một phiếm hàm song tuyến tính bị chặn và hơn
nữa phiếm hàm này cũng liên tục.
7
Định lí 1.4. Với mọi x, y thuộc không gian tiền Hilbert H ta luôn có đẳng
thức hình bình hành sau
||x + y||2 + ||x − y||2 = 2(||x||2 + ||y||2).
Chứng minh. Với mọi x, y ∈ H, ta có
||x + y||2 = (cid:104)x + y, x + y(cid:105) = ||x||2 + ||y||2 + 2(cid:104)x, y(cid:105)
và
||x − y||2 = (cid:104)x − y, x − y(cid:105) = ||x||2 + ||y||2 − 2(cid:104)x, y(cid:105).
(cid:3) Cộng hai đẳng thức trên ta được đẳng thức cần chứng minh.
Áp dụng đẳng thức hình bình hành cho hai véc tơ x − y, x − z ta có hệ
quả sau
Hệ quả 1.1. Cho H là một không gian tiền Hilbert và x, y, z ∈ H. Khi đó,
ta có đẳng thức Apollonius
2(||x − y||2 + ||x − z||2) = 4||x − ||2 + ||y − z||2. y + z 2
Nhận xét 1.3. (Ý nghĩa của đẳng thức hình bình hành)
1) Đẳng thức trên nói lên một tính chất hình học: tổng bình phương các
cạnh của hình bình hành bằng tổng bình phương hai đường chéo.
2) Từ định lý trên ta thấy, muốn đưa được tích vô hướng vào một không
gian định chuẩn thì không gian này phải thỏa mãn điều kiện hình bình
hành. Ngược lại nếu H là một không gian định chuẩn trong đó đẳng
thức hình bình hành được thỏa mãn với mọi phần tử thuộc H thì trên
H sẽ tồn tại một tích vô hướng (cid:104)., .(cid:105) sao cho chuẩn này được xác định
nhờ tích vô hướng. Điều này được thể hiện qua định lý sau.
8
Định lí 1.5. Giả sử (H, ||.||) là một không gian định chuẩn trên R trong đó đẳng thức hình bình hành nghiệm đúng với mọi x, y ∈ H. Và khi đó ta đặt
(||x + y||2 − ||x − y||2) (cid:104)x, y(cid:105) = p(x, y) = (1.3) 1 4
thì (cid:104)., .(cid:105) là một tích vô hướng trên H và ta có (cid:104)x, x(cid:105) = ||x||2.
Chứng minh. Ta chứng minh (cid:104)., .(cid:105) xác định như trên thỏa mãn các điều
kiện trong định nghĩa về tích vô hướng. Điều kiện a) - d) hiển nhiên được thỏa mãn (theo [2]). Để ý rằng (cid:104)., .(cid:105) : H × H −→ R là một hàm liên tục và
p(x, 0) = 0, p(−x, y) = −p(x, y), ∀x, y ∈ H.
Với mọi x, y, z ∈ H ta có
4(p(x, z) + p(y, z)) = (||x + z||2 − ||x − z||2 + ||y + z||2 − ||y − z||2
⇔ p(x, z) + p(y, z) = 2p( , z). x + y 2
Trong đẳng thức trên lấy y = 0 được p(x, z) = 2p( x
2 , z). Như vậy ta có , z) = p(x + y, z). Nghĩa là p(x, z) + p(y, z) = p(x + y, z). Vậy
2p( x + y 2
điều kiện b) được chứng minh. Thay thế x bằng 2x ta được
2p(x, z) = p(2x, z), ∀x, y, z ∈ H.
Bằng quy nạp ta kiểm tra được
p(nx, z) = np(x, z), ∀n ∈ N
và bằng lập luận như trên ta có
p(rx, z) = rp(x, z), ∀r ∈ Q và x, z ∈ H.
Nhờ tính liên tục của chuẩn ||.|| suy ra hàm p(., z) liên tục, qua giới hạn ta
có
p(ax, z) = ap(x, z), ∀x, z ∈ H và a ∈ R.
9
Vậy p(x, y) là một tích vô hướng trên H và hiển nhiên
(cid:104)x, x(cid:105) = p(x, x) = ||x||2.
(cid:3) Định lý được chứng minh.
Định lí 1.6. Với mọi không gian tiền Hilbert H đều tồn tại một không gian
Hilbert H1 chứa H sao cho H là không gian con trù mật trong H1.
Chứng minh. Dùng phép bổ sung đầy đủ của một không gian định chuẩn
ta được một không gian định chuẩn đầy đủ H1 chứa H sao cho H là không
gian định chuẩn trù mật trong H1 [4, Định lý 2.8]. Với mọi x, y ∈ H1 sẽ
tồn tại các dãy (xn)n, (yn)n ⊂ H sao cho
xn = x, yn = y lim n−→∞ lim n−→∞
trong H1. Theo đẳng thức hình bình hành ta có
||xn + yn||2 + ||xn − yn||2 = 2(||xn||2 + ||yn||2).
Cho n −→ ∞, do tính liên tục của hàm chuẩn ta suy ra
||x + y||2 + ||x − y||2 = 2(||x||2 + ||y||2).
Theo định lý trên sẽ tồn tại một tích vô hướng trong H1 cảm sinh ra chuẩn
của H1 và ta có
(cid:104)xn, yn(cid:105)H1 = (cid:104)x, y(cid:105)H1. lim n−→∞
(cid:3) Định lý được chứng minh .
Tính chất khác biệt của không gian Hilbert so với không gian định
chuẩn là ở đó khái niệm tích vô hướng bao hàm các khái niệm về tính trực
giao, trực chuẩn, góc giữa các vectơ.... Trong phần sau chúng ta nhắc lại
định nghĩa, tính chất của các khái niệm đó và một số ví dụ minh họa.
10
Định nghĩa 1.4. Cho H là không gian tiền Hilbert thực.
1) Hai phần tử x, y ∈ H được gọi là trực giao với nhau nếu (cid:104)x, y(cid:105) = 0 và
được kí hiệu là x⊥y.
2) Hệ S ⊂ H được gọi là hệ trực giao nếu các phần tử của S trực giao
với nhau từng đôi một, tức là ∀x, y ∈ S, x (cid:54)= y ta có (cid:104)x, y(cid:105) = 0.
3) Hệ E = {e1, e2, ..., } ⊂ H được gọi là hệ trực chuẩn nếu E là hệ trực
giao và ||ej|| = 1 ∀ei ∈ E . Một cách tương đương, hệ E được gọi là
hệ trực chuẩn nếu
0 nếu i (cid:54)= j (cid:104)ei, ej(cid:105) = δij = 1 nếu i = j.
4) Phần tử x ∈ H được gọi là trực giao với M ⊂ H nếu ∀y ∈ M ta có
(cid:104)x, y(cid:105) = 0 và được kí hiệu là x⊥M .
5) Phần bù trực giao của M ⊂ H được kí hiệu M ⊥ là tập hợp
M ⊥ = {x ∈ H : x⊥y, ∀y ∈ M }.
Định lí 1.7. Cho M là một không gian con đóng của không gian Hilbert
H. Khi đó mọi phần tử x ∈ H đều biểu diễn một cách duy nhất dưới dạng
x = y + z, y ∈ M, z ∈ M ⊥
trong đó y thỏa mãn
{||x − u||} = d(x, M ). ||x − y|| = ||z|| = inf u∈M
Nhận xét 1.4. Từ định lý này ta có thể viết
H = M ⊕ M ⊥
và y được gọi là hình chiếu trực giao của x lên không gian con M .
11
Định nghĩa 1.5. Dãy (xn)n∈N ∈ H được gọi là
(i) Hội tụ mạnh đến x0 ∈ H nếu nó hội tụ theo chuẩn, nghĩa là
||xn − x0|| = 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ó
(cid:104)xn, y(cid:105) = (cid:104)x, y(cid:105). lim n→∞
Ký hiệu là {xn} w−→ x hoặc {xn} (cid:42) x, khi n −→ ∞.
Chú ý 1.1. Nếu dãy {xn} hội tụ mạnh về x thì nó cũng hội tụ yếu về x,
nhưng điều ngược lại không đúng.
1.2 Một số vấn đề về giải tích lồi
Trước hết ta nhắc lại một số khái niệm và tính chất cơ bản của giải tích
lồi như tập lồi, hàm lồi, dưới vi phân,...
1.2.1. Tập lồi, bao lồi và nón lồi
Giả sử X là không gian tuyến tính, R là tập số thực.
Định nghĩa 1.6. Tập A ⊂ X, ∀x, y ∈ A, ta có
1) A được gọi là lồi ⇔ λx + (1 − λ)y ∈ A, với mọi λ ∈ [0, 1].
2) [x1, x2] = {x ∈ A : x = λx1 + (1 − λ)x2 , 0 ≤ λ ≤ 1}, là đoạn nối
x1, x2.
3) Giao của tất cả các tập lồi chứa A được gọi là bao lồi của A và ký hiệu
là coA.
12
Ví dụ 1.4. cho A = {(x, y) ∈ R| y ≥ x2}. Dễ thấy A là tập lồi.
Cho tập A ⊂ X, khi đó, ta có nhận xét sau:
1) coA là tập lồi nhỏ nhất chứa A.
2) Tập A là lồi nếu với mọi x1, x2 ∈ A suy ra [x1, x2] ⊂ A.
3) A là tập lồi khi và chỉ khi A ≡ coA.
m (cid:80) n=1
m (cid:80) n=1
4) coA = { λixi|xi ∈ A; λi = 1; λi > 0 ∀i = 1, 2, ..., m}.
Định nghĩa 1.7. Cho tập A ⊂ X khi đó,
i) Giao tất cả các tập con đóng của X chứa A được gọi là bao đóng của
A và ký hiệu là A.
ii) Giao tất cả các tập con lồi đóng của X chứa A được gọi là bao lồi đóng
của A và ký hiệu là coA.
Nhận xét 1.5. Ta có coA là tập lồi đóng và là tập lồi đóng nhỏ nhất chứa
A.
Chú ý 1.2. Bao lồi đóng của tập A trùng với bao lồi của A tức là ta có
co A = coA.
Định nghĩa 1.8. Cho tập K ⊂ X ta có các định nghĩa
1) Tập K được gọi là nón có đỉnh tại 0 nếu với mọi x ∈ K và mọi
λ > 0 suy ra λx ∈ K.
2) Tập K ⊂ X được gọi là nón có đỉnh tại x0 nếu K − x0 là nón có đỉnh
tại 0.
3) Nón K có đỉnh tại 0 được gọi là nón lồi nếu K là một tập lồi, có nghĩa
là với mọi x, y ∈ K và với mọi λ, µ > 0 suy ra λx + µy ∈ K.
13
Định lí 1.8. Tâp K ⊂ X là nón lồi có đỉnh tại 0 khi và chỉ khi với mọi
x, y ∈ K, với mọi λ > 0 suy ra x + y ∈ K, λx ∈ K.
Định nghĩa 1.9. Cho A ⊂ Rn, ta có:
1) A được gọi là tập affine nếu:
(1 − λ)x + λy ∈ A, ∀x, y ∈ A, ∀λ ∈ R.
2) Giao của tất cả các tập affine chứa A ⊂ Rn được gọi là bao affine của
m (cid:88)
m (cid:88)
A và ký hiệu là affA. Nghĩa là
n=1
n=1
affA := { λixi|xi ∈ A; λi = 1; ∀i = 1, 2, ..., m.}
1.2.2. Hàm lồi và dưới vi phân
Định nghĩa 1.10. Giả sử X là không gian lồi địa phương, D ⊂ X và f : D −→ R ∪ {−∞, +∞}. Ta có các định nghĩa:
1) Trên đồ thị (epigraph) của hàm f , ký hiệu là epif và
epif = {(x, r) ∈ D × R : f (x) ≤ r}.
2) Hàm f được gọi là hàm lồi nếu epif là tập lồi trong X × R. Hàm f
được gọi là hàm lõm nếu −f là hàm lồi.
3) Miền hữu dụng (miền xác định) của hàm f ký hiệu là domf và:
domf = {x ∈ D : f (x) < +∞}.
4) Hàm f xác định trên X được gọi là thuần nhất dương (positively ho-
mogeneous), nếu với mọi x ∈ X và với mọi λ ∈ (0, +∞) ta đều có:
f (λx) = λf (x).
14
Ví dụ 1.5. Dễ thấy f (x) = |x|, ∀x ∈ R là một hàm lồi.
Định lí 1.9. Giả sử D là tập lồi, khác rỗng trong không gian X, hàm
f : D → (−∞, +∞]. Khi đó, f lồi trên D khi và chỉ khi:
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀λ ∈ [0, 1] và ∀x, y ∈ D.
Định nghĩa 1.11. Hàm f được gọi là chính thường (proper) nếu f thỏa
mãn hai điều kiện sau:
i) domf (cid:54)= 0;
ii) f (x) > −∞ với mọi x ∈ D.
Mệnh đề 1.1. Hàm thuần nhất dương f : X → (−∞, +∞] là lồi khi và
chỉ khi với mọi x, y ∈ X ta luôn có:
f (x + y) ≤ f (x) + f (y).
Định nghĩa 1.12. Cho f là hàm lồi, phiếm hàm (vectơ) x∗ ∈ X ∗ được gọi là dưới gradient của f tại ¯x nếu:
f (x) − f (¯x) ≥ (cid:104)x∗, x − ¯x (cid:105) với mọi x ∈ X.
Tập tất cả các dưới gradient của f tại ¯x được gọi là dưới vi phân của f tại
¯x. Ký hiệu là: ∂f (¯x). Như vậy:
∂f (¯x) = {x∗ ∈ X : f (x) − f (¯x) ≥ (cid:104)x∗, x − ¯x(cid:105) với mọi x ∈ X}.
Hàm f được gọi là khả dưới vi phân tại ¯x nếu ∂f (¯x) (cid:54)= ∅.
Ví dụ 1.6. Cho C là tập lồi khác rỗng của H. Xét hàm chỉ của tập C có
dạng
nếu x ∈ C 0 δC(x) :=
+∞ nếu x /∈ C.
15
Khi đó dưới vi phân của δC(x) tại x0 ∈ C là nón pháp tuyến ngoài của C
tại x0. Thật vậy, khi x0 ∈ C thì
∂δC(x0) = {x∗ ∈ H : (cid:104)x∗, x − x0(cid:105) ≤ δC(x), ∀x ∈ C}.
Với x /∈ C thì δC(x) = +∞ nên bất đẳng thức (cid:104)x∗, x − x0(cid:105) ≤ δC(x) luôn
đúng. Do đó
∂δC(x0) = {x∗ ∈ H : (cid:104)x∗, x − x0(cid:105) ≤ 0, ∀x ∈ C} = NC(x0).
Ví dụ 1.7. Cho f : H −→ R là hàm lồi thuần nhất dương, (tức là f lồi và f (λx) = λf (x), ∀λ > 0, ∀x ∈ H.) Khi đó
∂f (x) = {z ∈ H : (cid:104)z; x(cid:105) = f (x), (cid:104)z, x(cid:105) ≤ f (x), ∀x ∈ C}.
Thật vậy, nếu z ∈ ∂f (x) thì
(cid:104)z, x − x(cid:105) ≤ f (x) − f (x), ∀x ∈ C.
Thay x = 2x, ta có
(cid:104)z, x(cid:105) ≤ f (2x) − f (x) = f (x).
Còn nếu thay x = 0, ta có
−(cid:104)z, x(cid:105) ≤ −f (x).
Từ kết quả trên suy ra
(cid:104)z, x(cid:105) = −f (x).
Hơn nữa,
(cid:104)z, x − x(cid:105) = (cid:104)z, x(cid:105) − (cid:104)z, x(cid:105) = (cid:104)z, x(cid:105) − f (x).
Do đó,
(cid:104)z, x(cid:105) ≤ f (x), ∀x ∈ C.
16
Suy ra,
(cid:104)z, x − x(cid:105) = (cid:104)z, x(cid:105) − (cid:104)z, x(cid:105) ≤ f (x) − f (x), ∀x ∈ C.
Vậy z ∈ ∂f (x).
Nhận xét 1.6. Nếu f là hàm lồi thuần nhất dương thỏa mãn
f (−x) = f (x) ≥ 0, ∀x ∈ C,
thì
(cid:104)z, x(cid:105) ≤ f (x), ∀x ∈ C
⇔ |(cid:104)z, x(cid:105)| ≤ f (x), ∀x ∈ C.
Chú ý 1.3. Nếu hàm lồi f khả vi Gâteaux thì f khả dưới vi phân và ngược
lại, nếu hàm lồi f khả dưới vi phân và tại điểm x0 và dưới vi phân tại đó
chỉ gồm một điểm thì f khả vi Gâteaux và đạo hàm Gâteaux tại x0 trùng
với dưới vi phân tại đó. Dưới đây, chúng tôi đề cập đến một số tính chất
đơn giản của dưới vi phân.
Định lí 1.10. f là hàm lồi chính thường trên X, x thuộc domf thì x∗ thuộc ∂f (¯x) khi và chỉ khi f (cid:48)(¯x, d) ≥ (cid:104)x∗, d(cid:105) với mọi d ∈ X.
Định lí 1.11 (Moreau - Rockafellar). Giả sử f1, ..., fm là hàm lồi chính
thường trên X. Khi đó, với mọi x ∈ X ta luôn có:
∂(f1 + ... + fm)(x) ⊃ ∂f1(x) + ... + ∂fm(x).
m (cid:92)
Hơn nữa, nếu tại điểm
i=1
x ∈ domfi,
tất cả các hàm f1, ..., fm liên tục (có thể trừ ra một hàm), thì:
∂(f1 + ... + fm)(x) = ∂f1(x) + ... + ∂fm(x).
17
Với f : H → R ∪ {∞}, kí hiệu tập các điểm cực tiểu của hàm f trên
f (x) và được xác định bởi C ⊂ H là arg min x∈C
f (x) /∈ ∞, {x ∈ C : f (x) = inf x∈C f (x)} nếu inf x∈C f (x) = arg min x∈C f (x) = ∞. 0 nếu inf x∈C
Định lí 1.12 (4, Định lý 5.1). Cho C là tập lồi, khác rỗng, hàm
f : C → R
là hàm lồi, khả dưới vi phân trên C. Khi đó y là nghiệm của bài toán
f (x) min f (x) : x ∈ C tức là y ∈ arg min x∈C
khi và chỉ khi 0 ∈ ∂f (y) + NC(y).
1.2.3. Phép chiếu mêtric trong không gian Hilbert
Mệnh đề 1.2. Cho C là tập con lồi đóng và khác rỗng của không gian
Hilbert H. Khi đó với mọi x ∈ H, tồn tại duy nhất phần tử PCx ∈ C sao
||x − u||. cho ||x − PCx|| ≤ inf u∈C
||x − u|| suy ra tồn tại {un} ⊂ C sao Chứng minh. Thật vậy, đặt d = inf u∈C
cho ||x − un|| −→ d, n −→ ∞. Từ đó ta có:
2 ||
||un − um||2 = ||(x − un) − (x − um)||2
= 2||x − un||2 + 2||x − um||2 − 4||x − un + um 2
≤ 2(||x − un||2 + ||x − um||2) − 4d2.
Như vậy :||un − um|| −→ 0 khin −→ ∞. Vậy {un} là dãy Cauchy trong H
un ∈ C. Từ tính liên tục của chuẩn suy ra ||x−u|| = d. nên tồn tại u = lim n→∞
Giả sử tồn tại v ∈ C sao cho ||x − v|| = d. Suy ra:
||u − v||2 = ||(x − u) + (x − v)||2
2 ||
18
= 2(||x − u||2 + ||x − v||2) − 4||x − u + v 2
≤ 0
(cid:3) Vậy u = v.
Chú ý 1.4. Phần tử PCx ∈ C là hình chiếu của x lên C khi và chỉ khi
(cid:104)y − PCx, x − PCx(cid:105) ≤ 0 với mọi y ∈ C.
(cid:107)x − u(cid:107). Với α ∈ [0, 1], ta đặt Thật vậy, giả sử (cid:107)x − PCx(cid:107) = inf u∈C
yα = αy + (1 − α)PCx.
Vì C lồi nên yα ∈ C và do đó ||x − PCx|| ≤ ||yα − x||. Điều này tương
đương với
||x − PCx||2 ≤ ||α(y − PCx) − (x − PCx)||2 = α2||y − PCx||2 + ||x − PCx||2
− 2α(cid:104)y − PCx, x − PCx(cid:105).
(cid:3) Vậy 2(cid:104)y − PCx, x − PCx(cid:105) ≤ α||y − PCx||2 −→ 0 khi α −→ 0+.
Ví dụ 1.8. Tập C = {x ∈ H : (cid:104)x, u(cid:105) = y}, u (cid:54)= 0. Khi đó
u. PC = x + y − (cid:104)x, u(cid:105) ||u||2
Mệnh đề 1.3. Cho C là một tập con lồi đóng khác rỗng của H. Với mọi
x, y ∈ H ta đều có Py+Cx = y + PC(x − y). Chứng minh. Rõ ràng y + PC(x − y) ∈ y + C. Đặt: z∗ = PC(x − y). Khi đó với mọi z ∈ C, từ Chú ý 1.4 ta có:
(cid:104)(y + z) − (y + z∗), x − (y + z∗)(cid:105) = (cid:104)z − z∗, (x − y) − z∗(cid:105) ≤ 0.
(cid:3) Suy ra Py+Cx = y + PC(x − y). Vậy ta có điều cần chứng minh.
19
Mệnh đề 1.4. Cho C là tập con lồi đóng khác rỗng của H. Khi đó với mọi
λ > 0 ta đều có
PC[PCx + λ(x − PCx)] = PCx.
Chứng minh. Với mọi y ∈ C ta có:
(cid:104)y−PCx, PCx+λ(x−PCx)−PCx(cid:105) = λ(cid:104)y−PCx, x−PCx(cid:105) ≤ 0, ∀y ∈ C.
(cid:3) Suy ra PC[PCx + λ(x − PCx)] ∈ C.
1.3 Toán tử đơn điệu, nghiệm của phương trình toán tử đơn điệu và của bất đẳng thức biến phân trong không gian Hilbert
Trong toán học, toán tử đơn điệu là một công cụ hữu ích trong việc
nghiên cứu ánh xạ nghiệm, giải tích biến phân. Mục này sẽ chúng tôi trình
bày một số khái niệm và tính chất của toán tử đơn điệu, đơn điệu cực đại,
tổng của các toán tử đơn điệu cực đại.
1.3.1. Toán tử đơn điệu
Định nghĩa 1.13. Cho hai không gian véctơ bất kỳ X và Y . Một ánh xạ
A : X −→ Y được gọi là ánh xạ tuyến tính hay toán tử tuyến tính nếu:
a) A(x1 + x2) = Ax1 + Ax2 với mọi x1, x2 ∈ X.
b) A(αx) = αAx với mọi x ∈ X và với mọi số thực α.
(i) Ở đây ta viết Ax thay cho A(x) để chỉ phần tử ứng với x Chú ý 1.5.
trong ánh xạ A.
(ii) Qua điều kiện của định nghĩa ta có điều kiện tương đương:
A(α1x1 + α2x2 + ... + αkxk) = α1Ax1 + α2Ax2 + ... + αkAxk.
20
(iii) Nếu Y = X ta nói A là một toán tử trong X.
Định nghĩa 1.14. Cho X, Y ⊂ H và A : X −→ 2Y (tập gồm toàn bộ các tập con của Y kí hiệu là 2Y ). Khi đó nói A là ánh xạ đa trị từ X vào Y .
Như vậy mỗi x ∈ X, A(x) là một tập con của Y (A(x) có thể là rỗng). Và
nếu mỗi x ∈ X, tập A(x) chỉ có một phần tử thì nói A là ánh xạ đơn trị từ
X vào Y , và kí hiệu A : X −→ Y.
Định nghĩa 1.15. Toán tử A được gọi là
(i) Nửa liên tục trên tại x ∈ domA nếu với mọi tập mở V ⊃ A(x), tồn
tại lân cận mở U của x sao cho
F (x∗) ⊆ V, ∀x∗ ∈ U.
(ii) Nửa liên tục dưới tại x ∈ domA nếu với mọi tập mở V ⊂ H thỏa
mãn A(x) ∩ V /∈ ∅ tồn tại lân cận mở U của x sao cho
A(x∗) ∩ V /∈ ∅, ∀x∗ ∈ U ∩ domF.
(iii) Toán tử A được gọi là nửa liên tục trên (nửa liên tục dưới) trên H
nếu A nửa liên tục trên (nửa liên tục dưới) tại mọi điểm thuộc H.
(iv) A được gọi là liên tục tại x ∈ domA nếu A đồng thời nửa liên tục
trên và nửa liên tục dưới tại x.
(v) Nếu A liên tục tại mọi điểm thuộc H thì A được gọi là liên tục trên
H.
Ví dụ 1.9. Cho toán tử A : R −→ 2R xác định bởi
{0} nếu x < 0
A(x) = [−1, 1] nếu x = 0
{1} nếu x > 0.
21
Khi đó A là nửa liên tục trên, trên R nhưng không liên tục dưới tại x = 0.
Thật vậy, dễ thấy A là nửa liên tục trên tại mọi x (cid:54)= 0. Hơn nữa, với mọi
tập mở (a, b) ⊃ [−1, 1] = A(0), tồn tại lân cận của 0 chẳng hạn (−1, 1), ta
có
{0} nếu − 1 < x < 0
A(x) = [−1, 1] nếu x = 0
{1} nếu 1 > x > 0.
Do đó A(x) ⊆ (a, b) với mọi x ∈ (−1, 1). Nghĩa là A(x) liên tục trên tại
x = 0. Vậy A(x) nửa liên tục trên tại x = 0. Như vậy A(x) nửa liên tục trên trên R.
Ví dụ 1.10. Cho toán tử F : R −→ 2R xác định bởi
{0} nếu x = 0 F (x) =
[−1, 1] nếu x (cid:54)= 0.
Khi đó F là nửa liên tục dưới tại x = 0, nhưng không nửa liên tục trên tại
x = 0. Thật vậy, với mọi tập mở (a, b) thỏa mãn (a, b) ∩ F (0) = {0} (cid:54)= ∅
, tồn tại lân cận của 0 chẳng hạn U = ( ), ta có −1 2 1 2
{0} nếu x = 0 F (x) =
[−1, 1] )\{0}. , nếu x ∈ ( −1 2 1 2
Do đó
, ). (a, b) ∩ F (0) (cid:54)= ∅, ∀x ∈ ( −1 2 1 2
, Lấy một lân cận mở của F (0) là V = ( ), khi đó không tồn tại lân −1 2 1 2
cận mở U của 0 sao cho
F (x∗) ⊂ ( ∀x∗ ∈ U. , ), −1 2 1 2
Do đó F không nửa liên tục trên tại x∗ = 0.
22
Định nghĩa 1.16. Cho H là một không gian Banach, toán tử A : H −→ 2H được gọi là đơn điệu nếu với mọi (x, u) và (y, v) thuộc đồ thị của gra(A)
của A (nghĩa là với mọi x, y ∈ domA, ∀u ∈ A(x), ∀v ∈ A(y)) ta luôn có
(cid:104)x − y, u − v(cid:105) ≥ 0.
Ví dụ 1.11. Cho f : H −→ R ∪ {+∞} là hàm lồi, chính thường. Ánh xạ dưới vi phân ∂f : H −→ 2H của f là toán tử đơn điệu trên dom∂f .
Thật vậy, với mọi x, y ∈ dom(∂f ), u ∈ ∂f (x), v ∈ ∂f (y) ta có
u ∈ ∂f (x) ⇔ (cid:104)u, y − x(cid:105) ≤ f (y) − f (x), ∀y ∈ H
v ∈ ∂f (x) ⇔ (cid:104)v, x − y(cid:105) ≤ f (x) − f (y), ∀y ∈ H
Vậy ta có
(cid:104)v, x − y(cid:105) − (cid:104)u, x − y(cid:105) ≤ 0
⇔ (cid:104)u − v, x − y(cid:105) ≥ 0.
Cũng có nghĩa là
(cid:104)x − y, u − v(cid:105) ≥ 0.
Hay ∂f là toán tử đơn điệu.
Định nghĩa 1.17 Một toán tử đơn điệu A : H −→ 2H được gọi là đơn điệu cực đại nếu đồ thị gra(A) = {(u, x) : x ∈ domA, u ∈ A(x)} của nó
không thực sự chứa trong đồ thị của một toán tử đơn điệu nào khác trên H.
Ví dụ 1.12 Cho f : E −→ R là một hàm lồi chính thường nửa liên
tục dưới. Khi đó, toán tử dưới vi phân
∂f (x) = {x∗ ∈ E∗ : f (y) − f (x) ≥ (cid:104)y − x, x∗(cid:105), ∀y ∈ E}
23
là một toán tử đơn điệu cực đại.
Ví dụ 1.13 Xét T : R −→ 2R xác định như sau :
1 nếu x > 0
T (x) = [0, 1] nếu x = 0
−x2 nếu x < 0.
là toán tử đơn điệu cực đại.
Thật vậy, với mọi M (x, y) /∈ gra(T ) ta luôn tìm được ít nhất điểm
−−→ OM và M0(x0, y0) ∈ gra(T ) sao cho góc giữa −−→ OM0 là góc tù. Nghĩa là
−−→ OM . (cid:104)(x, y), (x0, y0)(cid:105) = −−→ OM0 < 0.
Vậy T là toán tử đơn điệu cực đại.
Định lí 1.13 (Định lý Minty) Cho A là một toán tử đơn điệu từ H đến 2H. Khi đó A được gọi là đơn điệu cực đại khi và chỉ khi ran(Id+λA) = H
với mọi λ > 0, ở đây ran(Id + λA) là miền ảnh của toán tử Id + λA và
Id là toán tử đồng nhất trên H.
1.3.2. Nghiệm của phương trình toán tử đơn điệu và của bất đẳng thức biến phân trong không gian Hilbert
Cho H là không gian Hilbert thực, toán tử A : H −→ 2H là đơn điệu
cực đại, khi đó bài toán bao hàm thức đơn điệu cực đại được phát biểu như
sau
Tìm z ∈ H sao cho 0 ∈ A(z).
24
Nếu toán tử A là đơn trị thì đây là bài toán giải phương trình A(z) = 0.
Nếu toán tử A là đa trị thì đây là bài toán tìm không điểm của toán tử đơn
điệu cực đại A. Về mặt hình thức bài toán này khá đơn giản, tuy nhiên nó
bao hàm được nhiều lớp bài toán quan trọng khác thuộc nhiều lĩnh vực như
bài toán cực tiểu hàm lồi, bài toán bất đẳng thức biến phân, bài toán bù, bài
toán điểm bất động. Dưới đây chúng ta trình bày hai trường hợp riêng điển
hình nhất của bài toán bao hàm thức đơn điệu cực đại.
1.3.2.1. Bài toán cực tiểu hàm lồi
Ở phần trước ta đã biết, nếu A là dưới vi phân của một hàm lồi, chính thường và nửa liên tục dưới f : H −→ R ∪ {+∞} (tức là A = ∂f ) thì A
là toán tử đơn điệu cực đại và khi đó bài toán tìm z ∈ H sao cho 0 ∈ A(z)
sẽ trở thành bài toán
f (x) = f (z) và 0 ∈ Az Tìm z ∈ H sao cho min x∈H
và được gọi là bài toán cực tiểu hàm lồi. Thật vậy, ta có 0 ∈ A(z) khi và
chỉ khi 0 ∈ ∂f (z), theo định nghĩa dưới vi phân hàm lồi
(cid:104)0, u − z(cid:105) ≤ f (u) − f (z), ∀u ∈ H
⇔ f (z) ≤ f (u), ∀u ∈ H.
Như vậy việc tìm không điểm của toán tử đơn điệu cực đại A = ∂f tương
đương với việc tìm cực tiểu của hàm lồi và nửa liên tục dưới f .
1.3.2.2. Bài toán bất đẳng thức biến phân đơn điệu
Cho C là một tập lồi, đóng, khác rỗng trong không gian Hilbert H,
T0 : C −→ H là một toán tử đơn điệu đơn trị và bán liên tục và NC(z) là
25
nón pháp tuyến ngoài của C tại z ∈ C, đặt
nếu z ∈ C T0(z) + NC(z) T (z) =
nếu z /∈ C. ∅
Khi đó T là toán tử đơn điệu cực đại và bài toán tìm không điểm của toán
tử T quy về bài toán
(1.4) Tìm z ∈ C sao cho (cid:104)T0(z), u − z(cid:105) ≥ 0, ∀u ∈ C
và được gọi là bài toán bất đẳng thức biến phân đơn điệu trong không gian
Hilbert. Thật vậy ta có 0 ∈ T (z) khi và chỉ khi
0 ∈ T0(z) + NC(z)
tương đương với
−T0(z) ∈ NC(z).
Theo định nghĩa nón pháp tuyến ngoài của tập C tại z ∈ C ta có
(cid:104)T0(z), u − z(cid:105) ≥ 0, ∀u ∈ C.
Như vậy bài toán tìm z ∈ C sao cho 0 ∈ T (z) tương đương với bài toán
bất đẳng thức biến phân đơn điệu (1.4).
Nếu C là một nón thì bài toán trên trở thành bài toán
Tìm z ∈ C sao cho − T0(z) ∈ C 0 và (cid:104)T0(z), z(cid:105) = 0.
Điều này chỉ ra rằng z là không điểm của ánh xạ đơn điệu cực đại T khi
và chỉ khi z là nghiệm của bài toán bất đẳng thức biến phân đơn điệu. Như
vậy ta có thể thay thế việc giải bài toán bất đẳng thức biến phân đơn điệu
bằng việc tìm không điểm của ánh xạ đơn điệu cực đại T .
26
Trong Chương 1 chúng tôi đã nhắc lại một số vấn đề cơ bản, những
kiến thức này là cơ sở cho việc trình bày chương sau. Trong chương tiếp
theo chúng tôi trình bày bài toán tìm giao điểm của hai không gian con
đóng và trình bày phương pháp Dykstra tìm không điểm của tổng hai toán
tử đơn điệu.
27
Chương 2
Phương pháp Dykstra lai ghép cho hai toán
tử đơn điệu
Trong chương này chúng tôi trình bày thuật toán Neumann tìm giao
điểm của hai không gian con đóng và phương pháp Dykstra lai ghép cho
hai toán tử đơn điệu. Các kết quả trình bày dựa trên tài liệu số [5].
2.1 Bài toán tìm giao điểm của hai không gian con đóng
và thuật toán Neumann
Trước hết chúng tôi nhắc lại một số định nghĩa và kí hiệu hay dùng
trong chương này.
Kí hiệu 2.1. Giả sử A: H −→ 2H là toán tử. Thì :
domA = {x ∈ H| Ax (cid:54)= ∅}, là miền hữu dụng (miền xác định) của A;
ranA = {u ∈ H| (∃x ∈ H) u ∈ Ax}, là khoảng biến thiên giao độ
(miền ảnh) của A;
zerA = {x ∈ H| 0 ∈ Ax}, là tập 0 điểm của A;
gra(A) = {(x, u) ∈ H × H| u ∈ Ax}, là đồ thị của A. Ánh xạ ngược của A là toán tử A−1 : H −→ 2H với đồ thị của A−1 là
{(x, u) ∈ H × H| u ∈ Ax}. Toán tử giải của A là JA = (Id + A)−1. Chúng tôi xây dựng toán tử A∼
28
như sau
A∼ :H −→ 2H
x (cid:55)→ A∼(x) = −A−1(−x).
Chú ý 2.1. Bây giờ giả sử A đơn điệu, nghĩa là, cho mỗi (x, u) và (y, v)
trong gra(A),
(cid:104)x − y, u − v(cid:105) ≥ 0 (2.1)
thì JA : ran(Id + A) −→ H là ánh xạ đơn trị. Hơn nữa, toán tử A là đơn
điệu cực đại khi tính chất sau thỏa mãn, cho mỗi (x, u) ∈ H × H, nếu (2.1)
đúng cho mỗi (y, v) ∈ gra(A), thì (x, u) ∈ gra(A). Định lí của Minty
khẳng định rằng A là đơn điệu cực đại nếu và chỉ nếu ran(Id + A) = H.
Trong trường hợp này, ta có
(2.2) JA−1 = Id − JA và (JA−1)∼ = Id + A∼.
Cuối cùng, phần trong tương đối của C tập con lồi trong H là
λ>0
(cid:91) sriC = {x ∈ C| λ(C − x) = span(C − x)}. (2.3)
∗ ∈ D(x)},
Định nghĩa 2.1. Cho C và D là hai toán tử đơn điệu từ H đến 2H, thì C + D được xác định như sau
∗ + x2
∗ : x1
∗ ∈ C(x), x2
(C + D)(x) = C(x) + D(x) = {x1
là toán tử đơn điệu.
Định lí 2.1. (Thuật toán của Von Neumann, xem [5] và tài liệu trích dẫn)
Cho z ∈ H, cho U và V là các không gian véctơ con đóng của H, và đặt
(2.4) x0 = z và (∀n ∈ N ) yn = PV xn và xn+1 = PU yn.
29
Thì xn −→ PU ∩V z và yn −→ PU ∩V z.
Kết quả này không đúng cho trường hợp khi U và V là giao hai tập
đóng, lồi. Trước tiên, kết quả này đúng khi các dãy vô hạn (xn)n∈N và
(yn)n∈N trong (2.4) là hội tụ yếu, và có thể không đúng khi chúng hội tụ
mạnh; thứ hai, có thể chỉ ra ví dụ đơn giản mà điểm giới hạn không là
hình chiếu của z lên U ∩ V . Trong trường hợp U và V là các nón lồi, đóng
trong không gian Euclid, một cải biên của phép lặp ở (2.4), được phát biểu
bằng thuật toán Dykstra dưới dạng (2.5). Kết quả này được mở rộng cho
tập đóng lồi (xem [5], và tài liệu trích dẫn).
Định lí 2.2. (Thuật toán của Dykstra) Cho z ∈ H, cho U và V là các tập
con đóng, lồi của H, sao cho U ∩ V (cid:54)= ∅ và đặt
x0 = z,
yn = PV (xn + pn), và (∀n ∈ N ) p0 = 0,
pn+1 = xn + pn − yn, (2.5) q0 = 0,
xn+1 = PU (yn + qn), và
qn+1 = yn + qn − xn+1.
Thì xn −→ PU ∩V z và yn −→ PU ∩V z.
2.2 Phương pháp Dykstra tìm không điểm của tổng hai
toán tử đơn điệu
Cho C và D là hai toán tử đơn điệu, cực đại từ H đến 2H. Bao hàm thức 0 ∈ Cx + Dx với bao hàm thức đối ngẫu 0 ∈ C −1u + D∼u dễ dàng
được phân tích cho bài toán phi tuyến với đối ngẫu bao hàm. Nghĩa là có
mệnh đề tương đương:
zer(C + D) (cid:54)= ∅ ⇔ zer(C −1 + D∼) (cid:54)= ∅. (2.6)
30
Hiện tượng đối ngẫu này được chứng minh đặc biệt trong việc nghiên cứu
tính tiệm cận của tổ hợp hai toán tử giải (xem [5] và tài liệu trích dẫn).
Trong mục này ta xét sự liên quan giữa (2.5) và (2.14) trong đó xuất hiện
toán tử xấp xỉ.
Kí hiệu 2.2. Một hàm f : H −→ [−∞; +∞] là hàm chính thường nếu
domf = {x ∈ H| f (x) < +∞} (cid:54)= ∅. Lớp các hàm thực lồi, chính thường
và nửa liên tục dưới yếu, từ H vào [−∞; +∞], kí hiệu là Γ0(H). Và với f ∈ Γ0(H), liên hợp của f là f ∗ ∈ Γ0(H), được định nghĩa như sau
(cid:104)x, u(cid:105) − f (x), f ∗ : u (cid:55)→ sup x∈H
dưới vi phân của f là toán tử đơn điệu cực đại
∂f :H −→ 2H (2.7) x (cid:55)→ u ∈ H|(∀y ∈ H)(cid:104)y − x, u(cid:105) + f (x) ≤ f (y).
Tập hợp các điểm đạt cực tiểu của f là arg min f = zer∂f , bao hình
Moreau của f là hàm lồi liên tục:
+ ||x − y||2, (2.8) envf : H −→ R : x (cid:55)→ inf y∈H 1 2
và hàm phản xạ của hàm f là f v : x (cid:55)→ f (−x).
Với mỗi x ∈ H, hàm y (cid:55)→ f (y) + ||x − y||2/2 có điểm cực tiểu duy
nhất, được xác định bởi proxf x. Còn nếu không thì, proxf x = J∂f .
Mệnh đề 2.1. C và D là hai toán tử đơn điệu cực đại từ H đến 2H. Thì zer(C + Id − JD) (cid:54)= ∅ nếu và chỉ nếu JC −1+D∼0 tồn tại, trong trường hợp này ta có zer(C −1 + Id + D∼) = JC −1+D∼0.
Chứng minh. Về bản chất JC −1+D∼0 là nghiệm duy nhất của bao hàm 0 ∈ (C −1 + Id + D∼)u, nghĩa là, trong zer(C −1 + Id + D∼) tồn tại điểm
31
duy nhất. Mặt khác, từ (2.6), áp dụng cho C là toán tử đơn điệu, cực đại và
JD−1, và từ (2.2) ta có
zer(C + Id − JD) (cid:54)= ∅ ⇔ zer(C −1 + (JD−1)∼) (cid:54)= ∅ (2.9) ⇔ zer(C −1 + Id + D∼) (cid:54)= ∅.
(cid:3) Vậy định lí đã được chứng minh.
Định lí 2.3. C và D là hai toán tử đơn điệu cực đại từ H đến 2H, và cho
(2.10) u0 ∈ H và (∀n ∈ N )(vn) = JDun và un+1 = JCvn.
Khi đó,
i) Nếu zer(C + Id − JD) (cid:54)= ∅ thì vn − un −→ JC −1+D∼0
và vn − un+1 −→ JC −1+D∼0.
ii) Nếu zer(C + Id − JD) = ∅ thì ||un|| −→ +∞ và ||vn|| −→ +∞.
Kết quả chính của mục này là định lý về tính tiệm cận của mở rộng (2.5) từ
việc chiếu lên tập lồi đóng của toán tử giải của toán tử đơn điệu cực đại.
Định lí 2.4. sử z ∈ H, cho A và B là hai toán tử đơn điệu, cực đại từ H đến 2H, và
x0 = z,
yn = JB(xn + pn), và (∀n ∈ N ) p0 = 0,
pn+1 = xn + pn − yn, (2.11) q0 = 0,
xn+1 = JA(yn + qn), và
qn+1 = yn + qn − xn+1.
Khi đó,
32
i) Nếu z ∈ ran(Id + A + B) thì xn −→ JA+Bz
và yn −→ JA+Bz.
ii) Nếu z /∈ ran(Id + A + B) thì ||pn|| −→ +∞ và ||qn|| −→ +∞.
Chứng minh. Từ (2.11) ta có
(∀n ∈ N ) pn+1 + qn + yn = xn + pn − yn + qn + yn (2.12)
= xn + pn + qn.
Mặt khác, (∀n ∈ N ) pn + qn = z − xn. Theo (2.11), đồng nhất thức này
chắc chắn đúng khi n = 0. Và, nếu pn + qn = z − xn đúng với một vài giá
trị của n ∈ N , sau đó pn+1 +qn+1 = xn +pn −yn +yn +qn −xn = z −xn+1.
Ta có
(∀n ∈ N ) (2.13) z = pn+1 + qn + yn = pn + qn + xn.
Ta có thể viết lại (2.11) như sau
x0 = z,
yn = JB(z − qn), và (∀n ∈ N ) p0 = 0,
pn+1 = z − qn − yn, (2.14) q0 = 0,
xn+1 = JA(z − pn), và
qn+1 = z − pn+1 − xn+1.
Bây giờ đặt
(2.15) u0 = −z và (∀n ∈ N ) un = qn − z và vn = −pn+1.
Từ (2.15) và (2.13) ta có
(∀n ∈ N ) vn − un = −pn+1 − qn + z = yn (2.16)
và vn − un = −pn+1 − qn+1 + z = xn+1.
33
Tiếp theo, từ (2.15) và (2.14), các dãy (un)n∈N và (vn)n∈N thỏa mãn phương
trình
(∀n ∈ N ) vn = −pn+1 = qn − z + yn
= un + JB(−un), (2.17)
un+1 = qn+1 − z = −pn+1 − xn+1
= vn − JA(vn + z).
Bây giờ ta định nghĩa hai toán tử cực đại như sau
C : H −→ 2H : v −→ A−1(v + z) và D = B∼. (2.18)
Dễ thấy
C −1 = −z + A và D∼ = B. (2.19)
Hơn nữa,(2.2) cho ta kết quả
(∀u ∈ H)(∀v ∈ H) u =v − JA(u + v)
⇔ u + z =v + z − JA(v + z) = JA−1(v + z) (2.20)
⇔ v − u ∈A−1(u + z) = Cu
⇔ u =JCv,
và
(∀u ∈ H)u + JB − u = −(−u − JB(−u)) (2.21)
= −JB−1(−u) = JDu.
Do đó chúng ta viết lại (2.17) như sau
(2.22) (∀n ∈ N )vn = JDun và un+1 = JCvn.
Đây chính là quá trình lặp trong (2.10) với điểm đầu tiên u0 = −z. Mặt
khác, từ (2.19), với mỗi x ∈ H, ta có:
x = JA+Bz ⇔ 0 ∈ x + (−z + Ax + Bx) (2.23)
⇔ x = J(−z+A)+B0 = JC −1+D∼0.
34
Vì vậy,
z ∈ ran(Id + A + B) ⇔ z ∈ dom(Id + A + B)−1
⇔ JA+Bz exits
(2.24) ⇔ JC −1+D∼0 exits.
Do đó, từ Mệnh đề 2.1 và Định lí 2.3 ta có kết quả sau
i) Nếu z ∈ ran(Id + A + B), theo (2.16) ta có
yn = vn − un −→ JC −1+D∼0 = JA+Bz,
và
xn+1 = vn − un+1 −→ JC −1+D∼0 = JA+Bz.
ii) Nếu z /∈ ran(Id + A + B), thì (2.15) tương đương với
||pn+1|| = ||vn|| −→ +∞ và ||qn|| = ||un+z|| ≥ ||un||−||z|| −→ +∞.
Chú ý 2.2. Giả sử trong Định lí 2.4 ta bổ sung giả thiết A + B là toán tử
đơn điệu cực đại, điều đó đúng khi 0 ∈ sri(domA − domB); (xem [5] và
tài liệu trích dẫn) thì kết luận (ii) không đúng trong Định lí 2.4 nên do đó
(∀z ∈ H) xn −→ JA+Bz và yn −→ JA+Bz. Từ đây, ta có kết quả sau.
Định lí 2.5. Cho ϕ và ψ là hàm trong Γ0(H) sao cho
inf(ϕ + envψ)(H) > −∞ (2.25)
và lấy
(2.26) u0 ∈ H và (∀n ∈ N )vn = proxψun và un+1 = proxϕvn
thì ta có
35
i) Hàm ϕ∗ + ψ∗ + ||.||2/2 có điểm cực tiểu duy nhất w, vn − un −→ w
và vn − un+1 −→ w.
ii) Nếu arg min ϕ + envψ = ∅ thì ||un|| −→ +∞ và ||vn|| −→ +∞.
Định lí 2.6. sử z ∈ H, cho f và g là hàm trong Γ0(H) sao cho
domf ∩ domg (cid:54)= ∅. (2.27)
Đặt
x0 = z,
yn = proxg(xn + pn), và (∀n ∈ N ) p0 = 0,
pn+1 = xn + pn − yn, (2.28) q0 = 0,
xn+1 = proxf (yn + qn), và
qn+1 = yn + qn − xn+1.
Khi đó,
i) xn −→ proxf +gz và yn −→ proxf +gz.
ii) Nếu arg min f ∗(. + z) + envg∗v = ∅ thì ||pn|| −→ +∞
và ||qn|| −→ +∞.
Chứng minh. Đặt A = ∂f , B = ∂g. Thì JA = proxf , JB = proxg, và
(2.28) là trường hợp đặc biệt của (2.11). Chúng ta đặt như trong (2.15),
(2.29) u0 = −z và (∀n ∈ N ) un = qn − z và vn = −pn+1.
Thì ta đạt được như trong (2.16),
(2.30) (∀n ∈ N ) vn − un = yn và vn − un+1 = xn+1.
36
Và như ở (2.17)
(∀n ∈ N ) vn = un + proxg(−un) (2.31)
và un+1 = vn − proxf (vn + z).
Bây giờ định nghĩa hai hàm trong Γ0(H) như sau:
ϕ : H −→ [−∞; +∞]
(2.32) . v (cid:55)→ f ∗(v + u) − ||z||2 và ψ = g∗v 1 2
Thì
ϕ∗ = f − (cid:104)., z(cid:105) + ||z||2, ψ∗ = gv,
(2.33)
||.||2. 1 2 và (envψ)∗ = gv + 1 2
Do đó với mọi x ∈ H, ta có
ϕ∗(x) + ψ∗(x) + ||x||2 =f (x) − (cid:104)x, z(cid:105) + ||z||2 1 2
1 2 ||x||2. + g(x) + (2.34) 1 2
=(f + g)(x) + ||z − x||2. 1 2
Bây giờ, đặt C = ∂ϕ và D = ∂ψ, theo (2.32), ta có
(∀v ∈ H), Cv =∂f ∗(v + z) = A−1(v + z) (2.35)
và Dv = − ∂g∗(−v) = B∼v.
Vì thế, từ (2.20) và (2.21) ta có
(∀v ∈ H) proxϕv =v − proxf (v + z) (2.36)
và proxψv =v + proxg(−v).
Mà ta thấy khi đưa (2.31) về sơ đồ lặp (2.26) với bắt đầu bằng khởi động
u0 = −z. Mặt khác, từ (2.32) cho ta kết luận:
ϕ + envψ = f ∗(. + z) − ||z||2 + envg∗v. (2.37) 1 2
37
Do đó, từ (2.33) và tính đối ngẫu Fenchel ta có
(2.27) ⇔ f + g ∈ Γ0(H)
||z − .||2 (cid:54)= ∅ ⇔ arg min f + g + ⇒ proxf +gz exists 1 2
⇔ arg min f − (cid:104)., z(cid:105) + ||z||2 + g + ||.||2 (cid:54)= ∅ 1 2 1 2
⇔ arg min ϕ∗ + (envψ)∗v (cid:54)= ∅
⇔ inf(ϕ + envψ)(H) > −∞
⇔ (2.25). (2.38)
Bây giờ ta có kết luận
i) Theo (2.34), điểm đạt cực tiểu ϕ∗ + ψ∗v + ||.| |2/2 là w = proxf +gz.
Vì vậy, từ Định lí 2.6(i) và (2.30) ta có:
yn = vn − un −→ proxf +gz và xn+1 = vn − un+1 −→ proxf +gz.
ii) Từ (2.37), ta có arg min f ∗(. + z) + envg∗v = ∅ và ta suy ra được
arg min ϕ + envψ = ∅. Lần lượt, do Định lý 2.5(ii) và (2.29) ta có
||pn+1|| = ||vn|| −→ +∞
và
||qn+1|| = ||un + z|| > ||un|| − ||z|| −→ +∞.
(cid:3)
Chú ý 2.3. Định lý 2.6 chính xác hơn Định lý 2.4 khi áp dụng cho A = ∂f
và B = ∂g. Thực vậy, từ: ∂f + ∂g ⊂ ∂(f + g), ta có với mọi p ∈ H,
p = J∂f +∂gz ⇔ z − p ∈ ∂f (p) + ∂g(p) ⇒ z − p ∈ ∂(f + g)(p)
38
(2.39) ⇔ p = proxf +gz.
Qua Định lý 2.4 , ta có
(2.40) xn −→ proxf +gz và yn −→ proxf +gz,
miễn là
z ∈ ran(Id + ∂f + ∂g). (2.41)
Một điều kiện đủ cơ bản cho kết luận này là cho z ∈ H có:
0 ∈ sri(domf − domg). (2.42)
(xem [5]), và tài liệu trích dẫn). Mặt khác, trong Định lý 2.6(i), ta đạt được
(2.40) cho mỗi z ∈ H với (2.27), nghĩa là,
0 ∈ (domf − domg). (2.43)
Từ đó (2.43) là ít hạn chế hơn (2.41).
Lưu ý là với điều kiện (2.42), phương pháp luân hướng để tính toán
p = proxf +gz cho tùy ý z ∈ H là thuật toán Douglas–Rachford cho tính
toán không điểm của tổng hai toán tử đơn điệu cực đại (xem [5], và tài liệu
trích dẫn).
Thật vậy, từ (2.42), p đặc trưng bởi bao hàm
0 ∈ ∂(f + g)(p) = ∂f + ∂g + p − z = Cp + Dp,
khi C = −z + ∂f và D = Id + ∂g là đơn điệu cực đại.
Chú ý 2.4. Chof và g là hàm chỉ của các tập con đóng lồi U và V của H.
Thì theo Định lý 2.6(i) qui về Định lý 2.2. Nếu chúng ta mở rộng cho U
39
và V là các không gian con đóng, thì ta đạt được Định lý 2.1, từ đó trong
trường hợp này (2.5) cho ta kết quả
(∀n ∈ N ) yn = PV (xn + pn) = PV xn + PV pn = PV xn
và xn+1 = PU (yn + qn) = PU yn + PU qn = PU yn.
40
Kết luận
Đề tài đã trình bày về toán tử đơn điệu trong không gian Hilbert và giới
thiệu bài toán tìm giao điểm của hai không gian con đóng.
Đề tài cũng đã trình bày thuật toán của Neumann và phương pháp Dykstra
lai ghép cho hai toán tử đơn điệu.
Đóng góp của tác giả luận văn là tìm hiểu, nghiên cứu tài liệu, tổng hợp
kiến thức và làm chi tiết hơn một số chứng minh.
41
Tài liệu tham khảo
Tiếng Việt
[1] Nguyễn Văn Hiền, Lê Dũng Mưu (2003), Nhập môn Giải tích lồi và
ứng dụng, Viện Toán học, Hà Nội.
[2] Đỗ Văn Lưu, Phan Huy Khải (2000), Giải tích lồi, Nxb Khoa học và
Kỹ thuật, Hà Nội.
[3] Hoàng Tụy (2003), Hàm thực và Giải tích hàm, Nxb Đại học Quốc
gia, Hà Nội.
[4] Nguyễn Đông Yên (2007), Giáo trình Giải tích đa trị, Nxb Khoa học
tự nhiên và Công nghệ.
Tiếng Anh
[5] Bauscheke H. H. and Combettes D. L. (2008), "A Dykstra-like algo-
rithm for two monotone operators", Pacific Journal of Optimization,
vol. 4, pp. 383-391.
[6] Lions J. L. and Stampacchia G. (1967), Variational Inequalities,
Comm. Pure Appl. Math., 20, 493 - 519.
