ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————

NGÔ THỊ THO

PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN GIẢ ĐƠN ĐIỆU MẠNH

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

Hà Nội - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————

NGÔ THỊ THO

PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN GIẢ ĐƠN ĐIỆU MẠNH

Chuyên ngành: Toán ứng dụng.
Mã số: 60460112.

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


18
18
20
26

Chương 2. Phương pháp chiếu giải bài toán bất đẳng thức biến phân giả đơn
điệu mạnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1. Phương pháp chiếu dưới đạo hàm tăng cường . . . . . . . . . . . . . . . . . . . .

29

2.2. Phương pháp chiếu cơ bản cải biên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

1


LỜI CẢM ƠN

Lời đầu tiên, em xin chân thành cảm ơn GS.TSKH Lê Dũng Mưu. Thầy là người
đã hướng dẫn khóa luận tốt nghiệp và nay là hướng dẫn luận văn thạc sĩ cho em. Hai

hàm riêng. Năm 1980, Kinderlehrer và Stampacchia cho xuất bản cuốn sách "An
Introduction to Variational Inequalities and Their Applications", giới thiệu bài toán
biến phân trong không gian vô hạn chiều và ứng dụng của nó. Năm 1984, cuốn
sách "Variational and Quasivariational Inequalities: Applications to Free Boundary
Problems" của C. Baiocci và A. Capelo đã áp dụng bất đẳng thức biến phân và tựa
biến phân để giải các bài toán không có biên.
Hiện nay bài toán bất đẳng thức biến phân đã phát triển thành nhiều dạng khác
nhau,như là: bất đẳng thức biến phân vectơ, tựa bất đẳng thức biến phân, giả bất đẳng
thức biến phân, bất đẳng thức biến phân ẩn, bất đẳng thức biến phân suy rộng.... Bài
toán này đã thu hút được sự quan tâm của nhiều nhà toán học. Vì mô hình của nó
chứa nhiều bài toán quan trọng của một số lĩnh vực trong toán học cũng như thực tế
như tối ưu hóa, bài toán bù, lý thuyết trò chơi, cân bằng Nash, cân bằng mạng giao
thông, cân bằng di trú....
Một trong những hướng nghiên cứu quan trọng của bất đẳng thức biến phân là
việc xây dựng các phương pháp giải. Dựa trên tính chất của kiểu đơn điệu G. Cohen
đã nghiên cứu phương pháp nguyên lý bài toán phụ. Ngoài ra còn có phương pháp
hiệu chỉnh Tikhonov, phương pháp chiếu, phương pháp điểm trong. Những phương
pháp này khá hiệu quả, dễ thực hiện trên máy tính nhưng sự hội tụ của chúng chỉ
được đảm bảo trên cơ sở các giả thiết khác về tính chất đơn điệu.
Có nhiều phương pháp chiếu khác nhau, như là: phương pháp chiếu cơ bản,
phương pháp chiếu dưới đạo hàm, và phương pháp chiếu siêu phẳng. Mỗi phương
pháp giải quyết một lớp các bài toán bất đẳng thức biến phân nhất định. Do đó sự hội
tụ của thuật toán được đảm bảo.
Luận văn trình bày phương pháp chiếu dưới đạo hàm tăng cường và chiếu cơ bản
cải biên để giải bài toán bất đẳng thức biến phân giả đơn điệu mạnh. Các phương
pháp này tạo ra một dãy hội tụ của các điểm lặp dễ dàng tính được. Chúng đều hội tụ
3


tới nghiệm duy nhất của bài toán.

nghiệm của bài toán. Nội dung chủ yếu được trích dẫn từ tài liệu [1], [2], [3], [6],
[10].
Trong luận văn này, chúng ta sẽ làm việc trên không gian Hilbert thực trang bị
một tô pô yếu, với tích vô hướng ., . và chuẩn tương ứng của nó là ||.||.

5


1.1.

Kiến thức chuẩn bị

1.1.1.

Hội tụ mạnh và yếu trong không gian Hilbert

Định nghĩa 1.1.1. Giả sử H là không gian tuyến tính thực, với mọi x ∈ H xác định
một số gọi là chuẩn của x ( kí hiệu ||x||) thỏa mãn ba tiên đề sau:
1. Xác định dương: ∀x ∈ H

||x|| ≥ 0;

||x|| = 0 ⇔ x = 0.

2. Thuần nhất dương: ∀x ∈ H; ∀λ ∈ R
3. Bất đẳng thức tam giác: ∀x, y ∈ H

||λ x|| = |λ | ||x||.
||x + y|| ≤ ||x|| + ||y||.




2. H = C[a,b] là không gian các hàm liên tục. Khi đó với mọi x, y ∈ H tích vô
hướng chuẩn được xác định bởi
b

x, y =

x(t)y(t)dt,
a
b

|x(t)|2 dt.

||x|| =
a

Giả sử H là không gian Hilbert thực, H ∗ là không gian đối ngẫu của H và f ∈ H ∗ .
Kí hiệu ϕ f : H → R là các phiếm hàm tuyến tính ϕ f (x) = f (x). Khi f chạy khắp H ∗
ta có một họ ánh xạ (ϕ f ) f ∈H ∗ .
Định nghĩa 1.1.3. Tô pô yếu trên H được định nghĩa bởi tô pô sinh bởi họ ánh xạ
(ϕ f ) f ∈H ∗ . Kí hiệu σ (H, H ∗ ).
Như vậy tô pô yếu σ (H, H ∗ ) là tô pô yếu nhất trên H đảm bảo cho tất cả các
phiếm hàm f ∈ H ∗ đều liên tục.
Định nghĩa 1.1.4. 1) Ta nói dãy {xk } hội tụ mạnh đến x ( kí hiệu xk → x) nếu
lim ||xk − x|| = 0.

k→∞

2) Dãy {xk } hội tụ yếu đến x ( kí hiệu xk

trùng nhau. Đặc biệt, một dãy hội tụ mạnh khi và chỉ khi nó hội tụ yếu.
7


1.1.2.

Toán tử chiếu

Định nghĩa 1.1.5. Cho H là một không gian Hilbert thực, tập C ⊆ H được gọi là
• tập lồi nếu: ∀x, y ∈ C, λ ∈ [0, 1] ⇒ λ x + (1 − λ )y ∈ C,
• nón nếu: ∀λ > 0, ∀x ∈ C ⇒ λ x ∈ C,
• nón lồi nếu nó vừa là một nón vừa là một tập lồi.

Hình 1.1: tập lồi, nón, nón lồi

Mệnh đề 1.1.2. Giả sử A, B là các tập lồi trong không gian Hilbert thực H, thì các
tập sau là tập lồi:
A ∩ B :={x | x ∈ A, x ∈ B},
αA + β B :={x | x = αa + β b, a ∈ A, b ∈ B, α, β ∈ R},
A × B :={x | x = (a, b), a ∈ A, b ∈ B}.
Định nghĩa 1.1.6. Siêu phẳng trong không gian Hilbert thực H là một tập hợp các
điểm có dạng
{x ∈ H | a(x) = α},
trong đó a ∈ H ∗ là một phiếm hàm tuyến tính và α ∈ R.
Một siêu phẳng sẽ chia không gian ra hai nửa không gian. Nửa không gian được
định nghĩa như sau:
8


Định nghĩa 1.1.7. Cho a ∈ H là một phiếm hàm tuyến tính và α ∈ R. Tập

2. Nón pháp tuyến ε của C tại x0 được định nghĩa bởi:
NCε (x0 ) := {ω ∈ H| ω T (x − x0 ) ≤ ε
9

∀x ∈ C}.


Hiển nhiên 0 ∈ NC (x0 ) và từ định nghĩa trên ta thấy NC (x0 ) là một nón lồi đóng.
Định nghĩa 1.1.10. Giả sử C = 0/ (không nhất thiết lồi) là một tập con của không
gian Hilbert H và y là một véc-tơ bất kỳ, khoảng cách từ y đến C được định nghĩa bởi
dC (y) := inf ||x − y||.
x∈C

Nếu tồn tại π ∈ C sao cho dC (y) := ||π − y||, thì ta nói π là hình chiếu (khoảng cách)
của y trên C, kí hiệu π = pC (y).

Hình 1.2: Hình chiếu khoảng cách
Theo định nghĩa, ta thấy rằng hình chiếu pC (y) của y trên C sẽ là nghiệm của bài
toán tối ưu
1
min
||x − y||2 | x ∈ C .
x
2
Nói cách khác, việc tìm hình chiếu khoảng cách của y trên C có thể đưa về việc tìm
cực tiểu của hàm toàn phương ||x − y||2 trên C. Chú ý rằng, nếu C = 0,
/ thì dC (y) hữu
hạn, vì 0 ≤ dC (y) ≤ ||x − y||, ∀x ∈ C.
Mệnh đề 1.1.3. Cho C là một tập lồi đóng khác rỗng. Khi đó:
1. Với mọi y ∈ H, π ∈ C hai tính chất sau là tương đương:

0 ≥ (y − π)T (x − π) = (y − π)T (x − y + y − π)
= ||y − π||2 + (y − π)T (x − y).
Dùng bất đẳng thức Cauchy- Schwarz ta có:
||y − π||2 ≤ (y − π)T (y − x) ≤ ||y − π||.||y − x||.
Suy ra ||y − π|| ≤ ||y − x|| ∀x ∈ C, và do đó π = pC (y.)
11


2. Sự tồn tại. Do dC (y) := infx∈C ||x−y||, nên theo định nghĩa của cận dưới đúng,
tồn tại một dãy xk ∈ C sao cho
lim ||xk − y|| = dC (y) < +∞.
k

Vậy dãy {xk } bị chặn, do đó nó có một dãy con {xk j } hội tụ yếu đến một điểm
π nào đó. Do C lồi, đóng, nên π ∈ C. Vậy
||π − y|| = lim ||xk j − y|| = lim ||xk − y|| = dC (y).
j

k

Chứng tỏ π là hình chiếu của y trên C.
Tính duy nhất. Giả sử π và π 1 là hình chiếu của y trên C, thì
y − π ∈ NC (π), y − π 1 ∈ NC (π 1 ).
Tức là
π − y, π 1 − π ≥ 0,
π 1 − y, π − π 1 ≥ 0.
Cộng hai vế của đẳng thức này ta suy ra ||π − π 1 ||2 ≤ 0, và do đó π = π 1 .
3. Do y − π ∈ NC (π), nên
π − y, x − π ≥ 0


=||x − PC (x)||2 + ||y − PC (x)||2 − 2 x − PC (x), y − PC (x) .
Do x − PC (x), y − PC (x) ≤ 0, suy ra
||x − y||2 ≥ ||x − PC (x)||2 + ||y − PC (x)||2 .
Hệ quả được chứng minh.
Toán tử chiếu là một công cụ hữu hiệu nhằm giải bài toán cân bằng và các trường
hợp đặc biệt của nó như: Bài toán tối ưu, bất đẳng thức biến phân, điểm bất động,
bài toán điểm yên ngựa.... Trong luận văn này, ta sẽ vận dụng giải quyết bài toán bất
đẳng thức biến phân giả đơn điệu mạnh.

13


1.1.3.

Tính liên tục của hàm lồi

Cho C ⊆ H là tập lồi và f : C → R ∪ {+∞}, ta sẽ kí hiệu:
dom f := {x ∈ C : f (x) < +∞}.
Tập dom f được gọi là miền hữu dụng của tập f. Tập
epi f := {(x, µ) ∈ C × R : f (x) ≤ µ},
được gọi là trên đồ thị của hàm f.
Hàm f gọi là chính thường nếu dom f = 0/ và f (x) > −∞ với mọi x ∈ dom f .
Định nghĩa 1.1.11. Hàm f được gọi là lồi nếu epi f là một tập lồi. Hàm f là hàm lõm
nếu − f là hàm lồi. Nếu f vừa lồi vừa lõm thì ta nói f là hàm afin.

Hình 1.3: Hàm lồi
Tính chất 1.1.1. Cho C ⊂ H là một tập lồi, khác rỗng. Hàm f : H → R ∪ {+∞} được
gọi là
i) lồi trên C nếu:
f (λ x + (1 − λ )y) ≤ λ f (x) + (1 − λ ) f (y), ∀x, y ∈ C, λ ∈ [0, 1],

Nếu f tựa lồi trên C thì ∀x, y ∈ C và λ ∈ [0, 1] ta có
f (λ x + (1 − λ )y) ≤ max( f (x), f (y)).
Tương tự, nếu f tựa lõm trên C thì ∀x, y ∈ C và λ ∈ [0, 1] ta có
f (λ x + (1 − λ )y) ≥ min( f (x), f (y)).
15


Định lý 1.1.3. Giả sử f là hàm lồi chính thường trên H và x0 ∈ H. Khi đó, các khẳng
định sau là tương đương:
a) f liên tục tại điểm x0 .
b) f bị chặn trên trong một lân cận của x0 .
c) int(epi f ) = 0.
/
d) int(dom f ) = 0.
/ và f liên tục trong int(dom f ).
trong đó intC là kí hiệu phần trong của tập C.

1.1.4.

Đạo hàm và dưới vi phân của hàm lồi

Tính khả vi của hàm lồi đóng vai trò quan trọng trong các phương pháp tối ưu
hóa. Lớp các hàm lồi có những tính chất rất đẹp mà các lớp hàm khác không có. Giả
sử f : H → R là hàm lồi. Ta có các khái niệm sau
Định nghĩa 1.1.15. Vectơ ω ∈ H ∗ được gọi là dưới đạo hàm của f tại x0 ∈ H nếu:
ω, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ H.
Tập hợp tất cả các dưới đạo hàm của hàm f tại x0 được gọi là dưới vi phân của hàm
f tại x0 , kí hiệu là
∂ f (x0 ) := {ω ∈ H ∗ : ω, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ H}.
Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂ f (x0 ) = 0.


n

n

Nếu ∩ri(dom fi ) = 0/ thì

∑ ∂ fi (x) = ∂ ( ∑ fi (x)), ∀x ∈ H.

i=1

i=1

Định nghĩa 1.1.17. Giả sử x ∈ H, d ∈ H\{0}, hàm f được gọi là:
a) Khả vi Frechet tại x0 nếu tồn tại ω ∈ H ∗ sao cho
f (x) − f (x0 ) − ω, x − x0
lim
= 0, ∀x ∈ H.
||x − x0 ||
x→x0
Một điểm ω như thế nếu tồn tại, sẽ duy nhất và được gọi là đạo hàm của f tại
x0 , kí hiệu là f (x0 ) hoặc ∇ f (x0 ).
b) Có đạo hàm theo hướng d tại x0 nếu tồn tại giới hạn
f (x0 + td) − f (x0 )
.
lim
t
t→0+
ta gọi giới hạn đó là đạo hàm theo hướng d của f tại x0 , kí hiệu là f (x0 , d).
Định lý 1.1.4. Giả sử f là hàm lồi chính thường trên H và x ∈ dom f . Khi đó

(VIP)

Tập nghiệm của bài toán kí hiệu là S(K, F).
Định nghĩa 1.2.2. Giả sử K ⊂ H là một tập lồi đóng, khác rỗng và toán tử F : K → H
được gọi là
a) đơn điệu mạnh trên K nếu tồn tại γ > 0 sao cho
F(x) − F(y), x − y ≥ γ||x − y||2

∀x, y ∈ K,

b) đơn điệu trên K nếu
F(x) − F(y), x − y ≥ 0

∀x, y ∈ K,

c) giả đơn điệu mạnh trên K nếu tồn tại γ > 0 sao cho
F(x), y − x ≥ 0 ⇒ F(y), y − x ≥ γ||y − x||2

∀x, y ∈ K,

d) giả đơn điệu trên K nếu
F(x), y − x ≥ 0 ⇒ F(y), y − x ≥ 0

∀x, y ∈ K.

Theo định nghĩa trên các kéo theo (a) ⇒ (b), (a) ⇒ (c), (c) ⇒ (d), (b) ⇒ (d), là
hiển nhiên.
Chú ý rằng một toán tử giả đơn điệu mạnh có thể không đơn điệu.
Ví dụ 1.2.1.
Cho 0 < r < R, đặt K = B(r) := {x ∈ H : ||x|| ≤ r} và F được cho bởi

F(v∗ ), u∗ − v∗ ≥ 0 và F(v∗ ), v∗ − u∗ ≥ γ||v∗ − u∗ ||2 . Cộng từng vế của hai bất
đẳng thức ta được γ||v∗ − u∗ ||2 ≤ 0. Suy ra u∗ = v∗ .
Cho F liên tục và giả đơn điệu. Để chứng minh S(K, F) là một tập lồi ta chỉ cần
chứng minh rằng
{u∗ ∈ K : F(u), u − u∗ ≥ 0}.

S(K, F) =
u∈K

Thật vậy, nếu u∗ ∈ S(K, F) thì F(u∗ ), u − u∗ ≥ 0 với mọi u ∈ K. Do hàm F giả đơn
điệu nên F(u), u − u∗ ≥ 0 với mọi u ∈ K. Do vậy u∗ thuộc vế phải của đẳng thức
19


trên. Ngược lại, giả sử u∗ ∈
u

= τu∗ + (1 − τ)v

{u∗ ∈ K : F(u), u − u∗ ≥ 0}. Cho u ∈ K tùy ý, vectơ
u∈K

∈ K với mọi τ ∈ (0, 1), u∗ , v ∈ K. Do đó, ta có:
F(τu∗ + (1 − τ)v), u − u∗ ≥ 0, ∀τ ∈ (0, 1).

Cho τ → 1 thì F(u∗ ), u − u∗ ≥ 0. Do đó, u∗ ∈ S(K, F). Vì với mỗi u ∈ K, tập
{u∗ ∈ K : F(u), u − u∗ ≥ 0} là lồi và giao của các tập lồi là một tập lồi nên S(K, F)
là một tập lồi. Mệnh đề được chứng minh.
Định nghĩa 1.2.4. Ánh xạ F được gọi là liên tục Lipschitz trên K nếu tồn tại hằng số
L > 0 sao cho:

+ λωi là mức độ chi phí trên tuyến đường ω của phương tiện giao thông i.
i : là mật độ giao thông của phương tiện i ∈ I trên tuyến đường ω = (A, B)
+ xω
Giả sử trong mạng trên, phương trình cân bằng sau được thỏa mãn:
dωi =

∑

xip , ∀i ∈ I, ω ∈ A × B.

(1.1)

p∈Pω

Trong đó, Pω kí hiệu là tập các tuyến đường của ω = (A, B) (nối điểm nguồn A
và điểm đích B). Theo phương trình (1.1), thì nhu cầu sử dụng loại phương tiện i trên
tuyến đường ω đúng bằng mật độ giao thông của phương tiện đó trên tuyến đường
nối điểm nguồn và điểm đích của tuyến đường đó. Khi đó ta có:
fei =

∑

xip δep , ∀i ∈ I, ω ∈ A × B.

(1.2)

p∈Pω

Trong đó:


Định lý 1.2.1. Mỗi cặp vectơ ( f ∗ , d ∗ ) ∈ K là một điểm cân bằng của mạng giao
thông khi và chỉ khi nó là nghiệm của bài toán bất đẳng thức biến phân sau
Tìm ( f ∗ , d ∗ ) ∈ K :

c( f ∗ ), λ (d ∗ ) , ( f , d) − ( f ∗ , d ∗ ) ≥ 0, ∀( f , d) ∈ K.
21


Ví dụ 1.2.3. (Bài toán cân bằng di trú)
Bài toán cân bằng di trú bao gồm một tập hữu hạn các điểm X. Với mỗi i, j ∈ X,
gọi
+ bi là mật độ cố định tại vị trí i,
+ hi j là trọng số của dòng di trú từ vị trí đầu i đến đích j,
+ xi là mật độ hiện tại tại vị trí i,
+ ui là tiện ích di trú,
+ ci j là chi phí di trú.
Đặt x = {xi | i ∈ X} và h = {hi j | i, j ∈ X, i = j}, ta định nghĩa
X = (x,h) h > 0,

∑ hi j ≤ bi ,
i= j

xi = bi + ∑ h ji − ∑ hi j , ∀i ∈ X . (1.3)
i= j

i= j

Từ ràng buộc
h > 0,




≥ 0

nếu ∑ h∗is = bi ,


= 0

nếu ∑ h∗is < bi , với mỗi i ∈ N.

s=i

s=i

22

(1.5)


Tập các điều kiện cân bằng (1.4), (1.5) có thể được viết lại tương đương với bất
đẳng thức biến phân. Tìm một cặp (x∗ , h∗ ) sao cho

∑ (xi∗ − xi )ui (x∗ ) + ∑

i∈N

(hi j − h∗i j )ci j (h∗ ) ≥ 0, ∀(x, h) ∈ H.

i, j∈N,i= j