ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
TỐNG THỊ LIỄU
ĐỐI NGẪU CỦA BÀI TOÁN TỐI
ƯU LỒI
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
Hướng dẫn khoa học: PGS.TS Đỗ Văn Lưu
Thái Nguyên: 08/2013
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
MỤC LỤC
Mục lục
Mở đầu 2
Chương 1. LIÊN HỢP CỦA HÀM LỒI 4
1.1. Chính quy hóa Gamma 4
1.2. Hàm liên hợp 7
1.3. Định lý H¨ormander 12
1.4. Bổ đề Farkas suy rộng 14
Chương 2. ĐỐI NGẪU CỦA CÁC BÀI TOÁN TỐI ƯU
LỒI 19
2.1. Đối ngẫu dưới ngôn ngữ hàm Lagrange 19
2.2. Đối ngẫu Lagrange và các hàm khả vi Gâteaux 26
2.3. Đối ngẫu của bài toán biên 29
2.4. Đối ngẫu dưới ngôn ngữ hàm liên hợp 35
Kết luận 46
Tài liệu tham khảo 47
1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
MỞ ĐẦU
Lý thuyết đối ngẫu là một bộ phận quan trọng của lý thuyết tối ưu

H¨ormander mô tả một tập trong E
∗
qua các phiếm hàm dưới tuyến tính,
nửa liên tục dưới trên E, định lý về song cực, bổ đề Farkas suy rộng.
Chương 2. Đối ngẫu của các bài toán tối ưu lồi
Trình bày lý thuyết đối ngẫu cho bài toán tối ưu lồi bao gồm định lý
đối ngẫu Lagrange cho bài toán lồi với hữu hạn ràng buộc tập, định lý
đối ngẫu tổng quát, các định lý đối ngẫu cho bài toán với các hàm khả
vi Gâteaux, đối ngẫu của bài toán giá trị biên, đối ngẫu dưới ngôn ngữ
hàm giá trị và hàm nhiễu.
Nhân dịp này em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS
Đỗ Văn Lưu, người đã tận tình hướng dẫn, giúp đỡ em hoàn thành bản
luận văn này. Em xin chân thành cảm ơn Ban chủ nhiệm khoa toán,
phòng đào tạo sau đại học trường Đại học Khoa học - Đại học Thái
Nguyên cùng các thầy cô giáo đã tham gia giảng dạy khóa học. Xin
chân thành cảm ơn gia đình, bạn bè đồng nghiệp và các thành viên
trong lớp cao học toán K5 đã luôn quan tâm, động viên, giúp đỡ tôi
trong suốt thời gian học tập và quá trình làm luận văn.
Thái Nguyên, tháng 6 năm 2013
Tác giả
Tống thị Liễu
3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Chương 1
LIÊN HỢP CỦA HÀM LỒI
Chương 1 trình bày một số kết quả về liên hợp của hàm lồi. Kết quả chỉ
ra rằng một hàm lồi nửa liên tục dưới là bao đóng trên (upper envelope)
của các hàm afine liên tục. Khái niệm hàm liên hợp được trình bày cùng
với các định lý về song liên hợp, định lý về liên hợp của tổng hai hàm
qua tổng chập infimal của hai hàm liên hợp. Chương này cũng trình bày

định nghĩa như sau (xem [1]):
domf = {x ∈ M|f(x) < +∞} .
Hàm f được gọi là chính thường (proper) nếu domf = ∅ và f(x) >
−∞(∀x ∈ M).
Mệnh đề 1.1.1
Nếu f : E → R là hàm chính thường, thì các phát biểu dưới đây là
tương đương:
(a) f = f
Γ
;
(b) f là liên tục nửa dưới và lồi .
Chứng minh
(a) ⇒ (b) : Hiển nhiên.
(b) ⇒ (a): Rõ ràng là f
Γ
≤ f. Bây giời giả sử rằng với x
0
nào đó thuộc E
và một k nào đó thuộc R, ta có f
Γ
(x
0
) < k < f(x
0
). Ta chỉ ra rằng tồn
tại a ∈ A(f) thỏa mãn k < a(x
0
) thì dẫn đến một mâu thuẫn f
Γ
(x

c ≤
α − x
∗
, x
t

, ∀t

> max {0, t} .
5
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Do đó, cho t

→ +∞, ta nhận được c ≤ 0. Bây giờ chúng ta phân biệt
hai trường hợp.
Trường hợp 1. Giả sử rằngf(x
0
) < +∞. Khi đó, (1.1) với t := f(x
0
)
và (1.2) kéo theo
x
∗
, x
0
 + cf(x
0
) ≤ α < x
∗
, x

) > k.
Trường hợp 2: Giả sử rằng f(x
0
) = +∞. Nếu c < 0, thì ta định nghĩa
hàm số a như trong trường hợp 1. Bây giờ giả sử rằng c = 0. Bởi vì f là
hàm chính thường, tồn tại y
0
∈ domf. Theo trường hợp 1, với y
0
thay
cho x
0
, tồn tại a
0
∈ A(f). Định nghĩa a : E → R như sau
a(x) := a
0
(x) + ρ(x
∗
, x − α) trong đó ρ :=
|k − a
0
(x
0
)|
x
∗
, x
0
− α

)| + x
∗
, x
0
 − α > k.
6
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Chứng minh được hoàn thành. 
1.2 Hàm liên hợp
Khái niệm về hàm liên hợp có nguồn gốc từ phép biến đổi của tích
các phép biến đổi Legendre trong phép tính biến phân sẽ rất quan trọng
cho lý thuyết đối ngẫu trong tối ưu lồi.
Định nghĩa 1.2.1
Cho f : E → R. Hàm số f
∗
: E
∗
→ R định nghĩa bởi
f
∗
(x
∗
) := sup
x∈E
(x
∗
, x − f(x)), x
∗
∈ E
∗

và khả vi. Do đó, ϕ có một cực đại duy nhất x
0
thỏa mãn ϕ

(x
0
) =
0, tức là x
∗
− sgn(x
0
)|x
0
|
p−1
= 0. Ta suy ra
f
∗
(x
∗
) = ϕ(x
0
) =
|x
∗
|
q
q
, trong đó
1

∗
(x
∗
) > −∞ với mọi x
∗
∈ E
∗
.
(c) Nếu f là hàm chính thường, lồi và nửa liên tục dưới, thì f
∗
là hàm
chính thường, lồi và nửa liên tục dưới.
Chứng minh
(a) Dễ dàng thấy rằng f
∗
lồi. Để chứng minh khẳng định thứ hai, chú ý
rằng với mỗi x ∈ E, các hàm số ϕ
x
(x
∗
) := x
∗
, x − f(x), x
∗
∈ E
∗
liên
tục, và như vậy f
∗
= sup

→ R, hàm liên hợp g
∗
: E → R được định nghĩa tương tự
bởi
g
∗
(x) := sup
x
∗
∈E
∗
(x
∗
, x − g(x
∗
)), x ∈ E.
Bây giờ giả sử f : E → R. Với g := f
∗
, ta có hàm song liên hợp
f
∗∗
: E → R của f:
f
∗∗
(x) = sup
x
∗
∈E
∗
(x

và c ∈ R, ta
có
x
∗
, x + c ≤ f(x), ∀x ∈ E ⇔ f
∗
(x
∗
) = sup
x∈E
(x
∗
, x − f(x)) ≤ −c.
Như vậy,
f
Γ
(x) = sup {x
∗
, x + c|x
∗
∈ E, c ∈ R, c ≤ −f
∗
(x
∗
)} (1.4)
Nếu f
∗
(x
∗
) > −∞, ∀x

f
Γ
(x) = +∞ = f
∗∗
(x), ∀x ∈ E.
(b) Được suy ra từ (a) và mệnh đề 1.1.1. 
Ví dụ 1.2.2
Cho hàm chỉ δ
A
của một tập hợp con khác rỗng A của E. Ta có
δ
∗
A
(x
∗
) = σ
A
(x
∗
), ∀x
∗
∈ E
∗
,
Trong đó δ
A
: E
∗
→
R là hàm tựa của A. Nếu E là không gian véctơ

∗
[σ(E
∗
, E)]). Xác định f
∗
:
(I) Cho x
∗
∈ E
∗
, ||x
∗
|| ≤ 1. Khi đó, x
∗
, x ≤ ||x
∗
||||x|| ≤ ||x||, ∀x ∈
E và x
∗
, 0 = 0 = ||0||. Do đó
f
∗
(x
∗
) = sup
x∈E
(x
∗
, x − ||x||) = 0
(II) Cho x

∗
. Vì vậy,
||x|| = f(x) = f
∗∗
(x) = δ
∗
B
E
∗
(x) = sup
||x
∗
||≤1
x
∗
, x , ∀x ∈ E.
Ở đây dấu bằng thứ hai suy ra từ định lý 1.2.1 và dấu bằng cuối cùng
suy ra bằng cách áp dụng ví dụ 1.2.2 cho E
∗
thay cho E. Như một hệ
quả của định lý Hahn-Banach cận trên đúng đạt được, nghĩa là
||x|| = max
||x
∗
||≤1
x
∗
, x , ∀x ∈ E.
Định nghĩa 1.2.2
Cho f

: E → R là các hàm chính thường.
(a) Ta có
f
∗
0
+ f
∗
1
= (f
0
⊕ f
1
)
∗
và (f
0
+ f
1
)
∗
≤ f
∗
0
⊕ f
∗
1
.
10
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(b) Giả thiết thêm rằng f

)
∗
tồn tại x
∗
i
∈ domf
∗
i
, với i = 0, 1 sao
cho
x
∗
= x
∗
0
+ x
∗
1
và (f
0
+ f
1
)
∗
(x
∗
) = f
∗
0
(x

A
(x) := max
||x
∗
||≤1
(x
∗
, x − sup
y∈E
x
∗
, y), ∀x ∈ E.
Chứngminh
Đặt f
0
(x) := ||x|| và f
1
(x) := δ
A
(x), ta có
(f
0
⊕ f
1
)(x) = inf
y∈E
(||x − y|| + δ
A
(y)) = d
A

(x
∗
, x − (δ
B
(x
∗
) + sup
y∈A
x
∗
, y)).
= sup
x
∗
∈B
(x
∗
, x − sup
y∈A
x
∗
, y).
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Bởi vì với tôpô σ(E
∗
, E), B là compact (Định lý Alaoglu) và các hàm
x
∗
→ x

∗
∈ E
∗
| x
∗
, x ≤ σ
M
(x), ∀x ∈ E} . (1.6)
(b) Cho p : E → R là hàm chính thường, dưới tuyến tính, và nửa liên
tục dưới. Khi đó, tập
M
p
:= {x
∗
∈ E
∗
| x
∗
, x ≤ p(x), ∀x ∈ E} ,
khác rỗng, lồi, đóng và ta có σ
M
p
= p.
(c) Nếu M
1
và M
2
là các tập con khác rỗng, lồi và đóng của E
∗
, thì

12
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
σ
∗
M
(x
∗
) = sup
x∈E
(x
∗
, x − σ
M
(x)) = δ
M
p
(x
∗
), ∀x
∗
∈ E
∗
,
ở đây p := σ
M
. Vì vậy δ
M
= δ
M
p

đóng : ∀x ∈ E đặt ϕ
x
(x
∗
) := x
∗
, x , x
∗
∈ E
∗
. Khi đó, ϕ
x
liên
tục. Do đó, tập hợp
M
x
:= {x
∗
∈ E
∗
| x
∗
, x ≤ p(x)} = ϕ
−1
x
(−∞, p(x)]
đóng, và như vậy là M
p
=


.
(c) Suy luận ” ⇒ ” đúng theo định nghĩa, và suy luận ” ⇐ ” là một hệ
quả của (1.6) 
Nếu A ⊆ E là khác rỗng, thì nón cực của tập A:
A
◦
:= {x
∗
∈ E
∗
| x
∗
, x ≤ 0, ∀x ∈ A}
13
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
là một nón lồi. Hơn nữa, nón song cực của A là
A
◦◦
:= {x ∈ E| x
∗
, x ≤ 0, ∀x
∗
∈ A
◦
} .
Chúng ta ký hiệu ccA là giao của tất cả các nón lồi đóng chứa A.
Bổ đề 1.3.1[5]
(a) Nếu A ⊆ E khác rỗng, thì (ccA)
◦
= A

C
. Do đó, C = C
◦◦
, và bổ đề
1.3.1(a) cho thấy rằng C
◦◦
= A
◦◦

1.4 Bổ đề Farkas suy rộng
Trong phần này ta đặc trưng nghiệm của hệ các phương trình và bất
phương trình. Ta đưa vào các giả thiết sau đây:
(H) (E, E
∗
) và (F, F
∗
) là các cặp đối ngẫu các không gian lồi địa phương.
P ⊆ E và Q ⊆ F là các nón lồi, đóng.
T : E → F là ánh xạ tuyến tính liên tục.
Nhắc lại rằng các ánh xạ liên hợp T
∗
: F
∗
→ E
∗
của T được xác định
14
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
bởi
T

◦
))
◦
⇔ y

, x + z
∗
, T x ≤ 0, ∀(y

, z
∗
) ∈ P
◦
× Q
◦
⇔ (x, T x) ∈ (P
◦
× Q
◦
)
◦
.
Bởi vì (P
◦
× Q
◦
)
◦
= P
◦◦

∗
∈ Q
◦
: x
∗
− T
∗
z
∗
∈ P
◦
.
(b) ∀x ∈ P : Tx ∈ Q ⇒ x
∗
, x ≤ 0.
Kết quả thường được phát biểu dưới ngôn ngữ phủ định của (b) là:
(b) ∃x ∈ P : Tx ∈ Q và x
∗
, x > 0.
15
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Nhận xét 1.4.1
Mệnh đề 1.4.1 nói rằng (a) hoặc (b) đúng. Trong công thức này kết
quả được gọi là định lý thay thế.
Đặc biệt, nếu P = E, như vậy P
◦
= {0}, thì mệnh đề 1.4.1 cho ta
điều kiện cần và đủ để phương trình toán tử tuyến tính T
∗
z

, E) trong E
∗
được gọi là tôpô yếu *. Ta chỉ ra
rằng với bất kỳ ρ > 0, tập hợp
K := (P
◦
+ T
∗
(Q
◦
)) ∩ B
E
∗
(0, ρ)
là đóng trong B
E
∗
(0, ρ). Sau đó khẳng định sẽ được đưa ra bởi định lý
Krein - Smulian (Định lý 1.6.8[5]). Giả sử (z
∗
α
) là một lưới (dãy suy rộng)
trong K hội tụ tới z
∗
nào đó thuộc B
E
∗
(0, ρ). Khi đó, tồn tại các lưới
(x
∗

y

α
, T x

−

y

α
, y

≥

T
∗
y

α
, x

= z
∗
α
, x − x
∗
α
, x ≥ z
∗
α


∈ Q
◦
. Bởi vì
x
∗
α

= z
∗
α

− T
∗
y

α

và z
∗
α

→ z
∗
,
ta suy ra (x
∗
α

) hội tụ tới z

ρ(−y) ∈ V với ρ > 0 nào đó, và vì vậy, z := T x
0
− ρy ∈ Q. Từ đó ta suy
ra
y = T(
1
ρ
x
0
) −
1
ρ
z ∈ T(P ) − Q.

Xét trường hợp:
E = P = R
m
, F = R
n
, Q = −R
n
+
.
Hơn nữa, giả sử A là biểu diễn ma trận của T : R
m
→ R
n
theo cơ sở
thông thường. Khi đó, T
∗

z
∗
= x
∗
;
(b) ∀x ∈ R
m
: Ax ∈ −R
n
+
⇒ x
∗
, x ≤ 0 .
18
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Chương 2
ĐỐI NGẪU CỦA CÁC BÀI TOÁN TỐI ƯU LỒI
Chương 2 trình bày lý thuyết đối ngẫu của bài toán tối ưu lồi bao
gồm định lý đối ngẫu Lagrange cho bài toán có ràng buộc bất đẳng thức
và ràng buộc tập, định lý đối ngẫu tổng quát, các định lý đối ngẫu cho
bài toán với hàm khả vi Gâteaux, đối ngẫu của bài toán giá trị biên, đối
ngẫu dưới ngôn ngữ hàm giá trị và hàm nhiễu. Các kết quả trình bày
trong chương này được tham khảo trong [5].
2.1 Đối ngẫu dưới ngôn ngữ hàm Lagrange
Giả sử rằng
A ⊆ E là một tập không rỗng lồi,
f, g
1
, , : A → R là các hàm lồi,
M := {x ∈ A | g

q∈R
m
+
L(x, q) =



f(x), nếu x ∈ M,
+∞, nếu x ∈ A\M.
19
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Vì vậy, chúng ta nhận được
α := inf
x∈A
sup
q∈R
m
+
L(x, q). (2.3)
Bây giờ ta xét
β := sup
q∈R
m
+
inf
x∈A
L(x, q). (2.4)
Bài toán cực tiểu gốc được mô tả bởi (2.1) và do đó bởi (2.3), được
gọi là bài toán xuất phát. Bài toán mô tả bởi (2.4) được gọi là bài toán
đối ngẫu. Chúng ta nói rằng

0
∈ A : g
i
(x
0
) < 0, với i=1, ,m. (2.5)
Định lý 2.1.1 (Đối ngẫu Lagrange)
Giả sử rằng E là không gian phản xạ, tập hợp con A khác rỗng,
đóng và lồi và các hàm f, g
1
, g
2
, , g
m
là nửa liên tục dưới và lồi. Giả
thiết thêm rằng điều kiện Slater (2.5) thỏa mãn. Khi đó,
(i) α = β và bài toán đối ngẫu (2.4) có một nghiệm q ∈ R
m
+
.
(ii) Với
x ∈ M, các phát biểu sau đây là tương đương:
(a) x là một nghiệm của bài toán xuất phát (2.3).
20
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(b) Hàm Lagrange L có một điểm yên ngựa (x, q) trên A × R
m
+
.
(iii) Nếu (b) đúng, thì q là một nghiệm của bài toán đối ngẫu

Định lý 2.1.2 ( Định lý tính đối ngẫu tổng quát )
Giả sử E, F là các không gian Banach phản xạ, và A ⊆ E và B ⊆ F
là khác rỗng, đóng và lồi, và L : A × B → R thỏa mãn
x → L(x, q) là nửa liên tục dưới và lồi trên A với mỗi q ∈ B,
q → −L(x, q) là nửa liên tục dưới và lồi trên B với mỗi x ∈ A.
Khi đó,
(i) Ta có α ≥ β (tính đối ngẫu yếu).
(ii) Với (x, q) ∈ A × B, các mệnh đề sau đây là tương đương:
21
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
(a) x là một nghiệm của (2.6), q là một nghiệm của (2.7) và có
α = β (tính đối ngẫu mạnh).
(b) (x, q) là một điểm yên ngựa của L trên A × B
(iii) Giả sử thêm A bị chặn hoặc là L(x, q
0
) → +∞ khi ||x|| → +∞,
x ∈ A với q
0
nào đó thuộc B. Giả sử thêm rằng α < +∞. Khi đó,
bài toán xuất phát (2.6) có một nghiệm x ∈ A và α = β.
(iv) Giả thiết thêm: B bị chặn hoặc là −L(x
0
, q) → +∞ khi ||q|| →
+ ∞, q ∈ B với x
0
nào đó thuộc A. Giả sử thêm rằng β > −∞.
Khi đó bài toán đối ngẫu (2.7) có một nghiệm q ∈ B và α = β.
Chứng minh
Chứng minh bao gồm hai bước chính. Bước 1: kết quả được kiểm
chứng vói giả thiết thêm rằng A và B bị chặn. Trong trường hợp này,

q
i
g
i
(x
0
) → −∞, khi ||q|| → +∞, ||q|| ∈ R
m
+

Từ định lý 2.1.2, chúng ta có thể thiết lập một nguyên lí đối ngẫu
tổng quát
22
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
• Nguyên lí đối ngẫu tổng quát
Cho bài toán cực tiểu f(x) → min, x ∈ M, tìm các tập hợp A, B và một
hàm L : A × B → R sao cho
inf
x∈M
f(x) = inf
x∈A
sup
q∈B
L(x, q),
và xét bài toán đối ngẫu sau
sup
q∈B
inf
x∈A
L(x, q).

23
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Ta có
β = sup
q∈B
(−f
∗
(−T
∗
q) − h
∗
(q) − q, a). (2.12)
Chú ý rằng h
∗
là ký hiệu liên hợp của hàm h, còn T
∗
là liên hợp của
toán tử T .
Mệnh đề 2.1.1
Với giả thiết (A), bài toán đối ngẫu của (2.8) là (2.12). Do đó, tất cả
các phát biểu của định lý 2.1.2 đúng cho (2.8) và (2.12).
Chứng minh
(I) Từ định lý 2.2.4[5] ta có h = h
∗∗
, và do đó,
h(T x − a) = h
∗∗
(T x − a) = sup
q∈F
∗

∗
(−T
∗
, q) − h
∗
(q) − q, a .
Điều này chỉ ra rằng (2.11) trùng với (2.12). 
Ví dụ 2.1.1
Bây giờ chúng ta áp dụng mệnh đề 2.1.1 cho bài toán tối ưu tuyến
tính:
α := inf {c, x |x ∈ P
E
, T x − a ∈ P
F
} (2.13)
24
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn