ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐOÀN THỊ BÍCH
THUẬT TOÁN ĐẠO HÀM TĂNG CƯỜNG LAI GHÉP
GIẢI BÀI TOÁN CÂN BẰNG ĐƠN ĐIỆU
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2013
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐOÀN THỊ BÍCH
THUẬT TOÁN ĐẠO HÀM TĂNG CƯỜNG LAI GHÉP
GIẢI BÀI TOÁN CÂN BẰNG ĐƠN ĐIỆU
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số : 60.46.01.12
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
GS. TSKH. LÊ DŨNG MƯU
Thái Nguyên - Năm 2013
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
i
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Lời cảm ơn 1
Lời nói đầu 2
Một số ký hiệu và chữ viết tắt 5
1 Bài toán cân bằng 6
1.1 Một số khái niệm cơ bản . . . . . . . . . . . . . . . . . . . 6
1.2 Sự tồn tại nghiệm và các tính chất cơ bản của bài toán cân
bằng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Các trường hợp riêng của bài toán cân bằng . . . . . . . . . 28

LỜI NÓI ĐẦU
Cho H là một không gian Hilbert thực với tích vô hướng ., . và chuẩn
. tương ứng. Giả sử C là một tập lồi, đóng, khác rỗng trong H và f là
song hàm từ C × C vào R sao cho f(x, x) = 0 với mọi x ∈ C. Trong luận
văn này ta sẽ xét bài toán cân bằng sau đây, được ký hiệu là EP(C, f):
Tìm x
∗
∈ C sao cho f(x
∗
, y) ≥ 0, ∀y ∈ C.
Bài toán EP(C, f) còn được gọi là bất đẳng thức Ky Fan để ghi nhận sự
đóng góp của ông trong lĩnh vực này (xem [2], [5] và các trích dẫn).
Một phương pháp cơ bản để giải bài toán cân bằng là phương pháp
chiếu và các dạng của nó. Tuy nhiên phương pháp chiếu chỉ hội tụ với điều
kiện song hàm có tính đơn điệu mạnh, hay là có tính tự bức (đơn điệu
mạnh ngược), ngay cả cho bài toán bất đẳng thức biến phân đơn điệu, là
một trường hợp đặc biệt của bài toán cân bằng đơn điệu.
Để thu được phương pháp chiếu hội tụ cho bài toán cân bằng có tính
đơn điệu nhẹ hơn, trong [16] các tác giả đã mở rộng phương pháp đạo hàm
tăng cường (hay là chiếu hai lần) do Korpelevich [8] lần đầu tiên đề xuất
cho bài toán tối ưu và bài toán điểm yên ngựa. Với phương pháp này sự
hội tụ được đảm bảo ngay trong trường hợp song hàm f có tính giả đơn
điệu.
Bài toán cân bằng đơn điệu có liên quan chặt chẽ với bài toán tìm điểm
bất động của một ánh xạ không giãn. Về mặt lý thuyết bài toán cân bằng
đơn điệu và bài toán điểm bất động của ánh xạ không giãn có mối quan
hệ tương hỗ lẫn nhau, theo nghĩa, với một vài giả thiết tự nhiên, bài toán
này có thể mô tả dưới dạng bài toán kia và ngược lại. Cả hai lớp bài toán
này thực chất đều thuộc bài toán chấp nhận lồi, tức là bài toán tìm một
điểm chung của các tập lồi.



ω
k
= α
k
x
k
+ (1 − α
k
)T (z
k
),
C
k
=

z ∈ H :


ω
k
− z


≤


x
k

trong đó λ
k
> 0 là tham số tại bước lặp k; x
0
∈ C và P
C
k
∩D
k
(x
0
) là phép
chiếu khoảng cách trên C
k
∩ D
k
của điểm x
0
; T : C → C là ánh xạ không
giãn. Với giả thiết song hàm f đơn điệu trên C, các dãy {α
k
}, {λ
k
} thỏa
mãn các tính chất đề ra thì dãy {x
k
} hội tụ mạnh đến một nghiệm chung
của bài toán cân bằng EP (C, f) và điểm bất động của T.
Mục đích của bản luận văn này là giới thiệu những kiến thức cơ bản
nhất của bài toán cân bằng và trình bày một thuật toán lai ghép giữa

H: Không gian Hilbert thực;
X: Không gian Banach thực;
R: Tập các số thực;
∅: Tập rỗng;
I: Ánh xạ đồng nhất;
a, b: Tích vô hướng của 2 véc-tơ a và b;
x: Chuẩn của x;
∂f(x): Dưới vi phân của hàm f tại x;
∀x: Với mọi x;
x
n
→ x: Dãy {x
n
} hội tụ mạnh tới x;
x
n
 x: Dãy {x
n
} hội tụ yếu tới x;
x := y: Nghĩa là, x được định nghĩa bằng y;
P
C
(x): Hình chiếu của x lên C.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
Chương 1
Bài toán cân bằng
Chương này trình bày các khái niệm liên quan đến bài toán cân bằng,
sự tồn tại nghiệm, các tính chất cơ bản và các trường hợp riêng quan trọng
của bài toán cân bằng. Các kiến thức trong chương được trích từ tài liệu


a
f
2
(x) dx < +∞, là một không gian Hilbert với
tích vô hướng
f, g =
b

a
f (x) g (x) dx;
và chuẩn
f
L
2
[a,b]
=


b

a
f
2
(x)dx


1
2
.

• Nếu {x
n
} hội tụ mạnh đến x thì cũng hội tụ yếu đến x.
• Mọi dãy hội tụ mạnh (yếu) đều bị chặn và giới hạn theo sự hội tụ
mạnh (yếu) nếu tồn tại là duy nhất.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
• Nếu không gian Hilbert thực H là không gian hữu hạn chiều thì sự hội
tụ mạnh và sự hội tụ yếu là tương đương.
• Nếu {x
n
}
n≥0
là một dãy bị chặn trong không gian Hilbert thực H thì
ta trích ra được một dãy con hội tụ yếu.
• Nếu {x
n
}
n≥0
là một dãy bị chặn trong không gian Hilbert thực hữu hạn
chiều H thì ta trích ra được một dãy con hội tụ mạnh.
Tiếp theo, ta sẽ nêu một số định nghĩa và kết quả cơ bản của giải tích
lồi được phát biểu trong [2], [12].
Xét C là tập con khác rỗng trong không gian Hilbert thực H.
Định nghĩa 1.4. Tập C trong không gian Hilbert thực H được gọi là một
tập lồi nếu
∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
Định nghĩa 1.5. Điểm a được gọi là điểm biên của C nếu mọi lân cận
của a đều có điểm thuộc C và điểm không thuộc C;
Tập C được gọi là tập đóng nếu C chứa mọi điểm biên của nó;

Do đó nó không lồi chặt.
Cho C = ∅ là một tập lồi.
2. Hàm chỉ. Đặt
δ
C
(x) :=

0 khi x ∈ C,
+∞ khi x /∈ C.
Ta nói δ
C
là hàm chỉ của C. Do C lồi nên δ
C
là hàm lồi.
3. Hàm khoảng cách. Giả sử C là một tập đóng, khác rỗng. Hàm khoảng
cách d
C
(y) được định nghĩa như sau:
d
C
(y) = inf
x∈C
x − y.
Khi đó, nếu C là tập lồi thì d
C
là hàm lồi.
Thật vậy, xét x, y ∈ H và λ ∈ (0, 1) bất kỳ. Đặt z = λx + (1 − λ)y. Theo
định nghĩa của inf tồn tại các dãy

x

k
:= λx
k
+ (1 − λ)y
k
∈ C. Ta có
d
C
(z) ≤


z − z
k


=


λ(x − x
k
) + (1 − λ)(y − y
k
)


≤ λ


x − x
k

Ký hiệu hình chiếu của y trên C là P
C
(y). Khi đó, π = P
C
(y).
Tiếp theo ta sẽ chứng minh sự tồn tại và tính duy nhất của hình chiếu
xuống một tập lồi đóng. Sau đó ta sẽ khảo sát một số tính chất cơ bản
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
của toán tử chiếu được sử dụng trong chương sau của luận văn.
Mệnh đề 1.2. (xem [2])Giả sử C là tập lồi, đóng khác rỗng trong H. Khi
đó:
(i) Với mọi y ∈ H, π ∈ C hai tính chất sau tương đương:
(a) π = P
C
(y),
(b) y − π ∈ N
C
(π).
(ii) Với ∀y ∈ H, hình chiếu P
C
(y) của y trên C luôn tồn tại và duy nhất.
(iii) Nếu y /∈ C thì P
C
(y) − y, x − P
C
(y) = 0 là siêu phẳng tựa của C
tại P
C
(y) và tách hẳn y khỏi C, tức là

Chứng minh.
(i) Giả sử có (a), tức là π là hình chiếu của y trên C. Lấy x ∈ C. Đặt
x
λ
:= λx + (1 − λ)π.
Do C lồi nên x
λ
∈ C với mọi λ ∈ (0, 1). Theo định nghĩa hình chiếu ta có
π − y ≤ y − x
λ
. Hay
π − y
2
≤ y − x
λ

2
= (π − y) + λ(x − π)
2
.
Khai triển vế phải và giản ước ta thu được
λx − π
2
+ 2 x − π, π − y ≥ 0, ∀x ∈ C, λ ∈ (0, 1).
Cho λ tiến tới 0 ta thu được bất đẳng thức
π − y, x − π ≥ 0, ∀x ∈ C.
Vậy y − π ∈ N
C
(π).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

k


x
k
− y


= d
C
(y) < +∞.
Suy ra dãy

x
k

bị chặn, do đó trích ra được một dãy con

x
k
j

hội tụ
đến một điểm π nào đó. Mặt khác, do C đóng nên giới hạn này phải thuộc
C. Ta có
π − y = lim
j


x

).
Chọn x = π

trong mệnh đề trên ta có
y − π, π

− π ≤ 0.
Thay đổi vai trò của π và π

ta được
y − π

, π − π

 ≤ 0.
Cộng hai bất đẳng thức trên suy ra π − π


2
≤ 0. Điều này chỉ xảy ra
khi π = π

.
(iii) Do y − π ∈ N
C
(π) nên
π − y, x − π ≥ 0, ∀x ∈ C.
Vậy π − y, x = π − y, π là một siêu phẳng tựa của C tại π. Siêu phẳng
này tách y khỏi C vì y = π nên
π − y, y − π = −π − y

P
C
(y) − P
C
(x), P
C
(y) − P
C
(x) + x − y ≤ 0.
Kết hợp điều này và bất đẳng thức Cauchy-Schwarz, suy ra
P
C
(x) − P
C
(y) ≤ x − y.
(b) Áp dụng tính chất (b) của (i), lần lượt với P
C
(x) và P
C
(y), ta có:
P
C
(x) − x, P
C
(x) − P
C
(y) ≤ 0;
y − P
C
(y), P

(y), x − y ≥ P
C
(x) − P
C
(y)
2
.
Vậy mệnh đề đã được chứng minh. ✷
Định nghĩa 1.8. Cho f : H → R ∪ {+∞}. Ta nói x
∗
∈ H là dưới đạo
hàm của f tại x nếu
x
∗
, z − x + f(x) ≤ f(z), ∀z ∈ H.
Ký hiệu tập tất cả các dưới đạo hàm của f tại x là ∂f(x).
Khi ∂f(x) = ∅ thì ta nói hàm f khả dưới vi phân tại điểm x.
f được gọi là khả dưới vi phân trên một tập nếu f khả dưới vi phân tại
mọi điểm trên tập đó.
Ví dụ 1.3.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
1. f(x) = x , x ∈ R
n
. Tại điểm x = 0 hàm này không khả vi, nhưng nó
khả dưới vi phân và
∂f(0) = {x
∗
| x
∗

C
(x
0
) =

x
∗
|

x
∗
, x − x
0

≤ 0, ∀x ∈ C

= N
C
(x
0
).
Ta có mệnh đề sau nói lên tính khả dưới vi phân của hàm lồi.
Mệnh đề 1.3. Nếu f : H → R là hàm lồi thì ∂f(x) = ∅ với mọi x ∈ X
hay là f khả dưới vi phân khắp nơi.
Mệnh đề này là trường hợp riêng của Định lý 23.4, trang 217 trong tài liệu
[12].
Định nghĩa 1.9. Hàm f : H → R được gọi là nửa liên tục dưới đối
với E ⊂ H tại một điểm x, nếu như với mọi dãy x
k
⊂ E; x

trong việc trình bày tính duy nhất nghiệm của bài toán cân bằng (xem
[2], [7], [10], [15], [16]). Trong các định nghĩa sau xét C là tập khác rỗng,
đóng, lồi trong không gian Hilbert thực H.
Định nghĩa 1.11. Giả sử f : C × C → R. Ta nói
(i) f đơn điệu mạnh trên C với hệ số β > 0, nếu
f(x, y) + f(y, x) ≤ −βx − y
2
, ∀x, y ∈ C;
(ii) f đơn điệu chặt trên C, nếu
f(x, y) + f(y, x) < 0, ∀x, y ∈ C, x = y;
(iii) f đơn điệu trên C, nếu
f(x, y) + f(y, x) ≤ 0, ∀x, y ∈ C;
(iv) f giả đơn điệu trên C, nếu
f(x, y) ≥ 0 ⇒ f(y, x) ≤ 0, ∀x, y ∈ C;
(v) f liên tục có tính chất kiểu Lipschitz trên C với hằng số c
1
> 0 và
c
2
> 0, nếu
f(x, y) + f(y, z) ≥ f(x, z) − c
1
x − y
2
− c
2
y − z
2
, ∀x, y, z ∈ C.
Từ định nghĩa ta có (i) ⇒ (ii) ⇒ (iii) ⇒ (iv).

F (x) − F (y), x − y ≥ 0, ∀x, y ∈ C;
(iv) giả đơn điệu trên C, nếu
F (y), x − y ≥ 0 ⇒ F (x), x − y ≥ 0, ∀x, y ∈ C;
(v) liên tục L-Lipschitz trên C nếu
F (x) − F (y) ≤ L x − y , ∀x, y ∈ C, L > 0.
Từ định nghĩa ta có (i) ⇒ (ii) ⇒ (iii) ⇒ (iv).
Ví dụ 1.5. Cho C là tập lồi, hàm f : C → R, và ∂f liên tục. Khi đó:
• Nếu f là hàm khả vi, lồi trên C thì ∂f là đơn điệu trên C.
Thật vậy, lấy tùy ý x, y ∈ C và do f là hàm lồi nên
f(x) ≥ f(y) + ∂f(y), x − y ,
f(y) ≥ f(x) + ∂f(x), y − x .
Cộng hai bất đẳng thức trên với nhau, suy ra
∂f(y) − ∂f(x), y − x ≥ 0, ∀x, y ∈ C.
Vậy ∂f là đơn điệu trên C. ✷
• Nếu f là khả vi, lồi mạnh trên C thì ∂f là đơn điệu mạnh trên C.
• Nếu f là hàm khả vi, lồi chặt trên C thì ∂f là đơn điệu chặt trên C.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
Nhận xét 1.1.
Nếu F là L−Lipschitz trên C thì với mỗi x, y ∈ C, f(x, y) = F (x), y − x
có tính chất liên tục kiểu Lipschitz với hằng số c
1
= c
2
=
L
2
trên C.
Thật vậy
f(x, y) + f(y, z) − f(x, z)

Ta nhắc lại bài toán cân bằng (còn được gọi là bất đẳng thức Ky Fan):
Xét H là không gian Hilbert thực; C là tập lồi, đóng, khác rỗng trong H
và f : C × C → R ∪ {+∞}. Khi đó, bài toán cân bằng là bài toán
Tìm x ∈ C sao cho f(x, y) ≥ 0, ∀y ∈ C. (EP )
Tập nghiệm của bài toán cân bằng được ký hiệu là Sol(C, f).
Dưới đây ta sẽ luôn giả thiết f(x, x) = 0 với mọi x ∈ C. Một song hàm
thỏa mãn điều kiện này được gọi là song hàm cân bằng. C được gọi là tập
chấp nhận được hay là tập chiến lược và f là hàm cân bằng của bài toán
(EP).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
Tiếp theo ta xét sự tồn tại nghiệm và các tính chất cơ bản của bài toán
cân bằng. Để chứng minh kết quả về sự tồn tại nghiệm của bài toán ta sử
dụng định lý minimax quan trọng.
Định lý minimax
Cho một song hàm f : C × C → R. Nhiều vấn đề trong tối ưu hóa, lý
thuyết trò chơi và các lĩnh vực khác đưa đến câu hỏi khi nào có đẳng thức
γ := sup
y∈D
inf
x∈C
f(x, y) = inf
x∈C
sup
y∈D
f(x, y) := η. (1.1)
Đẳng thức này nói rằng việc lấy cận trên đúng và cận dưới đúng có thể
hoán vị cho nhau. Từ định nghĩa cận trên đúng, cận dưới đúng, ta có
sup
y∈D

< η := inf
x∈C
sup
y∈D
f(x, y) và mọi tập hữu hạn M ⊂ C, tập
D (M) :=

y ∈ D| min
x∈M
f(x, y) ≥ η


= ∅.
Chứng minh. Đặt
C
γ

(y) := {x ∈ C|f(x, y) ≤ γ

} .
Do C lồi, f(., y) tựa lồi và nửa liên tục dưới, nên C
γ

(y) lồi, đóng.
Khẳng định (i) có nghĩa là
∩
y∈N
C
γ


2
, , y
k+1
. Đặt
C

γ

(y
i
) := C
γ

(y
i
) ∩ C
γ

(y
k+1
), (i = 1, 2, , k).
Khi đó
k+1
∩
i=1
C
γ

(y
i


(y
i
) ∩ C
γ

(y
k+1
) = ∅.
Vậy vấn đề còn lại là chứng minh rằng với hai điểm bất kỳ a, b ∈ D, thì
C
γ

(a) ∩ C
γ

(b) = ∅.
Giả sử trái lại. Do tính nửa liên tục dưới theo biến thứ nhất của
hàm f, ta chỉ cần chứng minh (i) cho α với bất kỳ α ∈ (γ, γ

). Do
α > sup
y∈D
inf
x∈C
f(x, y), nên C
α
(y) = ∅, ∀y ∈ D. Để đơn giản, sau đây với mọi
y, ta viết C(y) thay cho C
α

Đặt
M
a
:= {t|0 ≤ t ≤ 1 : C(y
t
) ⊂ C(a)} ,
M
b
:= {t|0 ≤ t ≤ 1 : C(y
t
) ⊂ C(b)} .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
Hiển nhiên 0 ∈ M
a
, 1 ∈ M
b
và M
a
∪ M
b
= [0, 1].
Hoàn toàn tương tự như trên, ta chứng minh được
C(y
t
) ⊂ C(y
t
1
) ∪ C(y
t

x ∈ C(y
t
) với mọi t đủ gần s. Khi đó, C(y
t
) ⊂ C(a). Theo định nghĩa của
M
a
, ta có t ∈ M
a
. Nhưng t > s = sup M
a
: mâu thuẫn. Như vậy
C(a) ∩ C(b) = ∅.
Khẳng định (ii) có thể suy ra từ khẳng định (i), với chú ý hàm −f tựa
lồi, nửa liên tục dưới theo biến thứ hai và
− min
x∈M

sup
y∈D
f(x, y)

= max
x∈M

inf
y∈D
(−f(x, y))

.


y ∈ D| min
x∈M
∗
f(x, y) ≥ γ
∗

compact. Khi đó
sup
y∈D
inf
x∈C
f(x, y) = inf
x∈C
sup
y∈D
f(x, y);
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
Cụ thể hơn, ta có
sup
y∈D
min
x∈C(N
∗
)
f(x, y) = inf
x∈C
sup
y∈D


= α, ta có C

(y) = ∅. Cũng
theo bổ đề này họ tập {C

(y)|y ∈ D} có tính chất tương giao hữu hạn.
Ngoài ra tất cả các tập này đều nằm trong tập compact C(N
∗
). Do đó theo
định lý tương giao hữu hạn (Định lý Helley) của các tập lồi đóng, ta có
∩
y∈D
C

(y) = ∅. Nhưng theo định nghĩa của C

(y), thì
∩
y∈D
C

(y) =
∩
y∈D
C(y).
Lấy x
∗
∈
∩

Nhận xét 1.2. Điều kiện (A) sẽ thỏa mãn nếu có điều kiện bức sau:
(AC) Có một tập hữu hạn N
∗
⊂ D sao cho
m
ax
y∈N
∗
f(x, y) → +∞ khi x ∈ C, x → +∞.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
Điều kiện (B) thỏa mãn nếu ta có điều kiện bức sau:
(BC) Có một tập hữu hạn M
∗
⊂ C sao cho
min
x∈M
∗
f(x, y) → −∞ khi y ∈ D, y → +∞.
Thật vậy, giả sử có (AC). Ta có thể giả thiết
γ := sup
y∈D
inf
x∈C
f(x, y) < +∞,
vì nếu trái lại đẳng thức minimax (1.1) luôn đúng. Lấy η > γ thì tập
C(N
∗
) :=


m

j=1
y
j
g
j
(x).
Với mỗi y ≥ 0, đặt
d(y) := inf
x∈H
L(x, y),
và xét bài toán
d
∗
:= sup {d(y) : y ≥ 0} . (OD)
Ta nói (OD) là bài toán đối ngẫu của (OP), còn (OP) được gọi là bài toán
gốc. Từ định nghĩa suy ra
d
∗
= sup
y≥0
d(y) ≤ inf
x∈H
sup
y≥0
L(x, y) = f
∗
.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

⊂ C sao cho tập
C (N
∗
) :=

x ∈ C| min
y∈N
∗
f(x, y) ≥ 0

compact, hoặc
(B1) Có một tập hữu hạn M
∗
⊂ C sao cho tập
D (M
∗
) :=

y ∈ C| max
x∈M
∗
f(x, y) ≤ 0

compact. Khi đó bài toán (EP) có nghiệm.
Chứng minh. Đặt φ(x, y) := −f(x, y) và D ≡ C. Khi đó hàm φ thỏa
mãn mọi điều kiện của Định lý 1.1. Theo Định lý này, ta có
sup
x∈C
inf
x∈C