Mục lục
Mở đầu 2
Chương 1: Dưới vi phân 5
1.1. Định nghĩa và kí hiệu . . . . . . . . . . . . . . . . . . . . 5
1.2. Một số tính chất cơ bản của dưới vi phân . . . . . . . . . 6
1.3. Phép toán về dưới vi phân . . . . . . . . . . . . . . . . . 12
Chương 2: Điều kiện tồn tại nghiệm tối ưu 18
2.1. Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . . . 18
2.2. Các bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . 22
2.3. Bài toán tối ưu không ràng buộc . . . . . . . . . . . . . 23
2.3.1 Điều kiện tối ưu cấp 1 . . . . . . . . . . . . . . . 24
2.3.2 Điều kiện tối ưu cấp 2 . . . . . . . . . . . . . . . 25
2.4. Bài toán tối ưu có ràng buộc . . . . . . . . . . . . . . . . 40
2.4.1 Điều kiện tối ưu cấp 1 . . . . . . . . . . . . . . . 44
2.4.2 Điều kiện tối ưu cấp 2 . . . . . . . . . . . . . . . 47
Kết luận 62
Tài liệu tham khảo 63
1
Mở đầu
Trong tự nhiên sự vận hành và phát triển của vạn vật đều có thể
qui được về hai vấn đề cơ bản sau:
1) Tồn tại hay không tồn tại? Theo ngôn ngữ toán học: có tồn tại
hay không nghiệm của phương trình
f(x) = 0, x ∈ D (1)
2) Tồn tại như thế nào? Theo ngôn ngữ toán học: Tìm nghiệm tối
ưu của bài toán
min
x∈D
f(x) (2)
Chính vì vậy toán học nói chung luôn là công cụ hữu hiệu giải quyết
các bài toán nảy sinh từ thực tế sinh động. Lý thuyết tối ưu nói riêng

Luận văn được chia làm 2 chương.
Chương I: Dưới vi phân. Trong chương I, tác giả trình bày các kiến
thức cơ bản về dưới vi phân như: định nghĩa, các tính chất và các phép
toán về dưới vi phân.
Chương II: Điều kiện tồn tại nghiệm tối ưu. Trong chương II, tác
giả trình bày một cách chi tiết các điều kiện tối ưu cấp 1 và cấp 2 đối
với hai loại bài toán tối ưu không trơn là bài toán tối ưu không ràng
buộc và bài toán tối ưu có ràng buộc và có sự so sánh với bài toán tối
ưu trơn.
Bản luận văn được hoàn thành dưới sự hướng dẫn tận tình của
GS.TS Trần Vũ Thiệu. Tác giả hi vọng rằng một phần kiến thức nhỏ
3
trong luận văn sẽ là tài liệu tham khảo cho các bạn sinh viên đại học,
cao đẳng, những người làm toán quan tâm và yêu thích đề tài này.
Mặc dù tác giả đã cố gắng hết sức nhưng kết quả đạt được trong
luận văn còn rất khiêm tốn và không tránh khỏi những thiếu sót, tác
giả mong nhận được nhiều ý kiến đóng góp quý báu của các thầy cô và
đồng nghiệp.
Hà Nội, tháng 11 năm 2009
4
Chương 1
Dưới vi phân
1.1 Định nghĩa và kí hiệu
Định nghĩa 1.1. Cho f : R
n
→ R là một hàm lồi. Một véctơ g ∈ R
n
là
dưới gradient của f tại x ∈ R
n

{−1} nếu x < 0.
5
Ví dụ 1.2. Cho f(x) = e
x
− 1. Khi đó
∂f(0) = [0, 1],
∂f(x) =



{e
x
} nếu x > 0
{0} nếu x < 0.
Định nghĩa 1.3. Hàm f được gọi là khả dưới vi phân tại x nếu tập
∂f(x) = ∅.
1.2 Một số tính chất cơ bản của dưới vi phân
Bổ đề 1.1. Dưới vi phân ∂f(x) là một tập đóng, tức là: nếu ta có dãy
x
(k)
→ x

, g
(k)
→ g

, g
(k)
∈ ∂f
(k)


∈ ∂f

. 
Bổ đề 1.2. ∂f(x) là tập bị chặn với mọi x ∈ B ⊂ Int(K) trong đó
K ⊂ R
n
và B là tập compact.
Chứng minh. Giả sử ngược lại, khi đó tồn tại dãy g
(k)
∈ ∂f(x
(k)
) và dãy
x
(k)
∈ B sao cho g
(k)

2
→ ∞. Do tính compact nên tồn tại x
(k)
→ x

.
Định nghĩa
δ
(k)
=
g
(k)


, δ
(k)
→ 0.
Vì vậy f(x
(k)
+ δ
(k)
) → f

. Mâu thuẫn. 
Nhận xét 1.1.
i) Từ hai bổ đề trên suy ra ∂f(x) là một tập compact.
ii) Nếu f khả vi tại x thì
f(x + δ) = f(x) + δ
T
∇f(x)) + 0(δ)
mà
f(x + δ) ≥ f(x) + δ
T
g
nên
δ
T
(g − ∇f(x)) ≤ 0(δ).
Chọn δ = θ(g − ∇f(x)), θ ↓ 0 sao cho g = ∇f. Từ đây ta có ∂f(x) là
vectơ ∇f(x).
Bổ đề 1.3. Xét hàm đa trị
∂f : K → 2
K

Chứng minh. Lấy x
1
, x
2
∈ K, g
1
∈ ∂f(x
1
), g
2
∈ ∂f(x
2
). Theo định
nghĩa của dưới vi phân ta có
f(x
2
) ≥ f(x
1
) + g
T
1
(x
2
− x
1
)
f(x
1
) ≥ f(x
2

i
+ b
i
(1.4)
trong đó h
i
là các cột của ma trận hữu hạn H cho trước. Định nghĩa
A = A(c) = { i : c
T
h
i
+ b
i
= h(c) } (1.5)
là tập các siêu phẳng tựa tại c và do đó đạt giá trị lớn nhất. Khi đó dễ
dàng nhận thấy các siêu phẳng này xác định dưới vi phân ∂h(c). Điều
này được nêu trong bổ đề sau:
Bổ đề 1.4. ∂h(c) = conv
i∈A
h
i
Chứng minh. Ta có
∂h(c) = { λ : h(c + δ) ≥ h(c) + δ
T
λ,∀δ } (1.6)
Lấy λ ∈ conv
i∈A
h
i
, ta có λ =

h
i
µ
i
≤ max
i∈A
(c
T
h
i
+ b
i
) + max
i∈A
δ
T
h
i
= max
i∈A
(c + δ)
T
h
i
+ b
i
≤ h(c + δ).
8
Do đó λ ∈ ∂(h(c)) nên conv
i∈A

h
i
+ b
i
) + αs
T
λ
> c
T
h
i
+ b
i
+ αs
T
h
i
, ∀i ∈ A
= max
i∈A
(c + αs)
T
h
i
+ b
i
≥ max
i
(c + αs)
T

∈ K. Khi đó tập
{ x : x − λ
2
≤ x
0
− λ
2
}
là một tập bị chặn. Do đó tồn tại điểm cực tiểu x đối với bài toán
minx − λ
2
, x ∈ K.
Khi đó với bất kì x ∈ K ta có
(1 − θ)x + θx − λ
2
2
≥ x − λ
2
2
.
9
Cho θ → 0 ta được
(x − x)
T
(λ − x) ≤ 0, ∀x ∈ K.
Từ đó véctơ s = λ − x = 0 và thoả mãn đồng thời
s
T
(λ − x) > 0, s
T

(k)
→ s
( ở đây x
(k)
− x

= δ
(k)
s
(k)
, ∀k ) thì
lim
k→∞
f
(k)
− f

δ
(k)
= max
g∈∂f

s
T
g. (1.7)
Chứng minh. Ta có x
(k)
= x

+ δ

)
= f
(k)
− (x
k
− x

)
T
g
(k)
= f
(k)
− δ
(k)
s
(k)
T
g
(k)
và
f
(k)
≥ f

+ δ
(k)
s
(k)
T

∈ ∂f
(k)
mà g
(k)
→ g

và g

∈ ∂f

( theo Bổ đề 1.1 ).
Nếu (1.8) không đúng thì (1.9) chỉ ra mâu thuẫn tại giới hạn của dãy
con nêu trên. 
Nhận xét 1.2.
i) Nếu x
∗
là cực tiểu địa phương của hàm f(x) thì f
(k)
≥ f
∗
với k đủ
lớn và từ (1.8) ta có
max
g∈∂f
∗
s
T
g ≥ 0, ∀s : s = 1. (1.9)
Do đó điều kiện cần đối với cực tiểu địa phương là đạo hàm theo mọi
hướng phải không âm. Từ đó

∗
.
Thật vậy, nếu 0 ∈ ∂f(x
∗
) thì
f(x
∗
+ δ) ≥ f(x
∗
) + δ
T
0
11
hay
f(x
∗
+ δ) ≥ f(x
∗
), ∀x
∗
+ δ ∈ K,
do đó x
∗
là cực tiểu toàn cục.
Cuối cùng để nghiên cứu sự tồn tại và duy nhất của điểm cực tiểu,
chúng ta có kết quả sau đây:
Mệnh đề 1.1. Cho f : R
n
→ R là một hàm lồi và C là một tập con lồi
đóng khác rỗng của R

.
Để chứng minh chiều ngược lại ta giả sử A ⊆ B, tức là tồn tại a ∈ A và
a ∈ B. Vì B là tập lồi đóng khác rỗng nên từ định lý tách các tập lồi, a
và B có thể được tách ngặt bởi một siêu phẳng, nghĩa là tồn tại s ∈ R
n
12
và γ ∈ R sao cho
s, b < γ < s, a, ∀ b ∈ B
mà
Γ
B
(s) ≤ γ < s, a ≤ Γ
A
(s)
trái với giả thiết Γ
A
≤ Γ
B
. Vậy A ⊆ B.
ii) Suy ra từ (i). 
Trước hết ta xét dưới vi phân của một tổ hợp dương các hàm lồi:
Mệnh đề 1.2. Cho f
1
, f
2
: R
n
→ R là các hàm lồi và t
1
, t

f
2
)(x)
và
B = t
1
∂f
1
(x) + t
2
∂f
2
(x).
Cả hai tập này đều là các tập lồi, khác rỗng và compact. Theo Bổ đề
1.7, nếu Γ
A
= Γ
B
thì A = B.
Ta có
Γ
A
= (t
1
f
1
+ t
2
f
2

1
f
1
+ t
2
f
2
)

(x, .) = t
1
f

1
(x, .) + t
2
f

2
(x, .)
nên Γ
A
= Γ
B
, do đó A = B. 
13
Sau đây ta sẽ kiểm tra dưới vi phân của cận trên đúng của các
hàm lồi. Cho {f
j
}

j
với mọi x và j
thì f(x) = 0,∀x và J(x) = ∅.
Mệnh đề 1.3. Với mọi x ∈ R
n
ta có
∂f(x) ⊇ conv { ∪∂f
j
(x)|j ∈ J(x) }
trong đó conv kí hiệu cho bao lồi đóng.
Chứng minh. Nếu J(x) = ∅, mệnh đề luôn đúng.
Vì vậy ta giả sử J(x) = ∅. Từ ∂f(x) lồi, đóng, ta chứng minh
∂f
j
(x) ⊆ ∂f(x), ∀j ∈ J(x).
Lấy j ∈ J(x) và s ∈ ∂f
j
(x). Khi đó
f(y) ≥ f
j
(y) ≥ f
j
(x) + s, y − x, ∀y ∈ R
n
.
Từ f
j
(x) = f(x) suy ra s ∈ ∂f(x). Mệnh đề được chứng minh. 
14
Để đạt được dấu đẳng thức, ta giả sử J là tập hữu hạn, J(x) = ∅.

.
Thật vậy với mỗi d thì
Γ
conv(S)
(d) = Γ
s
(d) = sup
s∈S
s, d = sup
j∈J(x)
sup
s
j
∈∂f
j
(x)
s
j
, d = sup
j∈J(x)
f

j
(x; d).
Cho d ∈ R
n
, d = 0 và xét dãy t
k
→ 0, t
k

k
(x + t
k
d) = f(x + t
k
d)
và cho k → +∞ ta được
f
j
∗
(x) = f(x)
15
tức là j
∗
∈ J(x) (ở đây ta đã sử dụng tính liên tục của f
j
∗
và f tại x).
Cuối cùng với mỗi k ta có
f

(x; d) ≤
f(x + t
k
d) − f(x)
t
k
=
f
j

là các hàm lồi khả vi thì
∂f(x) = conv { ∇f
j
(x)|j ∈ J(x) }, ∀x ∈ R
n
.
Ví dụ 1.3. Xét hàm f(x) = max { f
1
(x), f
2
(x), f
3
(x) }
với
f
1
(x) = −x
1
− x
2
, f
2
(x) = −x
1
+ x
2
, f
3
(x) = x
1

dẫn tới lim sup f
j
n
(x) ≤ f
j
∗
(x) ).
Khi đó với mọi x ∈ R
n
ta có
∂f(x) = conv { ∇f
j
(x)|j ∈ J(x) }.
17
Chương 2
Điều kiện tồn tại nghiệm tối ưu
2.1 Sự tồn tại nghiệm tối ưu
Trong thực tế ta thấy, để tìm một thứ gì đó trước hết ta phải xem
xét nó có tồn tại hay không đã. Muốn sản xuất ra một loại hàng hoá
nào đó, trước hết phải xem có phương án hay cách thức nào đó để sản
xuất hay không? Muốn xây dựng một trung tâm thương mại ở khu dân
cư sao cho tối ưu, trước hết phải tính toán xem có cách nào để đạt được
không ?... Nói tóm lại, muốn tìm được lời giải của một bài toán tối ưu,
trước hết ta phải có cách nào đó nhận biết được xem nghiệm ấy có tồn
tại hay không đã rồi mới đưa ra cách để tìm nó. Ta biết trong bài toán
tối ưu có hai đối tượng quan trọng: Tập ràng buộc và hàm mục tiêu xác
định trên tập đó. Vì thế khi ta xét đến điều kiện để tồn tại nghiệm tối
ưu, ta phải quan tâm đến các điều kiện, tính chất của hai đối tượng ấy.
Ví dụ, trong giải tích cổ điển, định lý Weierstrass khẳng định rằng một
hàm liên tục trên một tập compact hay mở rộng là một hàm nửa liên tục

0
).
ii) x
0
∈ D được gọi là điểm cực tiểu địa phương nếu tồn tại lân cận U
chứa x
0
để các bất đẳng thức trên thoả mãn với mọi x ∈ U ∩ D.
19
Nhiều khi ta sử dụng kí hiệu
f(x
0
) = min
x∈D
f(x) (P )
chung cho các loại tối ưu trên.
Bài toán tìm cực đại của một hàm trên tập cho trước cũng được phát
biểu một cách tương tự. Nhưng để ý
min
x∈D
f(x) = − max
x∈D
(−f(x))
ta suy ra bài toán cực đại hoàn toàn có thể quy về bài toán cực tiểu. Do
đó trong lý thuyết tối ưu, nói chung ta chỉ cần xây dựng lý thuyết giải
cho một trong hai loại: cực tiểu hoặc cực đại. Trong chương này ta chỉ
quan tâm tới bài toán cực tiểu.
Chú thích:
Nếu x
0

Ngược lại, nếu tập f(D)
+
có một cận dưới hữu hạn thì cận dưới lớn nhất
20
( hay infimum ) của tập này là hữu hạn và ta ký hiệu nó là t
0
. Theo định
nghĩa của infimum, t ≥ t
0
với mọi t ∈ f(D)
+
và tồn tại {t
n
} ⊂ f(D)
+
hội tụ đến t
0
. Vì f(D)
+
là tập đóng nên t
0
∈ f(D)
+
. Theo định nghĩa của
tập f(D)
+
tồn tại x
0
∈ D sao cho t
0

} ⊂ D sao cho
lim
n→∞
f(x
n
) = −∞.
Vì D là tập compact, không mất tính tổng quát ta có thể giả thiết
lim
n→∞
x
n
= x
0
∈ D.
Ta thấy rằng giá trị của hàm f tại x
0
là hữu hạn và hàm f là nửa liên
tục dưới, do đó không thể có
f(x
0
) ≤ lim
n→∞
f(x
n
) = −∞.
Vậy f(D)
+
bị chặn dưới. Đặt t bằng cận dưới của tập này. Theo định
nghĩa của infimum, t cũng là infimum của hàm f trên D. Do vậy tồn tại
{x

x∈D
f(x) (P )
được gọi là bài toán tối ưu không ràng buộc.
Cho các hàm h
1
, ..., h
k
: D → R, g
1
, ..., g
m
: D → R. Bài toán
min
x∈D
0
f(x) (CP )
với
D
0
= { x ∈ D | g
i
(x) ≤ 0, h
j
(x) = 0, ∀ i = 1, m; j = 1, k }
được gọi là bài toán tối ưu có ràng buộc. Tập D
0
được gọi là tập chấp
nhận được.
Định nghĩa 2.2. Điểm x
0

hợp
φ(x) = f(x) + h(c(x)) (2.1)
với f(x) : R
n
→ R
1
, c(x) : R
n
→ R
m
là các hàm trơn thuộc lớp C
1
, còn
h(c) : R
m
→ R
1
là các hàm lồi nhưng không trơn thuộc lớp C
0
và ở đây
ta nghiên cứu hàm h(c) có dạng
h(c) = max
i
c
T
h
i
+ b
i
(2.2)


λ
i
= 1, λ ≥ 0, c
i
< max
i
c
i
⇒ λ
i
= 0 }.
∂c
∞
= { λ : c = 0 ⇒

λ
i
= 1
|c
i
| < c
i

∞
⇒ λ
i
= 0
|c
i


là dãy định hướng với δ
(k)
↓ 0 và s
(k)
→ s ( tức là
x
(k)
= x

+ δ
(k)
s
(k)
).
Theo khai triển Taylor ta có
f
(k)
= f

+ δ
(k)
g
T
s
(k)
+ 0(δ
(k)
)
trong đó g

i
(x

). Vì thế c
(k)
→ c

là dãy định hướng
trong R
m
với
c
(k)
− c

δ
(k)
→ A
T
s.
Từ Bổ đề 1.6 với h(c) ta có
lim
k→∞
φ
(k)
− φ

δ
(k)
= max

λ) ≥ 0, ∀s : s = 1.
Đây là điều kiện cần cấp 1 đối với cực tiểu địa phương và cũng giống
như (1.10), nó có thể được hiểu là đạo hàm theo mọi hướng là không
âm. Một lần nữa ta đưa ra kết quả tương tự là
0 ∈ ∂φ(x
∗
) = { γ : γ = g + Aλ, ∀λ ∈ ∂h }
x=x
∗
. (2.4)
24
Do đó tập ∂φ
∗
xác định, là tập lồi, compact nhưng không khả dưới vi
phân vì φ có thể không là hàm lồi.
Để phát biểu điều kiện (2.4) theo một cách khác, ta đưa ra hàm
Lagrange
L(x, λ) = f(x) + λ
T
c(x).
Khi đó một phát biểu tương tự (2.4) là
Định lý 2.3. (Điều kiện cần cấp một)
Nếu x
∗
là cực tiểu của φ(x) thì tồn tại một véctơ λ
∗
∈ ∂h
∗
thoả mãn
∇L(x

λ
∗
}. (2.6)
Định nghĩa 2.3. G
∗
là tập các phương tiếp xúc chấp nhận được của X
tại x
∗
( tức là nếu lấy s ∈ G
∗
thì tồn tại một dãy định hướng x
(k)
→ x
∗
với x
(k)
∈ X sao cho s
(k)
→ s trong đó s
(k)

2
= 1 ).
Nhận thấy các phương này liên quan chặt chẽ tới tập G
∗
là tập các hướng
tiếp xúc có độ dốc 0, tức là
G
∗
= { s : max