Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
LỜI CẢM ƠN
Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2,
dưới sự hướng dẫn của thầy PGS.TS Nguyễn Năng Tâm. Sự giúp đỡ và
hướng dẫn tận tình song rất nghiêm túc của thầy trong suốt quá trình
thực hiện luận văn này đã giúp tác giả trưởng thành hơn rất nhiều trong
cách tiếp cận một vấn đề mới. Tác giả xin được bày tỏ lòng biết ơn, lòng
kính trọng sâu sắc nhất đối với thầy.
Tác giả xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư phạm
Hà Nội 2, Phòng Sau đại học, các thầy cô giáo trong nhà trường và các
thầy cô giáo dạy cao học chuyên ngành Toán Giải tích đã giúp đỡ, tạo
điều kiện cho tác giả trong suốt quá trình học tập.
Tác giả xin được gửi lời cảm ơn chân thành tới gia đình, người thân,
bạn bè đã luôn giúp đỡ, động viên và tạo điều kiện thuận lợi để tác giả
hoàn thành khóa học Thạc sĩ và hoàn thành luận văn này.
Hà Nội, ngày 12 tháng 10 năm 2013
Tác giả
Phan Thị Ánh Vân
1
Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
LỜI CAM ĐOAN
Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2
dưới sự hướng dẫn của PGS. TS. Nguyễn Năng Tâm.
Tôi xin cam đoan luận văn này là công trình nghiên cứu của riêng tôi.
Trong quá trình nghiên cứu và hoàn thành luận văn, tôi đã kế thừa
những thành quả khoa học của các nhà khoa học và đồng nghiệp với sự
trân trọng và biết ơn. Tôi xin cam đoan rằng các thông tin trích dẫn
trong luận văn đã được chỉ rõ nguồn gốc.
Hà Nội, ngày 12 tháng 10 năm 2013
Tác giả
Phan Thị Ánh Vân

x
T
véctơ chuyển vị của véctơ x
x chuẩn của véctơ x
x, y tích vô hướng của x và y
A
T
ma trận chuyển vị của ma trận A
R
m×n
tập các ma trận m × n
R
n×n
S
tập các ma trận n × n đối xứng
det A định thức của ma trận vuông A
E ma trận đơn vị trong R
n×n
f

(x; v) đạo hàm theo hướng của f tại x theo hướng v
Sol(P ) tập nghiệm của bài toán (P )
loc(P ) tập nghiệm địa phương của bài toán (P )
v(P ) giá trị tối ưu của bài toán (P )
QP quy hoạch toàn phương
QP (Q, A, c, b) quy hoạch toàn phương xác định bởi
các ma trận Q, A và các véctơ c, b
Sol(Q, A, c, b) tập nghiệm của bài toán quy hoạch toàn phương
ϕ(Q, A, c, b) hoặc ϕ(c, b) hàm giá trị tối ưu của bài toán
quy hoạch toàn phương

3. Nhiệm vụ nghiên cứu
1. Tính liên tục và tính nửa liên tục của hàm giá trị tối ưu.
2. Tính khả vi theo hướng của hàm giá trị tối ưu.
Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
4. Đối tượng và phạm vi nghiên cứu
Tính liên tục và tính khả vi của hàm giá trị tối ưu trong quy hoạch
toàn phương có tham số.
5. Phương pháp nghiên cứu
Nghiên cứu lý thuyết: Thu thập tài liệu, đọc và phân tích, tổng hợp
để được một nghiên cứu tổng quan về tính liên tục và tính khả vi của
hàm giá trị tối ưu trong quy hoạch toàn phương có tham số.
6. Dự kiến đóng góp mới của đề tài
Tổng quan về những tính chất của hàm giá trị tối ưu trong quy hoạch
toàn phương có tham số.
6
Chương 1
KIẾN THỨC CHUẨN BỊ
1.1 Không gian Euclide R
n
Cho X là một tập tùy ý và X = ∅.
Định nghĩa 1.1.1. Một metric trong X là một ánh xạ:
d : X × X → R
thỏa mãn các điều kiện sau:
i) d(x, y) ≥ 0, ∀x, y ∈ X;
d(x, y) = 0 ⇔ x = y;
ii) d(x, y) = d(y, x), ∀x, y ∈ X;
iii) d(x, y) ≤ d(x, z) + d(z, y), ∀x, y, z ∈ X.
Một tập khác trống X cùng với metric được xác định trên tập đó lập
thành một không gian metric, ký hiệu là (X, d). Số d(x, y) gọi là khoảng
cách giữa các điểm x và y.

(x
1
, . . . , x
n
)
T
+ (y
1
, . . . , y
n
)
T
:= (x
1
+ y
1
, . . . , x
n
+ y
n
)
T
λ(x
1
, . . . , x
n
)
T
:= (λx
1

Khi đó, ta có chuẩn Euclide của vectơ x:
 x :=

x, x =




n

i=1
|x
i
|
2
, ∀x ∈ R
n
thỏa mãn các tính chất:
(i)  x ≥ 0 ∀x ∈ R
n
,  x = 0 ↔ x = 0.
(ii)  λx = |λ|  x  ∀x, y ∈ R
n
;
(iii) |x, y| ≤ x  .  y  ∀x, y ∈ R
n
, trong đó dấu "=" xảy ra khi và
chỉ khi x, y phụ thuộc tuyến tính.
(iv) | x  −  y | ≤ x + y ≤ x  +  y  ∀x, y ∈ R
n

được gọi là tập đóng nếu U := R
n
\F là mở.
Tập V ⊂ R
n
được gọi là lân cận của x ∈ R
n
nếu tồn tại ε > 0 sao cho
B(x, ε) ⊂ V .
Định nghĩa 1.1.6. Cho x ∈ R
n
, A là tập con của R
n
.
(i) Nếu có lân cận V (x) của x mà V (x) ⊂ A thì x gọi là điểm trong của
A.
(ii) Nếu có lân cận V (x) của x mà V (x) ⊂ R
n
\A thì x gọi là điểm ngoài
của A.
(iii) Nếu mọi lân cận V (x) của x đều chứa điểm trong và điểm ngoài
của A khác x, thì x gọi là điểm biên của A.
Định nghĩa 1.1.7. Cho A là tập con bất kỳ trong R
n
. Ký hiệu {

i
(A)}
i∈I
là họ tất cả các tập mở trong A, {F

∈ R
n
khi k → ∞ nếu dãy số  x
k
− x
0
 hội tụ tới 0 ∈ R khi k → ∞.
Khi đó ta gọi x
0
là giới hạn của {x
k
} và ký hiệu x
k
→ x
0
.
lim
k→∞
x
k
= x
0
↔ lim
k→∞
 x
k
− x
0
= 0
Sự hội tụ trong R

} trong A đều có dãy con {x
k
m
} hội tụ đến một điểm x
∗
∈ A.
Định lí 1.1.3. Tập A trong R
n
compact khi và chỉ khi A đóng và bị
chặn.
1.2 Hàm nhiều biến
Định nghĩa 1.2.1. Cho X ⊂ R
n
. Ta gọi ánh xạ f : X → R là một hàm
n biến xác định trên X.
Nếu n ≥ 2 thì hàm n biến được gọi là hàm nhiều biến.
Ví dụ 1.2.1.
X = {x = (x
1
, x
2
)
T
∈ R
2
: x
1
+x
2
−5 = 0}, f (x) = 2

tuyến tính f và hằng số α sao cho:
g(x) = f (x) + α, ∀x ∈ R
n
.
Như vậy, hàm afin luôn có dạng g(x) = c, x +α. Cho f : X ⊂ R
n
→
R.
Định nghĩa 1.2.4. Hàm f được gọi là hàm bị chặn dưới (hay bị chặn
trên) trên X nếu tồn tại α sao cho f(x) ≥ α (hay f (x) ≤ α) với mọi
x ∈ X.
Hàm f gọi là bị chặn trên X nếu nó vừa bị chặn dưới, vừa bị chặn trên
trên X. Như vậy, f bị chặn trên X nếu tồn tại α > 0 sao cho |f(x)| ≤ α
với mọi x ∈ X.
10
Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
Định nghĩa 1.2.5. Hàm f được gọi là nửa liên tục dưới tại x
0
∈ X
nếu:
lim
x∈X
inf
x→x
0
f(x) ≥ f (x
0
).
Điều kiện này tương đương là: với mọi ε > 0, tồn tại một lân cận mở U
của x

∈ X.
Định nghĩa 1.2.7. Hàm f được gọi là liên tục tại x
0
nếu nó vừa nửa
liên tục trên, vừa nửa liên tục dưới tại x
0
, tức là: với mọi ε > 0, tồn tại
một lân cận mở U của x
0
sao cho |f (x) − f(x
0
)| ≤ ε, ∀x ∈ U ∩ X. Hàm
f liên tục trên X khi và chỉ khi f liên tục tại mọi x
0
∈ X.
Ví dụ 1.2.3. Cho X = {x = (x
1
, x
2
) ∈ R
2
: x
1
− x
2
≥ 1}.
Khi đó, f(x) = x
2
1
+ x

Theo định nghĩa của α, tồn tại dãy {x
k
} ∈ X sao cho:
lim
k→∞
f(x
k
) = α.
Do X compact nên x
k
có dãy con hội tụ. Giả sử x
k
→ x
0
∈ X.
Vì f nửa liên tục dưới nên f(x
0
) ≤ α.
Mặt khác, do x
0
∈ X nên f(x
0
) ≥ α.
Vậy f(x
0
) = α = inf f(x) : x ∈ X.
(ii) Chứng minh tương tự phần (i).
1.3 Tập lồi, hàm lồi, ánh xạ đa trị
Định nghĩa 1.3.1. Tập X ⊂ R
n

hay C = {x ∈ R
n
: a
i
, x ≥ b
i
với i = 1, . . . , m}
Các bất phương trình đó thường được gọi là các ràng buộc xác định
C.
Ký hiệu A là ma trận cấp m × n có các cột phần tử là a
1
, . . . , a
m
∈
R
n
, b = (b
1
, . . . , b
m
)
T
∈ R
m
. Khi đó, C = {x ∈ R
n
: Ax ≥ b}.
Định nghĩa 1.3.3. Cho X ⊂ R
n
là một tập lồi và f : X → R là một

+ a
1
x
n−1
+ . . . + a
n−1
x + a
n
= 0
ở đó, n ∈ N và a
i
∈ R, (i = 1, . . . , n) là các hệ số thực.
Quy tắc cho tương ứng mỗi vectơ a = (a
1
, . . . , a
n
) ∈ R
n
với tập nghiệm,
ký hiệu bởi F (a) của bài toán trên cho ta một ánh xạ đa trị:
F : R
n
⇒ C.
từ không gian Euclide R
n
vào tập số phức C.
Định nghĩa 1.3.5. Miền hữu hiệu của ánh xạ đa trị F : X ⇒ Y được
xác định bởi:
domF = {x ∈ X : F (x) = ∅}
Định nghĩa 1.3.6. Ta nói F là nửa liên tục trên tại x ∈ domF nếu với

{0} nếu x = 0
là nửa liên tục dưới ở trong R, nhưng không là nửa liên tục trên tại
x = 0. Như vậy, F không phải ánh xạ liên tục ở trên R.
Ví dụ 1.3.6. Ánh xạ đa trị
F (x) =

[0, 1] nếu x ∈ Q
[−1, 0] nếu x ∈ I
không là nửa liên tục dưới ở trong R, cũng không là nửa liên tục trên và
do đó không phải ánh xạ liên tục ở trên R.
1.4 Bài toán quy hoạch toàn phương
1.4.1 Bài toán tối ưu
(P ) : min{f (x) : x ∈ C}.
14
Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
Với f : R
n
→ R là hàm cho trước và C ⊂ R
n
là tập con cho trước của
R
n
.
Ký hiệu R = [−∞; +∞] = R ∪ {−∞} ∪ {+∞} là đường thẳng thực.
R
n
là không gian Euclide n chiều với chuẩn:
 x = (
n


1
, , y
n
) ∈ R
n
.
Trong đó x
T
là ma trận chuyển vị của x.
Định nghĩa 1.4.1. Bài toán (P ) được gọi là bài toán tối ưu hay bài toán
quy hoạch toán học. Hàm f gọi là hàm mục tiêu và C là tập ràng buộc
(hay miền chấp nhận được của (P)). Các phần tử của C được gọi là các
véctơ chấp nhận được của (P ) hay các phương án.
C = R
n
thì ta nói rằng (P ) là một bài toán không có ràng buộc.
Các trường hợp còn lại P là bài toán có ràng buộc.
Định nghĩa 1.4.2. Một véctơ chấp nhận được x ∈ C được gọi là một
nghiệm, hoặc nghiệm tối ưu toàn cục, hoặc phương án tối ưu toàn cục,
hoặc cực tiểu toàn cục của (P) nếu f (x) = +∞ và f(x) ≥ f(x) với mọi
x ∈ C.
Ta nói rằng x ∈ C là một nghiệm tối ưu địa phương hoặc nghiệm
cực tiểu địa phương của (P ) nếu f(x) = +∞ và tồn tại một lân cận U
của x sao cho:
f(x) ≥ f (x), ∀x ∈ C ∩ U (1.1)
Tập tất cả các nghiệm tối ưu của (P) được kí hiệu Sol(P ). Tập tất cả
các nghiệm địa phương của (P ) kí hiệu là loc(P )
Ta nói hai bài toán tối ưu (bài toán quy hoạch toán học) là tương
đương nếu tập nghiệm của hai bài toán là trùng nhau.
15

tối ưu địa phương) của (P
1
) nếu và chỉ nếu x là một nghiệm tối ưu toàn
cục (tương ứng, một nghiệm tối ưu địa phương) của bài toán giá trị nhỏ
nhất sau:
min − f(x) với x ∈ C
Do vậy, bất kỳ bài toán giá trị lớn nhất nào của dạng (P
1
) cũng có
thể đưa về bài toán dạng giá trị nhỏ nhất dạng (P).
Bài toán P còn được gọi là bài toán "min", giá trị tối ưu của bài toán
còn được kí hiệu là:
min{f(x) : x ∈ C} hoặc min
x∈C
f(x).
16
Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
Nếu bài toán P có nghiệm x thì
f(x) = min{f (x) : x ∈ C}.
Bài toán (P
1
) được gọi là bài toán "max", giá trị tối ưu của bài toán
(P
1
) còn được kí hiệu là:
max{f(x) : x ∈ C} hoặc max
x∈C
f(x).
Nếu bài toán (P
1

lim
k→∞
f(x
k
) = sup f (C).
Hiển nhiên rằng, nghiệm tối ưu toàn cục của bài toán (P ) (hay (P
1
))
đều là nghiệm tối ưu địa phương của (P ) (tương ứng, của (P
1
)). Nhưng
điều ngược lại không phải lúc nào cũng đúng.
17
Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
Ví dụ 1.4.1.
min{f(x) = −x
2
1
− x
2
2
+ 1 : x = (x
1
, x
2
), x
1
≥ −1, −x
1
≥ −1, x

)
2
: x ∈ C} (1.3)
Với C = {x = (x
1
, x
2
) : x
1
≥ 0} ∪ {x = (x
1
, x
2
) : x
2
≥ 0} và
c = (c
1
, c
2
) = (−2, −1).
Chú ý rằng (1.3) tương đương với bài toán sau:
min{ x − c : c ∈ C}
Ta có thể chỉ ra rằng Sol(P ) = {(−2, 0)}, loc(P ) = {(−2, 0); (0, −1)}.
Tuy nhiên, nếu C là một tập lồi và f là một hàm lồi trên C thì mọi
nghiệm tối ưu địa phương của (P ) đều là nghiệm tối ưu toàn cục của
(P ). Khẳng định sau đây chứng minh điều đó.
Định lí 1.4.1. Cho C ⊂ R
n
là tập lồi, f : C → R là một hàm lồi. Khi

f(x) =
1
2
x, Qx + c, x + α. (1.4)
với ∀x ∈ R
n
.
Nếu
Q =


q
11
. . . q
1n
. . . . . . . . .
q
n1
. . . q
nn


; c =


c
1
.
.
.

i
x
j
) +
n

i=1
c
i
x
i
+ α.
Từ x, Qx = x,
1
2
(Q + Q
T
)x với ∀x ∈ R
n
, biểu thức (1.4) vẫn đúng
nếu ta thay Q bởi ma trận đối xứng
1
2
(Q + Q
T
).
Do đó ta sẽ giả sử ma trận vuông trong phép biểu diễn của hàm toàn
phương tuyến tính là đối xứng. Không gian các ma trận đối xứng n × n
được ký hiệu là R
n×n

không thể thay đổi được tập nghiệm của bài toán min{f(x) : x ∈ C},
với C ⊂ R
n
là một tập đa diện lồi. Do đó, thay vì (1.4) ta thường dùng
dạng rút gọn: f (x) =
1
2
x, Qx + c, x của hàm mục tiêu.
Thay thuật ngữ được dùng cho quy hoạch tuyến tính, ta gọi các dạng
sau của quy hoạch toàn phương:
min{
1
2
x, Qx + c, x : x ∈ R
n
, Ax ≥ b},
min{
1
2
x, Qx + c, x : x ∈ R
n
, Ax ≥ b, x ≥ 0},
min{
1
2
x, Qx + c, x : x ∈ R
n
, Ax ≥ b, Cx = d}
tương ứng là dạng chuẩn, dạng chính tắc và dạng tổng quát. (Nghĩa của
A, C, b và d giống như mô tả trong dạng điển hình của quy hoạch tuyến

ta có:
x
T
Ax = (x
1
x
2
)

1 1
1 1

x
1
x
2

= (x
1
x
2
)

x
1
+ x
2
x
1
+ x

= 0 ↔ x
2
= −x
1
Vậy A là nửa xác định dương.
Ví dụ 1.4.6.
Xét ma trận Q =


1 1 0
0 1 1
1 0 1


Với mọi x ∈ R
3
ta có:
x
T
Qx = (x
1
x
2
x
3
)


1 1 0
0 1 1

x
1
+ x
3


= x
2
1
+ x
1
x
2
+ x
2
2
+ x
2
x
3
+ x
3
x
1
+ x
2
3
=
1
2

1
2
x, Qx + c, x + α với Q ∈ R
n×n
S
, c ∈ R
n
và α ∈ R. Nếu Q là một ma trận nửa xác định dương, thì f là một hàm
lồi.
21
Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
Chứng minh. Do x → c, x + α là một hàm lồi và tổng hai hàm lồi là
một hàm lồi. Điều này đủ để suy ra
f
1
(x) := x, Qx là một hàm lồi.
Vì Q là một ma trận nửa xác định dương, với ∀u ∈ R
n
và ∀v ∈ R
n
, ta
có:
0 ≤ u − v, Q(u − v) = u, Qu − 2v, Qu + v, Qv.
Điều này suy ra rằng:
v, Qv ≤ u, Qu − 2 (1.3)
Lấy bất kỳ x ∈ R
n
, y ∈ R
n
và t ∈ (0, 1), ta đặt z = tx + (1 − t)y.

c, x với c ∈ R
n
là một hàm toàn phương tuyến tính bất định. Các bài
toán với hàm mục tiêu toàn phương tuyến tính bất định được gọi là các
quy hoạch toàn phương bất định.
Định lý Frank - Wolfe
Xét quy hoạch toàn phương có dạng:

Minf(x) :=
1
2
x, Qx + c, x
x ∈ R
n
, Ax ≥ b,
(1.5)
22
Luận văn thạc sĩ Toán học Học viên Phan Thị Ánh Vân
với Q ∈ R
n×n
S
, A ∈ R
n
, c ∈ R
n
và b ∈ R
m
.
Cho tập hằng số và giá trị tối ưu của (1.5), ta sẽ dùng kí hiệu:
C(A, b) = {x ∈ R

Định lí 1.4.2. ( Định lý Frank - Wolfe (1956)) Nếu f∗ = inf{f(x) :
x ∈ C(A, b)} là một số thực xác định thì bài toán (1.5) có nghiệm.
Trong định lý 1.2.1, giả sử f là một hàm toàn phương tuyến tính và
C là một tập đa diện lồi. Từ định nghĩa tập đa diện lồi suy ra tồn tại
một số nguyên m ∈ N, một ma trận A ∈ R
m×n
và một véctơ b ∈ R
m
sao
cho C = {x ∈ R
n
: Ax ≥ b}.
Điều này có nghĩa là định lý Frank - Wolfe có thể được phát biểu như
sau:
"Nếu một hàm toàn phương tuyến tính bị chặn trên một tập đa diện
lồi khác rỗng thì bài toán giá trị nhỏ nhất của hàm trên tập đó phải có
nghiệm"
Nếu f là một hàm toàn phương tuyến tính nhưng C không là một
tập đa diện lồi thì kết luận của định lý 1.2.1không còn đúng nữa.
Ví dụ 1.4.7. Cho f(x) = x
1
với ∀x = (x
1
, x
2
) ∈ R
2
.
Cho C = {x = (x
1

1
x
2
)
2
với ∀x = (x
1
, x
2
) ∈ R
2
.
Lấy C = {x = (x
1
, x
2
) ∈ R
2
: x
1
≥ 0, x
2
≥ 0}.
Ta thấy f(x) ≥ 0 với ∀x ∈ R
2
.
Chọn x
k
:= (
1

: Ax ≥ b}.
Xét bài toán QP(Q, A, c, b) phụ thuộc tham số ω = (Q, A, c, b) ∈ Ω
với Ω := R
n×n
S
× R
m×n
× R
n
× R
m
.
Tập nghiệm của (1.6) được ký hiệu là Sol(Q, A, c, b).
Hàm ϕ : Ω → R định nghĩa bởi:
ϕ(ω) = inf{f(x, c, Q) : x ∈ C(A, b)}
là hàm giá trị tối ưu của bài toán tham số (1.6).
Nếu v, Qv ≥ 0 với ∀v ∈ R
n
thì f(., c, Q) là một hàm lồi và (1.6) là
một bài toán quy hoạch toàn phương lồi.
Nếu v, Qv ≤ 0 với ∀v ∈ R
n
thì f(., c, Q) là một hàm lõm và (1.6) là
một bài toán quy hoạch toàn phương lõm.
Nếu các điều kiện trên không thỏa mãn thì nó là bài toán quy hoạch
toàn phương bất định.
24
Chương 2
TÍNH LIÊN TỤC CỦA HÀM GIÁ
TRỊ TỐI ƯU

.
Ta gọi hệ Ax ≥ b là chính quy nếu tồn tại x
0
∈ R
n
sao cho:Ax
0
> b
Bổ đề 2.1.1. Cho A ∈ R
m×n
, b ∈ R
m
. Kí hiệu 2
R
n
là tập tất cả các tập
con của R
n
.
Hệ Ax ≥ b là chính quy khi và chỉ khi hàm đa trị C(.) : R
m×n
×R
m
→ 2
R
n
xác định bởi :
C(A

, b