BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC VINH
ĐẬU XUÂN LƯƠNG
PHƯƠNG PHÁP HÀM PHẠT
CHO BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN
LUẬN ÁN TIẾN SĨ TOÁN HỌC
VINH - 2010
i
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC VINH
ĐẬU XUÂN LƯƠNG
PHƯƠNG PHÁP HÀM PHẠT
CHO BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN
LUẬN ÁN TIẾN SĨ TOÁN HỌC
Chuyên ngành: Toán giải tích
Mã số: 62 46 01 01
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS. TSKH. LÊ DŨNG MƯU
PGS. TS. TRẦN VĂN ÂN
VINH - 2010
MỤC LỤC
Mục lục i
Lời cam đoan iv
Lời cảm ơn 1
Mở đầu 2
1 Lí do chọn đề tài . . . . . . . . . . . . . . . . . . . . . . 2
2 Mục đích nghiên cứu . . . . . . . . . . . . . . . . . . . . 5
3 Đối tượng nghiên cứu . . . . . . . . . . . . . . . . . . . . 6
4 Phạm vi nghiên cứu . . . . . . . . . . . . . . . . . . . . 6

2 Kiến nghị . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Danh mục công trình khoa học của nghiên cứu sinh liên
quan đến luận án 63
Tài liệu tham khảo 63
iv
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, các
kết quả trình bày trong luận án là hoàn toàn trung thực, được các đồng
tác giả cho phép sử dụng và luận án hoàn toàn không trùng lặp với
bất kì tài liệu nào khác.
Đậu Xuân Lương
1
LỜI CẢM ƠN
Luận án được hoàn thành dưới sự hướng dẫn của GS. TSKH. Lê Dũng
Mưu và PGS. TS Trần Văn Ân. Tác giả xin bày tỏ lòng biết ơn sâu sắc
nhất tới các Thầy, những người đã tận tình hướng dẫn, giúp đỡ tác giả
trong cả quá trình học tập, nghiên cứu và viết bản luận án này.
Tác giả cũng xin chân thành cảm ơn Lãnh đạo trường Đại học Vinh,
lãnh đạo khoa Toán học, Khoa Sau đại học – Trường Đại học Vinh; Lãnh
đạo Viện Toán học, cùng tập thể GS và các Thầy, Cô của Trường Đại học
Vinh và Viện Toán học đã động viên giúp đỡ tạo nhiều điều kiện thuận
lợi trong thời gian tác giả học tập và nghiên cứu.
Tác giả xin gửi lời cảm ơn tới các nhà khoa học và các Thầy, Cô thuộc
Tổ Giải tích của Khoa Toán học – Trường Đại học Vinh đã dành thời
gian đọc luận án và cho những ý kiến nhận xét quý báu.
Tác giả xin gửi lời cảm ơn tới Trường Cao Đẳng Sư phạm Quảng Ninh
và Khoa Tự nhiên thuộc Trường Cao Đẳng Sư phạm Quảng Ninh, người
thân và bạn bè vì những góp ý, ủng hộ và động viên về tinh thần cũng
như vật chất cho tác giả.
Đậu Xuân Lương

(Weak Vector Variational Inequality Problem, viết tắt là WVVIP) trong
bài toán tối ưu đa mục tiêu (Multiobjective Optimization Problem, viết
tắt là MOP) (tham khảo chẳng hạn [16, 2, 4, 53, 18], trong bài toán xấp
xỉ vector (Vector Approximation Problem) ([54]), và trong bài toán cân
bằng giao thông vector (Vector Traffic Equilibrium Problem) ([55]). Sự
tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu cũng được
nghiên cứu trong nhiều công trình (tham khảo chẳng hạn [6, 4, 3, 31, 12]).
Để có thể ứng dụng bài toán bất đẳng thức biến phân vector yếu vào
thực tiễn, đòi hỏi phải có các thuật toán giải số hiệu quả cho bài toán
này. Tuy nhiên, theo hiểu biết của chúng tôi, cho tới nay chỉ có một vài
công trình nghiên cứu về các thuật toán để giải bài toán bất đẳng thức
biến phân vector yếu ([18, 19]). Từ rất lâu, phương pháp hàm phạt đã
được áp dụng để giải các bài toán tối ưu và các bài toán bất đẳng thức
biến phân dạng thường, đưa một bài toán với miền ràng buộc phức tạp
về một dãy các bài toán có ràng buộc đơn giản hơn hoặc không có ràng
buộc. Tuy nhiên, cho tới nay chưa có bất cứ công trình nào nghiên cứu
áp dụng phương pháp này cho bài toán bất đẳng thức biến phân vector
yếu mà chúng tôi được biết.
1.3 Khái niệm nghiệm tối ưu Pareto (mà trong luận án này chúng tôi
gọi là nghiệm Pareto) của bài toán tối ưu đa mục tiêu xuất hiện đầu tiên
trong các công trình của Edgeworth [13] và Pareto [44]. Một điểm x được
gọi là nghiệm Pareto của bài toán tối ưu đa mục tiêu với hàm mục tiêu
f = (f
1
, . . . , f
k
) (k mục tiêu) nếu không có một điểm nào khác tốt hơn
4
điểm đó, nghĩa là không tồn tại một điểm y = x sao cho f
i

yếu của các bài toán phạt nằm trong miền ràng buộc D. Giả thiết này là
một điểm bất lợi trong cách tiếp cận bài toán tối ưu đa mục tiêu với hàm
phạt mũ của Liu và Feng. Từ đó nảy sinh yêu cầu phải có một mô hình
hàm phạt cho các kết quả hội tụ tốt hơn, khắc phục được nhược điểm của
mô hình đề xuất trong [34].
Với các lí do nêu trên, chúng tôi chọn đề tài “Phương pháp hàm
phạt cho bài toán bất đẳng thức biến phân” làm đề tài luận án
tiến sĩ. Đề tài tập trung nghiên cứu những vấn đề sau.
(1) Kết hợp phương pháp hàm phạt và phương pháp chiếu để có một
5
thuật toán hoàn chỉnh giải các bài toán bất đẳng thức biến phân dạng
VIP(D, f), với D lồi đóng khác rỗng và f đơn điệu, liên tục Lipschitz.
Bằng cách này, ta khắc phục được trở ngại lớn nhất của phương pháp
chiếu là sự khó khăn khi tính toán hình chiếu của một điểm lên một miền
lồi bất kỳ.
(2) Áp dụng phương pháp hàm phạt để chuyển một bài toán bất đẳng
thức biến phân vector yếu với ràng buộc trên một miền D lồi đóng bất
kỳ về một dãy các bài toán bất đẳng thức biến phân vector yếu với miền
ràng buộc K ⊃ D đơn giản hơn, gọi là các bài toán phạt. Ta có thể chọn
K = R
k
, nghĩa là các bài toán phạt sẽ không có ràng buộc.
(3) Áp dụng phương pháp hàm phạt để chuyển một bài toán tối ưu đa
mục tiêu với ràng buộc trên một miền D lồi đóng bất kỳ về một dãy các
bài toán tối ưu đa mục tiêu với miền ràng buộc K ⊃ D đơn giản hơn, gọi
là các bài toán phạt. Ta có thể chọn K = R
k
, nghĩa là các bài toán phạt
sẽ không có ràng buộc. Bằng cách sử dụng hàm phạt ngoài, chúng tôi thu
được các kết quả hội tụ tốt hơn so với các kết quả nêu trong [34]. Ngoài

công trình nghiên cứu về bài toán bất đẳng thức biến phân (dạng thường)
trước đó là chúng tôi đổi vị trí của tham số phạt khi xây dựng bài toán
phạt. Nhờ đó tính hội tụ của thuật toán được chứng minh. Trong chương
thứ ba, thay vì áp dụng hàm phạt mũ như trong [34], chúng tôi sử dụng
hàm phạt ngoài và áp dụng kỹ thuật chứng minh trong [38], nhờ đó thu
được các kết quả hội tụ tốt hơn các kết quả nêu trong [34].
7
6 Ý nghĩa khoa học và thực tiễn
Kết quả của luận án góp phần giải quyết vấn đề giải số các bài toán
bất đẳng thức biến phân dạng thường và dạng vector yếu và bài toán tối
ưu đa mục tiêu.
Luận án là tài liệu tham khảo cho sinh viên, học viên cao học và nghiên
cứu sinh chuyên ngành Toán giải tích.
7 Tổng quan và cấu trúc luận án
7.1 Tổng quan luận án
Trong luận án này, chúng tôi nghiên cứu phương pháp hàm phạt cho
bài toán bất đẳng thức biến phân (dạng thường), bài toán bất đẳng thức
biến phân vector và bài toán liên quan với nó là bài toán tối ưu đa mục
tiêu.
Chương 1 nghiên cứu vấn đề kết hợp phương pháp hàm phạt và phương
pháp chiếu để giải bài toán bất đẳng thức biến phân. Chúng tôi nhắc lại
một số định nghĩa và kết quả cơ bản về sự tồn tại và duy nhất nghiệm của
bài toán bất đẳng thức biến phân. Phương pháp chiếu và phương pháp
hàm phạt cho bài toán bất đẳng thức biến phân được trình bày tương
ứng trong các mục 1.3 và 1.4. Kết quả chính của chương này được trình
bày trong mục 1.5. Trong mục này, chúng tôi đưa ra Thuật toán 3, kết
hợp các phương pháp hàm phạt và phương pháp chiếu để giải bài toán
bất đẳng thức biến phân. Thuật toán này trước hết chuyển một bài toán
bất đẳng thức biến phân ràng buộc trên một miền lồi đóng D bất kỳ
về một dãy các bài toán phạt với ràng buộc đơn giản hơn, sau đó giải

của bài toán ban đầu WVVIP(D, F ). Chúng tôi đưa ra một tính chất
mạnh hơn tính chất D-bức trên K, đó là tính chất D-bức mạnh trên K
của ánh xạ F : R
k
→ R
r×k
. Định lý 2.3.4 chứng minh rằng nếu F là một
ánh xạ liên tục, đơn điệu, thỏa mãn điều kiện D-bức mạnh trên K, thì
(1) các bài toán phạt luôn có ít nhất một nghiệm;
9
(2) một dãy nghiệm bất kỳ của các bài toán phạt luôn bị chặn và do đó
có ít nhất một điểm giới hạn;
(3) một điểm giới hạn bất kỳ của dãy các nghiệm của các bài toán phạt
sẽ là nghiệm của bài toán ban đầu.
Kết quả của Chương 2 được công bố trong [35].
Trong Chương 3, chúng tôi áp dụng phương pháp hàm phạt cho bài
toán tối ưu đa mục tiêu MOP(D, f). Sử dụng các kết quả về sự tồn tại
nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu ([30]) và sự tồn tại
nghiệm của bài toán bất đẳng thức biến phân vector yếu ([6]), trong Bổ
đề 3.2.1 chúng tôi đưa ra điều kiện đủ cho sự tồn tại nghiệm của các
bài toán phạt MOP(K, f
(t)
) với t > 0. Các kết quả chính về sự hội tụ
của thuật toán phạt được trình bày trong mục 3.3. Bổ đề 3.3.1 chứng
minh tính chấp nhận được của một điểm giới hạn của một dãy bất kỳ
các nghiệm Pareto yếu của các bài toán phạt MOP(K, f
(t)
) khi t tiến ra
vô cùng. Dựa vào bổ đề này, Định lý 3.3.2 chứng tỏ rằng một điểm giới
hạn bất kỳ của một dãy các nghiệm Pareto yếu của các bài toán phạt

có nghiệm của bài toán phạt, Mục 2.3 trình bày các định lý hội tụ của
phương pháp.
Chương 3 trình bày về phương pháp hàm phạt áp dụng cho bài toán
tối ưu đa mục tiêu, bao gồm 3 mục. Mục 3.1 trình bày các kết quả cần
dùng về sự tồn tại nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu,
Mục 3.2 trình bày về bài toán phạt và điều kiện có nghiệm của bài toán
phạt, Mục 3.3 trình bày các định lý hội tụ của phương pháp.
11
CHƯƠNG 1
HÀM PHẠT CHO BÀI TOÁN BẤT ĐẲNG THỨC
BIẾN PHÂN
Giả sử D ⊂ R
n
là một tập lồi đóng khác rỗng và f : R
n
→ R
n
là một
ánh xạ bất kỳ. Ký hiệu ·,· là tích vô hướng trên R
n
. Xét bài toán bất
đẳng thức biến phân sau đây
VIP(D, f) : Tìm x ∈ D, sao cho f(x), y− x ≥ 0, với mọi y ∈ D.
Tập nghiệm của VIP(D, f) được kí hiệu là S. Tập D được gọi là miền
ràng buộc của bài toán; f được gọi là ánh xạ giá của bài toán.
Nếu f là gradient của một ánh xạ lồi g thì VIP(D, f) tương đương với
bài toán tìm cực tiểu của g trên D. Tuy nhiên, không phải bài toán bất
đẳng thức biến phân nào cũng tương đương với một bài toán quy hoạch
lồi.
Phương pháp chiếu (tham khảo [15], Chương 12) là một lớp phương

với x ∈ D nào đó, thì VIP(D, f) có ít nhất một nghiệm.
1.1.2 Định nghĩa. ([15], Định nghĩa 2.3.1) Ánh xạ f : D → R
n
được
gọi là
13
(i) đơn điệu trên D nếu
f(x) − f(y), x − y ≥ 0, ∀x, y ∈ D;
(ii) đơn điệu ngặt trên D nếu
f(x) − f(y), x − y > 0, ∀x, y ∈ D và x = y;
(iii) đơn điệu mạnh trên D nếu tồn tại hằng số α > 0 sao cho
f(x) − f(y), x − y ≥ α||x − y||
2
, ∀x, y ∈ D;
(iv) liên tục Lipschitz trên D nếu tồn tại hằng số L > 0 sao cho
||f(x) − f(y)|| ≤ L||x − y||, ∀x, y ∈ D;
(v) giả đơn điệu trên D tương ứng với S nếu S = ∅ và
∀x ∈ S : f (y), y − x ≥ 0, ∀y ∈ D.
Một thí dụ điển hình của ánh xạ đơn điệu (mạnh) là đạo hàm của một
hàm lồi (mạnh).
1.1.3 Định lí. ([15], Định lý 2.3.3)
(i) Nếu f đơn điệu ngặt trên D thì VIP(D, f) có nhiều nhất là một
nghiệm.
(ii) Nếu f đơn điệu mạnh trên D thì VIP(D, f) có nghiệm duy nhất.
1.2 Phép chiếu và mối quan hệ với bất đẳng thức
biến phân
1.2.1 Định nghĩa. Giả sử D là một tập con lồi đóng khác rỗng của R
n
.
Với mọi vector x ∈ R

D
(x) ≡ x − P
D
(x − ξf (x)).
1.2.3 Nhận xét. Nếu D là một tập con lồi đóng khác rỗng thì hình
chiếu của một điểm bất kỳ lên D luôn tồn tại và là duy nhất. Nếu K là
một hình hộp, hình cầu, hay một không gian con thì tính hình chiếu của
một điểm lên K rất dễ dàng.
A. Hình chiếu của một điểm lên một hình hộp
Giả sử rằng
K = {x = (x
1
, x
2
, ..., x
n
)
T
∈ R
n
: a
i
≤ x
i
≤ b
i
, i = 1, 2, ..., n},
a = (a
1
, a


a
i
, x
i
< a
i
,
x
i
, x
i
∈ [a
i
, b
i
],
b
i
, x
i
> b
i
.
(1.1)
15
B. Hình chiếu của một điểm lên một hình cầu
Giả sử
x = (x
1

− a
i
)
2
≤ R
2
}.
Ta cần tìm hình chiếu y = P
C
(x) của x lên C. Nếu x ∈ C, ta có y ≡ x.
Nếu x ∈ C, hình chiếu của x lên C là giao điểm của đường thẳng nối x
và tâm A của C, ký hiệu là ∆, với mặt cầu
S = {z ∈ R
n
:
n

i=1
(z
i
− a
i
)
2
= R
2
}.
Ta có
∆ = {z ∈ R
n

2
.
Do đó
t = R


n

i=1
(x
i
− a
i
)
2

1/2
.
Vì vậy y có tọa độ như sau
y
i
= a
i
+ (x
i
− a
i
)
R
(

k

j=1
y
j
η
j
∈ L,
trong đó y
j
là các hệ số thực sao cho w = x − y thỏa mãn
w, η
j
 = 0,
với mọi j = 1, 2, . . . , k (ta sẽ tìm y thỏa mãn điều kiện này sau). Khi
đó y là hình chiếu của x lên L. Thật vậy, vì w trực giao với mọi vector
trong cơ sở của L nên nó cũng trực giao với mọi vector của L. Do đó, với
z ∈ L,
||x − z||
2
= x − y + y − z, x − y + y − z
= x − y, x − y + y − z, y − z + 2w, y − z
= ||x − y||
2
+ ||y − z||
2
≥ ||x − y||
2
.
Vì vậy y là hình chiếu của x lên L. Bây giờ ta tìm vector y như thế. Với

i
.
Khi đó từ (1.2) ta thu được một hệ tuyến tính k phương trình k ẩn
Ay = b,
trong đó
A = (a
ij
),
và
b = (b
1
, b
2
, . . . , b
k
)
T
.
Hơn nữa theo định nghĩa, A là một ma trận xác định dương, nghĩa là
det(A) = 0.
Do đó hệ này có đúng một nghiệm. Vì
y =
k

j=1
y
j
η
j
,

toán chiếu được mô tả dưới đây.
Thuật toán 1. ([15], Mục 12.1.2)
Dữ liệu: x
(0)
∈ D và η > 0.
Bước 0: Đặt k = 0.
Bước 1: Nếu x
(k)
∈ S, nghĩa là x
(k)
= P
D
(x
k
− ηf(x
(k)
)), dừng và trả
ra x
(k)
là một nghiệm.
Bước 2: Tính
x
(k+1/2)
= P
D
(x
(k)
− ηf(x
(k)
)),

− (1 − η
2
L
2
)||x
(k+1/2)
− x
(k)
||
2
.
(ii) Nếu 0 < η < 1/L thì dãy {x
(k)
} sinh bởi Thuật toán 1 hội tụ về
một nghiệm của VIP(D, f).
19
1.4 Phương pháp hàm phạt
Phương pháp hàm phạt được trình bày sau đây được đề xuất bởi
L. D. Muu [38].
Cho D là một tập con lồi đóng khác rỗng của R
n
, K là một tập con
của R
n
chứa D. Ta sẽ xây dựng một hàm lồi khả vi P : K → R thỏa
mãn
P (x) ≤ 0⇐⇒x ∈ D. (1.3)
Hàm P thỏa mãn (1.3) được gọi là hàm phạt của D. Một hàm P thỏa
mãn (1.3) còn được gọi là hàm thưởng-phạt, hay còn gọi là hàm phạt
kiểu Lagrange. Khác với hàm phạt điểm ngoài thông thường đòi hỏi phải

(x) := [max{0, g
i
(x)}]
2
= (α ◦ g
i
)(x),
trong đó
α(x) := [max{0, x}]
2
=



x
2
, x > 0,
0, x ≤ 0.
20
Dễ thấy với x > 0 ta có α

(x) = 2x và với x < 0 ta có α

(x) = 0. Tại
x = 0, đạo hàm bên phải của α bằng 0
lim
∆x→0
+
α(0 + ∆x) − α(0)
∆x

(t)
là
đơn điệu với mọi t > 0 nếu f là đơn điệu. Ta xét bài toán bất đẳng thức
biến phân ứng với tham số phạt t, ký hiệu
VIP(K, f
(t)
) : Tìm x
(t)
∈ K sao cho f
(t)
(x
(t)
), x−x
(t)
 ≥ 0 , ∀x ∈ K,
trong đó K ⊃ D là một tập lồi đóng bao D sao cho hình chiếu của một
điểm bất kỳ của R
n
lên K có thể được xác định dễ dàng, thậm chí là bởi
một công thức hiển (ví dụ K là một hình hộp, một hình cầu hay một
không gian con).
Kí hiệu S(t) là tập nghiệm của VIP(K, f
(t)
) và đặt
t
∗
= sup{t ≥ 0 : S(t) ⊂ D}.
1.4.1 Bổ đề ([38]). Giả sử f là ánh xạ đơn điệu trên K, P là một
hàm phạt lồi, khả vi, thỏa mãn (1.3) và bị chặn dưới. Khi đó
(i) S(t) ∩ D = ∅ nếu t > t