Luận văn Thuật toán dưới gradient và phương pháp chỉnh lặp song song

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ạn yế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 hoặc 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) hoặc hội tụ theo chuẩn hoặc 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 đó m−1∑ l=n ∑ i∈I λ (l) i < δ γ1 . 29 Từ khẳng định II, lại có ‖x(m) − y‖ ≤ ‖x(n) − y‖+ γ2 m−1∑ l=n ∑ i∈I λ (l) i < δ + γ2 γ1 δ = r, từ đó suy ra x(m) ∈ B, mâu thuẫn. Định lý chứng minh xong. Ơ Hệ quả 13. Giả sử 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. Giả sử thêm rằng X là không gian hữu hạn chiều hoặc phần trong của C khác rỗng. Khi đó dãy (x(n)) hội tụ theo chuẩn tới một điểm x nào đó. Nếu ∑ n à (n) i = +∞ với một chỉ số i nào đó thì x ∈ Ci. Do đó nếu ∑ n à (n) i = +∞ với mọi chỉ số i thì x ∈ C. Chứng minh: Nếu int C 6= ∅ thì dãy (x(n)) hội tụ theo chuẩn theo hệ quả 4(i). Nếu X là không gian hữu hạn chiều thì (x(n)) có một điểm dính theo chuẩn; do đó theo định lý trên, (x(n)) cũng hội tụ theo chuẩn. Phần còn lại của hệ quả được suy từ định lý 3(iii). Ơ Ta có hai ví dụ quan trọng sau: Ví dụ 12 (Flâm và Zowe). Giả sử rằng X là không gian hữu hạn chiều, 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)) hội tụ theo chuẩn tới một điểm x. (i) Nếu lim inf n:n thiết thực cho i à (n) i > 0 ∀i thì x ∈ C. (ii) Nếu int C 6= ∅ và∑ n à (n) i = +∞ ∀i thì x ∈ C. Ví dụ 13 (Aharoni và Censor). Giả sử X là hữu hạn chiều, thuật toán chiếu có các tập hằng (do đó là tụ tuyến tính), và tồn tại số ε > 0 sao cho ε ≤ α(n)i ≡ α(n) ≤ 2 − ε với mọi n đủ lớn và mọi chỉ số i thiết thực tại n. Khi đó, dãy 30 (x(n)) hội tụ theo chuẩn và giới hạn của nó nằm trong ⋂ i∈I∗ Ci trong đó I ∗ := {i ∈ {1, . . . , N} : ∑ n à (n) i = +∞}. Chú ý 4. • Với các giả thiết về tham số nới lỏng α(n)i như trong hai ví dụ trên, điều kiện lim inf n:n thiết thực cho i à (n) i > 0 tương đương với lim inf n:n thiết thực cho i λ (n) i > 0 còn điều kiện ∑ n à (n) i = +∞ tương đương với ∑ n λ (n) i = +∞ • Nếu ta bỏ giả thiết∑ n à (n) i = +∞ trong ví dụ 12 thì có thể giới hạn của dãy (x(n)) không nằm trong Ci. Ví dụ sau cho ta thấy điều này. Ví dụ 14. Cho X := R, N := 2, C1 := C(n)1 :≡ (−∞, 0], C2 := C(n)2 :≡ [0,+∞). Giả sử x(0) > 0, α(n)1 :≡ α(n)2 :≡ 3/2 và λ(n)1 < 2/3 ∀n. Khi đó x(n) = ( 1− 3 2 λ (n−1) 1 ) ã ã ã ( 1− 3 2 λ (0) 1 ) x(0) và do đó, lim n x(n) ∈ C1 ⇐⇒ lim n x(n) = 0 ⇐⇒ ∑ n à (n) 1 = +∞ Định lý 6. Cho trước một thuật toán chiếu, giả sử rằng (P (n) i ) hội tụ từng điểm tới Pi với mọi chỉ số i. Giả sử thêm rằng tồn tại một dãy con (n ′) của (n) sao cho với mọi chỉ số i ta có α (n′) i −→ αi, λ(n ′) i −→ λi với αi nào đó thuộc (0, 2] và λi nào đó thuộc (0, 1]. Nếu phần trong của C khác rỗng, thì dãy (x(n)) hội tụ theo chuẩn tới một điểm thuộc C. Chứng minh: Theo hệ quả 4(i), dãy (x(n)) hội tụ theo chuẩn tới một điểm x. Ta phải chỉ ra rằng x ∈ C. Ta sẽ chứng minh P (n′) i x (n′) −→ Pix ∀i. Thật vậy, vì tính không giãn của phép chiếu, ta có ‖P (n′)i x(n ′) − P (n′)i x‖ ≤ ‖x(n ′) − x‖. Mặt khác, ta có P (n′) i x (n′) − P (n′)i x −→ 0. Do λ(n ′) i −→ λi > 0, ta thấy rằng i là thiết thực tại n′ với mọi n′ đủ lớn. Từ giả thiết cho P (n ′) i suy ra rằng P (n′) i x (n′) −→ 31 Pix. Bây giờ ta có x(n ′+1) = N∑ i=1 λ (n′) i ( (1− α(n′)i )x(n ′) + α (n′) i P (n′) i x (n′)) Bằng cách lấy giới hạn theo dãy con (x(n ′)) và từ chứng minh trên ta có x = N∑ i=1 λi ( (1− αi)x+ αiPix ) hay x = N∑ i=1 ( λiαi∑N j=1 λjαj ) Pix Từ đẳng thức trên, áp dụng mệnh đề 5(ii) ta suy ra x ∈ N⋂ i=1 Ci = C. Định lý chứng minh xong. Ơ Ví dụ sau đây minh họa kết quả của định lý vừa nêu. Ví dụ 15 (Butnariu và Censor). Giả sử X là hữu hạn chiều, thuật toán chiếu có các tập hằng, và các tham số nới lỏng chỉ phụ thuộc n, tức là α (n) i ≡ α(n) với mọi chỉ số i và mọi n. Giả sử thêm rằng tồn tại một dãy con nào đó (n′) của (n) sao cho với mọi chỉ số i, λ (n′) i −→ λi với một số λi > 0 nào đó. (i) Nếu tồn tại số ε sao cho ε ≤ α(n) ≤ 2 − ε với mọi n đủ lớn, khi đó dãy (x(n)) hội tụ theo chuẩn tới một điểm thuộc C. (ii) Nếu phần trong của C khác rỗng và tồn tại một dãy con (n′′) của (n′) sao cho α(n ′′) −→ 2 thì dãy (x(n)) hội tụ theo chuẩn tới một điểm nào đó thuộc C. Chứng minh: (i): Giả thiết về các trọng suy ra ∑ n à (n) i = +∞ với mọi chỉ số i. Do đó (i) suy ra từ ví dụ 12. (ii): Suy trực tiếp từ định lý 6 Ơ 32 Định nghĩa 13 (Điều khiển). Ta nói thuật toán chiếu là xét tập xa nhất nếu với mọi n, ít nhất một chỉ số xa nhất được xét; tức là I(n)rem := {i : d(x(n), Ci) = max{d(x(n), Cj) : j = 1, . . . , N}} ∩ I(n) 6= ∅. Theo cách gọi của Censor, ta nói điều khiển tập xa nhất nếu thuật toán chiếu là suy biến và xét tập xa nhất. Tương tự như phần thuật toán tổng quát, tới đây ta có thể phát biểu và chứng minh một kết quả cơ bản trong tôpô yếu. Định lý 7 (Các kết quả trong tôpô yếu). Giả sử rằng thuật toán chiếu là tụ mạnh và xét tập xa nhất. Giả sử thêm rằng (i(n)) một dãy các chỉ số xa nhất; tức là i(n) ∈ I(n)rem ∀n. (i) Nếu ∑ n à (n) i(n) = +∞, khi đó tồn tại một dãy con (x(nk))k của x(n) sao cho max{d(x(nk), Cj) : j = 1, . . . , N} −→ 0. và (x(nk))k hội tụ yếu tới điểm dính yếu duy nhất của (x (n)) trong C. (ii) Nếu lim inf n à (n) i(n) > 0 thì (x(n)) hội tụ yếu tới một điểm thuộc C và max{d(x(n), Cj) : j = 1, . . . , N} −→ 0. Chứng minh: (i): Từ bổ đề 2(iv), chuỗi ∑ n à (n) i(n) d2(x(n), C (n) i(n) ) hội tụ. Do đó, lim inf n d(x(n), C (n) i(n) ) = 0. Do đó ta có thể trích ra một dãy con (x(nk))k và cố định một chỉ số i sao cho d(x(n), C (n) i(n) ) −→ 0; i(nk) ≡ i,và dãy (x(nk))k hội tụ yếu. Do thuật toán là tụ mạnh và xét chỉ số xa nhất, ta đi tới kết luận là max{d(x(nk), Cj) : j = 1, . . . , N} −→ 0. Do tính nửa liên tục dưới yếu của d(ã, Cj) với mọi chỉ số j, giới hạn yếu của (x(nk))k nằm trong C. Theo định lý 1(ii), (x (n)) có nhiều nhất một điểm dính yếu trong C; do đó, (i) chứng minh xong. (ii): Chứng minh tương tự (i). Ơ 33 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 Để đảm bảo sự hội tụ theo chuẩn cũng như hội tụ tuyến tính, ta cần đến khái niệm sau đây. Định nghĩa 14. Ta nói bộ N tập lồi đóng (C1, . . . , CN) là chính quy nếu ∀ε > 0 ∃δ > 0∀x ∈ X : max{d(x,Cj) : j = 1 . . . N} ≤ δ ⇒ d(x,C) ≤ ε Nếu điều này chỉ đúng trên các tập bị chặn, tức là: ∀S ⊆ X bị chặn ∀ε > 0 ∃δ > 0 ∀x ∈ S : max{d(x,Cj) : j = 1 . . . N} ≤ δ ⇒ d(x,C) ≤ ε thì ta nói bộ N tập trên là chính quy bị chặn. ý nghĩa hình học của định nghĩa này rất rõ ràng: Nếu một phần tử x đã ở gần tất cả các tập Ci thì nó cũng không thể ở xa giao C của tất cả các tập ấy. Với khái niệm vừa nêu ta có một số kết quả sau. Định lý 8. Giả sử rằng thuật toán là tụ mạnh và p−lặp đoạn với số nguyên dương p nào đó. Giả sử thêm rằng bộ N tập (C1, . . . , CN) là chính quy bị chặn. Đặt νn = min{à(l)i : np ≤ l ≤ (n+ 1)p− 1 i thiết thực tại l} ∀n ≥ 0. Nếu ∑ n νn = +∞, thì dãy (x(n)) hội tụ theo chuẩn tới một điểm nằm trong C. Nói riêng, điều này đúng nếu lim inf n:n thiết thực cho i à (n) i > 0 ∀i. Chứng minh: Từ định lý 3, ta nhận được một dãy con (x(nkp))k sao cho (x (nkp))k hội tụ yếu tới điểm dính yếu duy nhất của (x(n)) trong C, giả sử đó là x, ngoài ra ta còn có (nk+1)p−1∑ l=nkp ∑ i∈I(l) d(x(l), C (l) i ) −→ 0 (3.1) 34 x(nkp+rk) − x(nkp) −→ 0 (3.2) với mọi dãy (rk) nằm trong {0, . . . , p − 1}. Cố định một chỉ số i. Do thuật toán chiếu là lặp đoạn, ta có một dãy (rk) nằm trong {0, . . . , p−1} sao cho i ∈ I(nkp+rk) với mọi k. Khi đó, do (3.1), d(x(nkp+rk), C (nkp+rk) i ) −→ 0. Do dãy (x(nkp+rk))k cũng hội tụ tới x (do (3.2))và thuật toán chiếu là tụ mạnh, ta suy ra rằng d(x(nkp+rk), Ci) −→ 0. Do đó, từ (3.2), d(x(nkp), Ci) −→ 0. Do chỉ số i chọn bất kỳ nên ta có max{d(x(nkp), Cj) : j = 1 . . . N} −→ 0. Mặt khác, bộ (C1, . . . , CN) là chính quy bị chặn và dãy (x (nkp)) bị chặn. Từ đó suy ra d(x(nkp), C) −→ 0. áp dụng hệ quả 4(ii) dãy x(n) hội tụ theo chuẩn tới x. Ơ Định lý 9. Giả sử thuật toán chiếu là tụ mạnh và xét tập xa nhất. Giả sử thêm rằng bộ N tập (C1, . . . , CN) là chính quy bị chặn và (i (n)) là một dãy các chỉ số xa nhất. Nếu ∑ n à (n) i(n) = +∞ 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 khi lim inf n à (n) i(n) > 0. Chứng minh:Từ định lý 7(i), tồn tại một dãy con hội tụ yếu (x(nkp))k của (x (n)) với max{d(x(nkp), Cj) : j = 1, . . . , N} −→ 0. Do bộ (C1, . . . , CN) chính quy bị chặn nên d(x(nkp), C) −→ 0. áp dụng hệ quả 4(ii) ta có điều phải chứng minh. Ơ Để có thể sử dụng được các định lý nêu trên, ta cần có những điều kiện đủ đơn giản để kiểm tra khi nào một bộ N tập là chính quy bị chặn. Mệnh đề 7. Cho một bộ N tập lồi đóng. (i) Nếu có một tập Ci nào đó là compact bị chặn thì bộ N tập (C1, . . . , CN) là chính quy bị chặn. (ii) Nếu bộ N tập là chính quy bị chặn và một tập Ci nào đó là bị chặn thì bộ N tập là chính quy. 35 (iii) Nếu X là không gian hữu hạn chiều thì mọi bộ N tập là chính quy bị chặn. Định nghĩa sau đây cho phép ta đánh giá tốc độ hội tụ của thuật toán. Định nghĩa 15. Ta nói bộ N tập lồi đóng (C1, . . . , CN) là chính quy tuyến tính nếu ∃κ > 0 ∀x ∈ X d(x,C) ≤ κmax{d(x,Cj) : j = 1, . . . , N} Nếu điều này chỉ đúng với các tập bị chặn ∀X ⊇ S bị chặn ∃κS > 0 ∀x ∈ X d(x,C) ≤ κmax{d(x,Cj) : j = 1, . . . , N} thì ta nói bộ N tập là chính quy tuyến tính bị chặn. Với định nghĩa trên ta có kết quả sau: Định lý 10. Giả sử thuật toán chiếu là tụ tuyến tính và lặp đoạn. Giả sử thêm rằng bộ N tập là chính quy tuyến tính bị chặn và tồn tại một số ε > 0 sao cho ε ≤ α(n)i ≤ 2− ε với mọi n đủ lớn và i thiết thực tại n. Khi đó, dãy (x(n)) hội tụ tuyến tính tới một điểm thuộc C và tốc độ hội tụ không phụ thuộc vào điểm xuất phát nếu bộ N tập là chính quy tuyến tính. Chứng minh: Giả sử thuật toán chiếu là p−lặp đoạn. Cố định một chỉ số i. Khi đó, với mọi k ≥ 0, ta có mk với kp ≤ mk ≤ (k + 1)p − 1 sao cho i ∈ I(mk). Theo định nghĩa phép lặp, ta có x(mk) = A(mk−1) . . . A(kp)x(kp) và từ bổ đề 1(iv) và mệnh đề 5(i), A(n) là min{2− α (n) j α (n) j : j thiết thực tại n} − hút tương ứng với C∀n ≥ 0. Do đó, từ giả thiết về các tham số nới lỏng, A(n) là ε/2-hút tương ứng với C với mọi n đủ lớn. Do đó, theo mệnh đề 5(i) A(mk−1) . . . A(kp) là ε 2p−1 − hút đối với C với mọi k đủ lớn. 36 Do thuật toán là tụ tuyến tính nên tồn tại một số β > 0 sao cho βd(x(n), Cj) ≤ d(x(n), C (n) j ) với mọi n đủ lớn và mọi chỉ số j thiết thực tại n. Ta có d2(x(kp), Ci) ≤ (‖x(kp) − x(mk)‖+ d(x(mk), Ci))2 ≤ 2‖x(kp) − x(mk)‖2 + 2d2(x(mk), Ci) Cố định một điểm bất kỳ c ∈ C. Ta có với k đủ lớn, ‖x(kp) − x(mk)‖2 = ‖A(mk−1) . . . A(kp)x(kp) − x(kp)‖ ≤ 2 p−1 ε (‖x(kp) − c‖2 − ‖x(mk) − c‖2) ≤ 2 p−1 ε (‖x(kp) − c‖2 − ‖x((k+1)p) − c‖2) Mặt khác, từ giả thiết về β, các tham số nới lỏng, các trọng và bổ đề 2 và chú ý 1, ta có đánh giá sau khi k đủ lớn. d2(x(mk), Ci) ≤ 1 β2 d2(x(mk), C (mk) i ) = 1 β2 ‖x(mk) − P (mk)i x(mk)‖2 ≤ 1 β2à (mk) i (‖x(mk) − c‖2 − ‖x(mk+1) − c‖2) ≤ 1 β2ε3 (‖x(mk) − c‖2 − ‖x(mk+1) − c‖2) ≤ 1 β2ε3 (‖x(kp) − c‖2 − ‖x((k+1)p) − c‖2) Kết hợp lại ta được: d2(x(kp), Ci) ≤ (2p ε + 2 β2ε3 )(‖x(kp) − c‖2 − ‖x((k+1)p) − c‖2). Chọn c = PCx (kp) ta được d2(x(kp), Ci) ≤ (2p ε + 2 β2ε3 )( d2(x(kp), C)− d2(x((k+1)p), C)). Do chỉ số i chọn tùy ý nên với k đủ lớn, đánh giá trên đúng cho mọi i. Do bộ (C1, . . . , CN) là chính quy tuyến tính bị chặn, với S := {x(n) : n ≥ 0} ta có một số κS sao cho d(x(n), C) ≤ κS max{d(x(n), Cj) : j = 1, . . . , N} ∀n ≥ 0. 37 Nhận xét rằng nếu bộ (C1, . . . , CN) là chính quy tuyến tính, thì hằng số κS có thể chọn được độc lập với S. Kết hợp lại ta được d(x(kp), C) ≤ κ2S (2p ε + 2 β2ε3 )( d2(x(kp), C)− d2(x((k+1)p), C)). Từ đó, áp dụng định lý 1(iv) cho dãy con x(kp), dãy này hội tụ tuyến tính tới một điểm x thuộc C. Từ định lý 1(i) và mệnh đề 4 toàn bộ dãy (x(n)) hội tụ tuyến tính về x và tốc độ hội tụ không phụ thuộc cách chọn điểm xuất phát nếu bộ (C1, . . . , CN) là chính quy tuyến tính. Ơ Định lý 11. Giả sử thuật toán là tụ tuyến tính và xét tập xa nhất. Giả sử thêm rằng bộ N tập (C1, . . . , CN) là chính quy tuyến tính bị chặn và (i (n)) là dãy các chỉ số xa nhất. Nếu lim inf n à (n) i(n) > 0 thì dãy x(n) hội tụ tuyến tính tới một điểm thuộc C; tốc độ hội tụ không phụ thuộc điểm xuất phát nếu bộ (C1, . . . , CN) là chính quy tuyến tính. Chứng minh: Trước hết, do thuật toán chiếu là tụ tuyến tính, ta có β > 0 sao cho βd(x(n), Ci) ≤ d(x(n), C(n)i ) với mọi n đủ lớn và i thiết thực tại n. Tiếp theo, do bộ (C1, . . . , CN) là chính quy tuyến tính bị chặn, với tập S := {x(n) : n ≥ 0} tồn tại một hằng số κS > 0 sao cho d(x(n), C) ≤ κS max{d(x(n), Cj) : j = 1 . . . N} với mọi n ≥ 0. Dễ thấy hằng số κS có thể chọn độc lập với tập S nếu bộ (C1, . . . , CN) là chính quy tuyến tính. Tiếp theo, tồn tại một số ε > 0 sao cho à (n) i(n) ≥ ε với mọi n đủ lớn. Kết hợp lại và sử dụng bổ đề 2(ii) ta có đánh giá sau: d2(x(n), C) ≤ κ2S max{d2(x(n), Cj) : j = 1 . . . N} = κ2Sd 2(x(n), Ci(n)) ≤ (κS β )2 ‖x(n) − P (n) i(n) ‖2 ≤ (κS β )2 1 à (n) i(n) (‖x(n) − PCx(n)‖2 − ‖x(n+1) − PCx(n)‖2) ≤ (κS β )21 ε ( d2(x(n), C)− d2(x(n+1), C)). 38 Do đó, theo định lý 1(vi), dãy x(n) hội tụ tuyến tính tới một điểm thuộc C. Ơ Tính chất chính quy tuyến tính (bị chặn) cho phép ta đưa ra nhiều kết quả, ta sẽ nghiên cứu kỹ hơn khái niệm này và đưa ra một vài điều kiện đủ cho tính chất này. 2.4. Một vài ví dụ về tính chính quy tuyến tính (bị chặn) Mệnh đề 8. Nếu mỗi tập Ci là một nón lồi đóng thì các điều kiện sau tương đương: (i) Bộ (C1, . . . , CN) là chính quy. (ii) Bộ (C1, . . . , CN) là chính quy tuyến tính. (iii) Bộ (C1, . . . , CN) là chính quy tuyến tính bị chặn. Định lý 12 (Tính chính quy tuyến tính (bị chặn) đưa về từng cặp). Nếu mỗi cặp trong N − 1 cặp: (C1, C2), (C1 ∩ C2, C3), . . . (C1 ∩ C2 ∩ . . . ∩ CN−2, CN−1), (C1 ∩ C2 ∩ . . . ∩ CN−2 ∩ CN−1, CN) là chính quy tuyến tính (bị chặn) thì bộ N tập (C1, C2, . . . , CN) cũng là chính quy tuyến tính (bị chặn). Như vậy tính chất chính quy tuyến tính (bị chặn) ta đưa về tính chính quy theo từng cặp. Với tính chính quy tuyến tính (bị chặn) theo cặp, ta công nhận điều kiện đủ sau đây Bổ đề 4. Giả sử E,F là hai tập lồi đóng. Nếu 0 ∈ icr(E −F )(icr(S) = intaff S S là nhân trong của S), thì cặp (E,F ) là chính quy tuyến tính bị chặn. Nói riêng, điều này đúng nếu 39 (i) 0 ∈ int(E − F ). (ii) E − F là không gian con đóng. Kết hợp định lý và bổ đề vừa nêu ta có hệ quả sau: Hệ quả 14. Nếu 0 ∈ icr(C1 − C2) ∩ icr((C1 − C2)− C3) ∩ . . . icr((C1 ∩ . . . CN−1)− CN) thì bộ N -tập là chính quy tuyến tính bị chặn. Hệ quả 15. Nếu CN ∩ int(C1 ∩ . . . CN−1) 6= ∅ thì bộ N -tập là chính quy tuyến tính bị chặn. Tiếp theo ta xét tính chính quy tuyến tính (bị chặn) của một số bộ tập đặc biệt. Ta có một số kết quả sau đây. Mệnh đề 9. Bộ N -tập (C1, . . . , CN) là chính quy tuyến tính nếu (i) Mỗi tập Ci là một siêu phẳng. (ii) Mỗi tập Ci là một đa diện. (iii) Mỗi tập Ci là một nửa không gian. (iv) Mỗi tập Ci là một không gian con đóng và ít nhất một không gian con là hữu hạn chiều hoặc tất cả các không gian con (có thể ngoại trừ một không gian con) có đối chiều hữu hạn. 40 Chương 3. Thuật toán dưới gradient và phương pháp chỉnh lặp song song Trong chương này ta xét trường hợp tổng quát khi các tập Ci có dạng Ci = {x ∈ X : fi(x) ≤ 0} trong đó fi là một hàm lồi. Như vậy Ci là tập mức dưới của một hàm lồi. Chú ý rằng ánh xạ khoảng cách d(ã, C) khi C là tập lồi cũng là một hàm lồi và tập lồi C bất kỳ đều có thể xem như tập mức dưới của hàm f(ã) = d(ã, C). 3.1. Thuật toán dưới gradient 3.1.1. Cơ sở Định nghĩa 16 (Dưới vi phân). Giả sử f : X −→ X là một hàm lồi. Cho trước một điểm x0 ∈ X , tập hợp {x∗ ∈ X : 〈x∗, x− x0〉 ≤ f(x)− f(x0) ∀x ∈ X} được gọi là dưới vi phân của f tại x0 và ký hiệu là ∂f(x0) Bổ đề 5. Giả sử rằng f : X −→ X là một hàm lồi và x0 ∈ X . Khi đó (i) f liên tục tại x0 và ∂f(x0) chỉ có một phần tử nếu và chỉ nếu f là nửa liên 41 tục dưới và khả vi Gâteaux tại x0. Trong trường hợp này, dưới vi phân duy nhất của f tại x0 chính là đạo hàm Gâteaux của f tại x0. (ii) Nếu f liên tục tại x0 thì f khả dưới vi phân tại x0. (iii) Nếu X hữu hạn chiều thì f liên tục và khả dưới vi phân tại mọi điểm. Bổ đề 6. Giả sử f : X −→ X là một hàm lồi, x0 ∈ X và f khả dưới vi phân tại x0. Giả sử thêm rằng tập S := {x ∈ X : f(x) ≤ 0} 6= ∅. Với mọi g(x0) ∈ ∂f(x0), định nghĩa tập lồi đóng H bởi: H := H(f, x0, g(x0)) := {x ∈ X : f(x0) + 〈g(x0), x− x0〉 ≤ 0}. Khi đó (i) H ⊇ S. Nếu g(x0) 6= 0 thì H là một nửa không gian; ngược lại thì H = X . (ii) PHx0 = x0 − f(x0) ‖g(x0)‖2 g(x0) nếu f(x0) > 0 x0 ngược lại (iii) d(x0, H) =  f(x0) ‖g(x0)‖ nếu f(x0) > 0 0 ngược lại Chú ý 5. Nửa không gian trong bổ đề vừa định nghĩa được sử dụng với ý tưởng sau. Giả sử ta cần tìm một phần tử của tập S = {x ∈ X : f(x) ≤ 0}. Xuất phát từ điểm x0, nếu f(x0) ≤ 0 thì ta tìm được x0 ∈ S; ngược lại f(x0) > 0, ta đi tìm nghiệm của phương trình f(x) = 0. Tuy nhiên do điều này khó thực hiện nên ta thay f(x) bởi xấp xỉ bậc 1 của nó tức là f(x) ≈ f˜(x) := f(x0) + 〈g(x0), x− x0〉 với g(x0) ∈ ∂f(x0), và giải phương trình f˜(x0) = 0. Phương trình này có một nghiệm là PH(x0) = x0 − f(x0)‖g(x0)‖2 g(x0). Ta đưa ra định nghĩa chính xác của thuật toán dưới gradient. 42 Định nghĩa 17. Giả sử với một chỉ số i ∈ {1, 2, . . . , N} nào đó và mọi chỉ số n, các tập C (n) i của thuật toán chiếu có dạng C (n) i = H (n) i = {x ∈ X : fi(xn) + 〈gi(x(n)), x− xn〉 ≤ 0} với mỗi hàm lồi fi : X −→ R, trong đó fi khả dưới vi phân tại mọi điểm x(n) và gi(x (n)) ∈ ∂fi(x(n)). Giả sử thêm rằng Ci = {x ∈ X : fi(x) ≤ 0}. Khi đó ta gọi thuật toán chiếu này là thuật toán dưới gradient. Mỗi chỉ số i được gọi là chỉ số dưới gradient. Chú ý rằng không phải mọi chỉ số i đều là chỉ số dưới gradient. Nhận xét 1. Thuật toán chiếu và thuật toán dưới gradient có mối liên hệ mật thiết theo nghĩa