Luận văn Thạc sĩ Toán học: Phương pháp điểm gần kề suy rộng tìm không điểm của toán tử đơn điệu cực đại trong không gian Hilbert

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC

——————–o0o——————–

NGUYỄN CẨM DƯƠNG

PHƯƠNG PHÁP ĐIỂM GẦN KỀ SUY RỘNG TÌM KHÔNG ĐIỂM CỦA TOÁN TỬ ĐƠN ĐIỆU CỰC ĐẠI TRONG KHÔNG GIAN HILBERT

LUẬN VĂN THẠC SĨ TOÁN HỌC

THÁI NGUYÊN - 2017

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC

——————–o0o——————–

NGUYỄN CẨM DƯƠNG

PHƯƠNG PHÁP ĐIỂM GẦN KỀ SUY RỘNG

TÌM KHÔNG ĐIỂM CỦA TOÁN TỬ ĐƠN ĐIỆU CỰC ĐẠI TRONG KHÔNG GIAN HILBERT

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 - 2017

i

Mục lục

Bảng ký hiệu ii

Mở đầu 1

1 Một số vấn đề cơ bản liên quan

1.1 Không gian Hilbert và một số tính chất . . . . . . . . . . . . 3 3

1.2 Toán tử đơn điệu cực đại . . . . . . . . . . . . . . . . . . . . 12 1.3 Phương pháp điểm gần kề cổ điển . . . . . . . . . . . . . . . 20

2 Thuật toán điểm gần kề suy rộng

2.1 Thuật toán điểm gần kề suy rộng của Ackstein và Bertsekas 23 23

2.2 Thuật toán điểm gần kề co . . . . . . . . . . . . . . . . . . . 28

Kết luận 34

Tài liệu tham khảo 35

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:

R tập số thực

Rn

C[a, b] không gian véc tơ n chiều tương ứng tập các hàm thực liên tục trên [a, b]

conv C bao lồi của tập C

bao lồi đóng của tập C toán tử liên hợp của toán tử A

conv C A∗ A dom A toán tử mở rộng của toán tử A miền xác định của toán tử A

gra A domf đồ 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ả cá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(.)

1

Mở đầu

Toán tử đơn điệu là một trong những lĩnh vực của giải tích hiện đại đã

và đang được nhiều nhà toán học hàng đầu thế giới nghiên cứu, đặc biệt phải kể đến như Browder F. E, Rockafellar R. T, Minty G. J. Bên cạnh

các kết quả đặc biệt có ý nghĩa về mặt lý thuyết, 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.

Phương pháp cơ bản tìm không điểm của toán tử đơn điệu cực đại chỉ

có sự hội tụ yếu. Để khắc phục điểm yếu đó Xu đưa ra một cải biên

zk+1 = λku + (1 − λk)(I + ckT )−1zk + ek, k ≥ 0

với điều kiện {ck} tiến tới vô cùng.

Mục đích của đề tài luận văn là nghiên cứu về một số phương pháp điểm gần kề suy rộng để tìm không điểm của toán tử đơn điệu cực đại trong

không gian Hilbert.

Nội dung của đề tài luận văn được viết trong hai chương:

Chương 1: "Một số vấn đề cơ bản liên quan". 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 thức cơ bản về

giải tích lồi, 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ử đơn điệu cực đại và cuối cùng là giới thiệu về

thuật toán điểm gần kề cổ điển.

Chương 2: "Thuật toán điểm gần kề suy rộng". Chương này trình bày

hai phương pháp tìm không điểm của toán tử đơn điệu cực đại trong không

gian Hilbert.

Luận văn này được hoàn thành tại Trường Đại học Khoa học - Đại học

2

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 8 năm 2017

Học viên

Nguyễn Cẩm Dương

3

Chương 1

Một số vấn đề cơ bản liên quan

Chương này trình bày một số vấn đề cơ bản để phục vụ cho chương sau.

Cụ thể: Mục 1.1 giới thiệu về không gian Hilbert thực và một số tính chất của không gian Hilbert. Mục 1.2 trình bày một số kiến thức về giải tích

lồi, giới thiệu về toán tử đơn điệu cực đại, định nghĩa không điểm. Mục 1.3 trình bày phương pháp điểm gần kề cổ điển. Các kiến thức của chương

được tổng hợp từ tài liệu [1], [2], [3].

1.1 Không gian Hilbert và một số tính chất

Định nghĩa 1.1.1 Một tập X được gọi là không gian tuyến tính trên R nếu với mỗi cặp (x, y) ∈ X × X, một phần tử của X, ta gọi là tổng của x và y, ký hiệu là x + y; với mỗi α ∈ R và x ∈ X, một phần tử của X, gọi là tích của α và x, ký hiệu là αx thỏa mãn các điều kiện sau:

(i) x + y = y + x với mọi x, y ∈ X (tính chất giao hoán);

(ii) (x + y) + z = x + (y + z) với mọi x, y, z ∈ X (tính chất kết hợp);

(iii) tồn tại phần tử không của X, ký hiệu 0, sao cho: x + 0 = 0 + x với

mọi x ∈ X;

(iv) với mọi x ∈ X, tồn tại phần tử đối của x, ký hiệu là −x, sao cho

x + (−x) = 0 với mọi x ∈ X;

(v) 1 · x = x · 1 = x, với mọi x ∈ X (1 là phần tử đơn vị);

(vi) α(βx) = (αβ)x, với mọi α, β ∈ R, với mọi x ∈ X;

4

(vii) (α + β)x = αx + βx), với mọi α, β ∈ R, với mọi x ∈ X;

(viii) α(x + y) = αx + αy), với mọi α ∈ R, với mọi x, y ∈ X.

Định nghĩa 1.1.2 Cho H là một không gian tuyến tính trên trường số thực R. 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 R, ký hiệu là (cid:104)., .(cid:105), thỏa mãn các điều kiện sau:

(i) (cid:104)x, y(cid:105) = (cid:104)y, x(cid:105) với mọi x, y ∈ H;

(ii) (cid:104)x + y, z(cid:105) = (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105) với mọi x, y, z ∈ H;

(iii) (cid:104)αx, y(cid:105) = α(cid:104)x, y(cid:105) với mọi x, y ∈ H và mọi α ∈ R;

(iv) (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.3 Từ Định nghĩa 1.1.2 ta suy ra

(i) (cid:104)x, αy(cid:105) = α(cid:104)y, x(cid:105) với mọi x, y ∈ H và mọi α ∈ R;

(ii) (cid:104)x, y + z(cid:105) = (cid:104)x, y(cid:105) + (cid:104)x, z(cid:105) với mọi x, y, z ∈ H.

Định nghĩa 1.1.4 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.5 (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). (1.1)

Chứng minh. Với mọi số thực α và với mọi x, y ∈ H 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).

Từ đây suy ra

∆ = |(cid:104)x, y(cid:105)|2 − (cid:104)x, x(cid:105)(cid:104)y, y(cid:105) ≤ 0 với mọi x, y ∈ H.

Hay

|(cid:104)x, y(cid:105)|2 ≤ (cid:104)x, x(cid:105)(cid:104)y, y(cid:105) với mọi x, y ∈ H.

5

(cid:3)

Dấu đẳng thức trong bất đẳng thức (1.1) xảy ra khi và chỉ khi x và y

phụ thuộc tuyến tính.

Định lý 1.1.6 Không gian tiền Hilbert H là một không gian tuyến tính định chuẩn với chuẩn được xác định bởi

(cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105) với mọi x ∈ H. (1.2)

Chuẩn này được gọi là chuẩn cảm sinh từ tích vô hướng. Hàm số (cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105) với mọi x ∈ H là một chuẩn trên H. Chứng minh. Thật vậy, từ điều kiện (iv) của Định nghĩa 1.1.2 ta có

(cid:107)x(cid:107) > 0 nếu x (cid:54)= 0 và (cid:107)x(cid:107) = 0 nếu x = 0 với x ∈ H. Từ điều kiện (i) và (iii) của Định nghĩa 1.1.2 ta suy ra (cid:107)αx(cid:107) = |α|.(cid:107)x(cid:107) với mọi α ∈ R và mọi x ∈ H. Từ bất đẳng thức Schwarz và cách định nghĩa chuẩn ta có

|(cid:104)x, y(cid:105)| ≤ (cid:107)x(cid:107).(cid:107)y(cid:107) với mọi x, y ∈ H. (1.3)

Từ đó với mọi x, y ∈ H ta có:

(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)

≤ (cid:107)x(cid:107)2 + 2(cid:107)x(cid:107).(cid:107)y(cid:107) + (cid:107)y(cid:107)2 = (cid:0)(cid:107)x(cid:107) + (cid:107)y(cid:107)(cid:1)2.

(cid:3) Suy ra (cid:107)x + y(cid:107) ≤ (cid:107)x(cid:107) + (cid:107)y(cid:107) với mọi x, y ∈ H.

Định nghĩa 1.1.7 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.2) thì H được gọi là không gian Hilbert thực.

Ví dụ 1.1.8 Không gian

∞ (cid:88)

n=1

(cid:110) (cid:111) l2 = x = {xn}n ∈ R : |xn|2 < +∞

6

∞ (cid:88)

là không gian Hilbert với tích vô hướng

n=1

(cid:104)x, y(cid:105) = xnyn, x = {xn}n∈N, y = {yn}n∈N ∈ l2

∞ (cid:88)

và chuẩn

n=1

n=1

(cid:16) ∞ (cid:88) (cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105) = |xn|2 = |xn|2(cid:17) 1 2 . (cid:118) (cid:117) (cid:117) (cid:116)

b

Ví dụ 1.1.9 Không gian L2[a, b] là không gian Hilbert với tích vô hướng

a

(cid:90) (x, y) = x(t)y(t)dt, ∀x, y ∈ L2 [a, b]

2

a

và chuẩn (cid:33) 1 (cid:32) b (cid:90) |x(t)|2dt (cid:107)x(cid:107) = .

Ví dụ 1.1.10 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

a

(cid:90) b x(t)y(t).dt, x(t), y(t) ∈ C[a, b]. (cid:104)x, y(cid:105) =

2

Không gian C[a, b] với chuẩn

a

(cid:16) (cid:90) b (cid:17) 1 (cid:107)x(cid:107) = |x(t)|2.dt

là không gian tiền Hilbert, nhưng không phải là không gian Hilbert.

Định lý 1.1.11 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 Hilbert Chứng minh. Giả sử lim n→∞ xn = x0, lim n→∞

7

H.

Ta sẽ chứng minh

trong R. (cid:104)xn, yn(cid:105) = (cid:104)x0, y0(cid:105) lim n→∞

Thật vậy,

|(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)|

≤ (cid:107)xn(cid:107).(cid:107)yn − y0(cid:107) + (cid:107)xn − x0(cid:107).(cid:107)y0(cid:107).

Vì dãy {xn}n∈N hội tụ trong H nên tồn tại một số M > 0 sao cho (cid:107)xn(cid:107) ≤ M với mọi n ∈ N. Do đó,

(cid:104)xn, yn(cid:105) = (cid:104)x0, y0(cid:105). lim n→∞

(cid:3)

Nhận xét 1.1.12 Tích vô hướng là một phiếm hàm song tuyến tính liên

tục trên H × H.

Định lý 1.1.13 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:

(cid:16) (cid:107)x + y(cid:107)2 + (cid:107)x − y(cid:107)2 = 2 (cid:107)x(cid:107)2 + (cid:107)y(cid:107)2(cid:17) .

Chứng minh. Với mọi x, y ∈ H, ta có

(cid:107)x + y(cid:107)2 = (cid:104)x + y, x + y(cid:105) = (cid:107)x(cid:107)2 + (cid:107)y(cid:107)2 + 2(cid:104)x, y(cid:105)

và

(cid:107)x − y(cid:107)2 = (cid:104)x − y, x − y(cid:105) = (cid:107)x(cid:107)2 + (cid:107)y(cid:107)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 và x − z ta có

hệ quả sau.

8

Hệ quả 1.1.14 Cho H là một không gian tiền Hilbert và x, y, z ∈ H. Khi

đó, ta có đẳng thức Apollonius:

(cid:16) = 4 (cid:107)x − y(cid:107)2 + (cid:107)x − z(cid:107)2(cid:17) 2 x − + (cid:107)y − z(cid:107)2. y + z 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:13)

Nhận xét 1.1.15 (ý 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 được xác định nhờ

tích vô hướng. Điều này được thể hiện qua định lý sau.

Định lý 1.1.16 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. Nếu đặt

(cid:16) (cid:107)x + y(cid:107)2 − (cid:107)x − y(cid:107)2(cid:17) , (1.4) (cid:104)x, y(cid:105) = 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) = (cid:107)x(cid:107)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. Thật vậy, các điều kiện (1) và (4)

trong Định nghĩa 1.1.2 hiển nhiên được thỏa mãn. Đặt (cid:16) (cid:107)x + y(cid:107)2 − (cid:107)x − y(cid:107)2(cid:17) . p(x, y) = 1 4

Để ý 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.

9

Với mọi x, y, z ∈ H ta có

4 (p(x, z) + p(y, z)) = (cid:107)x + z(cid:107)2 − (cid:107)x − z(cid:107)2 + (cid:107)y + z(cid:107)2 − (cid:107)y − z(cid:107)2

(cid:19) (1.5) , z . ⇔ p(x, z) + p(y, z) = 2p (cid:18)x + y 2

Trong đẳng thức (1.5) lấy y = 0 được

(cid:17) p(x, z) = 2p , z . (1.6) (cid:16)x 2

Như vậy ta có (cid:19) , z 2p = p(x + y, z). (cid:18)x + y 2

Nghĩa là p(x, z) + p(y, z) = p(x + y, z). Vậy điều kiện (2) trong Định nghĩa 1.1.2 được chứng minh. Thay thế x bằng 2x trong (1.6) 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.

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) = (cid:107)x(cid:107)2 .

(cid:3) Định lý được chứng minh.

n=1 trong không gian Hilbert H được

Định nghĩa 1.1.17 (i) Dãy {xn}∞

10

gọi là hội tụ yếu đến phần tử x ∈ H nếu

y ∈ H. (cid:104)xn, y(cid:105) = (cid:104)x, y(cid:105) với mọi lim n→∞

n=1 được gọi là hội tụ mạnh đến x ∈ H nếu

(ii) Dãy {xn}∞

(cid:107)xn − x(cid:107) = 0. lim n→∞

Ký hiệu xn (cid:42) x chỉ sự hội tụ yếu, xn → x chỉ sự hội tụ mạnh của dãy

{xn} đến phần tử x ∈ H.

Chú ý 1.1.18 (1) Trong không gian Hilbert H, hội tụ mạnh kéo theo hội

tụ yếu, nhưng điều ngược lại không đúng.

(2) Mọi không gian Hilbert đều có tính chất Kadec–Klee, tức là nếu dãy {xn} trong không gian Hilbert H thỏa mãn các điều kiện (cid:107)xn(cid:107) → (cid:107)x(cid:107) và xn (cid:42) x, thì xn → x khi n → ∞.

Chứng minh. Thật vậy, trong không gian Hilbert nếu xn (cid:42) x0 và (cid:107)xn(cid:107) → (cid:107)x0(cid:107) thì xn → x0. Với mọi x, ta có

(cid:107)xn − x0(cid:107)2 = (cid:104)xn − x0, xn − x0(cid:105)

= (cid:107)xn(cid:107)2 − (cid:104)x0, xn(cid:105) − (cid:104)xn, x0(cid:105) + (cid:107)x0(cid:107)2 .

Từ giả thiết suy ra

(cid:104)x0, xn(cid:105) = (cid:107)x0(cid:107)2. (cid:107)xn(cid:107)2 = (cid:107)x0(cid:107)2, (cid:104)xn, x0(cid:105) = (cid:107)x0(cid:107)2, lim x→∞ lim x→∞ lim x→∞

Do đó

(cid:107)xn − x0(cid:107)2 = (cid:107)x0(cid:107)2. lim x→∞

(cid:3)

Sau đây là các bổ đề được sử dụng trong chương 2.

11

Bổ đề 1.1.19 Cho {ak} là một dãy các số thực không âm sao cho

k=0 δk < ∞. Khi

ak+1 ≤ ak + σk, k ≥ 0,

trong đó σk là một dãy các số thực không âm sao cho (cid:80)∞ đó limk→∞ak tồn tại.

Bổ đề 1.1.20 (Nguyên lý nửa đóng). Cho C là một tập lồi đóng của không

gian Hillbert H và cho f : C → C là một ánh xạ không giãn sao cho F ix(f ) (cid:54)= ∅. Giả sử {xk} là một dãy trong C hội tụ yếu đến x ∈ C và {(I − f )xk} hội tụ mạnh tới y ∈ H. Khi đó (I − f )x = y.

Bổ đề 1.1.21 (Đẳng thức giải) Với mỗi λ, µ > 0, ta có đẳng thức sau

(cid:17) , x ∈ H. x + (1 − )Jλx Jλx = Jµ (cid:16)µ λ µ λ

Bổ đề 1.1.22 Giả sử rằng 0 < c1 ≤ c2. Khi đó

(cid:107) Jc1 − x (cid:107)≤(cid:107) Jc2 − x (cid:107)

với mọi x ∈ H.

Bổ đề 1.1.23 Cho {xn} và {zn} là dãy giới nội trong không gian Banach X và cho {αn} là một dãy trong [0, 1] với

αn < 1. 0 < lim infn→∞αn ≤ lim sup n→∞

Giả sử rằng xn+1 = αnxn + (1 − αn)zn với mọi số nguyên n ≥ 0 và lim supn→∞((cid:107) zn+1 − zn (cid:107) − (cid:107) xn+1 − xn (cid:107)) ≤ 0. Khi đó,

limn→∞ (cid:107) zn − xn (cid:107)= 0.

Bổ đề 1.1.24 Cho {an} là một dãy các số thực không âm thỏa mãn các tính chất

an+1 ≤ (1 − sn)an + sntn + δn, n ≥ 0,

trong đó {sn} ⊂ (0, 1) và {tn} sao cho

12

n=0sn = ∞;

(i) Σ∞

n=0 | sntn |< ∞;

(ii) Hoặc lim supn→∞tn ≤ 0 hoặc Σ∞

n=0σn < ∞.

(iii) Σ∞

Khi đó {an} hội tụ về 0.

1.2 Toán tử đơn điệu cực đại

Định nghĩa 1.2.1 Cho hai không gian tuyến tính 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:

(i) A(x1 + x2) = Ax1 + Ax2 với mọi x1, x2 ∈ X;

(ii) A(αx) = αAx với mọi x ∈ X và mọi α ∈ R.

Chú ý 1.2.2 (1) Điều kiện (i) và (ii) trong Định nghĩa 1.2.1 tương đương

với:

A(α1x1 + α2x2 + ... + αkxk) = α1Ax1 + α2Ax2 + ... + αkAxk

với mọi xi ∈ X với mọi αi ∈ R, i = 1, . . . , k.

(2) Nếu Y ≡ X thì ta cũng nói A là toán tử trong X.

Ký hiệu R(A) là miền giá trị của toán tử A, tức là tập hợp các phần tử y ∈ Y sao cho y = Ax với một x ∈ X nào đó. Nếu y1, y2 ∈ R(A) thì α1y1 + α2y2 ∈ R(A) với mọi α1, α2 ∈ R nên R(A) là một không gian con của Y .

Định nghĩa 1.2.3 Một toán tử A từ X vào Y là liên tục khi và chỉ khi

nó bị chặn (giới nội), nghĩa là tồn tại một hằng số dương K sao cho:

(cid:107)Ax(cid:107) ≤ K (cid:107)x(cid:107) ∀x ∈ X.

Định lý 1.2.4 Một toán tử A từ X vào Y được gọi là bị chặn (giới nội) nếu có một hằng số K > 0 sao cho:

(cid:107)Ax(cid:107) ≤ K. (cid:107)Ax(cid:107) (cid:107)x(cid:107) = sup x>1 (cid:107)A(cid:107) = sup x(cid:54)=0

13

Ký hiệu mặt cầu tâm a bán kính r > 0 trong không gian X là S(a, r),

nghĩa là

S(a, r) = {x ∈ X : (cid:107)x − a(cid:107) = r}.

Hệ quả 1.2.5 Toán tử tuyến tính A bị chặn (liên tục) nếu tập các trị của nó trên một mặt cầu (tùy ý) bị chặn. Chứng minh. Thật vậy, giả sử (cid:107)Ax(cid:107) ≤ N với mọi x ∈ S(x0, α). Khi đó, với mọi x mà (cid:107)x(cid:107) = 1 thì αx + x0 ∈ S, cho nên A(αx + x0) ≤ N , và do đó (cid:107)Aαx + Ax0(cid:107) ≤ N hay α (cid:107)Ax(cid:107) ≤ N + (cid:107)Ax0(cid:107) . Từ đó suy ra

(cid:107)Ax(cid:107) ≤ (N + (cid:107)Ax0(cid:107))/α.

Vậy theo Định lý 1.2.4 ta có:

(cid:107)Ax(cid:107) ≤ K, (cid:107)Ax(cid:107) (cid:107)x(cid:107) = sup x(cid:54)=1 sup x(cid:54)=0

(cid:3) với K = (N + (cid:107)Ax0(cid:107))/α.

Ví dụ 1.2.6 Toán tử A : L2[0, 1] → L2[0, 1] xác định bởi

0

(cid:90) 1 x(s)ds, t ∈ [0, 1] (Ax)(t) =

là toán tử tuyến tính liên tục.

t

Thật vậy, áp dụng Bất đẳng thức Bunhiacopxki ta có

1 (cid:90)

1 (cid:90)

 2  (cid:90) |x(s)|2ds = (cid:107)x(cid:107)2, |x(s)| ds ≤ x(s)ds ≤  

0

0

0

(cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13)

2

t

với mọi t ∈ [0, 1]. Suy ra, A bị chặn. Do đó

1 (cid:90)

(cid:90) dt ≤ (cid:107)x(cid:107)2.

0

0

(cid:12) (cid:12) (cid:12) x(s)ds (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)

Suy ra, A bị chặn.

14

Dễ dàng thấy rằng, A là một toán tử tuyến tính. Do đó, A là toán tử (cid:3) tuyến tính liên tục.

k (cid:88)

Ví dụ 1.2.7 Cho X = Rk, Y = Rm, A(ξ1, ξ2, . . . , ξk) = (η1, η2, . . . , ηm) với

j=1

i = 1, 2, 3, . . . , m, (1.7) ηi = aijξj

trong đó aij là những hằng số. Ma trận

 

   

a11 ... am1 . . . a1k ... . . . · · · amk

k (cid:88)

là ma trận của toán tử A. Thật vậy, (1.7) là dạng tổng quát của toán tử tuyến tính từ Rk vào Rm. Cho A là toán tử tuyến tính bất kì từ Rk vào Rm. Gọi e1, e2, . . . , ek và f1, f2, . . . , fk là các cơ sở của Rk và Rm sao cho với mọi x = (ξ1, ξ2, . . . , ξk) ∈ Rk, y = (η1, η2, . . . , ηm) ∈ Rm:

j=1

x = ξjej

m (cid:88)

và

i=1

y = ηifi

với

e1 = (1, 0, . . . , 0), e2 = (0, 1, . . . , 0), . . . , ek = (0, 0, . . . , 1),

f1 = (1, 0, . . . , 0), f2 = (0, 1, . . . , 0), . . . , fm = (0, 0, . . . , 1).

k (cid:88)

Vì A là toán tử tuyến tính nên

j=1

Ax = ξj(Aej).

Đặt

Ax = (η1, η2, . . . , ηm)

15

Aej = (a1j, a2j, . . . , amj)

(cid:3) ta có (1.7).

Cho H là một không gian Hilbert thực, C là một tập con của H.

Định nghĩa 1.2.8 Tập C ⊂ H là một tập lồi nếu với mọi x1, x2 ∈ C và với mọi số thực λ ∈ [0, 1] ta đều có λx1 + (1 − λ)x2 ∈ C.

Từ định nghĩa trên ta thấy tập ∅ là một tập lồi.

Định nghĩa 1.2.9 Hàm f : C → R được gọi là:

(i) Lồi trên C nếu với mọi λ ∈ [0, 1], với mọi x, y ∈ C thì

f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) ;

(ii) lồi chặt trên C nếu với mọi λ ∈ (0, 1), với mọi x, y ∈ C, x (cid:54)= y thì

f (λx + (1 − λ) y) < λf (x) + (1 − λ) f (y) .

Định nghĩa 1.2.10 Cho C là một tập con lồi đóng, khác rỗng của không gian Hilbert thực H, A : C → H là một ánh xạ. Ánh xạ A được gọi là:

(i) L-liên tục Lipschitz trên C, nếu tồn tại hằng số L > 0 sao cho

(cid:107)A(x) − A(y)(cid:107) ≤ L (cid:107)x − y(cid:107) ∀x, y ∈ C.

Nếu 0 < L < 1 thì A là ánh xạ co, nếu L = 1 thì A là ánh xạ không

giãn;

(ii) bị chặn trên C, nếu với mỗi tập con khác rỗng, bị chặn B của C, tồn

tại hằng số dương kB chỉ phụ thuộc vào tập B sao cho

∀x, y ∈ B; (cid:104)A(x) − A(y), x − y(cid:105) ≤ kB (cid:107)x − y(cid:107)

(iii) bị chặn Lipschitz trên C nếu với mỗi tập con bị chặn B của C, A là

ánh xạ liên tục Lipschitz trên B.

16

Định nghĩa 1.2.11 Cho C là một tập con lồi đóng, khác rỗng của không

gian Hilbert thực H, A : C → H là một ánh xạ. Ánh xạ A được gọi là:

(i) Đơn điệu trên C, nếu

(cid:104)A(x) − A(y), x − y(cid:105) ≥ 0 ∀x, y ∈ C;

(ii) η-đơn điệu mạnh trên C, nếu tồn tại một hằng số η dương sao cho

(cid:104)A(x) − A(y), x − y(cid:105) ≥ η (cid:107)x − y(cid:107)2 ∀x, y ∈ C;

(iii) hemi-liên tục (hemicontinuous) trên C nếu A(x + ty) (cid:42) Ax khi t → 0 với mọi x, y ∈ C và demi-liên tục (demicontinuous) trên C nếu từ xn → x suy ra Axn (cid:42) Ax khi n → ∞;

(iv) bức trên C nếu

= +∞, x ∈ C. lim (cid:107)x(cid:107)→+∞ (cid:104)Ax, x(cid:105) (cid:107)x(cid:107)

Bổ đề 1.2.12 Cho X là không gian Banach thực, X ∗ là không gian đối ngẫu của X, f ∈ X ∗ và A : X → X ∗ là một toán tử hemi-liên tục. Khi đó nếu tồn tại x0 ∈ X thỏa mãn bất đẳng thức:

∀x ∈ X (cid:104)A(x) − f, x − x0(cid:105) ≥ 0,

thì x0 là nghiệm của phương trình A(x) = f . Nếu A là một toán tử đơn điệu trên X thì điều kiện trên tương đương với

∀x ∈ X. (cid:104)A(x0) − f, x − x0(cid:105) ≥ 0,

Tiếp theo chúng tôi sẽ trình bày về bài toán cực tiểu phiếm hàm lồi.

Bài toán cực tiểu phiếm hàm lồi được phát biểu như sau:

min

Tìm z ∈ H sao cho f (z) = x ∈ H f (x).

Điểm cực tiểu của bài toán trên chính là không điểm của toán tử đơn điệu

17

cực đại T = ∂f. Để tìm không điểm của T, Rockafellar đã phát triển thuật

toán điểm gần kề cho bài toán tìm không điểm của ánh xạ đơn điệu cực đại T trong không gian Hilbert thực H. Theo định lý 1.3 nếu T là dưới vi phân của một hàm lồi, chính thường, nửa liên tục dưới f : H → R ∪ {+∞}(tức là T = ∂f ) thì T là toán tử đơn điệu cực đại. Theo định lý Minty, với mỗi z ∈ H và ck > 0, tồn tại duy nhất u ∈ H sao cho

z ∈ (I + ckT )(u).

Khi đó, toán tử Pk = (I + ckT )−1 là đơn trị, xác định trên toàn bộ H và Pk là toán tử không giãn, tức là:

(cid:107) Pk(z) − Pk(z(cid:48)) (cid:107)≤(cid:107) z − z(cid:48) (cid:107)

khi và chỉ khi

z ∈ (I + ckT )(z) = z + ckT (z)

hay 0 ∈ ckT (z). Do đó z là không điểm của ánh xạ T.

Sau đây chúng tôi trình bày 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.13 Toán tử K trên H được gọi là không giãn nếu

(cid:107)x(cid:48) − x(cid:107) (cid:62)(cid:107) y(cid:48) − y (cid:107) ∀(x, y), (x(cid:48), y(cid:48)) ∈ K.

Bổ đề 1.2.14 Mọi toán tử không giãn là đơn trị.

Chứng minh. Cho (x, y1), (x, y2) ∈ K, 0 =(cid:107) x − x (cid:107)(cid:62)(cid:107) y1 − y2 (cid:107), suy ra (cid:3) y1 = y2.

Định nghĩa 1.2.15 K là không giãn chặt nếu

(cid:104)x(cid:48) − x, y(cid:48) − y(cid:105) (cid:62) (cid:107) y(cid:48) − y (cid:107)2 ∀(x, y), (x(cid:48), y(cid:48)) ∈ K.

Bổ đề 1.2.16 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ị.

18

Chứng minh. Cho K là toán tử không giãn chặt. Vì

(cid:104)x(cid:48) − x, y(cid:48) − y(cid:105) (cid:62) (cid:107) y(cid:48) − y (cid:107)2 ∀(x, y), (x(cid:48), y(cid:48)) ∈ K,

nên K là đơn điệu.

Một khái niệm tương đương về toán tử không giãn chặt được đưa ra

như sau:

(cid:107) y(cid:48) − y (cid:107)2 (cid:54) (cid:107) x(cid:48) − x (cid:107)2 − (cid:107) (x(cid:48) − y(cid:48)) − (x − y) (cid:107)2 ∀(x, y), (x(cid:48), y(cid:48)) ∈ 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.14 thì (cid:3) K là đơn trị.

Định nghĩa 1.2.17 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.12

2

2

ta có

2 (cid:54) (cid:107) xk − w (cid:107)

(cid:107) xk+1 − w (cid:107) − (cid:107) xk+1 − xk (cid:107) ∀k (cid:62) 0.

Suy ra khoảng cách giữa xk và những điểm bất động là không tăng, và (cid:107) xk+1 − xk (cid:107) −→ 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.18 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.19 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 trên toàn không gian.

19

Chứng minh. Ta có

(x, y) ∈ T ⇔ (x + y, x) ∈ (I + T )−1 (cid:104)x(cid:48) − x, y(cid:48) − y(cid:105) (cid:62) 0 ⇔ (cid:104)x(cid:48) − x + y(cid:48) − y, x(cid:48) − x(cid:105) (cid:62) (cid:107) x(cid:48) − x (cid:107)2.

Suy ra kết luận thứ nhất.

Mặt khác, theo Bổ đề 1.2.12, 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 trên toàn (cid:3) không gian. Điều này xác minh cho kết luận thứ hai.

Hệ quả 1.2.20 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 trên toàn không gian khi và chỉ khi K −1 − I là đơn điệu cực đại.

Hệ quả 1.2.21 Hàm số từ T (cid:55)−→ (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.22 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 trên toàn không gian.

Chứng minh. Theo Bổ đề 1.1.20, 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 trên toàn không gian.

Bổ đề 1.2.23 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.

Từ đây ta có thể xây dựng xấp xỉ không điểm của toán tử T . Xuất phát

∀r > 0 và x0 ∈ H ta có

xk+1 = Jr,T (xk) = (I + rT )−1xk.

20

Rockafellar [11] đã 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

xk+1 = Jrk,T (xk) = (I + rkT )−1xk.

Mệnh đề 1.2.24 Cho T là toán tử đơn điệu cực đại. Nếu zer(T ) (cid:54)= ∅, 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 mà ta cần lưu ý là 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 trên toàn không gian, 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.

1.3 Phương pháp điểm gần kề cổ điển

Cho H là một không gian Hillbert thực với tích vô hướng (cid:104)., .(cid:105) và chuẩn

(cid:107) . (cid:107) và cho T là một toán tử với miền xác định D(T) và miền giá trị

R(T) trong H. T được gọi là toán tử đơn điệu nếu đồ thị của nó G(T ) = {(x, y) ∈ H × H : x ∈ D(T ), y ∈ T x} là một tập đơn điệu trong H × H.

Có nghĩa là T là đơn điệu khi và chỉ khi

(x, y), (x(cid:48), y(cid:48)) ∈ G(T ) ⇒ (cid:104)x − x(cid:48), y − y(cid:48)(cid:105) ≥ 0,

Toán tử đơn điệu T được gọi là đơn điệu cực đại nếu đồ thị G(T) không nằm thực sự trong đồ thị của toán tử đơn điệu bất kì khác trong H.

Giả sử rằng T là toán tử đơn điệu cực đại trong H. Ta gọi z ∈ D(T ) là một không điểm của T nếu 0 ∈ T z. Ta kí hiệu S là tập không điểm của T, S = T −1.

Một bài toán quan trọng trong lý thuyết toán tử đơn điệu cực đại là tìm

một điểm trong tập nghiệm S, với giả thiết rằng S khác rỗng. Có nhiều bài toán, ví dụ, quy hoạch lồi và bất đẳng thức biến phân có thể phát

biểu dưới dạng tìm không điểm của toán tử đơn điệu cực đại. Thuật toán

đơn điệu cực đại được xem xét như là một thuật toán hữu hiệu trong việc

21

tìm nghiệm của toán tử đơn điệu cực đại. Xuất phát từ z0 ∈ H cho trước, thuật toán điểm gần kề đề xuất một dãy {zk} theo bao hàm thức

(1.7) zk ∈ zk+1 + ckT zk+1,

ở đây ck > 0 là một tham số hiệu chỉnh. Vì giải bài toán bao hàm thức (1.7) là khó hơn là giải bài toán ban đầu

tìm một nghiệm của bao hàm thức 0 ∈ T z, một thuật toán có tính ứng dụng được đề xuất bởi Rockaffellar [5] sai số của thuật toán điểm gần kề đưa đến một dãy {ek} theo hệ thức sau:

(1.8) zk + ek ∈ zk+1 + ckT zk+1,

∞ (cid:88)

ở đây ek là một dãy các sai số. Tiêu chuẩn chính xác của dãy ek của thuật toán điểm gần kề có sai số (1.8) có thể được nghiên cứu rộng rãi sao cho sự hội tụ mạnh của (1.8) được đảm bảo. Hai tiêu chuẩn được đưa ra như sau:

k=1

∞ (cid:88)

(1.9) (cid:107) ek (cid:107)≤ εk, εk < ∞,

k=1

(1.10) (cid:107) ek (cid:107)≤ δk (cid:107) zk+1 − zk (cid:107), δk < ∞.

∞ (cid:88)

Sử dụng tiêu chuẩn (1.9), Rockafellar chứng minh sự hội tụ yếu của thuật toán (1.8) với điều kiện dãy tham số ck bị chặn dưới bởi hằng số khác 0. He cũng nhận được tốc độ hội tụ khi sử dụng tiêu chuẩn (1.10). Một tiêu chuẩn khác được đưa ra như sau:

k < ∞.

k=1

η2 (1.11) (cid:107) ek (cid:107)≤ ηk (cid:107) zk+1 − zk (cid:107),

Nếu H là một không gian Hillbert hữu hạn chiều thì dãy {zk} đưa ra bởi thuật toán (1.8) hội tụ đến một điểm trong S với điều kiện (1.11) thỏa mãn và dãy hiệu chỉnh {ck} bị chặn dưới bởi 0.

22

Ackstein và Bertsekas xét thuật toán điểm gần kề suy rộng dưới đây:

(1.12) zk+1 = (1 − ρk)zk + ρkwk, k ≥ 0

trong đó ρk ∈ (0, 2)(∀k) và

(cid:107) wk − (I + ckT )−1zk (cid:107)≤ εk, k ≥ 0.

∞ (cid:88)

Họ chứng minh sự hội tụ yếu của thuật toán (1.12) cho

k=1

< ∞, infkck > 0

và có một số ρ ∈ (0, 2) với tính chất

ρ ≤ ρk ≤ 2 − ρ, ∀k ≥ 0.

Mặt khác, vì thuật toán điểm gần kề (1.7) không hội tụ mạnh nên một

điều thú vị đưa ra là làm thế nào cải biên thuật toán điểm gần kề (1.7) sao cho sự hội tụ mạnh được đảm bảo. Năm 2002, Xu đưa ra một cải biên

của thuật toán điểm gần kề co như sau:

(1.13) zk+1 = λku + (1 − λk)(I + ckT )−1zk + ek, k ≥ 0

và chứng minh sự hội tụ mạnh của (1.13) với điều kiện dãy {ck} tiến tới vô cùng.

Mới đây, Marino và Xu tiếp tục xem xét thuật toán gần kề co (1.13) và

nhận được một số sự hội tụ mạnh với một số điều kiện nhất định.

Trong chương này chúng tôi đã 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, giới thiệu về một số kiến thức của giải tích lồi, về toán tử đơn điệu cực đại và phương pháp điểm gần kề cổ điển.

Trong chương sau, chúng tôi sẽ trình bày hai phương pháp điểm gần kề suy rộng tìm không điểm của toán tử đơn điệu cực đại trong không gian

Hilbert.

23

Chương 2

Thuật toán điểm gần kề suy rộng

Chương này trình bày hai phương pháp để giải bài toán tìm không điểm

của toán tử đơn điệu cực đại trong không gian Hilbert. Các kiến thức của chương được tổng hợp từ tài liệu [4], [5], [6], [7], [8], [9], [10], [11].

2.1 Thuật toán điểm gần kề suy rộng của Ackstein và Bertsekas

Ackstein và Bertsekas đã đưa ra thuật toán điểm gần kề suy rộng như

sau:

(2.1) zk+1 = (1 − ρk)zk + ρkJck(zk) + ek, k ≥ 0,

trong đó ek là một sai số.

Thuật toán của Ackstein và Bertsekas mở rộng thuật toán của Gol’shtein

và Tret’yakov được định nghĩa

(2.2) zk+1 = (1 − ρk)zk + ρkJc(zk) + ek, k ≥ 0.

Gol’shtein và Tret’yakov xét thuật toán (2.2) trong một không gian hữu

hạn chiều và không cho phép thông số c thay đổi theo từng bước lặp.

Kí hiệu wω(zk) là tập điểm tụ yếu của {zk}. Khi đó, wω(zk) là tập tất

cả các điểm mà là giới hạn yếu của dãy {zk}.

Bổ đề 2.1.1 Cho {zk} được sinh ra bởi thuật toán (2.1), khi đó {zk} hội tụ yếu đến z ∈ S khi và chỉ khi wω(zk) ⊂ S.

Đầu tiên xét thuật toán của Gol’shtein và Tret’yakov (2.2) với các sai

24

số, cụ thể là thuật toán sau:

(2.3) zk+1 = (1 − ρk)zk + ρkJc(zk) + ek, k ≥ 0.

Định lý 2.1.2 Cho {zk} được sinh ra bởi thuật toán (2.3). Giả sử rằng limk→∞ (cid:107) ek (cid:107)= 0 và 0 < lim infk→∞ρk ≤ lim supk→∞ρk < 1. Khi đó {zk} hội tụ yếu đến một điểm của S.

Chứng minh. Đầu tiên, ta thấy rằng {zk} là giới nội. Khi đó, chọn p ∈ S, khi đó ta có

(cid:107) zk+1 − p (cid:107) ≤ (1 − ρk) (cid:107) zk − p (cid:107) +ρk (cid:107) Jc(zk) − p (cid:107) + (cid:107) ek (cid:107)

≤ ((1 − ρk) (cid:107) zk − p (cid:107) +ρk (cid:107) zk − p (cid:107) + (cid:107) ek (cid:107)

=(cid:107) zk − p (cid:107) + (cid:107) ek (cid:107) .

Vì vậy, theo Bổ đề 1.1.19, limk→∞ (cid:107) zk+1 − p (cid:107) tồn tại. Điều đó suy ra {zk} giới nội, đặt zk+1 = (1 − ρk)zk + ρkyk. Chú ý rằng {yk} giới nội. Khi đó ta có:

− yk+1 − yk = zk+2 − (1 − ρk+1)zk+1 ρk+1 zk+1 − (1 − ρk)zk ρk (2.4)

− . = Jc(zk+1) − Jc(zk) + ek+1 ρk+1 ek ρk

Từ tính không giãn của Jc và (2.4), ta có:

(cid:107) yk+1 − yk (cid:107) − (cid:107) zk+1 − zk (cid:107)≤ (cid:107) ek+1 (cid:107) + (cid:107) ek (cid:107), 1 ρk+1 1 ρk

từ đó suy ra rằng (lưu ý limk→∞ (cid:107) ek (cid:107)= 0 )

(2.5) sup((cid:107) yk+1 − yk (cid:107) − (cid:107) zk+1 − zk (cid:107)≤ 0. lim k→∞

(cid:107) zk − yk (cid:107) . Từ (2.5) và Bổ đề 2.1.1 suy ra lim k→∞

(cid:107) Jc(zk) − zk (cid:107)= 0. Khi Vì vậy limk→∞ (cid:107) zk+1 − zk (cid:107)= 0, do đó ta có lim k→∞

đó áp dụng Bổ đề 1.1.20 ta thấy wω(zk) ⊂ F ix(Jc) = S, theo Bổ đề 1.1.19, {zk} hội tụ yếu tới một điểm trong S. Điều này kết thúc chứng minh. (cid:3)

25

Lúc này ta cho ck thay đổi với các bước lặp và nghiên cứu sự hội tụ của

thuật toán điểm gần kề của Ackstein và Bertsekas (2.1).

Định lý 2.1.3 Cho {zk} được sinh ra bởi (2.1). Giả sử có các điều kiện sau:

∞ (cid:80) k=1

(i) (cid:107) ek (cid:107)< ∞;

(ii) 0 < lim infk→∞ρk ≤ lim supk→∞ρk < 1;

(iii) ck ≥ c,trong đó c là hằng số;

(iv) ck+1 − ck → 0.

Khi đó {zk} hội tụ yếu đến một điểm trong S.

Chứng minh. Lấy một điểm p ∈ S và lưu ý rằng Jrp = p với mọi r > 0. Từ (2.1), ta có

(cid:107) zk+1 − p (cid:107) ≤ (1 − ρk) (cid:107) zk − p (cid:107) +ρk (cid:107) Jc(zk) − p (cid:107) + (cid:107) ek (cid:107)

(2.6) ≤ ((1 − ρk) (cid:107) zk∂ − p (cid:107) +ρk (cid:107) zk − p (cid:107) + (cid:107) ek (cid:107)

= (cid:107) zk − p (cid:107) + (cid:107) ek (cid:107).

Từ Bổ đề 1.1.19, (i) và (2.6), ta suy ra

(cid:107) zk+1 − p (cid:107) lim k→∞

tồn tại và điều đó suy ra rằng {zk} là giới nội. Đặt zk+1 = (1−ρk)zk +ρkyk. Khi đó ta có

− yk+1 − yk =

zk+1 − (1 − ρk)zk ρk . − zk+2 − (1 − ρk+1)zk+1 ρk+1 = Jck+1(zk+1) − Jc(zk) + ek+1 ρk+1 ek ρk

Nếu ck ≤ ck+1, từ Bổ đề 1.1.21, sử dụng đẳng thức

zk+1 + (1 − )Jck+1(zk+1)) Jck+1(zk+1) = Jck( ck ck+1 ck ck+1

26

ta được

(cid:107) Jck+1(zk+1) − Jck(zk) (cid:107) ≤

(cid:107) zk+1 − zk (cid:107) (cid:17) ck ck+1 (cid:16) 1 − + (cid:107) Jck+1(zk+1) − zk (cid:107) ck ck+1

≤(cid:107) zk+1 − zk (cid:107)

+ |ck+1 − ck| (cid:107) Jck+1(zk+1) − zk (cid:107) . 1 c

Nếu ck > ck+1, theo Bổ đề 1.1.21

(cid:16) (cid:17) (cid:17) 1 − zk + (cid:107) Jck(zk) − Jck+1(zk+1) (cid:107) =(cid:107) Jck+1 Jck(zk) (cid:16)ck+1 ck ck+1 ck

− Jck+1(zk+1) (cid:107)

≤

(cid:16) ck+1 ck 1 − + (cid:107) Jck(zk) − zk+1 (cid:107) (cid:107) zk − zk+1 (cid:107) (cid:17) ck+1 ck

≤(cid:107) zk+1 − zk (cid:107)

+ |ck+1 − ck| (cid:107) Jck(zk) − zk+1 (cid:107) . 1 c

Từ các đánh giá trên, ta có

(2.7) |ck+1 − ck| , (cid:107) Jck+1(zk+1) − Jck(zk) (cid:107)≤(cid:107) zk+1 − zk (cid:107) + M c

trong đó M là hằng số sao cho

sup{ (cid:107) Jck+1(zk+1) − Jck(zk) (cid:107), Jck(zk) − Jck(zk+1) (cid:107), k ≥ 0} ≤ M.

Vì thế, ta có

+ (cid:107) yk+1 − yk (cid:107) ≤(cid:107) Jck+1(zk+1) − Jck(zk) (cid:107) + (cid:107) ek+1 (cid:107) ρk+1 (cid:107) ek (cid:107) ρk

+ . |ck+1 − ck| + ≤(cid:107) zk+1 − zk (cid:107) + M c (cid:107) ek+1 (cid:107) ρk+1 (cid:107) ek (cid:107) ρk

27

Suy ra

sup((cid:107) yk+1 − yk (cid:107) − (cid:107) zk+1 − zk (cid:107)≤ 0. lim k→∞

Bằng suy luận tương tự chứng minh của Định lý 2.1.2, ta có

(2.8) (cid:107) Jckzk − zk (cid:107)= 0. lim k→∞

Tiếp theo, từ Bổ đề 1.1.22 và (2.8)

(cid:107) Jczk − zk (cid:107)= 0. lim k→∞

Kết hợp với Bổ đề 1.1.20 suy ra

wω(zk) ⊂ F ix(Jc) = S.

Vì vậy, Bổ đề 2.1.1 đảm bảo rằng {zk} hội tụ yếu tại một điểm trong S. (cid:3) Điều này kết thúc chứng minh.

Chú ý 2.1.4 (1) Mặc dù thuật toán (2.3) là trường hợp riêng của thuật toán (2.1), tuy nhiên việc chứng Định lý 2.1.2 là đơn giản hơn nhiều

so với Định lý 2.1.3.

k=1

(2) Lưu ý rằng (cid:88)∞ (cid:107) ek (cid:107)< ∞

suy ra limk→∞ (cid:107) ek (cid:107)= 0. Khi đó không thể nhận được Định lý 2.1.2 từ Định lý 2.1.3.

(3) Chú ý rằng giả thiết

k=1

(cid:88)∞ (cid:107) ck+1 − ck (cid:107)< ∞

dẫn đến

(ck+1 − ck) = 0. lim k→∞

28

(4) Các kết quả của Định lý 2.1.2 và 2.1.3 mở rộng và làm tốt một số kết

quả khác, cụ thể là kết quả của Marino và Xu.

2.2 Thuật toán điểm gần kề co

Thuật toán điểm gần kề chỉ có sự hội tụ yếu. Mới đây một số cải biên

thuật toán điểm gần kề với sự hội tụ mạnh đã được đề xuất (xem [9], [10], [11]). Thuật toán điểm gần kề co mở rộng được phát biểu như sau: cho u ∈ H, và {zk} được cho bởi công thức

(2.9) zk+1 = λku + γkzk + δkJck(zk) + ek, k ≥ 0,

Trong đó λk, γk, δk ∈ (0, 1) và λk + γk + δk = 1, ∀k ≥ 0, ck > 0 và ek là một sai số.

Chú ý 2.2.1 Chú ý rằng thuật toán (2.9) chứa cả thuật toán của Marino

và Xu.

Định lý 2.2.2 Cho {zk} được tạo bởi thuật toán điểm gần kề co (2.9). Giả sử rằng

k=0 λk = ∞;

(i) limk→∞λk = 0; (ii) (cid:80)∞

(iii) 0 < lim infk→∞γk ≤ lim supk→0γk < 1;

(iv) ck ≥ c; trong đó c là hằng số;

k=1 (cid:107) ek (cid:107)< ∞.

(v) ck+1 − ck → 0; (vi) (cid:80)∞

Khi đó {zk} hội tụ mạnh tới một điểm z ∈ S là điểm chiếu gần nhất của u lên S.

29

Chứng minh. Lấy p ∈ S. Chú ý rằng Jc là không giãn, ta có

(cid:107) zk+1 − p (cid:107) =(cid:107) λk(u − p) + γk(zk − p)

+ δk(Jck(zk) − p)+ (cid:107) ek (cid:107) ≤ λk (cid:107) u − p (cid:107) +γk (cid:107) zk − p (cid:107)

+ δk (cid:107) zk − p (cid:107) + (cid:107) ek (cid:107)

= λk (cid:107) u − p (cid:107) +(1 − λk) (cid:107) zk − p (cid:107) + (cid:107) ek (cid:107) .

k (cid:88)

Suy ra

i=0

(cid:107) ei (cid:107), k ≥ 0. (cid:107) zk − p (cid:107)≤ max{(cid:107) u − p (cid:107), (cid:107) z0 − p (cid:107) } +

Vì vậy {zk} là giới nội.

Tiếp theo cần chứng minh wω(zk) ⊂ S. Để điều này kết thúc chứng

minh thì (cid:107) zk+1 − zk (cid:107)→ 0. Đặt zk+1 = γkzk + (1 − γk)yk. Khi đó ta có

− yk+1 − yk = zk+2 − γk+1zk+1 1 − γk+1 zk+1 − γkzk 1 − γk

=

− λk+1u − δk+1Jck+1(zk+1) + ek+1 1 − γk+1 λku + δkJck(zk) + ek 1 − γk (cid:19) (cid:18) λk+1 u − = (2.10) λk 1 − γk

+

(Jck+1(zk+1) − Jck(zk)) (cid:19) 1 − γk+1 δk+1 1 − γk+1 (cid:18) δk+1 − + Jck(zk) 1 − γk+1 (cid:19) (cid:18) ek+1 + − . 1 − γk+1 δk 1 − γk ek 1 − γk

30

Lập luận tương tự như (2.7), ta cũng có

|ck+1 − ck| , (cid:107) Jck+1(zk+1) − Jck(zk) (cid:107)≤(cid:107) zk+1 − zk (cid:107) + M1 c

trong đó M1 là hằng số sao cho

sup{(cid:107) Jck+1(zk+1) − zk (cid:107), (cid:107) Jck(zk) − zk+1 (cid:107), k ≥ 0} ≤ M1.

Khi đó ta có

− (cid:107) u (cid:107) + (cid:107) yk+1 − yk (cid:107) ≤ (cid:107) zk+1 − zk (cid:107) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) δk+1 1 − γk+1 λk 1 − γk

+ |ck+1 − ck| M1 c

− + (cid:107) Jck(zk) (cid:107) (cid:12) (cid:12) (cid:12) (cid:12)

+ , + λk+1 1 − γk+1 δk+1 1 − γk+1 (cid:12) δk+1 (cid:12) (cid:12) 1 − γk+1 (cid:12) (cid:107) ek+1 (cid:107) 1 − γk+1 δk 1 − γk (cid:107) ek (cid:107) 1 − γk

từ đó suy rằng

sup((cid:107) yk+1 − yk (cid:107) − (cid:107) zk+1 − zk (cid:107)) ≤ 0. lim n→∞

Từ Bổ đề 1.1.23, ta có

(cid:107) zk − yk (cid:107)= 0. lim n→∞

vậy nên

(2.11) (cid:107) zk+1 − zk (cid:107)= 0. lim n→∞

Lưu ý rằng

(cid:107) zk − Jck(zk) (cid:107) ≤(cid:107) zk+1 − zk (cid:107) + (cid:107) zk+1 − Jck(zk) (cid:107) ≤(cid:107) zk+1 − zk (cid:107) +λk (cid:107) u − Jck(zk) (cid:107) + γk (cid:107) zk − Jck(zk) (cid:107) + (cid:107) ek (cid:107),

31

như vậy

(cid:107) zk+1 − zk (cid:107) (cid:107) zk − Jck(zk) (cid:107) ≤

+ (cid:107) ek (cid:107) . (cid:107) u − Jck(zk) (cid:107) + 1 1 − γk λk 1 − γk 1 1 − γk

Kết hợp với (i), (iii), (vi) và (2.11) suy ra rằng

(cid:107) zk − Jck(zk) (cid:107)= 0. lim k→∞

Từ Bổ đề 1.1.22 ta có

(cid:107) zk − Jck(zk) (cid:107)= 0. lim k→∞

Khi đó, ta có wω(zk) ⊂ F ix(Jc) = S. Bây giờ đặt z = PSu và lấy một dãy {zkj } của {zk} sao cho

(cid:10)u − z, zkj − z(cid:11) , (cid:104)u − z, zk − z(cid:105) = lim j→∞ lim sup k→∞

và zkj → z(cid:48) hội tụ yếu. Vì z(cid:48) ∈ S, nên ta có

(2.12) (cid:104)u − z, zk − z(cid:105) = (cid:104)u − PSu, z(cid:48) − PSu(cid:105) ≤ 0. lim sup k→∞

Cuối cùng áp dụng Bổ đề 1.1.24, ta có

(cid:107) zk+1 − z(cid:107)2 =(cid:107) λk(u − z) + γk(zk − z) + δk(Jck(zk) − z) + ek(cid:107)2

≤ [ (cid:107) λk(u − z) + γk(zk − z) + δk(Jck(zk) − z) + (cid:107)ek(cid:107)]2 =(cid:107) λk(u − z) + γk(zk − z) + δk(Jck(zk) − z)(cid:107)2 + (cid:107) ek (cid:107) { (cid:107) ek (cid:107) +2 (cid:107) λk(u − z) + γk(zk − z)

+ δk(Jck(zk) − z) (cid:107) }

32

≤(cid:107) λk(u − z) + γk(zk − z) + δk(Jck(zk) − z)(cid:107)2 +M2 (cid:107) ek (cid:107) ≤(cid:107) γk(zk − z) + δk(Jck(zk) − z)(cid:107)2 + 2λk (cid:104)u − z, zk+1 − z − ek(cid:105)

(2.13)

+ M2 (cid:107) ek (cid:107) ≤ (γk (cid:107) zk − z (cid:107) +δk (cid:107) zk − z) (cid:107) )2 + 2λk (cid:104)u − z, zk+1 − z(cid:105)

+ (2λk (cid:107) u − z (cid:107) +M2) (cid:107) ek (cid:107) ≤ (1 − λk) (cid:107) zk − z(cid:107)2 + 2λk (cid:104)u − z, zk+1 − z(cid:105) + (2λk (cid:107) u − z (cid:107) +M2) (cid:107) ek (cid:107),

trong đó M2 > 0 là hằng số sao cho

sup { (cid:107) ek (cid:107) +2 (cid:107) λk(u − z) + γk(zk − z) + δk(Jck(zk) − z) (cid:107) } ≤ M2

với mọi k ≥ 0. Theo Bổ đề 1.1.24, (2.12) và (2.13), ta có thể kết luận rằng zk → z hội tụ (cid:3) mạnh. Điều này kết thúc chứng minh.

Hệ quả 2.2.3 Cho {zk} được sinh ra bởi thuật toán

zk+1 = λku + γkzk + δkJc(zk) + ek, k ≥ 0,

trong đó c > 0 là một hằng số. Giả sử rằng

k=0 λk = ∞;

(i) limk→∞λk = 0; (ii) (cid:80)∞

k=0 (cid:107) ek (cid:107)< ∞.

(iii) 0 < lim infk→∞γk ≤ lim supk→∞γk ≤ 1; (iv) (cid:80)∞

Khi đó {zk} hội tụ mạnh tại một điểm z ∈ S là hình chiếu của u lên S.

Ví dụ 2.2.4 Cho φ : H → R ∪ {∞} là hàm lồi thực sự liên tục dưới. Cho

33

∂φ là dưới vi phân của φ, khi đó,

∂φ(x) = {z ∈ H : φ(y) ≥ φ(x) + (cid:104)y − x, z(cid:105), ∀y ∈ H}, x ∈ dom(∂φ).

Điều đó cho thấy ∂ là một toán tử đơn điệu cực đại trên H. Cụ thể

0 ∈ ∂φ(x) tương đương với x là một điểm cực tiểu của φ trên

H : φ(x) = inf{φ(v) : v ∈ H}.

Cho T = ∂φ. Giả sử rằng, tập cực tiểu S của φ trên H là không rỗng. Nếu H là vô hạn, thì khi đó thuật toán điểm gần kề của Rockafellar chỉ có hội

tụ yếu. Mặc dù vậy, thuật toán điểm gần kề co (2.9) lại có sự hội tụ mạnh.

k=1 |ck+1 − ck| < ∞ suy ra ck+1−ck → 0;

Chú ý 2.2.5 (1) Rõ ràng rằng (cid:80)∞

k=1 |λk+1 − λk| < ∞ hoặc limk→∞λk/λk+1 = 1,

(2) Ta bỏ giả thiết (cid:80)∞

nhưng ta thêm một ràng buộc yếu hơn nhiều 0 < lim infk→∞γk < lim supk→∞γk < 1.

34

Kết luận

Đề tài luận văn đã trình bày một số thuật toán điểm gần kề suy rộng

tìm không điểm của toán tử đơn điệu cực đại trong không gian Hilbert. 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, thuật toán điểm gần kề cổ điển;

(2) Trình bày thuật toán điểm gần kề suy rộng của Eckstein và Bertsekas

tìm không điểm của toán tử đơn điệu cực đại;

(3) Trình bày thuật toán điểm gần kề co tìm không điểm của toán tử đơn

điệu cực đại.

Mặc dù đã có sự cố gắng và nỗ lực nhưng đề tài luận văn không tránh

khỏi những hạn chế và thiếu sót. Em rất mong nhận được sự đóng góp quý

báu của các thầy giáo, cô giáo và các bạn học viên để đề tài được hoàn thiện hơn.

35

Tài liệu tham khảo

Tiếng Việt

[1] Đỗ 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.

[2] 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.

Tiếng Anh

[3] Y. Yao and M.A. Noor (2008), "On convergence criteria of general- ized proximal point algorithms", Journal of computational and Applied

Mathematics 217, 46-55.

[4] A. Bnouhachem and M.A. Noor (2006), "Inexact proximal point

method for general variational inequalities", Journal of Mathematics

Analysis and Applications 324, 1195-1212.

[5] R.T. Rokafellar (1976), "Monotone Operators and the Proximal Point

Algorithm", SIAM Journal on Control and Optimization 14, 877-898.

[6] J. Eckstein (1988), "The Lions-Mercier splitting algorithm and the

alternating direction method are instances of the proximal point al-

gorithm", Report LIDS-P-1769, Laboratory for Information and De- cision Sciences.

[7] D. Bertsekas and J. Tsitsiklis (1989), "Parallel and Distributed Com- putation: Numerical Methods", Englewood Cliffs: Prentice-Hall.

36

[8] H. Brézis (1973), "Opérateurs Maximaux Monotones et Semi-Groupes

de Contractions dans les Espaces de Hilbert", Amsterdam: North - Holland.

[9] B.S. He (1999), "Inexact implicit methods for monotone general vari-

ational inequalities", Math. Programming 86 113-123.

[10] E.G. Gol’shtein and N.V. Tret’yakov (1979), "Modified Lagrangians in

convex programming and their generalizations", Math. Programming Stud. 10 86-97.

[11] H.K. Xu (2002), "Iteratve algorithms for nonlinear operators", J. Lon-

don Math. Soc. 66 240-256.