ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC -------------------------------

TRẦN THỊ HƯƠNG THƠM

NGHIỆM XẤP XỈ 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 - 2016

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC -------------------------------

TRẦN THỊ HƯƠNG THƠM

NGHIỆM XẤP XỈ 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

NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS. Nguyễn Bường

THÁI NGUYÊN - 2016

i

Mục lục

Bảng ký hiệu ii

Mở đầu 1

1 Không gian Hilbert 3

3 1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . .

3 1.1.1 Khái niệm và ví dụ . . . . . . . . . . . . . . . . . . .

8 1.1.2 Một số tính chất của không gian Hilbert . . . . . . .

1.1.3 Phép chiếu mêtric . . . . . . . . . . . . . . . . . . . . 10

1.2 Toán tử đơn điệu và toán tử đơn điệu cực đại . . . . . . . . 11

1.3 Một số phương pháp tìm không điểm của toán tử đơn điệu . 14

1.3.1 Phương pháp điểm gần kề . . . . . . . . . . . . . . . 16

1.3.2 Phương pháp lặp Mann . . . . . . . . . . . . . . . . 17

1.3.3 Phương pháp lặp Halpern . . . . . . . . . . . . . . . 17

2 Xấp xỉ không điểm của toán tử đơn điệu cực đại 18

2.1 Phương pháp xấp xỉ không điểm của toán tử đơn điệu cực đại18

2.1.1 Mô tả phương pháp . . . . . . . . . . . . . . . . . . . 18

2.1.2 Định lý hội tụ mạnh . . . . . . . . . . . . . . . . . . 19

2.1.3 Định lý hội tụ yếu . . . . . . . . . . . . . . . . . . . 23

2.2 Áp dụng cho bài toán cực tiểu . . . . . . . . . . . . . . . . . 30

Kết luận 34

Tài liệu tham khảo 35

ii

Bảng ký hiệu

N tập số nguyên không âm

N∗ tập số nguyên dương

R tập số thực

H không gian Hilbert thực

C tập con đóng lồi của H

∅ tập rỗng

∀x mọi x

∃x tồn tại 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 (cid:42) x T xn hội tụ mạnh đến x xn hội tụ yếu x toán tử đơn điệu trong không gian Hilbert

I toán tử đồng nhất trong H

toán tử giải của T

phép chiếu mêtric từ H lên tập lồi C của H

Jr PC lim supn→∞ xn lim infn→∞ xn ∂f giới hạn trên của dãy số {xn} giới hạn dưới của dãy số {xn} dưới vi phân của hàm lồi f

1

Mở đầu

Toán tử đơn điệu là một công cụ hiệu quả và được sử dụng rộng rãi

trong nhiều lĩnh vực khác nhau của toán học như: phương trình vi phân,

lý thuyết tối ưu, lý thuyết xác suất, kinh tế,. . . Đặc biệt trong giải tích

lồi, tính lồi của một hàm nửa liên tục dưới có thể được đặc trưng bởi tính

đơn điệu của dưới vi phân của nó.

Ta xét bài toán

Tìm một phần tử v ∈ H sao cho 0 ∈ T v, (1)

trong không gian Hilbert thực H, ở đây T : H → 2H là một toán tử đơn

điệu cực đại.

Một phương pháp phổ biến để giải bài toán (1) là phương pháp điểm

gần kề được đề xuất và nghiên cứu bởi Rockafellar [12] vào năm 1976.

Phương pháp này được xây dựng như sau: xuất phát từ điểm x0 = x ∈ H, dãy lặp {xn} trong H được xác định bởi

n = 0, 1, 2, . . . (2) xn+1 = Jrnxn,

trong đó Jrn = (I + rnT )−1 và {rn} là một dãy số thực dương. Rockafellar [12] đã chứng minh được tính hội tụ yếu của phương pháp (2) về một

nghiệm của bài toán (1).

Năm 1991, Guler [7] đã chỉ ra rằng phương pháp điểm gần kề (2) không

hội tụ mạnh trong không gian Hilbert vô hạn chiều bằng một ví dụ. Năm

2004, Bauschke, Matousková và Reich [11] cũng đã chỉ ra ví dụ mà phương

2

pháp điểm gần kề chỉ hội tụ yếu nhưng không hội tụ theo chuẩn. Do đó,

vấn đề nghiên cứu, cải tiến phương pháp điểm gần kề (2) nhằm thu được

sự hội tụ mạnh cũng đã được nhiều nhà toán học trên thế giới quan tâm,

chẳng hạn như Kamimura và Takahashi [13], Tan và Xu [14],. . .

Mục đích của đề tài luận văn nhằm trình bày các nghiên cứu xây dựng

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 thực. Nội dung của luận văn được trình bày trong hai chương:

Chương 1: Trình bày về không gian Hilbert, một số tính chất của

không gian Hilbert, toán tử đơn điệu, toán tử đơn điệu cực đại, bài

toán và một số phương pháp tìm không điểm của toán tử đơn điệu

cực đại làm cơ sở nghiên cứu cho Chương 2.

Chương 2: Trình bày hai phương pháp tìm xấp xỉ không điểm của

toán tử đơn điệu cực đại trong không gian Hilbert thực. Phần cuối

của chương là áp dụng cho bài toán tìm điểm cực tiểu của hàm lồi.

Luận văn này được thực hiện tại Trường Đại học Khoa học – Đại học

Thái Nguyên và hoàn thành dưới sự hướng dẫn của GS.TS. Nguyễn Bường.

Tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy, người đã tận tình

hướng dẫn, giúp đỡ cho tác giả trong quá trình học tập, nghiên cứu và viết

luận văn này.

Tác giả 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, TS. Nguyễn Thị Thu

Thủy cùng toàn thể các thầy cô trong trường đã giảng dạy và giúp đỡ cho

tác giả trong suốt thời gian học tập tại trường.

Tác giả xin bày tỏ lòng cảm ơn tới trường THPT Chu Văn An – Thái

Nguyên, tập thể lớp Cao học Toán K8A (khóa 2014-2016), bạn bè, đồng

nghiệp và gia đình đã tạo điều kiện, động viên, giúp đỡ tác giả trong quá

trình học tập, nghiên cứu.

3

Chương 1

Không gian Hilbert

Chương này trình bày các khái niệm và tính chất của không gian Hilbert,

toán tử đơn điệu, toán tử đơn điệu cực đại và một số phương pháp tìm

không điểm của toán tử đơn điệu cực đại. Các kiến thức của chương này

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

1.1 Không gian Hilbert

1.1.1 Khái niệm và ví dụ

Định nghĩa 1.1.1 Cho H là không gian vectơ trên R, tích vô hướng xác

định trong H là một ánh xạ

(cid:104)., .(cid:105) :H × H −→ R

(x, y) (cid:55)−→ (cid:104)x, y(cid:105)

thỏa mãn các điều kiện sau đây

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

2. (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;

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

4. (cid:104)x, x(cid:105) ≥ 0 với mọi x ∈ H và (cid:104)x, x(cid:105) = 0 ⇔ x = 0.

Số (cid:104)x, y(cid:105) được gọi là tích vô hướng của hai vectơ x, y trong H.

4

Nhận xét 1.1.2 Từ định nghĩa suy ra

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

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

3. (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.3 Cặp (H, (cid:104)., .(cid:105)), trong đó H là một không gian tuyến tính trên R, (cid:104)., .(cid:105) là tích vô hướng trên H được gọi là không gian tiền

Hilbert thực.

Định lý 1.1.4 (Bất đẳng thức Cauchy - 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 y = 0, bất đẳng thức hiển nhiên đúng.

Giả sử y (cid:54)= 0, khi đó với mọi số λ ∈ R ta đều có

(cid:104)x + λy, x + λy(cid:105) ≥ 0,

tức là

(cid:104)x, x(cid:105) + λ(cid:104)y, x(cid:105) + λ(cid:104)x, y(cid:105) + |λ|2(cid:104)y, y(cid:105) ≥ 0.

ta được Chọn λ = − (cid:104)x, y(cid:105) (cid:104)y, y(cid:105)

≥ 0 (cid:104)x, x(cid:105) − |(cid:104)x, y(cid:105)|2 (cid:104)y, y(cid:105)

⇔ |(cid:104)x, y(cid:105)|2 ≤ (cid:104)x, x(cid:105).(cid:104)y, y(cid:105).

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

Nhận xét 1.1.5 Dấu trong bất đẳng thức Cauchy-Schwarz xảy ra khi và

chỉ khi x và y phụ thuộc tuyến tính.

5

Mối quan hệ giữa khái niệm chuẩn và tích vô hướng được thể hiện qua

định lý sau.

Định lý 1.1.6 Mọi không gian tiền Hilbert H đều là không gian tuyến

tính định chuẩn, với chuẩn được xác định bởi công thức

(1.2) (cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105) ∀x ∈ H.

Chuẩn này được gọi là chuẩn cảm sinh từ tích vô hướng.

Nhận xét 1.1.7 Với kí hiệu này, bất đẳng thức Schwarz được viết lại

thành

|(cid:104)x, y(cid:105)| ≤ (cid:107)x(cid:107)(cid:107)y(cid:107).

Như vậy một không gian tiền Hilbert được xem như không gian định

chuẩn có thể đầy đủ hoặc không đầy đủ.

Định nghĩa 1.1.8 Nếu H là 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.9 Trong không gian Rn cho Không gian Rn với:

k=1 xkyk dễ dàng chứng minh được hàm số trên thỏa mãn

x = (x1, x2, . . . , xn); y = (y1, y2, . . . , yn) ∈ Rn,

n (cid:88)

n (cid:88)

đặt (cid:104)x, y(cid:105) = (cid:80)n các điều kiện về tích vô hướng. Ngoài ra, với x = (x1, . . . , xn) ∈ Rn,

k=1

k=1

(cid:107)x(cid:107)2 = (cid:104)x, x(cid:105) = xkxk = |xk|2,

nên Rn là một không gian Hilbert.

Để nghiên cứu về không gian l2(Λ), trước hết ta cần mở rộng khái niệm tổng của một họ (tùy ý) các phần tử của không gian định chuẩn. Cho

6

Λ (cid:54)= ∅ là một tập hợp, X là một không gian định chuẩn và f : Λ → X là

một ánh xạ. Ký hiệu F(Λ) là họ tất cả các tập con hữu hạn của Λ. Với

t∈F

mỗi F ∈ F(Λ), đặt (cid:88) S(F ) = f (t) ∈ X.

Giả sử tồn tại S ∈ X thỏa mãn: với mỗi ε > 0, tồn tại F0 ∈ F(Λ) sao cho với mọi F ∈ F(Λ), F ⊃ F0 thì (cid:107)S(F ) − S(cid:107) < ε. Khi đó ta nói họ S(F ) hội = S. Trong trường hợp này ta nói S là tổng tụ về S và kí hiệu là lim F ∈F(Λ)

của họ các phần tử {f (t)}t∈Λ trong không gian định chuẩn X và viết:

t∈Λ

(cid:88) S = f (t).

Ví dụ 1.1.10 Cho Λ là một tập hợp khác rỗng tùy ý. Ký hiệu l2(Λ) là tập hợp các hàm số f xác định trên Λ lấy giá trị trên K sao cho

t∈Λ

(cid:88) |f (t)|2 < ∞.

Với f, g ∈ l2(Λ), λ ∈ K, đặt

(f + g)(t) = f (t) + g(t)

(λf )(t) = λf (t).

Dễ chứng minh được l2(Λ), với hai phép toán trên là một không gian tuyến tính. Ngoài ra, với f, g ∈ l2(Λ), với mỗi t ∈ λ, ta có |f (t)g(t)| ≤ |f (t)|2 + |g(t)|2. Điều này kéo theo

t∈Λ

t∈Λ

t∈Λ

(cid:88) (cid:88) (cid:88) |f (t)g(t)| ≤ |f (t)|2 + |g(t)|2.

f (t)g(t) là tồn tại với mỗi f, g ∈ l2(Λ). Do đó (cid:80) t∈Λ

7

Xét hàm số (cid:104)., .(cid:105) : l2(Λ) × l2(Λ) → K, xác định bởi

t∈Λ

(cid:88) (cid:104)f, g(cid:105) = f (t)g(t)

với mỗi f, g ∈ l2(Λ). Dễ chứng minh được (cid:104)., .(cid:105) thỏa mãn các điều kiện về tích vô hướng. Suy ra l2(Λ) là không gian tiền Hilbert.

Với mỗi f ∈ l2(Λ),

t∈Λ

t∈Λ

(cid:88) (cid:88) (cid:107)f (cid:107)2 = (cid:104)f, f (cid:105) = f (t)f (t) = |f (t)|2.

Thực hiện việc chứng minh giống như trong l2, ta cũng có l2(Λ) đầy đủ. Như vậy l2(Λ) là không gian Hilbert.

Ví dụ 1.1.11 Không gian (cid:32)L2(X, µ): Cho (X, M, µ) là một không gian độ đo. Với f, g ∈ (cid:32)L2(X, µ), đặt

X

(cid:90) (cid:104)f, g(cid:105) = f gdµ. (1.3)

Chú ý rằng, tích phân vế phải luôn tồn tại và hữu hạn vì theo bất đẳng

1/2

thức Holder:

1/2 

X

X

X

   (cid:90) (cid:90) (cid:90) < +∞. |g|dµ |f |2dµ |f g|dµ ≤    

Dễ chứng minh được hàm số xác định bởi (1.3) là tích vô hướng trên

1/2

1/2

(cid:32)L2(X, µ). Ngoài ra ta thấy với mỗi f ∈ (cid:32)L2(X, µ),

X

X

    (cid:90) (cid:90) ||f || = (cid:112)(cid:104)f, f (cid:105) = f f dµ = |f |2dµ .    

Điều này kéo theo (cid:32)L2(X, µ) là một không gian Hilbert.

8

Khi X = N∗ và µ({n}) = 1 với mọi n ∈ N∗ thì ta có l2 là không gian

∞ (cid:88)

Hilbert với tích vô hướng

n=1

(cid:104)x, y(cid:105) = xnyn,

trong đó x = (xn); y = (yn) ∈ l2.

1.1.2 Một số tính chất của không gian Hilbert

Định lý 1.1.12 Cho X là một không gian tiền Hilbert. Khi đó tích vô

hướng là một hàm số liên tục trên X × X.

xn = x0 ∈ X, lim x→∞ Chứng minh. Giả sử {(xn, yn)} là một dãy các phần tử hội tụ về (x0, y0) yn = y0 ∈ X. Khi đó với mỗi trong X × X, tức là lim x→∞ n ∈ N∗,

| (cid:104)xn, xn(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) |

(1.4) = | (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) + ||y0(cid:107).(cid:107)xn − x0(cid:107)

Do xn → x0 nên dãy {xn} là giới nội, tức là tồn tại K > 0 sao cho (cid:107)xn(cid:107) ≤ K với mọi n ∈ N∗. Từ (1.4) ta có

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

Điều này kéo theo tích vô hướng là hàm số liên tục.

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

Định lý 1.1.13 Nếu E là một tập lồi đóng trong không gian Hilbert H thì

tồn tại một phần tử duy nhất x0 ∈ E sao cho

với mọi x ∈ E. (cid:107)x0(cid:107) ≤ (cid:107)x(cid:107),

9

Chứng minh. Áp dụng đẳng thức hình bình hành, với mọi x, y ∈ E ta có (cid:107)x + y(cid:107)2 + (cid:107)x − y(cid:107)2 = 2((cid:107)x(cid:107) + (cid:107)y(cid:107))2 do đó

. (1.5) (cid:13) (cid:107)x − y(cid:107)2 = 2((cid:107)x(cid:107)2 + (cid:107)y(cid:107)2) − 4 (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) x + y 2

(cid:107)x(cid:107). Đặt d = inf x∈E

∈ E, kéo theo Vì E là một tập lồi nên (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) ≥ d. Từ (1.5) ta x + y 2 x + y 2 có

(cid:107)x − y(cid:107)2 ≤ 2((cid:107)x(cid:107)2 + (cid:107)y(cid:107)2) − 4d2. (1.6)

Từ đó, nếu (cid:107)x(cid:107) = (cid:107)y(cid:107) = d thì x = y. Suy ra, x0 trong định lý nếu tồn tại là duy nhất. Từ định nghĩa của d suy ra tồn tại một dãy {xn} các phần tử của E sao cho

(cid:107)xn(cid:107) = d. lim n→∞

Theo (1.6), với mỗi m, n ∈ N∗, ta có

(cid:107)xn − yn(cid:107)2 ≤ 2((cid:107)xn(cid:107)2 + (cid:107)yn|2) − 4d2 → 0 khi m, n → ∞.

Suy ra {xn} là dãy Cauchy trong không gian Hilbert H nên nó hội tụ đến x0 ∈ H. Do E là một tập hợp đóng nên x0 ∈ E. Suy ra

(cid:107)xn(cid:107) = d. (cid:107)x0(cid:107) = lim n→∞

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

Hệ quả 1.1.14 Nếu E là một tập lồi đóng trong không gian Hilbert H thì

mỗi phần tử x ∈ H, tồn tại một phần tử duy nhất y ∈ E sao cho

(cid:107)x − u(cid:107). (cid:107)x − y(cid:107) = ρ(x, E) = inf u∈E

10

Chứng minh. Ta thấy tập x − E = {x − u : u ∈ E} là một tập đóng

trong H. Theo (1.1.13), tồn tại duy nhất một phần tử y ∈ E sao cho

(cid:107)x − u(cid:107). (cid:107)x − y(cid:107) ≤ (cid:107)x − u(cid:107) với mọi u ∈ E hay (cid:107)x − y(cid:107) = ρ(x, E) = inf u∈E (cid:3) Hệ quả được chứng minh.

Mệnh đề 1.1.15 Trong không gian Hilbert thực H ta có

(cid:107)λx + (1 − λ)y(cid:107)2 ≤ λ(cid:107)x(cid:107)2 + (1 − λ)(cid:107)y(cid:107)2,

với mọi x, y ∈ H và λ ∈ [0; 1].

Định nghĩa 1.1.16 Cho H là không gian Hilbert. Dãy {xn} được gọi là hội tụ mạnh tới phần tử x ∈ H, ký hiệu xn → x, nếu (cid:107)xn − x(cid:107) → 0 khi n → ∞.

Định nghĩa 1.1.17 Cho H là không gian Hilbert. Dãy {xn} được gọi là hội tụ yếu tới phần tử x ∈ H, ký hiệu xn (cid:42) x, nếu (cid:104)xn, y(cid:105) → (cid:104)x, y(cid:105) khi n → ∞ với mọi y ∈ H.

Nhận xét 1.1.18 Trong không gian Hilbert H:

a) Hội tụ mạnh kéo theo hội tụ yếu, nhưng điều ngược lại không đúng.

b) 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 → ∞.

1.1.3 Phép chiếu mêtric

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

gian Hilbert thực H. Ta biết rằng với mỗi x ∈ H đều tồn tại phần tử

PCx ∈ C thỏa mãn

(cid:107)x − y(cid:107). (cid:107)x − PC(x)(cid:107) = inf y∈C

Phần tử PC(x) được xác định như trên được gọi là hình chiếu của x lên C và ánh xạ PC : H → C biến mỗi phần tử x ∈ H thành PC(x) được gọi

11

là phép chiếu mêtric từ H lên C.

Đặc trưng của phép chiếu mêtric được cho bởi mệnh đề dưới đây.

Mệnh đề 1.1.20 Cho C là tập con lồi, đóng, khác rỗng của không gian

Hilbert thực H. Khi đó, ánh xạ PC : H → C là phép chiếu mêtric từ H lên C khi và chỉ khi

với mọi y ∈ C. (cid:104)x − PC(x), y − PC(y)(cid:105) ≤ 0

Nhận xét 1.1.21 Về phương diện hình học, với mọi y ∈ C, nếu ta gọi α

. là góc tạo bởi các véctơ x − PC(x) và y − PC(y), thì α ≥ π 2

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

Định nghĩa 1.2.1 Cho X, Y ⊂ H và F : X → 2Y là các ánh xạ từ tập X vào tập hợp gồm các tập con của Y (được kí hiệu là 2Y ). Khi đó ta nói

F là ánh xạ đa trị từ X vào Y . Như vậy với mỗi x ∈ X, F (x) là một tập

con của Y (F (x) có thể là tập rỗng).

Nếu với mọi x ∈ X, tập F (x) chỉ có đúng một phần tử thì ta nói F là

ánh xạ đơn trị từ X vào Y và được kí hiệu F : X → Y .

Ví dụ 1.2.2 Xét phương trình đa thức

xn + a1xn−1 + ... + an−1x + an = 0,

trong đó n ∈ Z ∗, ai ∈ R(i = 1, · · · , n). Quy tắc cho tương ứng mỗi điểm a = (a1, a2, a3, · · · , an) ∈ R với tập nghiệm của phương trình trên, ký hiệu bởi F (a) cho ta ánh xạ đa trị F : Rn → 2C trong đó C là tập hợp số phức.

Định nghĩa 1.2.3 Ánh xạ đa trị T : H → 2H với miền hữu hiệu

domT = {z ∈ H : T z (cid:54)= ∅}

12

và miền ảnh

R(T ) = ∪{T z : z ∈ domT }.

T được gọi là đơn điệu nếu (cid:104)x1 − x2, y1 − y2(cid:105) ≥ 0 ∀xi ∈ domT và yi ∈ T xi, i = 1, 2

Ví dụ 1.2.4 Ví dụ dơn giản nhất về các toán tử đơn điệu là các toán tử

tuyến tính và đơn trị. Chẳng hạn, nếu H là một không gian Hillbert thực và T : H → H ∗ ≡ H là một ánh xạ tuyến tính thì T là đơn điệu khi và

chỉ khi T là toán tử dương, nghĩa là (cid:104)T x, x(cid:105) ≥ 0, ∀x ∈ H.

Ví dụ 1.2.5 Cho D là một tập con khác rỗng của tập số thực R. Một hàm ϕ : D → R∗ ≡ R là một toán tử đơn điệu khi và chỉ khi ϕ là một

hàm đơn điệu không giảm theo nghĩa thông thường.

Thật vậy, nếu ϕ là một hàm đơn điệu không giảm theo nghĩa thông

thường thì

∀t1, t2 ∈ D, t1 < t2 ⇒ ϕ(t1) ≤ ϕ(t2)

hay

[ϕ(t2) − ϕ(t1)](t2 − t1) ≥ 0, ∀t1, t2 ∈ D.

Định nghĩa 1.2.6 Cho ánh xạ đa trị T : H → 2H được gọi là:

(i) Nửa liên tục trên tại x ∈ domT nếu với mọi tập mở V ⊃ T (x), tồn tại

lân cận mở U của x sao cho

T (x(cid:48)) ⊆ V, ∀x(cid:48) ∈ U ;

(ii) Nửa liên tục dưới tại x ∈ domT nếu với mọi tập mở V ⊂ H thỏa mãn

T (x) ∩ V (cid:54)= ∅, tồn tại lân cận mở U của x sao cho

T (x(cid:48)) ∩ V (cid:54)= ∅, ∀x(cid:48) ∈ U ∩ domT ;

(iii) Nửa liên tục tại x ∈ domT nếu T đồng thời nửa liên tục trên và nửa

liên tục dưới tại x;

13

(iv) Nửa liên tục trên (nửa liên tục dưới) trên H nếu T 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;

(v) Nếu T liên tục tại mọi điểm thuộc H thì T được gọi là liên tục trên

H.

Định nghĩa 1.2.7 Cho C ⊆ H là tập khác rỗng. Ánh xạ đa trị F : C → 2H được gọi là liên tục Lipschitz với hệ số L > 0 (viết tắt là L-Lipschitz)

trên C nếu

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

Nếu L < 1 thì ta nói F là ánh xạ co trên C.

Nếu L = 1 thì ta nói F là ánh xạ không giãn trên C.

Định nghĩa 1.2.8 Một toán tử đơn điệu T được gọi là đơn điệu cực đại

nếu đồ thị G(T ) = {(x, y) : y ∈ T x} không chứa thực sự trong đồ thị của

toán tử đơn điệu khác.

Mệnh đề 1.2.9 Cho toán tử đơn điệu T trên H, T là đơn điệu cực đại

khi và chỉ khi R(I + T ) = H.

Định nghĩa 1.2.10 Cho T : H → 2H là một toán tử đơn điệu cực đại, với mỗi r > 0 một toán tử Jr : H → H xác định bởi Jr = (I + rT )−1 được gọi là toán tử giải (ánh xạ gần kề) của T trong đó I là toán tử đồng nhất

trong H.

Mệnh đề 1.2.11 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 = (I + rT )−1 là không giãn (do đó là đơn trị) và có miền xác định đầy đủ.

Mệnh đề 1.2.12 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(x) = {x}.

14

Chứng minh. Bằng cách tính trực tiếp, Jr = {(x + ry, x) | (x, y) ∈ T }. Vì vậy

0 ∈ T x ⇔ (x, 0) ∈ T ⇔ (x, x) ∈ Jr.

(cid:3) vì Jr là đơn trị nên phần chứng minh được kết thúc.

Ta xác định toán tử xấp xỉ Ar bằng

. Ar = I − Jr r

Ta biết rằng

Arx ∈ T Jrx và ||Arx|| ≤ inf{||y|| : y ∈ T x}

với mọi x ∈ H. Ta có T −10 = F (Jr), ∀r > 0. Rockafellar [12] và Takahashi [13] đã chỉ ra rằng

||Jrx − Jry||2 + r2||Arx − Ary||2 ≤ ||x − y||2

với mọi x, y ∈ H và r > 0.

Nhận xét 1.2.13 Cho f : H → (−∞; +∞] là hàm lồi, chính thường, nửa

liên tục dưới. Ta xác định dưới vi phân ∂f của f bởi

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

∂f là một toán tử đơn điệu cực đại từ H vào H.

1.3 Một số phương pháp tìm không điểm của toán tử đơn điệu

Cho H là không gian Hilbert thực, toán tử T : 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 ∈ T z. (1.7)

15

Nếu T là đơn trị thì đây chính là bài toán giải phương trình T z = 0.

Nếu T 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 T.

Về mặt hình thức thì 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 điểm

bất động . . .

Trong trường hợp T 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à T = ∂f ) thì T là toán tử đơn

điệu cực đại và khi đó bài toán (1.7) sẽ trở thành bài toán:

f (x) Tìm z ∈ H sao cho f (z) = 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 ∈ T 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.

Điều này cho thấy việc tìm không điểm của toán tử đơn điệu cực đại

tương đương với việc tìm cực tiểu hàm lồi và nửa liên tục dưới f .

Trong mục này ta trình bày phương pháp lặp Mann, phương pháp lặp

Halpern và phương pháp điểm gần kề để tìm nghiệm của bài toán 0 ∈ T z

trong trường hợp T là toán tử đơn điệu cực đại.

Ta biết rằng, với mỗi z ∈ H và r > 0, tồn tại duy nhất u ∈ H sao cho

z ∈ (I + rT )(u).

16

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

(cid:107)Jr(z) − Jr(z(cid:48))(cid:107) ≤ (cid:107)z − z(cid:48)(cid:107).

Từ đây ta nhận thấy mặc dù T là ánh xạ đa trị, đơn điệu cực đại nhưng

ánh xạ Jr là đơn trị và không giãn trên H. Nếu z là điểm bất động của ánh xạ Jr, nghĩa là z = Jr(z) = (I + rT )−1(z) thì

z ∈ (I + rT )(z) = z + rT (z)

hay 0 ∈ rT (z). Do vậy z là không điểm của toán tử T . Như vậy thay vì

tìm không điểm của ánh xạ đa trị T ta đi tìm điểm bất động của ánh xạ

không giãn Jr với r > 0.

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

Bước 1: Chọn điểm xuất phát x0 = x ∈ H, dãy số {rn} là một dãy số thực dương, với mọi n = 1, 2, 3, . . .. Ta xây dựng công thức truy hồi.

Bước n: Xây dựng dãy điểm {xn} ⊂ H bằng cách: tại bước lặp thứ n ta tính xn+1 bởi công thức

n = 0, 1, 2, . . . xn+1 = Jrnxn,

trong đó Jrn = (I + rnT )−1 và {rn} là một dãy số thực dương.

Rockafellar [12] đã chỉ ra rằng dãy {xn} hội tụ yếu đến một phần tử x∞ sao cho 0 ∈ T (x∞).

Sau đây là hai phương pháp lặp cơ bản tìm điểm bất động của ánh xạ

không giãn.

17

1.3.2 Phương pháp lặp Mann

Phương pháp này được Mann [10] nghiên cứu và đề xuất năm 1953. Về

cơ bản là tạo ra một dãy số theo sơ đồ lặp:

(cid:40)

(1.8) x0 = x ∈ H xn+1 = αnxn + (1 − αn)U xn,

với mọi n = 0, 1, 2, . . ., trong đó x0 = x ∈ H, {αn} là một dãy trong [0; 1] và U : H → H là ánh xạ không giãn.

Dãy lặp (1.8) được gọi là dãy lặp Mann.

Mann [10] đã chứng minh được dãy {xn} sinh bởi (1.8) hội tụ yếu tới z ∈ Fix(U ) với tâp Fix(U ) là tập các điểm bất động của U , nghĩa là

FixU := {x ∈ H : U (x) = x}.

1.3.3 Phương pháp lặp Halpern

Một phương pháp khá thông dụng, đảm bảo sự hội tụ mạnh của dãy

lặp là phương pháp lặp do Halpern [8] đề xuất vào năm 1967 như sau:

(cid:40)

(1.9) x0 = x ∈ H xn+1 = αnx + (1 − αn)U xn,

với mọi n = 0, 1, 2, . . . trong đó {αn} là một dãy trong (0; 1).

Dãy lặp (1.9) được gọi là dãy lặp Halpern.

Nếu Fix(U ) (cid:54)= ∅ thì dãy {xn} sinh bởi (1.9) hội tụ mạnh đến z ∈ Fix(U ).

18

Chương 2

Xấp xỉ không điểm của toán tử đơn

điệu cực đại

Chương này trình bày hai phương pháp xấp xỉ không điểm của toán tử

đơn điệu cực đại trong không gian Hilbert H. Cụ thể, trình bày một dãy lặp hội tụ mạnh tới phần tử v ∈ T −10, và sự hội tụ yếu của phương pháp

điểm gần kề. Phần cuối của chương là một áp dụng cho bài toán tìm điểm

cực tiểu của hàm lồi. Nội dung của chương được tổng hợp từ các tài liệu

[4]–[14].

2.1 Phương pháp xấp xỉ không điểm của toán tử đơn điệu cực

đại

2.1.1 Mô tả phương pháp

Cho H là không gian Hilbert thực. Dựa trên cơ sở các phương pháp

(1.8) và (1.9) ta xét các phương pháp lặp sau:

(2.1) xn+1 = αnx + (1 − αn)Jrnxn n = 0, 1, 2, . . .

và

(2.2) xn+1 = αnxn + (1 − αn)Jrnxn n = 0, 1, 2, . . .

19

trong đó x0 = x ∈ H, {αn} ⊂ [0; 1] và {rn} ⊂ (0; ∞).

Ta sẽ chứng minh dãy {xn} sinh bởi (2.1) hội tụ mạnh tới v ∈ T −10 và dãy {xn} sinh bởi (2.2) hội tụ yếu tới v ∈ T −10. Hơn nữa sử dụng kết quả này ta xét trong trường hợp T = ∂f , với f là một hàm lồi.

2.1.2 Định lý hội tụ mạnh

Cho T : H → 2H là một toán tử đơn điệu cực đại, cho Jr : H → H là

toán tử giải của T ta xét thuật toán sau: Dãy {xn} được tạo bởi

(2.3)

   x0 = x ∈ H yn ≈ Jrnxn xn+1 = αnx + (1 − αn)yn,

với n ∈ N, {αn} ⊂ [0; 1] và {rn} ⊂ (0; ∞) và tiêu chuẩn để tìm xấp xỉ yn trong công thức (2.3) là

∞ (cid:88)

(2.4) (cid:107)yn − Jrnxn(cid:107) ≤ δn

n=0

trong đó δn < ∞. Ta có định lý sau.

Định lý 2.1.1 Cho H là không gian Hilbert thực, T : H → 2H là một

toán tử đơn điệu cực đại, x ∈ H, {xn} là dãy tạo bởi (2.3) theo tiêu chuẩn (2.4), với {αn} ⊂ [0; 1] và {rn} ⊂ (0; +∞) thỏa mãn

∞ (cid:88)

αn = 0; (i) lim n→∞

n=0

(ii) αn = ∞ và;

rn = ∞. (iii) lim n→∞

Khi đó, nếu T −10 (cid:54)= ∅ thì dãy {xn} hội tụ mạnh tới P x trong đó P là phép chiếu mêtric từ H lên T −10.

20

Chứng minh. Từ T −10 (cid:54)= ∅ suy ra tồn tại u ∈ T −10 sao cho Jsu = u với mọi s > 0. Khi đó ta có

(cid:107)x1 − u(cid:107) = (cid:107)α0x + (1 − α0)y0 − u(cid:107)

≤ α0(cid:107)x − u(cid:107) + (1 − α0)(cid:107)y0 − u(cid:107)

≤ α0(cid:107)x − u(cid:107) + (1 − α0)(δ0 + (cid:107)Jr0x0 − u(cid:107))

≤ α0(cid:107)x − u(cid:107) + (1 − α0)(δ0 + (cid:107)x0 − u(cid:107))

≤ (cid:107)x − u(cid:107) + δ0.

k−1 (cid:88)

Nếu

i=0

(cid:107)xk − u(cid:107) ≤ (cid:107)x − u(cid:107) + δi

k (cid:88)

với bất kì k ∈ N\{0} thì

i=0

∞ (cid:88)

(cid:107)xk+1 − u(cid:107) ≤ (cid:107)x − u(cid:107) + δi.

n=0

Do đó, từ δn < ∞ và dãy {xn} giới nội, suy ra các dãy {Jrnxn} và {yn}

cũng giới nội. Cho rn → ∞ ta nhận được

= 0. (cid:107)Arnxn(cid:107) = lim n→∞ lim n→∞ (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) xn − Jrnxn rn

Tiếp theo ta chứng minh

(2.5) (cid:104)x − P x, yn − P x(cid:105) ≤ 0, lim sup n→∞

trong đó P là phép chiếu mêtric từ H lên T −10.

Để chứng minh được điều này, ta chứng minh

(cid:104)x − P x, Jrnxn − P x(cid:105) ≤ 0. lim sup n→∞

21

Vì yn − Jrnxn → 0 khi đó tồn tại dãy con {xni} ⊂ {xn} sao cho

n→∞

xni − P x(cid:105) = lim sup (cid:104)x − P x, Jrnxn − P x(cid:105). (cid:104)x − P x, Jrni lim sup i→∞

xni} hội tụ yếu tới v ∈ H,

Do {Jrnxn} giới nội, ta có thể giả thiết rằng {Jrni từ đó suy ra v ∈ T −10.

Do Arnxn ∈ T Jrnxn và T đơn điệu nên

xni(cid:105) ≥ 0 với z(cid:48) ∈ T z. (cid:104)z − Jrni xni, z(cid:48) − Arni

Từ Arnxn → 0, ta nhận được (cid:104)z − v, z(cid:48)(cid:105) ≥ 0 với z(cid:48) ∈ T z. Do đó từ tính đơn điệu cực đại của T , ta có v ∈ T −10, vì P là phép chiếu mêtric từ H lên T −10 nên ta nhận được:

i→∞

(cid:104)x − P x, Jrnxn − P x(cid:105) = lim sup xni − P x(cid:105) (cid:104)x − P x, Jrni lim sup n→∞

= (cid:104)x − P x, v − P x(cid:105) ≤ 0.

n=0

∞ (cid:88)

Vì vậy ta có (2.5). ∞ (cid:88) Cho ε > 0, từ δn < ∞, (2.5) và αn → 0, tồn tại m ∈ N sao cho

j=m

M δj ≤

(cid:104)x − P x, yn − P x(cid:105) ≤

∀n ≥ m αn(cid:107)x − P x(cid:107)2 ≤ ε 2 ε 6 ε 6

(δn + 2(cid:107)xn − P x(cid:107)). Từ đây suy ra trong đó M = sup n∈N

(cid:107)xn+m+1 − P x(cid:107)2 = (cid:107)αn+mx + (1 − αn+m)yn+m − P x(cid:107)2

n+m(cid:107)x − P x(cid:107)2 + (1 − αn+m)2(cid:107)yn+m − P x(cid:107)2 + 2αn+m(1 − αn+m)(cid:104)x − P x, yn+m − P x(cid:105)

= α2

22

≤ αn+m + (1 − αn+m)(δn+m + (cid:107)Jrn+mxn+m − P x(cid:107))2

≤ αn+m + (1 − αn+m)(δn+m + (cid:107)xn+m − P x(cid:107))2

≤ αn+m + (1 − αn+m)(δn+mM + (cid:107)xn+m − P x(cid:107)2)

≤ αn+m + δn+mM ε 2 ε 2 ε 2 ε 2

∀n ∈ N. + (1 − αn+m)||xn+m − P x||2,

Bằng phương pháp quy nạp ta nhận được

n+m (cid:89)

(cid:40) (cid:41)

j=m

1 − (cid:107)xn+m+1 − P x(cid:107)2 ≤ (1 − αj)

n+m (cid:88)

j=m

j=m

(cid:41) ε 2 (cid:40) n+m (cid:89) + M δj + (cid:107)xm − P x(cid:107)2 (1 − αj)

với mọi n ∈ N. Từ đó suy ra

n+m (cid:88)

j=m (cid:32)

(cid:41) (cid:40) n+m (cid:89) + M (cid:107)xn+m+1 − P x(cid:107)2 ≤ δj + (1 − αj) (cid:107)xm − P x(cid:107)2 ε 2

n+m (cid:88)

j=m n+m (cid:88)

(cid:33)

j=m

j=m

≤ + M − δj + exp αj (cid:107)xm − P x(cid:107)2. ε 2

n=0 αn = ∞ ta có

Do đó, từ (cid:80)∞

∞ (cid:88)

(cid:107)xn+m+1 − P x(cid:107)2 lim sup n→∞ (cid:107)xn − P x(cid:107)2 = lim sup n→∞

j=m

≤ + M δj ≤ ε. ε 2

(cid:3) Vì ε bất kì, nên suy ra dãy {xn} → P x. Định lý được chứng minh.

23

2.1.3 Định lý hội tụ yếu

Trong mục này ta trình bày sự hội tụ yếu của thuật toán điểm gần kề.

Dãy {xn} được tạo bởi

  (2.6)

 x0 = x ∈ H yn ≈ Jrnxn xn+1 = αnxn + (1 − αn)yn, n ∈ N,

với {αn} ⊂ [0; 1] và {rn} ⊂ (0; ∞).

Bổ đề 2.1.2 Cho T : H → 2H là một toán tử đơn điệu cực đại và P là phép chiếu mêtric từ H lên T −10. Cho x ∈ H và dãy {xn} xác định bởi (2.6) theo tiêu chuẩn (2.4), với {αn} ⊂ [0; 1] và {rn} ⊂ (0; ∞). Nếu T −10 (cid:54)= ∅ thì dãy {P xn} hội tụ mạnh tới v ∈ T −10, là phần tử duy nhất của T −10 sao cho

(cid:107)xn − u(cid:107) : u ∈ T −10}. lim n→∞ (cid:107)xn − v(cid:107) = inf{ lim n→∞

Chứng minh. Cho u ∈ T −10 khi đó ta có

(cid:107)xn+1 − u(cid:107) = (cid:107)αnxn + (1 − αn)yn − u(cid:107)

≤ αn(cid:107)xn − u(cid:107) + (1 − αn)(cid:107)yn − u(cid:107)

≤ αn(cid:107)xn − u(cid:107) + (1 − αn)(δn + (cid:107)Jrnxn − u(cid:107))

≤ αn(cid:107)xn − u(cid:107) + (1 − αn)(δn + (cid:107)xn − u(cid:107))

≤ (cid:107)xn − u(cid:107) + δn.

n=0 δn < ∞ tồn tại

với mọi n ∈ N. Vì vậy từ (cid:80)∞

(cid:107)xn − u(cid:107) g(u) = lim n→∞

với g là hàm lồi liên tục và g(u) → ∞ hay (cid:107)u(cid:107) → ∞, vì vậy g đạt được giá trị cực tiểu trên T −10.

24

Cho

l = inf{g(u) : u ∈ T −10}

và

K = {w ∈ T −10 : g(w) = l}.

Cố định v ∈ K, vì P là phép chiếu mêtric từ H lên T −10, ta có

(cid:107)xn − P xn(cid:107) ≤ (cid:107)xn − v(cid:107)

với mọi n ∈ N và vì thế

(cid:107)xn − P xn(cid:107) ≤ l. lim sup n→∞

n→∞

Giả thiết rằng lim sup (cid:107)xn − P xn(cid:107) < l.

Tiếp theo ta chọn a > 0 và m ∈ N sao cho

∀n ≥ m. (cid:107)xn − P xn(cid:107) ≤ l − a,

n+h (cid:88)

n+h (cid:88)

Khi đó,

i=n

i=n

(cid:107)xn+h+1 − P xn(cid:107) ≤ (cid:107)xn − P xn(cid:107) + δi ≤ l − a + δi,

n+h (cid:88)

với mọi n ≥ m, h ∈ N. Từ đây suy ra

i=n

(cid:107)xn+h+1 − P xn(cid:107) ≤ l − a + δi, l ≤ lim h→∞ (cid:107)xh − P xn(cid:107) = lim h→∞

n=0 kết luận rằng

với mọi n ≥ m. ∞ (cid:88) Từ δn < ∞ ta có l ≤ l − a < l điều này mâu thuẫn, vì vậy ta có thể

(cid:107)xn − P xn(cid:107) = l. lim sup n→∞

25

Tiếp đến ta chỉ ra

P xn = v. lim n→∞

(cid:114)

∞ (cid:88)

h(cid:48) ≥ h. Cho b > 0 sao cho b < l2 + − l thì ta có giá trị h(cid:48) ∈ N sao cho Nếu không tồn tại ε > 0 sao cho với bất kì h ∈ N, (cid:107)P xh(cid:48) − v(cid:107) ≥ ε với ε2 8

i=h(cid:48)

M δi ≤ ε2 8

(cid:107)xh(cid:48) − P xh(cid:48)(cid:107) ≤ l + b

(cid:107)xh(cid:48) − v(cid:107) ≤ l + b,

∞ (cid:88)

trong đó

n=0

M = xn − P xn + v 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) . (cid:13) (cid:13) δn + 2 sup n∈N

Khi đó ta có

n+h(cid:48) (cid:88)

(cid:33)2

i=h(cid:48)

n+h(cid:48) (cid:88)

≤ + xn+h(cid:48)+1 − xh(cid:48) − δ2 i P xh(cid:48) − v 2 P xh(cid:48) + v 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:32)(cid:13) (cid:13) (cid:13) (cid:13) (cid:13)

i=h(cid:48)

+ M ≤ δi xh(cid:48) − P xh(cid:48) + v 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13)

n+h(cid:48) (cid:88)

= 2 + 2 xh(cid:48) − P xh(cid:48) 2 xh(cid:48) − v 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13)

i=h(cid:48)

− 2 + M δi P xh(cid:48) − v 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13)

n+h(cid:48) (cid:88)

(cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:32) (cid:32) (cid:33)2 (cid:33)2

i=h(cid:48)

n+h(cid:48) (cid:88)

≤ 2 + 2 − + M δi l + b 2 l + b 2 ε2 4

i=h(cid:48)

+ M ≤ (l + b)2 − δi ε2 4

26

với mọi n ∈ N. Từ đó ruy ra

xn+h(cid:48)+1 − l2 ≤ lim h→∞ (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13)

i=h(cid:48)

P xh(cid:48) + v 2 ∞ (cid:88) ≤ (l + b)2 − + M δi ε2 4

≤ (l + b)2 − < l2. ε2 8

Điều này mâu thuẫn. Do đó dãy {P xn} hội tụ mạnh tới v ∈ T −10, dẫn đến v là một phần tử duy nhất của T −10 sao cho

g(v) = inf{g(u) : u ∈ T −10}.

(cid:3) Điều phải chứng minh.

Định lý 2.1.3 Cho T : H → 2H là một toán tử đơn điệu cực đại và P là phép chiếu mêtric từ H lên T −10. Cho x ∈ H và dãy {xn} là dãy tạo bởi (2.6) theo tiêu chuẩn (2.4), {αn} ⊂ [0; 1] và {rn} ⊂ (0; +∞) thỏa mãn rn = ∞. Nếu T −10 (cid:54)= ∅ thì {xn} hội αn ∈ [0; k] trong đó 0 < k < 1 và lim n→∞ tụ yếu tới v ∈ T −10, trong đó v = lim P xn. n→∞

Chứng minh. Theo chứng minh Bổ đề 2.1.2, luôn tồn tại

(cid:107)xn − u(cid:107) ∀u ∈ T −10 lim n→∞

đặc biệt tồn tại dãy {xn} giới nôi do đó tồn tại dãy con {xni} ⊂ {xn} sao cho {xni} hội tụ yếu đến v ∈ H. Ta sẽ chứng minh v ∈ T −10.

Trước tiên ta chứng minh

(cid:107)xn+1 − yn(cid:107) = 0. lim n→∞

27

Thật vậy ta có

n(cid:107)xn − yn(cid:107)2 ≤ (1 − k)αn(cid:107)xn − yn(cid:107)2

(1 − k)α2

= αn(cid:107)xn − u(cid:107)2 + (1 − αn)(cid:107)yn − u(cid:107)2

− (cid:107)xn+1 − u(cid:107)2

≤ αn(cid:107)xn − u(cid:107)2 + (1 − αn)(δn + (cid:107)Jrnxn − u(cid:107))2

− (cid:107)xn+1 − u(cid:107)2

≤ αn(cid:107)xn − u(cid:107)2 + (1 − αn)(δn + (cid:107)xn − u(cid:107))2

− (cid:107)xn+1 − u(cid:107)2

≤ αn||xn − u||2 + (1 − αn)(δnM + (cid:107)xn − u(cid:107))2

− (cid:107)xn+1 − u(cid:107)2

≤ (cid:107)xn − u(cid:107)2 − (cid:107)xn+1 − u(cid:107)2 + δnM,

ở đây M = supn∈N(δn + 2(cid:107)xn − u(cid:107)), do đó

αn(cid:107)xn − yn(cid:107) = 0. lim n→∞ (cid:107)xn+1 − yn(cid:107) = lim n→∞

xni → 0. xni (cid:42) v do yn − Jrni

Ta có thể giả thiết rằng yni (cid:42) v dẫn đến Jrni Vì Arnxn ∈ T Jrnxn và T là đơn điệu,

(2.7) xni(cid:105) ≥ 0 (cid:104)z − Jrni xni, z(cid:48) − Arni

thỏa mãn khi z(cid:48) ∈ T z. Từ rn → ∞, ta có

= 0. lim n→∞ (cid:107)Arnxn(cid:107) = lim n→∞ (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) xn − Jrnxn rn

Trong (2.7) cho i → ∞, ta nhận được (cid:104)z − v, z(cid:48)(cid:105) ≥ 0 với mọi z, z(cid:48) trong đó z(cid:48) ∈ T z. Do T cực đại suy ra v ∈ T −10. Theo Bổ đề 2.1.2 {P xn} hội tụ mạnh tới v(cid:48) ∈ T −10 và P là phép chiếu mêtric từ H lên T −10, ta có

(cid:104)xni − P xni, w − P xni(cid:105) ≤ 0

28

với mọi w ∈ T −10 thì ta có

(cid:104)v − v(cid:48), w − v(cid:48)(cid:105) ≤ 0

với mọi w ∈ T −10. Đặt w = v ta nhận được (cid:107)v − v(cid:48)(cid:107)2 ≤ 0 do đó v = v(cid:48).

Điều này chứng tỏ rằng mọi điểm hội tụ yếu của {xn} chính là điểm hội tụ mạnh của {P xn}, vì thế {xn} hội tụ yếu đến v ∈ T −10, ở đây

P xn. v = lim n→∞

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

Tiếp theo ta nghiên cứu tốc độ hội tụ của (2.6). Ta biết rằng T −1 được

goi là liên tục Lipschitz tại 0 ∈ T z với hệ số a ≥ 0. Nếu tại 0 ∈ T z có một nghiệm duy nhất z0 (tức là T −10 = z0), với mỗi τ > 0, ta có

(2.8) (cid:107)z − z0(cid:107) ≤ a(cid:107)w(cid:107)

với bất kì z ∈ T −1w và (cid:107)w(cid:107) ≤ τ . Rockafellar [12] đã chỉ ra rằng, nếu T −1

liên tục Lipschitz tại 0 và rn → ∞ thì tốc độ hội tụ của (2.6) là siêu tuyến tính, Áp dụng phương pháp của Rockafellar [12], ta có kết quả sau.

Định lý 2.1.4 Cho T : H → 2H là một toán tử đơn điệu cực đại. Cho

{xn} là dãy tạo bởi (2.6) theo tiêu chuẩn (cid:107)yn − Jrnxn(cid:107) ≤ γn(cid:107)yn − xn(cid:107), trong đó {αn} ⊂ [0; 1], {rn} ⊂ (0; ∞) và {γn} ⊂ (0; ∞) thỏa mãn

(i) αn ∈ [0; k] với 0 < k < 1;

rn = ∞ ; (ii) lim n→∞

γn = 0. (iii) lim n→∞

Nếu {xn} giới nội và T −1 liên tục Lipschitz tại 0 ∈ T z với hệ số a ≥ 0, thì {xn} hội tụ mạnh tới v = T −10. Hơn nữa tồn tại một số nguyên N > 0 sao cho

(cid:107)xn+1 − v(cid:107) ≤ θn(cid:107)xn − v(cid:107) với mọi n ≥ N

29

trong đó

n

µn = a (cid:112)a2 + r2

θn = αn + (1 − αn)(µn − γn) 1 − γn

và 0 ≤ θn < 1 với mọi n ≥ N .

Chứng minh. Từ T −1 liên tục Lipschitz tại 0 ∈ T z với hệ số a ≥ 0, với mỗi số τ > 0, ta có (cid:107)z − v(cid:107) ≤ a(cid:107)w(cid:107) với bất kì z ∈ T −1w và (cid:107)w(cid:107) ≤ τ .

Từ (cid:107)Jrnxn − v(cid:107) ≤ (cid:107)xn − v(cid:107) dãy {Jrnxn} giới nội suy ra Arnxn → 0. Khi

đó tồn tại một số nguyên N > 0 sao cho (cid:107)Arnxn(cid:107) ≤ τ và

< 1 θn = αn + (1 − αn)(µn − γn) 1 − γn

với mọi n ≥ N .

Từ Jrnxn ∈ T −1Arnxn, ta có

(2.9) (cid:107)Jrnxn − v(cid:107) ≤ a(cid:107)Arnxn(cid:107)

với mọi n ≥ N. Ta suy ra

n(cid:107)Arnxn(cid:107)2 ≤ (cid:107)xn − v(cid:107)2.

(2.10) (cid:107)Jrnxn − v(cid:107)2 + r2

Kết hợp (2.9) và (2.10) ta được

n

(cid:107)xn − v(cid:107) (cid:107)Jrnxn − v(cid:107) ≤ a (cid:112)a2 + r2

với mọi n ≥ N . Từ đó ta có

(cid:107)yn − v(cid:107) ≤ (cid:107)yn − Jrnxn(cid:107) + (cid:107)Jrnxn − v(cid:107)

n

≤ γn(cid:107)yn − xn(cid:107) + (cid:107)xn − v(cid:107)

a (cid:112)a2 + r2 ≤ γn(cid:107)yn − v(cid:107) + γn(cid:107)xn − v(cid:107) + µn(cid:107)xn − v(cid:107)

30

với mọi n ≥ N . Từ đó suy ra

(cid:107)yn − v(cid:107) ≤ (cid:107)xn − v(cid:107) µn + γn 1 − γn

với mọi n ≥ N . Do đó ta nhận được

(cid:107)xn+1 − v(cid:107) ≤ αn(cid:107)xn − v(cid:107) + (1 − αn)(cid:107)yn − v(cid:107)

(cid:32) (cid:33)

≤ (cid:107)xn − v(cid:107) αn + (1 − αn)(µn + γn) 1 − γn

= θn(cid:107)xn − v(cid:107)

với mọi n ≥ N .

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

αn = 0 Định lý này đã chỉ ra tốc độ hội tụ của (2.6) tuyến tính. Nếu lim n→∞ thì tốc độ hội tụ là siêu tuyến tính.

2.2 Áp dụng cho bài toán cực tiểu

Trong mục này, ta xét trường hợp T = ∂f với f là hàm lồi, chính thường,

rn = ∞, ta có nửa liên tục dưới. Nếu lim n→∞

x0 = x ∈ H

z∈H

{f (z) + (2.11) yn ≈ argmin (cid:107)z − xn(cid:107)2}

   1 2rn xn+1 = αnx + (1 − αn)yn

với mọi n ∈ N, {αn} ⊂ [0; 1], {rn} ⊂ (0; ∞). Ở đây xét tiêu chuẩn sau

∞ (cid:88)

(2.12) , d(0, Sn(yn)) ≤ δn rn

n=0

trong đó δn < ∞; Sn(z) = ∂f (z) + z − xn rn

d(0; A) = inf{(cid:107)x(cid:107) : x ∈ A}.

31

Bổ đề sau được chứng minh bởi Rockafellar [12]:

Bổ đề 2.2.1 Nếu yn thỏa mãn tiêu chuẩn (2.12) thì (cid:107)yn − Jrnxn(cid:107) ≤ δn, trong đó Jrn = (I + rn∂f )−1.

Định lý 2.2.2 Cho f : H → (−∞; +∞] là hàm lồi, chính thường, nửa liên

∞ (cid:88)

tục dưới. Cho x ∈ H và {xn} là dãy tạo bởi (2.11) theo tiêu chuẩn (2.12),

n=0

αn = 0, αn = trong đó {αn} ⊂ [0; 1] và {rn} ⊂ (0; ∞) thỏa mãn lim n→∞

rn = ∞. Nếu (∂f )−10 (cid:54)= ∅ thì {xn} hội tụ mạnh tới v ∈ H, đó ∞ và lim n→∞ là phần tử cực tiểu của f theo x. Hơn nữa ta có

(cid:107)yn − v(cid:107)(δn + (cid:107)yn − xn(cid:107)). f (xn+1) − f (v) ≤ αn(f (x) − f (v)) + 1 − αn rn

Chứng minh. Đặt

gn(z) = f (z) + (cid:107)z − xn(cid:107)2 2rn

ta có

(z − xn) = Sn(z) ∂gn(z) = ∂f (z) + 1 rn

với mọi z ∈ H và

z∈H

gn(z). Jrnxn = (I + rn∂f )−1xn = argmin

Từ Định lý 2.1.1 và Bổ đề 2.2.1 ta suy ra {xn} hội tụ mạnh tới v ∈ H và

f (z). f (v) = min z∈H

Từ ∂gn(yn) là tập đóng lồi ∂gn(yn) (cid:54)= ∅, ta có thể tìm thấy thành phần duy nhất wn của ∂gn(yn) gần θ nhất. Khi đó ta có

wn − (yn − xn) ∈ ∂f (yn) 1 rn

32

và

. (2.13) (cid:107)wn(cid:107) = δn rn

Từ định nghĩa dưới vi phân dẫn đến

(cid:28) (cid:29) (2.14) f (v) ≥ f (yn) + v − yn, wn − (yn − xn) 1 rn

Từ (2.13) và (2.14) ta nhận được

f (xn+1) − f (v) = f (αnx + (1 − αn)yn) − f (v)

≤ αn(f (x) − f (v)) + (1 − αn)(f (yn) − f (v))

≤ αn(f (x) − f (v))

(cid:28) (cid:29)

+ (1 − αn) yn − v, wn − (yn − xn) 1 rn

≤ αn(f (x) − f (v))

(cid:18) (cid:19)

+ (1 − αn)(cid:107)yn − v(cid:107) (cid:107)wn(cid:107) + (cid:107)yn − xn(cid:107) 1 rn

+ (cid:107)yn − v(cid:107)(δn + (cid:107)yn − xn(cid:107)). ≤ αn(f (x) − f (v)) 1 − αn rn

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

Tương tự ta thấy định lý sau liên quan đến (2.6). Định lý này tương

đương với Định lý 2.2.2.

Định lý 2.2.3 Cho f : H → (−∞; +∞] là hàm lồi, chính thường, nửa

liên tục dưới. Cho x ∈ H và {xn} là dãy tạo bởi (2.11) theo tiêu chuẩn (2.12), trong đó {αn} ⊂ [0; 1] và {rn} ⊂ (0; ∞) thỏa mãn αn ∈ [0; k] trong rn = ∞. Nếu (∂f )−10 (cid:54)= ∅ và {un} là dãy các điểm đó 0 < k < 1 và lim n→∞ của (∂f )−10 gần xn nhất, thì {xn} hội tụ yếu tới v ∈ H, đó là phần tử của

33

un hơn nữa ta có f và thỏa mãn v = lim n→∞

f (xn+1) − f (v) ≤ αn(f (x) − f (v)) + (cid:107)yn − v(cid:107)(δn + (cid:107)yn − xn(cid:107)) 1 − αn rn

34

Kết luận

Đề tài luận văn đã trình bày hai phương pháp tìm xấp xỉ không điểm

của toán tử đơn điệu cực đại trong không gian Hilbert, trình bày sự hội

tụ mạnh và sự hội tụ yếu của phương pháp điểm gần kề tìm không điểm

của toán tử đơn điệu cực đại. Cụ thể:

(1) Trình bày một số tính chất của không gian Hilbert, các kiến thức cơ

bản trong giải tích lồi và giải tích biến phân như: Tập lồi, ánh xạ liên

tục, ánh xạ liên tục Lipschitz, dưới vi phân, toán tử đa trị, toán tử

đơn điệu, toán tử đơn điệu cực đại.

(2) Trình bày một số phương pháp tìm không điểm của toán tử đơn điệu

cực đại.

(3) Trình bày hai phương pháp tìm xấp xỉ không điểm của toán tử đơn

điệu cực đại trong không gian Hilbert H; trình bày định lý hội tụ

mạnh và định lý hội tụ yếu của phương pháp và ứng dụng của phương

pháp tìm xấp xỉ không điểm cho bài toán tìm điểm cực tiểu hàm lồi.

Việc cải tiến các phương pháp lặp xấp xỉ không điểm của toán tử đơn

điệu cực đại nhằm gia tăng hiệu quả của nó và mở rộng kết quả lên không

gian Banach vv. . . là hướng phát triển tiếp theo của đề tài này.

35

Tài liệu tham khảo

Tiếng Việt

[1] Lê Dũng Mưu, Nguyễn Văn Hiền (2009), Nhập môn giải tích lồi ứng

dụng, NXB Khoa học tự nhiên và Công nghệ, 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.

Tiếng Anh

[4] Atsushiba S. and Takahashi W. (1997), "Approximating common fixed

poits of nonexpansive semigroups by the Mann iteration process",

Ann. Univ. Mariae Curie- Sklodowska.A, 51, pp. 1-16.

[5] Bauschke H.H, Matousková E., Reich S. (2004), "Projection and prox-

imal point methods: convergence results and counterexamples", Nonl.

Anal., 56, pp. 715-738.

[6] Bruck E.R. (1974), "A strongly convergent iterative solutiono of 0 ∈

U (x) for a maximal monotone operaor U in Hilbert space", J. Math.

Anal. Appl., 48, pp. 114-126.

[7] Guler O. (1991), "On the convergence of the proximal point algorithm

for convex minimization", SIAM J. Optim., 29, pp. 403 - 419.

36

[8] Halper B. (1967), "Fixed points of nonexpanding maps", Bull.Amer.

Math. Soc., 73, pp. 957 - 961.

[9] Kamimura S. and Takahashi W. (2000), "Approximating Solutions of

Maximal Monotone Operators in Hilbert spaces", Journal of Approx-

imation Theory 106, pp. 226 - 240.

[10] Mann R .W. (1953), "Mean value methods in iteration", Proc.Amer.

Math. Soc., 4, pp. 506-510.

[11] Reich S. (1953), "Weak convergence theorems for nonexpansive map-

pings in Banach spaces", J. Math. Anal. Appl., 67, pp. 247-276.

[12] Rockafellar R. T. (1976), "Monotone operators and the proximal point

algorithm", SIAM J. Optim., 14, pp. 877-898.

[13] Takahashi W. and Ueda Y. (1984), "On Reich’s strong convergence

theorems for resolvents of accretive operators", J. Math. Anal. Appl.,

104, pp. 546-533.

[14] Tan K.K. and Xu H.K. (1993), "Approximating fixed points of nonex-

pansive mappings by the Ishikawa iteration process", J. Math. Anal.

Appl., 178, pp. 301-308.