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 PGS.TS Nguyễn Năng Tâm. Thầy đã hướng
dẫn và truyền đạt cho tác giả những kinh nghiệm quý báu trong học tập
cũng như trong nghiên cứu khoa học. Thầy luôn động viên, khích lệ tác
giả vươn lên trong học tập, tự tin vượt qua khó khăn trong việc nghiên
cứu và hoàn thiện luận văn. Tác giả xin bày tỏ lòng biết ơn lớn lao, 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 thuận lợi cho tác giả trong suốt quá trình học tập.
Tác giả xin chân thành cảm ơn Ban lãnh đạo tỉnh Lào Cai, Sở
GD-ĐT tỉnh Lào Cai, Ban giám hiệu, các thầy cô giáo, đồng nghiệp
trường Trung học phổ thông số III Bảo Yên cùng gia đình, người thân,
bạn bè đã 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, tháng 12 năm 2013
Tác giả
Phạm Trọng Dầ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 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, tháng 12 năm 2013
Tác giả
Phạm Trọng Dần

2.2. Dưới vi phân dưới bị chặn của hàm toàn phương . . . . . 19
2.3. Dưới vi phân dưới của hàm toàn phương . . . . . . . . . 30
3 ỨNG DỤNG CỦA DƯỚI VI PHÂN DƯỚI VÀO BÀI
TOÁN TỐI ƯU TOÀN PHƯƠNG 46
3.1. Bài toán tối ưu toàn phương . . . . . . . . . . . . . . . . 46
3.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . 47
3.3. Thuật toán tìm nghiệm . . . . . . . . . . . . . . . . . . . 48
Kết luận 51
Tài liệu tham khảo 52
iv
BẢNG KÝ HIỆU
R Tập số thực
R R ∪ (−∞; +∞)
R
n
Không gian Euclide n - chiều
R
s
n×n
Tập các ma trận thực đối xứng n × n
R
m×n
Tập các ma trận thực m × n
x; y Tích vô hướng của x và y
x Chuẩn của x
B

x
0
; ε

 Kết thúc chứng minh
1. Lý do chọn đề tài
Khái niệm dưới vi phân dưới được giới thiệu bởi Plastria [10] xem
như một sự nới lỏng khái niệm dưới vi phân trong giải tích lồi. Động cơ
thúc đẩy việc đưa ra khái niệm mới này là thuật toán, từ khi Plastria
chứng minh rằng, phương pháp mặt phẳng cắt cổ điển của Kelley cũng
dùng được cho bài toán tối ưu lồi, dưới một số giả thiết thích hợp sử
dụng dưới gradient dưới để sinh ra những mặt phẳng cắt. Plastria cũng
lưu ý rằng, tính dưới khả vi dưới của hàm số suy ra tính tựa lồi. Sau đó
mối liên quan giữa khái niệm dưới vi phân dưới với một số khái niệm
khác đã được nghiên cứu bởi Greenberg và Pierskalla [4]. Một số kết quả
của dưới vi phân dưới của hàm số được định nghĩa trong không gian lồi
và được ứng dụng vào các bài toán trong lĩnh vực quy hoạch phân thức.
Tính tựa lồi của hàm toàn phương được nghiên cứu bởi một số tác
giả [3]. Động cơ thúc đẩy họ là sự tin tưởng khái niệm dưới vi phân dưới
là điều kiện chắc chắn thích hợp mà ta đặt cho hàm tựa lồi để tạo nên
một lý thuyết, ở một mức độ nào đó, song song với giải tích lồi.
Sau khi học được các kiến thức về Toán giải tích, với mong muốn
tìm hiểu sâu hơn về các kiến thức đã học, mối quan hệ và ứng dụng của
chúng. Tôi đã chọn đề tài nghiên cứu:
“ Dưới vi phân dưới của hàm toàn phương và ứng dụng ”.
2. Mục đích nghiên cứu
Để hiểu sâu hơn về những kiến thức đã học, mối quan hệ và ứng
dụng của chúng. Đồng thời thu nhận được kiến thức về dưới vi phân
dưới của hàm toàn phương và ứng dụng.
2
3. Nhiệm vụ nghiên cứu
Dưới vi phân dưới của hàm toàn phương và ứng dụng.
4. Đối tượng và phạm vi nghiên cứu
Hàm toàn phương, dưới vi phân dưới của hàm toàn phương và bài

T
| x
1
, x
2
, , x
n
∈ R

trong đó
x = (x
1
, x
2
, , x
n
)
T
với hai phép toán
(x
1
, , x
n
)
T
+ (y
1
, , y
n
)

T
∈ R
n
thì x
i
gọi là thành phần tọa độ thứ i
của x. Véc tơ không của không gian này gọi là gốc của R
n
và được kí
hiệu là 0, vậy 0 = (0, , 0)
T
.
3
4
Ta gọi hệ e
1
= (1, 0, , 0)
T
; e
2
= (0, 1, 0, , 0)
T
; ; e
n
= (0, , 0, 1)
T
là cơ sở chính tắc của không gian R
n
.
1.1.1. Tích vô hướng và chuẩn

)
T
∈ R
n
ta định nghĩa
x =

x, x =




n

i=1
x
2
i
và gọi là chuẩn Euclid của véc tơ x.
1.1.2. Tập đóng và tập mở
Định nghĩa 1.1.1. Cho x
0
∈ R
n
,ε > 0 ,ta gọi tập
B(x
0
, ε) =

x ∈ R

. Kí hiệu {U
i
(K)}
i∈I
là họ tất cả các tập mở chứa trong K. {F
j
(K)}
j∈J
là họ tất cả các tập
đóng chứa trong K. Ta có U =
∪
i∈I
U
i
(K) là tập mở và F =
∩
j∈J
F
j
(K) là
tập đóng.
Tập U gọi là phần trong của K và kí hiệu: intK. Tập F gọi là bao
đóng của K và kí hiệu: K
5
Ta có một số kết quả:
(i) K là tập mở khi và chỉ khi K = intK.
(ii) K là tập đóng khi và chỉ khi K = K.
1.1.3. Sự hội tụ
Định nghĩa 1.1.4. Dãy điểm


. Ta nói x ∈ R
n
tiến đến x
0
∈ R
n
. Kí hiệu x → x
0
nếu


x − x
0


→ 0.
Dễ dàng chứng minh được tính chất sau: Tập A ⊂ R
n
được gọi là
tập đóng khi và chỉ khi với mọi dãy

x
k

⊂ A mà x
k
hội tụ đến x
0
thì
x

1.2.1. Tập lồi - tập affine
Định nghĩa 1.2.1. Cho X là không gian véc tơ. Tập M ⊂ X được gọi
là đa tạp affine (tập affine) nếu với ∀x, y ∈ M, λ ∈ R ta có:
λx + (1 − λ) y ∈ M
Nếu K ⊂ X bất kì. Ta gọi bao affine của K, kí hiệu: affK, là
giao của tất cả các tập affine chứa K.
Định nghĩa 1.2.2. Tập K ⊂ R
n
được gọi là lồi nếu
λx + (1 − λ) y ∈ K ∀x, y ∈ K, ∀λ ∈ [0; 1]
Giả sử X ⊂ R
n
. Giao của tất cả các tập lồi trong R
n
chứa X được gọi
là bao lồi của tập X, kí hiệu là coX.
Theo định nghĩa tập rỗng được xem là tập lồi.
Ví dụ 1.2.1. Các tam giác và hình tròn trong mặt phẳng là tập lồi.
Hình cầu đơn vị trong không gian R
n
là tập lồi.
1.2.2. Hàm lồi
Định nghĩa 1.2.3. Cho K ⊂ R
n
là một tập lồi và f : K → R là một
hàm số.
Hàm f được gọi là hàm lồi trên K nếu với mọi x, y ∈ K và với
mọi t ∈ [0, 1] ta có:
f(tx + (1 − t)y ≤ tf(x) + (1 − t)f(y)
Hàm f được gọi là hàm lồi chặt trên K nếu với mọi x, y ∈ K và

Vậy f(x) = x
3
không phải là hàm lồi trên R
1.2.3. Hàm lồi suy rộng
Định nghĩa 1.2.5. Cho K ⊂ R
n
là một tập lồi và f : K → R là một
hàm số.
Hàm f được gọi là hàm giả lồi trên K nếu với mọi x, y ∈ K sao
cho f(x) ≤ f(y) và với mọi λ ∈ [0, 1], tồn tại một số β > 0 thỏa mãn
f(λx + (1 − λ)y) ≤ f(y) − λ(1 − λ)β
8
Hàm f được gọi là hàm giả lồi chặt trên K nếu với mọi x, y ∈ K
sao cho f(x) ≤ f(y) và với mọi λ ∈ [0, 1], tồn tại một số β > 0 thỏa
mãn
f(λx + (1 − λ)y) < f(y) − λ(1 − λ)β
Ta có một số tính chất sau:
(i)Hàm lồi là hàm giả lồi, hàm lồi chặt là hàm giả lồi chặt, nhưng
hàm giả lồi có thể không lồi.
(ii)Hàm lồi chưa chắc đã là hàm giả lồi chặt.
(iii)Hàm giả lồi chưa chắc đã là hàm giả lồi chặt.
Định nghĩa 1.2.6. Cho K ⊂ R
n
là một tập lồi và f : K → R là một
hàm số.
Hàm f được gọi là hàm tựa lồi trên K nếu với mọi x, y ∈ K và
với mọi t ∈ [0, 1], ta có:
f(tx + (1 − t)y) ≤ max {f(x), f(y)}
Hàm f được gọi là hàm tựa lồi chặt trên K nếu với mọi x, y ∈ K
và với mọi t ∈ [0, 1], ta có:

Định nghĩa 1.3.1. Nếu x
0
là điểm trong của A thì ta cũng nói A là lân
cận của x
0
.
Cho không gian tôpô (X, τ). Một họ B ⊂ τ được gọi là một cơ sở
lân cận của τ nếu mọi tập U ∈ τ đều được biểu diễn dưới dạng hợp của
các tập thuộc B. Một họ V ⊆ τ được gọi là một cơ sở lân cận của x
0
∈ X
nếu mọi lân cận U của x
0
đều tồn tại V ∈ V sao cho x
0
∈ V ⊆ U.
10
1.3.2. Không gian tôpô tuyến tính
Cho không gian véc tơ X. Khi đó một tôpô τ trên X được gọi là
tương đương với cấu trúc đại số trên X nếu dưới tôpô này các ánh xạ
sau lên tục:
+ : X × X → X
. : R × X → X
Tức là:
Với mọi x, y ∈ X và mọi lân cận W của x + y, tồn tại các lân cận
U của x, V của y sao cho U + V ⊂ W.
Với mọi λ ∈ R, x ∈ X và mọi lân cận W của λx, tồn tại ε > 0 và
lân cận V của x sao cho µV ⊂ W với mọi µ ∈ (λ − ε, λ + ε).
Khi đó, τ được gọi là tôpô tuyến tính trên X và X được gọi là
không gian tôpô tuyến tính.

(i) Nếu τ là một tôpô lồi địa phương trên X, thì tồn tại một cơ sở
lân cận gốc gồm các tập lồi, cân đối và hấp thụ.
(ii) Ngược lại, nếu V
0
là họ gồm các tập lồi, cân đối và hấp thụ thì
họ sau

V = ε
m
∩
1
V
i
| ε > 0; m ∈ N; V
i
∈ V
0

là cơ sở lân cận gốc của một tôpô lồi địa phương nào đó. Hơn nữa, tôpô
là Hausdorff khi và chỉ khi
∩
V ∈V
0
,ε>0
εV = {0}
Trong phần này ta định nghĩa phần trong tương đối của K (Với K
là tập lồi trong X) là phần trong của tập này theo tôpô cảm sinh trong
aff(K). Cụ thể:
riK = {x ∈ K | ∃V : (x + V ) ∩aff(K) ⊂ K}
(Với V là lân cận gốc)

Với 0 < λ < 1; x, y ∈ K ta có (1 −λ)x ∈ K; λy ∈ K và (1 −λ)x +
λy ∈ K
Chú ý với λ = 0 ta vẫn có (1 − λ)x + λy ∈ K. Vậy K là tập lồi.
Từ đó ta suy ra K là nón lồi.
Định nghĩa 1.3.5. Cho D là tập lồi khác rỗng trong R
n
.
Véc tơ v ∈ R
n
khác 0 được gọi là phương lùi xa của D nếu với mọi
x ∈ D, với mọi t ≥ 0 ta có x + tv ∈ D.
Tập tất cả các phương lùi xa của D cùng véc tơ 0 của R
n
lập thành
một nón lồi. Ta gọi nón đó là nón lùi xa của D và kí hiệu là 0
+
D.
13
1.4. Hàm Lipschitz
Định nghĩa 1.4.1. Giả sử X là không gian Banach, f : X → R
Hàm f được gọi là Lipschitz địa phương tại x
0
∈ X hay Lipschitz
địa phương gần x
0
, nếu tồn tại lân cận U của x
0
số K > 0 sao cho với
mọi x, x


và x
T
Ax = 0 ⇔ x = 0.
(iii) A được gọi là nửa xác định âm (xác định âm) nếu −A là nửa
xác định dương (xác định dương) .
Ta kí hiệu:
diag(a
1
, , a
n
) =




a
1
0

0 a
n




14
1.6. Hàm toàn phương và bài toán quy hoạch toàn
phương
1.6.1. Hàm toàn phương
Trong luận văn này ta xét hàm toàn phương Q : R

A(x − y) ≥ 0
suy ra
1
2
x
T
Ax +
1
2
y
T
Ay ≥ x
T
Ay
Do đó với mọi x, y ∈ R
n
và với mọi t ∈ (0, 1) ta có:
Q [tx + (1 − t) y] =
t
2
2
x
T
Ax + tb
T
x +
1 − t
2
2
y

T
Ax
1
2
y
T
Ay

≤ tQ(x) + (1 − t)Q(y)
Vậy Q lồi.
15
Áp dụng. Trường hợp n = 1 ta thấy hàm toàn phương như trên có
dạng hàm bậc hai f(x) = ax
2
+ bx
Theo định lý trên ta thấy hàm bậc hai là hàm lồi khi a > 0.
Dựa vào các kết quả của S.Schaible [12], các tính chất của hàm
toàn phương, tựa lồi, ta có các kết quả sau:
Định lý 1.6.2. Cho K ⊂ R
n
là thể lồi và Q(x) =
1
2
x
T
Ax + b
T
x.
Khi đó Q là tựa lồi, nhưng không lồi trên K khi và chỉ khi rankA =
rank(A; b) và tồn tại ma trận không suy biến P sao cho với mọi véc tơ

, , y
n
) ∈ R
n
| G(y) ≤ δ, y
1
≤ 0}
trong trường hợp này hàm số h(x) = −(δ − Q(x))
1
2
là hàm lồi trên K.
Hệ quả 1.6.1. Cho K ⊂ R
n
là tập lồi, mở.
Khi đó
Q(x) =
1
2
x
T
Ax + b
T
x
gọi là tựa lồi trên clK khi và chỉ khi nó là hàm giả lồi trên K.
Định lý 1.6.3. K ⊂ R
n
là tập lồi, mở. Khi đó
Q(x) =
1
2

T
x
Với điều kiện
x ∈ R
n
; Cx ≥ d
trong đó A ∈ R
s
n×n
, C ∈ R
m×n
, b ∈ R
n
, c ∈ R
m
Ta dùng các kí hiệu:
∆(C, d) = {x ∈ R
n
|Cx ≥ d}
θ = inf {f(x) | x ∈ ∆(C, d)}
Ta có các định lý sau:
Định lý 1.6.4. (Định lý Frank - Wolf) Nếu θ = inf {f(x) | x ∈ ∆(C; d)}
là một số thực hữu hạn thì bài toán (P ) có nghiệm
Định lý 1.6.5. (Định lý Eaves) Bài toán (P) có nghiệm khi và chỉ khi
các điều kiện sau được thỏa mãn:
(i)∆(C; d) = ∅.
(ii) Nếu v ∈ R
n
và Cv ≥ 0 thì v
T

f(y) ≥ f(x) + (x
∗
)
T
(y − x)
với mọi y ∈ K mà f(y) < f(x).
Véc tơ x
∗
được gọi là dưới gradient dưới của f tại x. Tập hợp các
dưới gradient dưới của f tại x được gọi là dưới vi phân dưới của f tại x
và được kí hiệu là ∂
−
f(x).
Cho f : K → R. Ta nói rằng f là dưới khả vi dưới trên K nếu nó
là dưới khả vi dưới tại mọi điểm x ∈ K. (Ta thường viết tắt dưới vi phân
dưới là l.s.d).
18
19
2.2. Dưới vi phân dưới bị chặn của hàm toàn phương
Nếu tồn tại N > 0 sao cho ∂
−
f(x)∩B(O; N) = ∅ với mọi x ∈ K ta
nói rằng f là dưới khả vi dưới bị chặn (viết tắt là b.l.s.d), trong trường
hợp này N được gọi là cận của dưới vi phân dưới bị chặn f.
Bổ đề 2.2.1. Cho K ⊂ R
n
là tập lồi và f : clK → R là hàm liên tục.
Khi đó các mệnh đề sau tương đương
(i) f là hàm tựa lồi trên riK.
(ii) f là hàm tựa lồi trên K.

Chú ý. Ngay cả trong trường hợp 1 chiều, giả thiết tính liên tục
trong khẳng định trước cũng không thể thay thế bằng tính nửa liên tục
20
dưới.
Ví dụ 2.2.1. Xét hàm số f : [0; 1] → R xác định bởi f(0) = f(1) = 0
và f(x) = 1 với x ∈ (0; 1).
Ta thấy f(x) là hàm nửa liên tục dưới nhưng nó không liên tục.
Ta chứng minh được f(x) không phải là hàm tựa lồi. Thật vậy:
Chọn x = 1, y = 0 và t ∈ (0; 1) bất kì, ta có:
f(tx + (1 − t)y) = f(t) = 1
và
max {f(x); f(y)} = 0
hay là
f(tx + (1 − t)y) > max {f(x); f(y)}
Tuy nhiên, dễ thấy tính nửa liên tục trên là đủ để diều kiện tương
đương đúng trong trường hợp hàm của một biến thực.
Nhưng khi n > 1, tính nửa liên tục trên là chưa đủ
Ví dụ 2.2.2. Cho hàm số f : [−1; 1] × [−1; 1] → R cho bởi biểu thức
f(x; y) =

0; x = 1
1 − y
2
; x = 1
Ta thấy hàm trên không phải hàm tựa lồi. Thật vậy:
Chọn t ∈ (0; 1) bất kì, x
1
= 1, x
2
= 1, y

2
; y
2
)] > max {f(x
1
; y
1
); f(x
2
; y
2
)}