ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
——————————–

TRẦN ĐOÀN THẢO NGUYÊN

MỘT SỐ ỨNG DỤNG CỦA PHÉP CHIẾU ĐỂ
GIẢI BÀI TOÁN TỐI ƯU VÀ BẤT ĐẲNG THỨC
BIẾN PHÂN

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

ĐÀ NẴNG - NĂM 2019


ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC SƯ PHẠM
——————————–

TRẦN ĐOÀN THẢO NGUYÊN

MỘT SỐ ỨNG DỤNG CỦA PHÉP CHIẾU ĐỂ
GIẢI BÀI TOÁN TỐI ƯU VÀ BẤT ĐẲNG THỨC
BIẾN PHÂN
Chuyên ngành: Toán giải tích
Mã số: 8460102

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

Người hướng dẫn khoa học
TS. Phạm Quý Mười

ĐÀ NẴNG - NĂM 2019


LỜI CAM ĐOAN

Tồn bộ nội dung trình bày trong luận văn này là cơng trình nghiên
cứu tổng quan của tơi, được hoàn thành dưới sự hướng dẫn của TS.Phạm
Quý Mười. Những khái niệm và kết quả trong luận văn được tổng hợp từ
các tài liệu khoa học đáng tin cậy, và được chỉ rõ nguồn gốc trích dẫn.
Đóng góp của tơi là tổng hợp tài liệu, trình bày thêm các ví dụ minh hoạ.
Tơi xin chịu trách nhiệm với những lời cam đoan của mình.
Tác giả

Trần Đồn Thảo Ngun




LỜI CẢM ƠN

Lời đầu tiên của luận văn tác giả xin gửi lời cảm ơn sâu sắc tới thầy
giáo hướng dẫn TS. Phạm Quý Mười đã tận tình hướng dẫn tác giả trong
suốt quá trình thực hiện để tác giả có thể hồn thành được luận văn này.
Tác giả cũng xin gửi lời cảm ơn chân thành nhất đến tất cả các thầy
cơ giáo đã tận tình dạy bảo tác giả trong suốt thời gian học tập của
khóa học.
Đồng thời, tác giả cũng xin gửi lời cảm ơn đến các anh chị em trong lớp
Tốn giải tích K34-Đà Nẵng đã nhiệt tình giúp đỡ tác giả trong quá trình
học tập tại lớp.

Tác giả

Trần Đoàn Thảo Nguyên


MỤC LỤC
MỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
CHƯƠNG 1. KIẾN THỨC CƠ SỞ . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1. KHÔNG GIAN Rn và CHUẨN
1.2. TẬP LỒI, HÀM LỒI

..................................... 4

............................................. 5

1.2.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3. PHÉP CHIẾU LÊN TẬP LỒI

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

CHƯƠNG 2. ỨNG DỤNG CỦA PHÉP CHIẾU ĐỂ GIẢI
BÀI TOÁN TỐI ƯU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1. BÀI TOÁN TỐI ƯU

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17

2.1.1. Mơ tả bài tốn tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.2. Sự tồn tại nghiệm và điều kiện của nghiệm . . . . . . . . . . 17
2.2. ỨNG DỤNG CỦA PHÉP CHIẾU ĐỂ GIẢI BÀI TỐN TỐI ƯU

2.3. MỘT SỐ VÍ DỤ

. . . . . . . . . 21

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

CHƯƠNG 3. ỨNG DỤNG CỦA PHÉP CHIẾU ĐỂ GIẢI
BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN . . . . . . . . . . . . 29
3.1. BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN

. . . . . . . . . . . . . . . . . . . . . . . . 29

3.1.1. Mơ tả bài tốn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2. Tính đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.3. Sự tồn tại nghiệm và điều kiện của nghiệm . . . . . . . . . . 30


MỤC LỤC
3.2. ỨNG DỤNG CỦA PHÉP CHIẾU ĐỂ GIẢI BÀI TOÁN BẤT ĐẲNG THỨC BIẾN
PHÂN

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.3. MỘT SỐ VÍ DỤ

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42


6


DANH MỤC

1. Danh mục
Rn
∀x
x
x, y
V I(F, C)
CP (F, C)

các ký hiệu:
Khơng gian Euclide n-chiều
Với mọi x
Chuẩn của vectơ x
Tích vơ hướng của hai vectơ x, y
Bài toán bất đẳng thức biến phân
Bài toán bù phi tuyến.

2. Danh mục các bảng:
Số hiệu bảng
2.1
2.2
3.1
3.2
3.3

Tên bảng

Nghiệm tối ưu toàn cục là x∗ = (1, 1)
Nghiệm tối ưu toàn cục là x∗ = (0, 1)
Nghiệm tối ưu toàn cục là x∗ = 0, 4, 0)
Nghiệm tối ưu toàn cục là x∗ = (0, 0)
Nghiệm tối ưu toàn cục là x∗ = (0, 0)

Trang
26
28
38
39
40


1

MỞ ĐẦU

1. Lý do chọn đề tài
Giải tích lồi là bộ mơn cơ bản của giải tích hiện đại, nghiên cứu về tập lồi
và hàm lồi cùng những vấn đề liên quan. Bộ mơn này có vai trị quan trọng
trong nhiều lĩnh vực khác nhau của toán học ứng dụng, đặc biệt là trong
tối ưu hoá, bất đẳng thức biến phân, các bài toán cân bằng. Một trong
những vấn đề quan trọng của giải tích lồi đó là phép chiếu. Đây là một
công cụ sắc bén và khá đơn giản để chứng minh nhiều định lý quan trọng
như Định lý tách, Định lý xấp xỉ tập lồi, Định lý về tồn tại nghiệm của Bất
đẳng thức biến phân. Hơn nữa phép chiếu còn được dùng để xây dựng các
phương pháp giải nhiều lớp bài toán quan trọng như bài toán quy hoạch
lồi, bài toán tối ưu, bài toán bất đẳng thức biến phân. Những năm gần
đây, bài toán bất đẳng thức biến phân đã có những bước phát triển rất

mạnh và thu hút được sự quan tâm của nhiều nhà nghiên cứu. Một trong
các hướng nghiên cứu quan trọng của bài toán bất đẳng thức biến phân là
việc xây dựng các phương pháp giải. Có rất nhiều phương pháp giải, trong
đó có phương pháp dựa vào cách tiếp cận điểm bất động. Ý tưởng chính
của phương pháp này là chuyển việc giải bất đẳng thức biến phân về bài
tốn tìm điểm bất động của một ánh xạ thích hợp. Một trong những cách
tiếp cận điểm bất động là dựa trên phương pháp chiếu .
Với các lí do trên, dưới sự hướng dẫn của TS. Phạm Quý Mười, tôi chọn
nghiên cứu đề tài: "Một số ứng dụng của phép chiếu để giải bài toán tối
ưu và bất đẳng thức biến phân."
2. Mục đích nghiên cứu
Tìm hiểu, nghiên cứu kỹ các tài liệu từ nhiều nguồn khác nhau, cố gắng
lĩnh hội được các kiến thức về phép chiếu,bài toán tối ưu, bài toán bất
đẳng thức biến phân và những ứng dụng của phép chiếu để giải hai dạng


2

bài tốn đó. Hy vọng luận văn có thể được sử dụng như một tài liệu tham
khảo bổ ích cho sinh viên các trường Đại học, Cao đẳng.
3. Đối tượng nghiên cứu
Đối tượng nghiên cứu là:
- Phép chiếu để giải bài toán tối ưu.
- Phép chiếu để giải bài toán bất đẳng thức biến phân.
4. Phạm vi nghiên cứu
Phạm vi nghiên cứu của luận văn chỉ đi sâu tìm hiểu các định lí, bổ đề,
thuật tốn liên quan, từ đó đưa ra ứng dụng các phương pháp chiếu để
giải các bài toán tối ưu,bất đẳng thức bik F (xk ), x∗ − xk+1 ≤ −2λk γ xk+1 − x∗
xk − xk+1


2

2

+

(Lλk )2 xk+1 − x∗ .

Mặt khác,
2

2 xk − xk+1 , x∗ − xk+1 = xk − xk+1

(xk − xk+1 ) − (x∗ − xk+1 )
= xk − xk+1

2

+ x∗ − xk+1

2

2

+ x∗ − xk+1

− xk − x∗

2


−

.

2

(3.3)

Kết hợp (3.2), (3.3), ta nhận được:

xk − xk+1

2

+ x∗ − xk+1

2

− xk − x∗

2

2

≤ −2λk γ x∗ − xk+1
+ xk − xk+1

2

+ (Lλ2k ) x∗ − xk+1


2

,

và định lý được chứng minh.
Giả sử bài tốn V I(F, C) có nghiệm, hàm giá F là giả đơn điệu mạnh và
liên tục trên C . Ta sẽ chỉ ra rằng dãy xk xác định bởi Thuật toán 3.2.1
hội tụ tới nghiệm theo tốc độ tuyến tính.
Định lí 3.2.2. Cho C là một tập con, lồi, đóng, khác rỗng của Rn ,
F : C −→ Rn là giả đơn điệu mạnh với hằng số γ > 0 và liên tục
Lipschitz với hằng số L > 0. Chọn dãy lặp {λk } thỏa mãn:


35

2γ
∀k ≥ 0,
(3.4)
L2
trong đó a, b là các hằng số dương. Khi đó, dãy số xk xác định bởi Thuật
tốn 3.2.1. Nếu x∗ là nghiệm duy nhất của bài toán V I(F, C) thì dãy xk
hội tụ tuyến tính tới x∗ . Hơn nữa tốc độ hội tụ được xác định bởi:
µk+1
k+1
∗
x0 − x1 ,
(3.5)
x
−x ≤

1−µ
và:
µk
k+1
∗
xk+1 − xk , ∀k ≥ 0,
(3.6)
x
−x ≤
1−µ
trong đó:
1
µ :=
∈ (0, 1).
(3.7)
1 + a(2γ − bL2 )
0 < a ≤ λk ≤ b <

Chứng minh. Từ (3.4), suy ra rằng:

1 + λk (2γ − L2 λk ) ≥ 1 + a(2γ − L2 b) > 1, ∀k ≥ 0.
Kết hợp điều này với Định lý 3.2.1, ta nhận được:

1 + a(2γ − L2 b)

xk+1 − x∗

2

≤ xk − x∗


2

, ∀k ≥ 0.

Khi đó,

xk+1 − x∗ ≤ µ xk − x∗ , ∀k ≥ 0,

(3.8)

với µ ∈ (0, 1) xác định bởi (3.7). Tính chất (3.8) kéo theo tốc độ hội tụ
tuyến tính tới x∗ của xk . Hơn nữa, theo (3.8), ta có:

xk+1 − x∗ ≤ µ xk − x∗ ≤ µ2 xk−1 − x∗ ≤ ... ≤ µk+1 x0 − x∗ .
Khi đó, ta có:

xk − x∗ ≤ xk+1 − xk + xk+1 − x∗ ≤ xk+1 − xk + xk − x∗ ,
và như vậy:

xk − x∗ ≤

1
xk+1 − xk , ∀k ≥ 0.
1−µ

Suy ra:

xk+1 − x∗ ≤ µk+1 x0 − x∗ ≤


µk+1
x0 − x1 ,
1−µ


36

và

xk+1 − x∗ ≤ µ xk − x∗ ≤

µ
xk+1 − xk .
1−µ

Định lý được chứng minh.
Tại mỗi bước lặp k của Thuật toán 3.2.1., tham số λk thường được gọi
là độ dài bước lặp. Khi a = b = λk , độ dài bước là không đổi xác định bởi:
2γ
λ ∈ 0, 2 .
L
Khi đó, hệ số co µ của thuật tốn lặp được xác định bởi:
1
.
µ=
1 + λ(2γ − λL2 )
Dễ nhận thấy rằng hệ số µ càng nhỏ thì dãy lặp xk hội tụ càng nhanh
tới nghiệm x∗ . xét µ như một hàm số theo ẩn λ, ta có µ nhỏ nhất khi và
chỉ khi λ = λ∗ =


γ
L2 .

Khi đó, hệ số co nhỏ nhất xác định bởi:
L
µ = µ∗ =
.
L2 + γ 2
Bây giờ, ta giả sử hệ số µ xác định bởi (3.5) là một hàm theo hai biến số

a và b, hay µ = µ(a, b) xác định trên miền:
2γ
.
L2
Để đơn giản, đặt b = ta, ở đây t ∈ [1, +∞) là cố định. Dễ dàng nhận thấy
γ2
1
rằng µ(a, b) = µ(a, ta) đạt giá trị cực tiểu là
tại
điểm
tL2 . Mặt
γ2
(a, b) : 0 < a ≤ b <

D=

1+ tL2

khác:
min






1




1+

γ2
tL2




L
: t ∈ [1, +∞) = 2
.
2

 L +γ

Như vậy, ta có thể kết luận rằng:
min {µ(a, b) : (a, b) ∈ D} =

L
L2 + γ 2


đạt được tại điểm:

γ2 γ2
(a , b ) =
,
.
tL2 tL2
Như ta đã biết, nếu một ánh xạ F là đơn điệu mạnh với hằng số γ > 0
∗

∗


37

thì F sẽ là giả đơn điệu với hằng số γ > 0. Khi đó, ta có hệ quả sau.
Hệ quả 3.2.3. Cho C là một tập con, lồi, đóng, khác rỗng của Rn , F :

C → Rn là đơn điệu mạnh với hằng số γ > 0 và liên tục Lipschitz với
hằng sô L > 0. Chọn dãy lặp λk thỏa mãn:
2γ
0 < a ≤ λk ≤ b < 2 , ∀k ≥ 0,
L
Trong đó, a, b là các hằng số dương. Khi đó, dẫy số xk xác định bởi Thuật
tốn 3.2.1 hội tụ tuyến tính tới nghiệm duy nhất x∗ của bài toán V I(F, C)
với sai số tính tốn xác định bởi (3.6), (3.7).
Định lí 3.2.4. Cho C là một tập con, lồi, đóng, khác rỗng của Rn , F :
C → Rn là giả đơn điệu mạnh với hằng số γ > 0 và liên tục Lipschitz với
hằng số L > 0. Chọn dãy số dương λk thỏa mãn:

∞

lim λk = 0,

k→∞

λk = +∞.
k=0

Giả sử bài tốn V I(F, C) có duy nhất một nghiệm x∗ . Khi đó, dãy số
xk xác định bởi Thuật toán 3.2.1 hội tụ tới x∗ . Hơn nữa, tồn tại k0 sao
cho:

λk (2γ − λk L2 ) > 0, xk+1 − x∗ ≤

1

xk0 − x∗ ,

k

[1 + λi (2γ − λi L2 )]
i=k0

∀k ≥ k0 .

3.3. MỘT SỐ VÍ DỤ
Ví dụ 3.3.1. Xét bài tốn bất đẳng thức biến phân V I(F, C), trong đó

F (x) = Ax + b, b = (2, 3) và:

5 1
A = −1 8 , C = {x ∈ Rn : x1 ≥ 0, x2 ≥ 0, x1 + x2 ≤ 4} .
Lời giải. Ta chứng minh được hàm f là hàm đơn điệu mạnh với hệ số
đơn điệu mạnh β = 5 và L = 8, 0766. Chọn λk = 0, 1. Khi đó, điều kiện


38

0 ≤ a ≤ λk ≤ b < L2β2 được thỏa mãn. Áp dụng Thuật toán chiếu một lần
vào giải bài tốn nói trên ta được kết quả như dưới đây. Điều kiện dừng
của thuật toán là xk+1 − xk ≤ với = 10−4 .
Bước 0: Chọn x0 = (2, 2). Đặt k = 0.
Bước 1: Tính giá trị x1 = P rC (x0 − 0, 1 ∗ F (x0 )) = (1, 0, 5). Ta có
x1 − x0 = 1, 8028 > nên chuyển sang Bước 2.
Bước 2: Tính giá trị x2 = P rC (x1 − 0, 1 ∗ F (x1 )) = (0, 65, 0, 1). Ta có
x2 − x1 = 0, 5315 > nên chuyển sang Bước 3.
Bước 3: Tính giá trị x3 = P rC (x2 − 0, 1 ∗ F (x2 )) = (0, 5150, 0). Ta có
x3 − x2 = 0, 1680 > nên chuyển sang bước tiếp theo.

Tiếp tục quá trình trên, ta thu được kết quả như bảng dưới đây.
Bước k
k=0
k=1
k=2
k=3
k=4
k=5
k=6
k=7
k=8

k=9
k=10
k=11
k=12
k=13
k=14

xk
(2, 2)
(1, 0,5)
(0,65, 0,1)
(0,515, 0)
(0,4575, 0)
(0,4288, 0)
(0,4144, 0)
(0,4072, 0)
(0,4036, 0)
(0,4018, 0)
(0,4009, 0)
(0,4004, 0)
(0,4002, 0)
(0,4001, 0)
(0,4001, 0)

xk+1 − xk
1,8028
0,5315
0,1680
0,0575
0,0287

0,0144
0,0072
0,0036
0,0018
8, 9844.10−4
4, 4922.10−4
2, 2461.10−4
1, 123.10−4
5, 6152.10−5

Bảng 3.1: Nghiệm tối ưu toàn cục là x∗ = (0, 4, 0).

Ví dụ 3.3.2. Miền ràng buộc C và hàm xác định trên C được cho bởi:

C = x ∈ R2 : x ≤ α, F (x) = (β − x )x,
2(β−α)
trong đó α = 23 , β = 2 và λk = λ ∈ 0, (α+2β)
2 . Dễ dàng tính được rằng


39

tập nghiệm của bài toán V I(F, C) là Sol(F, C) = {(0, 0)}. Theo Ví dụ
3.3.1, F là liên tục Lipschitz với hằng số L = α + 2β và giả đơn điệu mạnh
trên C với hằng số γ := β − α. Nhưng F không đơn điệu trên C .
Lời giải. Ta chứng minh được hàm f là hàm đơn điệu mạnh với hệ số
đơn điệu mạnh β = 2 và L = α + 2β = 5, 5. Chọn λk = 0, 03. Khi đó, điều
kiện 0 ≤ a ≤ λk ≤ b < L2β2 được thỏa mãn. Áp dụng Thuật toán chiếu một
lần vào giải bài tốn nói trên ta được kết quả như dưới đây.
Bước 0: Chọn x0 = (0, 5, 1). Đặt k = 0.

Bước 1: Tính giá trị x1 = P rC (x0 − 0, 03 ∗ F (x0 )) = (0, 4868, 0, 9735). Ta
có x1 − x0 = 0, 0296 > nên chuyển sang Bước 2.
Bước 2: Tính giá trị x2 = P rC (x1 − 0, 03 ∗ F (x1 )) = (0, 4735, 0, 9469). Ta
có x2 − x1 = 0, 0297 > nên chuyển sang bước tiếp theo.
Bước 3: Tính giá trị x3 = P rC (x2 − 0, 03 ∗ F (x2 )) = (0, 4601, 0, 9202). Ta
có x3 − x1 = 0, 0299 > nên chuyển sang bước tiếp theo.
Tiếp tục quá trình trên, ta thu được kết quả như bảng dưới đây. Dãy xk
sẽ hội tụ tới nghiệm duy nhất x∗ = (0, 0).
Bước k
k=0
k=1
k=2
k=3
k=4
k=5
k=6
k=7
k=8
k=9

xk
(0,5, 1)
(0,4868, 0,9735)
(0,4735, 0,9469)
(0,4601, 0,9202)
(0,4467, 0,8934)
(0,4333, 08665)
(0,4199, 0,8397)
(0,4065, 0,8130)
(0,3932, 0,7864)

(0,3800, 0,7599)

xk+1 − xk
0,0296
0,0297
0,0299
0,03
0,03
0,03
0,0299
0,0297
0,0296

Bảng 3.2: Nghiệm tối ưu toàn cục là x∗ = (0, 0).


40

Tuy nhiên, nếu thay đổi độ dài bước λk = 0, 3 và thực hiện tương tự
thì tốc độ của thuật toán sẽ thay đổi với kết quả chi tiết trong bảng sau:
Bước k
k=0
k=1
k=2
k=3
k=4
k=5
k=6
k=7
k=8

k=9

xk
(0,5, 1)
(0,3677, 0,7354)
(0,3481, 0,6962)
(0,2378, 0,4756)
(0,1330, 0,2661)
(0,0651, 0,1302)
(0,0289, 0,0578)
(0,0121, 0,0242)
(0,0049, 0,0099)
(0,0020, 0,0040)

xk+1 − xk
0,2958
0,0438
0,2466
0,2342
0,1519
0,0809
0,0376
0,0160
6, 5.10−3

Bảng 3.3: Nghiệm tối ưu toàn cục là x∗ = (0, 0).


41


KẾT LUẬN

1. Kết luận

Sau một thời gian tìm hiểu và nghiên cứu, luận văn đã thu được những
kết quả sau.
1.1. Nghiên cứu bài tốn tối ưu có điều kiện và phương pháp chiếu để
tìm nghiệm xấp xỉ của bài tốn..
1.2. Nghiên cứu bài toán bất đẳng thức biến phân và phương pháp
chiếu để tìm nghiệm xấp xỉ của bài tốn.
1.3. Áp dụng các giải thuật đã nghiên cứu để giải các bài toán toán cụ
thể.
2. Hướng phát triển của luận văn
Thời gian tới, chúng tôi tiếp tục nghiên cứu những vấn đề sau.
2.1. Tìm ra một số phương pháp chiếu khác để giải bài toán bất đẳng
thức biến phân như phương pháp chiếu hai lần, phương pháp chiếu siêu
phẳng.
2.2. Có thể sử dụng phương pháp chiếu để giải các bài toán tối ưu và
bất đẳng thức biến phân phức tạp hơn.


42

TÀI LIỆU THAM KHẢO

Tiếng Việt
[1] Phạm Ngọc Anh (2015), Các phương pháp tối ưu và ứng dụng, Nhà
xuất bản Thông tin và Truyền thông.
[2] Trần Việt Anh (2018), Các phương pháp giải bất đẳng thức biến phân
trên tập nghiệm của bài toán chấp nhận suy tách suy rộng, Nhà xuất

bản Đại học Quốc gia Hà Nội.
[3] Nguyễn Hữu Điền (2001), Một số vấn đề về thuật toán, Nhà xuất bản
Giáo dục.
[4] Đỗ Văn Lưu (2000), Giải tích lồi, Nhà xuất bản Khoa học kỹ thuật.
Tiếng Anh
[5] Svaiter B.F., Teboulle M., Iusem A.N. (1994). Entropy-like proximal
methods in covex programming. Math. Oper. Res.