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
Chuyên ngành: Toán giải tích
Mã số: 62 46 01 01
TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC
VINH - 2010
Công trình được hoàn thành tại Trường Đại học Vinh
Người hướng dẫn khoa học: GS. TSKH. Lê Dũng Mưu
PGS. TS. Trần Văn Ân
Phản biện 1: PGS. TS. Nguyễn Hữu Điển
Phản biện 2: PGS. TS. Phan Nhật Tĩnh
Phản biện 3: PGS. TS. Bùi Thế Tâm
Luận án sẽ được bảo vệ tại Hội đồng chấm luận án cấp trường họp tại
Trường Đại học Vinh vào hồi . . . . giờ . . . . . . ngày . . . . . . tháng . . . . . . năm
. . . . . .
Có thể tìm hiểu luận án tại:
- Thư viện Quốc gia
- Trung tâm thông tin thư viện Nguyễn Thúc Hào - Trường Đại học
Vinh
1
MỞ ĐẦU
1. Lí do chọn đề tài
1.1. Lý thuyết bất đẳng thức biến phân ra đời vào những năm 60 (Stam-
pacchia (1964), Hartman và Stampacchia (1966), Lions và Stampacchia
(1967)), là một công cụ mạnh và thống nhất để nghiên cứu các bài toán
cân bằng. Cho đến nay, những bài toán được quy về các bài toán bất
đẳng thức biến phân gồm có: bài toán cân bằng mạng giao thông (Traf-

Để 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 (Goh và Yang (1999, 2000)). 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 vô hướng. 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 (1881) và Pareto (1906). 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 điểm đó, nghĩa là không tồn tại một điểm y = x sao cho f
i
(y) ≤ f
i
(x)
với mọi i = 1, . . . , k, và f
j
(y) < f
j
(x) với một chỉ số j nào đó. Điểm x
được gọi là nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu nếu không
có một điểm nào khác tốt hơn điểm đó xét trên tất cả các mục tiêu, nghĩa

(1) Kết hợp phương pháp hàm phạt và phương pháp chiếu để có một
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ỳ.
4
(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ả mà Liu và Feng (2009)
đưa ra. Ngoài ra, chúng tôi còn chỉ ra điều kiện đủ để các bài toán phạt
đều có nghiệm Pareto yếu, đồng thời dãy các nghiệm đó có ít nhất một
điểm giới hạn và đó chính là một nghiệm của bài toán ban đầu.
2. Mục đích nghiên cứu
Luận án nhằm mục đích nghiên cứu áp dụng phương pháp hàm phạt
cho bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân
vector yếu và bài toán tối ưu đa mục tiêu, trong đó bài toán cuối cùng
trong một số trường hợp đặc biệt là tương đương với bài toán bất đẳng

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. 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
6
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 mỗi bài toán phạt này bằng phương pháp chiếu. Vì các
bài toán phạt có miền ràng buộc đơn giản, việc tính hình chiếu của một
điểm bất kỳ lên miền ràng buộc đó trở nên dễ dàng hơn. Do đó phương
pháp chiếu có thể giải các bài toán phạt một cách hiệu quả. Chúng tôi
minh họa Thuật toán 3 trong ba ví dụ 1.6.1, 1.6.2 và 1.6.3, giải số bài toán
bất đẳng thức biến phân trong trường hợp hai chiều và nhiều chiều, trong
đó trường hợp nhiều chiều lấy theo mô hình Nash (Konnov (2001)).
Trong Chương 2, chúng tôi nghiên cứu phương pháp hàm phạt áp dụng
cho bài toán bất đẳng thức biến phân vector yếu WVVIP(D, F ). Kết quả
cơ bản 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 mà chúng tôi sử dụng trong chương này là một định lý đưa ra bởi

(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.
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 (Lee và Kim (1998)) 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 (Chen
và Yang (1990)), 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 MOP(K, f
(t)
) khi t tiến ra vô cùng là một nghiệm Pareto yếu của
bài toán ban đầu MOP(D, f ). Dùng kỹ thuật bao nghiệm Pareto yếu của
các bài toán phạt bởi một hình cầu, trong Định lý 3.3.3 chúng tôi đưa ra
một điều kiện đủ để
(1) các bài toán phạt luôn có ít nhất một nghiệm;
(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.
8
Kết quả chính của luận án được công bố trong các bài báo liệt kê trong

bất đẳng thức biến phân, trong đó các khái niệm về ánh đơn điệu và ánh
xạ thỏa mãn điều kiện bức đóng vai trò quan trọng trong các điều kiện đủ
để bài toán có nghiệm.
1.2. Phép chiếu và mối quan hệ với bất đẳng thức biến phân
Mục này trình bày mối quan hệ giữa tập nghiệm S của bài toán bất đẳng
thức biến phân và phép chiếu Euclide. Chú ý rằng 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.
10
1.3. Phương pháp chiếu
Mục này trình bày phương pháp chiếu hai lần cho bài toán bất đẳng thức
biến phân (tham khảo Facchinei và Pang (2003), Mục 12.1.2).
1.4. Phương pháp hàm phạt
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.
Bây giờ ta xây dựng bài toán phạt sử dụng hàm phạt vừa định nghĩa
ở trên. Với mỗi t > 0, đặt f
(t)
= tf + ∇P . Dễ thấy rằng f
(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

ban đầu VIP(D, f) khi t
k
→ t
∗
. Đây là ý tưởng cơ bản của thuật toán mô
tả dưới đây.
11
Thuật toán 3
Xây dựng một tập lồi đóng K ⊃ D có hình dạng đặc biệt (chẳng hạn, hình
hộp, hình cầu, hoặc không gian con) và một hàm phạt lồi khả vi P sao cho
P bị chặn dưới.
Lấy một số dương tùy ý t
0
> 0. Chọn ε
k
> 0, sao cho ε
k
→ 0 khi k → ∞.
Đặt a = 0, b = ∞ và chuyển sang Bước k với k = 0.
Bước k (k = 0, 1, . . .):
• Bước k
0
: Chọn các hằng số λ > 0, η ∈ (0; 1/L
t
k
), trong đó L
t
k
là
hằng số Lipschitz của f

(k)
∈ D, đặt a := t
k
và
t
k+1
:=

(a + b)/2, b < ∞,
2a, b = ∞.
Chuyển sang Bước k với k := k + 1.
a2) Nếu x
(k)
/∈ D, đặt b := t
k
và t
k
:= (a + b)/2. Đặt k := k + 1
và quay lại Bước k.
b) Nếu ||y
(j)
− P
K
(y
(j)
− λf
(t
k
)
(y

k
)
(y
(j+1/2)
)).
Gán j := j + 1 và quay lại Bước k
1
.
Trên đây P
K
(x) là hình chiếu Euclide của x lên K. Khi K có hình
dạng đặc biệt, ta có thể tính P
K
(x) dễ dàng nhờ vào một công thức hiển.
12
1.5.1 Định lí. Giả sử f là một ánh xạ đơn điệu trên miền lồi đóng K ⊃ D,
P là một hàm phạt lồi khả vi của D. Hơn nữa giả sử P bị chặn dưới trên
K, f và ∇P liên tục Lipschitz trên K. Gọi {x
(k)
} là dãy sinh bởi Thuật
toán 3. Khi đó, một điểm giới hạn bất kỳ của {x
(k)
} là nghiệm của bài
toán ban đầu VIP(D, f ).
1.6. Ví dụ
Chúng tôi đã cài đặt Thuật toán 3 dùng ngôn ngữ C để giải số các ví dụ
dưới đây và phân tích kết quả chạy chương trình trong luận án. Các kết
quả số thu được phù hợp với các kết quả nêu trong lý thuyết.
1.6.1 Ví dụ. Xét
D = {x ∈ R

x
i
−
e
5
+ n − 1
n
2
.
Chọn hàm P (x) ≡ g(x) trên R
n
. Khi đó P là một hàm phạt của D. Ánh
xạ f được lấy theo mô hình Nash (Konnov (2001)).
f(x) = H(x) − p(σ
x
)e − p

(σ
x
)x,
trong đó
e = (1, . . . , 1)
T
∈ R
n
,
σ
x
= x, e =


trong đó γ lấy ngẫu nhiên trong khoảng [0, 15].
Ánh xạ f , hàm phạt P , các miền D và K lấy như trên thỏa mãn các
giả thiết của Định lý 1.5.1. Do đó, dãy sinh bởi Thuật toán 3 có tính chất
bất kỳ điểm giới hạn nào của dãy đó đều là một nghiệm của bài toán ban
đầu.
Ta lấy
D = {x = (x
1
, x
2
)
T
∈ R
2
: g
1
(x) ≤ 0, g
2
(x) ≤ 0},
trong đó g
1
(x) = x
2
− x
1
− 1, g
2
(x) = −x
2
+ x

− 1}]
2
+ [max{0, −x
2
+ x
2
1
− 1}]
2
.
Có thể bao D bởi hình hộp
K = {x = (x
1
, x
2
) ∈ R
2
: −1 ≤ x
1
≤ 2, −1 ≤ x
2
≤ 3}.
Khi đó các giả thiết của Định lý 1.5.1 đều được thỏa mãn.
1.6.3 Ví dụ. Lấy
f(x) =

x
1
+ x
2

Với x = (x
1
, . . . , x
k
)
T
∈ R
k
và y = (y
1
, . . . , y
k
)
T
∈ R
k
, ta dùng các ký
hiệu sau đây
x < y⇐⇒x
i
< y
i
, ∀i = 1, . . . , p,
x < y⇐⇒∃i : x
i
≥ y
i
.
Giả sử D là một tập con khác rỗng của R
k

(2.1)
Ta luôn chọn P sao cho P không những là hàm lồi mà còn khả vi. Đặt
Q
i
:= ∇P và Q : R
k
→ R
r×k
với các hàm thành phần Q
i
: R
k
→ R
k
,
i = 1, . . . , r. Cố định một tập K ⊃ D. Với t > 0 ta xét bài toán phạt sau
đây
WVVIP(K, F
(t)
) : Tìm x
(t)
∈ K sao cho (F
(t)
(x
(t)
))(y − x
(t)
) < 0,
với mọi y ∈ K,
trong đó F

2
.
2.2.4 Định nghĩa. Ánh xạ F : R
k
→ R
r×k
được gọi là thỏa mãn điều
kiện D-bức trên K nếu tồn tại s ∈ R
r
+
và a ∈ D sao cho
s
T
F (y), y − a → +∞ khi y → +∞, y ∈ K.
Hiển nhiên khi r = 1 thì hai định nghĩa trên là như nhau vì ta có thể
lấy s = 1. Bổ đề sau đây chỉ ra một điều kiện đủ để cả bài toán ban đầu
và bài toán phạt có nghiệm.
17
2.2.5 Bổ đề. Giả sử D = ∅ là một tập con lồi đóng của R
k
và F : R
k
→
R
r×k
là một ánh xạ liên tục, đơn điệu và thỏa mãn điều kiện D-bức trên
K. Khi đó WVVIP(D, F ) có nghiệm. Hơn nữa, với mọi t > 0, bài toán
phạt WVVIP(K, F
(t)
) cũng có nghiệm.

− 1

.
Khi đó các miền D, K = R
2
và ánh xạ F định nghĩa như trên thỏa
mãn tất cả các giả thiết của Bổ đề 2.2.5. Do đó, cả WVVIP(D, F ) và
WVVIP(K, F
(t)
) (t > 0) tương ứng với D, K và F này đều có nghiệm.
2.3. Các định lý hội tụ
Ký hiệu S và S(t) tương ứng là các tập nghiệm của WVVIP(D, F ) và
WVVIP(K, F
(t)
). Giả sử {t
n
}
n
là một dãy số thực dương tăng đơn điệu
tới +∞ khi n → +∞.
2.3.1 Bổ đề. Giả sử x
(n)
∈ S(t
n
) với mọi n ∈ N, {x
(n
m
)
}
m

kiện D-bức mạnh trên K nếu tất cả các ánh xạ thành phần của nó thỏa
mãn điều kiện D-bức trên K với cùng một vector a, nghĩa là tồn tại a ∈ D
18
sao cho với mọi j = 1, . . . , r,
F
j
(y), y − a → +∞, khi y → +∞, y ∈ K.
Dễ thấy với ánh xạ F và các miền D và K = R
2
định nghĩa trong Ví
dụ 2.2.6 thì F thỏa mãn điều kiện D-bức mạnh trên K. Hiển nhiên nếu F
thỏa mãn điều kiện D-bức mạnh trên K, thì F cũng thỏa mãn điều kiện
D-bức trên K. Tuy nhiên, điều ngược lại không phải lúc nào cũng đúng.
2.3.4 Định lí. Cho D = ∅ là một tập con lồi đóng của R
k
và F : R
k
→
R
r×k
là một ánh xạ liên tục, đơn điệu, đồng thời thỏa mãn điều kiện D-bức
mạnh trên K. Giả sử x
(n)
∈ S(t
n
) với mọi n ∈ N. Khi đó dãy {x
(n)
}
n
có

i
: R
k
→ R, i = 1, . . . , r là các ánh xạ xác định trên R
k
. D được
gọi là miền ràng buộc của MOP(D, f ). Nếu x ∈ D thì x được gọi là một
điểm chấp nhận được của MOP(D, f).
Vector x ∈ D được gọi là một nghiệm Pareto yếu của MOP(D, f) nếu
không tồn tại y ∈ D nào thỏa mãn f(y) < f(x). Do đó, x ∈ D là một
nghiệm Pareto yếu MOP(D, f) nếu và chỉ nếu với mọi y ∈ D luôn tồn tại
một chỉ số i sao cho
f
i
(y) ≥ f
i
(x).
3.1. Điều kiện đủ cho sự tồn tại nghiệm của bài toán tối ưu đa
mục tiêu
Mục này trình bày một vài điều kiện đủ để bài toán tối ưu đa mục tiêu có
nghiệm Pareto yếu.
20
3.2. Bài toán phạt
Cố định một tập K ⊃ D. Với t > 0 ta định nghĩa bài toán phạt như
sau
MOP(K, f
(t)
) : min
x∈K
f

i=1
s
i
∇f
i
(y), y − a = +∞,
3. K không bị chặn và tồn tại a ∈ D sao cho
lim
y→+∞, y∈K
∇f
i
(y), y − a > 0, i = 1, . . . , r.
Khi đó MOP(K, f
(t)
) có một nghiệm Pareto yếu.
3.3. Các định lý hội tụ
Ký hiệu S và S(t) tương ứng là các tập nghiệm của MOP(D, f) và
MOP(K, f
(t)
). Lấy {t
n
}
n
là một dãy các số thực dương tăng đơn điệu tới
+∞ khi n → +∞.
3.3.1 Bổ đề. Giả sử f liên tục và x
(n)
∈ S(t
n
) với mọi n ∈ N. Giả sử

1. K bị chặn,
2. K không bị chặn và tồn tại a ∈ D sao cho
lim
y→+∞, y∈K
∇f
i
(y), y − a > 0, i = 1, . . . , r.
Giả sử x
(n)
∈ S(t
n
) với mọi n ∈ N. Khi đó dãy

x
(n)

n
có ít nhất một
điểm giới hạn và mỗi điểm giới hạn của dãy này là một nghiệm Pareto yếu
của MOP(D, f ).
3.3.4 Ví dụ. Xét D và P như trong Ví dụ 1.6.2. Cho f(x) = (f
1
(x), f
2
(x)),
trong đó
f
1
(x) =
x

x
2
2
2
+ 1.
Lấy K = R
2
. Khi đó f, K và D thỏa các giả thiết của Định lý 3.3.3.
Do đó 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
n
)
), n = 1, 2, . . . sẽ có ít nhất một điểm giới hạn và mọi điểm
giới hạn của dãy đó là một nghiệm Pareto yếu của MOP(D, f ).
Kết luận Chương 3
Trong chương này, luận án đã giải quyết được những vấn đề sau.
- Nghiên cứu mối quan hệ giữa tập các nghiệm Pareto yếu của bài toán
tối ưu đa mục tiêu ban đầu và các tập nghiệm Pareto yếu của các bài toán
phạt tương ứng.
22
- Chứng minh được rằng nếu miền D là lồi đóng, ánh xạ f lồi, khả vi
và thỏa mãn tính chất bức, thì các bài toán phạt đều có nghiệm Pareto
yếu. Hơn nữa, bất kỳ dãy nghiệm Pareto yếu nào của các bài toán phạt
đều bị chặn, do đó có ít nhất một điểm giới hạn và đó chính là một nghiệm
Pareto yếu của bài toán tối ưu đa mục tiêu ban đầu. Định lý 3.3.2 chứng
minh rằng một điểm giới hạn bất kỳ của dãy các nghiệm Pareto yếu của
các bài toán phạt là một nghiệm Pareto yếu của bài toán ban đầu, chỉ
cần giả thiết về tính liên tục của hàm mục tiêu f. Ta không yêu cầu f lồi
hoặc khả vi trong định lý này. Tuy nhiên, Định lý 3.3.3 đòi hỏi những tính

đẳng thức biến phân.
2. Giảm nhẹ các giả thiết nêu trong các điều kiện đủ đã thiết lập trong
Chương 2 và Chương 3. Trước hết là nghiên cứu kỹ hơn các điều kiện đủ
này trong trường hợp hàm mục tiêu là không trơn và không đơn điệu.
3. Nghiên cứu mở rộng phương pháp hàm phạt cho các dạng tổng quát
hơn của bài toán bất đẳng thức biến phân vector.