fantasyforever91
New Member
Download miễn phí Luận văn Thuật toán dưới gradient và phương pháp chỉnh lặp song song
Mục lục
Mở đầu 1
1. Một số kiến thức chuẩn bị 3
1.1. ánh xạ không giãn . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. ánh xạ hút và dãy đơn điệu Fejer . . . . . . . . . . . . . . . . . 6
1.3. Mô tả thuật toán tổng quát . . . . . . . . . . . . . . . . . . . . . . 14
1.4. Một số tính chất cơ bản . . . . . . . . . . . . . . . . . . . . . . . 15
2. Một số thuật toán chiếu 24
2.1. Xây dựng thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2. Một số kết quả hội tụ . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3. Một số điều kiện đảm bảo sự hội tụ theo chuẩn và hội tụ tuyến tính 34
2.4. Một vài ví dụ về tính chính quy tuyến tính (bị chặn) . . . . . . . . 39
3. Thuật toán dưới gradient và phương pháp chỉnh lặp song song 41
3.1. Thuật toán dưới gradient . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.1. Cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.1.2. Các kết quả hội tụ . . . . . . . . . . . . . . . . . . . . . . 47
3.2. Phương pháp chỉnh lặp song song . . . . . . . . . . . . . . . . . . 50
3.2.1. Một số kết quả bổ trợ . . . . . . . . . . . . . . . . . . . . . 50
3.2.2. Một số ví dụ minh hoạ . . . . . . . . . . . . . . . . . . . . 51
3.3. Một vài thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . . . 55
3.3.1. Bài toán với Ci
là hình cầu . . . . . . . . . . . . . . . . . . 55
3.3.2. Bài toán với Ci
là tập mức dưới của một hàm lồi . . . . . . 57
3.3.3. Phương pháp chỉnh lặp trong không gian vô hạn chiều . . . 61
Kết luận 62
Tài liệu tham khảo 63
Phụ lục 65
A Một số điểm lưu ý khi tính dưới vi phân 65
1.1. Một vài tính chất của dưới vi phân . . . . . . . . . . . . . . . . . 65
1.2. Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Nếu (snk) là một dãy hội tụ yếu với snk ∈ Snk với mọi k, thì giới hạnyếu của nó nằm trong S.
(iii) Nếu (xnk) là một dãy hội tụ yếu với xnk − PSnkxnk −→ 0 thì giới hạn yếu
của nó nằm trong S.
Hơn nữa, nếu một trong các điều kiện trên được thỏa mãn thì S =
⋂
n
Sn.
Định lý 4 (Dạng thứ nhất của một thuật toán chiếu tụ). Nếu (P
(n)
i ) hội tụ từng
điểm tới Pi với mọi chỉ số i, thì thuật toán chiếu là tụ và Ci =
⋂
n:n thiết thực cho i
C
(n)
i
với mọi chỉ số i.
Chứng minh: Với mỗi i, áp dụng bổ đề 3 cho dãy tập (C
(n)
i )n:n thiết thực cho i. Ơ
Ví dụ 8. Giả sử rằngCi =
⋂
n
C
(n)
i và dãy tập (C
(n)
i ) là dãy giảm. Khi đó thuật toán
chiếu là tụ. Nếu thêm giả thiết thuật toán chiếu là lặp đoạn và lim inf
n:n thiết thực cho i
àni > 0
với mọi chỉ số i thì dãy (x(n)) là chính quy tiệm cận và hội tụ yếu tới một điểm
thuộc C.
Chứng minh: Mosco đã chứng minh rằng dãy giảm các tập lồi đóng thì hội tụ
theo nghĩa Mosco tới giao của dãy tập ấy. Theo định lý và bổ đề vừa nêu trên,
thuật toán chiếu là tụ. Kết quả được suy ra từ định lý 3(i). Ơ
Ví dụ 9 (Về phép chiếu ngẫu nhiên). Giả sử rằng thuật toán chiếu là suy biến,
không nới lỏng và có các tập hằng. Nếu với một chỉ số j nào đó tập Cj compact
bị chặn (tức là giao của nó với mọi tập bị chặn là tập compact) thì dãy (x(n)) hội
tụ theo chuẩn tới một điểm thuộc C. Nói riêng, điều này đúng nếu X là không
gian hữu hạn chiều.
Chứng minh: Ví dụ trên chỉ ra rằng thuật toán là tụ. Đồng thời, à
(n)
i ≡ 1 với mọi
n ≥ 0 và mọi chỉ số i thiết thực tại n. Dãy (x(n))n:n thiết thực cho j bị chặn và nằm
trong Cj do đó có một điểm dính theo chuẩn. Theo định lý 2, toàn bộ dãy (x
(n))
hội tụ theo chuẩn tới một điểm thuộc C. Ơ
25
Để có thể đưa ra dạng thứ hai của một thuật toán chiếu tụ cũng như các kết quả
hội tụ và hội tụ tuyến tính trong các mục tiếp sau, ta cần định nghĩa sau.
Định nghĩa 12. Ta nói một thuật toán chiếu là tụ tuyến tính nếu tồn tại một số
β > 0 sao cho:
βd(x(n), Ci) ≤ d(x(n), C(n)i ) với mọi n đủ lớn và mọi chỉ số i thiết thực tại n .
Ta nói thuật toán là tụ mạnh nếu
x(nk) ⇀ x
d(x(nk), C
(nk)
i ) → 0
i thiết thực tại nk
⇒ d(x
(nk), Ci) = ‖x(nk) − Pix(nk)‖ → 0
với mọi chỉ số i và mọi dãy con x(nk) của x(n).
Từ định nghĩa về tính tụ và tính nửa liên tục dưới của hàm khoảng cách
d(., Ci) ta suy ra
tụ tuyến tính⇒ tụ mạnh⇒ tụ
Từ nhận xét trên ta dễ dàng suy ra bổ đề sau đây.
Hệ quả 10 (Dạng thứ hai của một thuật toán chiếu tụ). Mọi thuật toán chiếu tụ
tuyến tính đều tụ.
Hệ quả 11 (Dạng của một thuật toán chiếu tụ tuyến tính). Nếu thuật toán chiếu
có các tập hằng thì nó tụ tuyến tính.
Hệ quả 12 (Dạng của một thuật toán chiếu tụ mạnh). Giả sử thuật toán chiếu là
tụ. Nếu dãy (x(n)) là một tập compact tương đối thì thuật toán là tụ mạnh. Nói
riêng, điều này đúng khi X là không gian hữu hạn chiều hay phần trong của tập
C khác rỗng.
Chứng minh: Giả sử ngược lại, tồn tại một số ε > 0, phần tử x ∈ X , một chỉ số i
và một dãy con (x(nk))k với x
(nk) → x, x(nk)−P (nk)i x(nk) → 0, i thiết thực tại nk,
nhưng ‖x(nk) − Pix(nk)‖ ≥ ε. Do thuật toán là tụ ta có x ∈ Ci. Chuyển qua dãy
26
con nếu cần thiết, ta có thể giả sử (do tính compact tương đối) rằng x(nk) −→ x.
Nhưng khi đó x(nk)−Pix(nk) → x−Pix = 0, vô lý. Do đó, thuật toán chiếu là tụ
mạnh. Nếu X là hữu hạn chiều, dãy (x(n)) là tập compact tương đối vì dãy (x(nk))
bị chặn (bổ đề 2(iv)). Cuối cùng, nếu intC 6= ∅ thì dãy (x(n)) hội tụ theo chuẩn
(theo hệ quả 4(i)). Ơ
Chú ý 3. Hai dạng của thuật toán chiếu tụ (định lý 4 và hệ quả 10) không có
liên hệ gì với nhau.
Hai ví dụ sau đây chỉ ra điều này.
Ví dụ 10. Giả sử rằng X := R, N = 1, C := C1 = {0}, C(n)1 := [0, 1/(n+1)]
và x(0) = 2. Khi đó thuật toán chiếu là tụ mạnh và dãy giảm các tập lồi compact
C
(n)
1 hội tụ tới C1 theo nghĩa Mosco. Tuy nhiên thuật toán chiếu là không tụ tuyến
tính. Thật vậy, với n ≥ 1
x(n) =
1
n
;
d(x(n), C
(n)
1 )
d(x(n), C1)
=
1
n+ 1
→ 0.
Ví dụ 11. Giả sử rằng X := R; N := 1; C := C1 = {0}, C(n)1 := (−1)n[0, 1]
và x(0) ∈ X tùy ý. Khi đó thuật toán là tụ mạnh vì x(n) ≡ 0 ∈ C với mọi n ≥ 2.
Tuy nhiên, dãy tập compact lồi C
(n)
1 không hội tụ về C theo nghĩa Mosco.
2.2. Một số kết quả hội tụ
Định lý 5 (Định lý loại trừ II). Giả sử rằng thuật toán chiếu là tụ tuyến tính và
tồn tại một số ε > 0 sao cho ε ≤ α(n)i ≤ 2 − ε với mọi n đủ lớn và mọi chỉ số i
thiết thực tại n. Khi đó, dãy x(n) hay hội tụ theo chuẩn hay không có điểm dính
theo chuẩn nào.
Chứng minh: Giả sử ngược lại, (x(n)) có ít nhất hai điểm dính theo chuẩn là y
và z. Do tính tụ tuyến tính, ta có thể chọn được số β > 0 sao cho βd(x(n), Ci) ≤
d(x(n), C
(n)
i ) với mọi l đủ lớn và mọi chỉ số i thiết thực tại l. Cố định c ∈ C. Do
27
y 6∈ C(vì nếu y ∈ C thì dãy (x(n)) sẽ hội tụ theo chuẩn theo bổ đề 4), tập các chỉ
số I = {i ∈ {1, . . . , N} : y 6∈ Ci} là khác rỗng. Ta đặt B := y + rBX trong đó
r := 12 min({‖y − z‖} ∪ {d(y, Ci) : i ∈ I}).
Khẳng định I.
Tồn tại số γ1 > 0 để với l đủ lớn, x
(l) ∈ B suy ra ‖x(l) − c‖ − ‖x(l+1) − c‖ ≥
γ1
∑
i∈I
λ
(l)
i .
Thật vậy, từ bổ đề 2(ii), định nghĩa số β, và ‖y−x(l)‖ ≥ d(y, Ci)−d(x(l), Ci)(ánh
xạ khoảng cách là không giãn), ta có
‖x(l) − c‖2 − ‖x(l+1) − c‖2 ≥
∑
i∈I
à
(l)
i d
2(x(l), C
(l)
i )
≥
∑
i∈I
λ
(l)
i ε
2β2d2(x(l), Ci)
≥ ε2β2r2
∑
i∈I
λ
(l)
i
Mặt khác,
‖x(l)−c‖2−‖x(l+1)−c‖2 = (‖x(l)−c‖−‖x(l+1)−c‖)ì(‖x(l)−c‖+‖x(l+1)−c‖)
và chuẩn của nhân tử phía sau lớn nhất chỉ là 2(r+‖y− c‖). Như vậy, số γ1 trong
khẳng định có thể chọn là
ε2β2r2
2(r + ‖y − c‖) . Khẳng định I được chứng minh.
Khẳng định II.
Tồn tại số γ2 > 0 để với l đủ lớn, x
(l) ∈ B suy ra ‖x(l+1) − c‖ − ‖x(l) − c‖ ≤
γ2
∑
i∈I
λ
(l)
i .
Thật vậy, với mọi chỉ số i ∈ {1, . . . , N} \ I , điểm y bất động qua ánh xạ R(l)i . Do
28
đó ta có đánh giá:
‖x(l+1) − y‖ =
∥∥∥∥∥∥
∑
i∈{1,...,N}\I
λ
(l)
i (R
(l)
i x
(l) − y) +
∑
i∈I
λ
(l)
i (R
(l)
i x
(l) − y)
∥∥∥∥∥∥
≤
∑
i∈{1,...,N}\I
λ
(l)
i ‖x(l) − y‖+
∑
i∈I
λ
(l)
i ‖R(l)i x(l) − y‖
≤ ‖x(l) − y‖+
∑
i∈I
λ
(l)
i {‖R(l)i x(l) − x(l)‖+ ‖x(l)− y‖}
≤ ‖x(l) − y‖+
∑
i∈I
λ
(l)
i {α(l)i ‖x(l) − P (l)i x(l)‖+ ‖x(l)− y‖}
≤ ‖x(l) − y‖+
∑
i∈I
λ
(l)
i {2d(x(l), Ci) + r}
≤ ‖x(l) − y‖+
∑
i∈I
λ
(l)
i {2d(y, Ci) + ‖x(l) − y‖+ r}
Do đó, có thể chọn γ2 = 2max{d(y, Ci) : i ∈ I}+3r. Khẳng định II được chứng
minh.
Đặt
δ := r
γ1
γ1 + γ2
(< r).
và chọn số n đủ lớn sao cho ‖x(n) − y‖ < δ; khi đó x(n) ∈ B. Do z là một điểm
dính theo chuẩn khác của dãy (x(n)) và có khoảng cách tới B là dương, do đó
tồn tại một số m > n bé nhất để x(m) 6∈ B. Do tính đơn điệu Fejer của (x(n)) và
khẳng định I, ta có
‖y − c‖ ≤ ‖x(m) − c‖ ≤ ‖x(n) − c‖ − γ1
m−1∑
l=n
∑
i∈I
λ
(l)
i
< δ + ‖y − c‖ − γ1
m−1∑
l=n
∑
i∈I
λ
(l)
i
Do đ...