i
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chương 1. Các kiến thức cơ bản về tập lồi và hàm lồi . . . . . . . . . 2
1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Chương 2. Điều kiện cực tiểu hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1. Bài toán quy hoạch lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1. Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.2. Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.3. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2. Tối ưu có ràng buộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1. Đối ngẫu Lagrange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Chương 3. Một số phương pháp giải bài toán quy hoạch lồi . . 27
3.1. Các thuật toán sử dụng đạo hàm bậc nhất . . . . . . . . . . 27
3.1.1. Thuật toán gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.2. Phương pháp chiếu Gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.3. Thuật toán chiếu dưới gradient xấp xỉ . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.1.4. Thuật toán Frank-Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2. Phương pháp Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3. Phương pháp hàm phạt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.1. Phương pháp hàm phạt điểm ngoài . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.2. Phương pháp hàm phạt điểm trong . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Kết luận. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
ii
LỜI CẢM ƠN
Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lòng

University Press in năm 2004.
Mục đích của bản luận văn này là để trình bày một số phương pháp
cơ bản nhất cho bài toán quy hoạch lồi. Cụ thể luận văn trình bày các
phương pháp sau: các phương pháp sử dụng đạo hàm bậc nhất, phương
pháp Newton và các phương pháp hàm phạt.
Luận văn gồm có 3 chương:
• Chương 1: Giới thiệu các kiến thức cơ bản nhất về giải tích lồi, đặc
biệt chú trọng vào phép chiếu vuông góc lên một tập lồi đóng và tính dưới
vi phân của hàm lồi; chúng được sử dụng trong các chương tiếp theo.
• Chương 2: Trình bày đối ngẫu Lagrange và áp dụng Định lý Krush -
Kuhn - Tucker, Định lý Kuhn - Tucker để giải bài toán quy hoạch lồi và
các định lý về sự tồn tại nghiệm tối ưu của bài toán quy hoạch lồi.
• Chương 3: Trình bày các phương pháp giải bài toán quy hoạch lồi như:
phương pháp dùng đạo hàm bậc nhất gradient, chiếu gradient và trường
hợp tổng quát của nó là chiếu dưới gradient xấp xỉ, thuật toán Frank -
Wolf, phương pháp Newton dùng đạo hàm bậc hai và các phương pháp
hàm phạt.
2
Chương 1
Các kiến thức cơ bản về tập lồi và
hàm lồi
Trong luận văn này, ta chỉ xét không gian hữu hạn chiều IR
n
với tích
vô hướng được ký hiệu là ., . và chuẩn tương ứng được ký hiệu là ..
Chương này trình bày một số kiến thức cơ bản nhất của giải tích lồi
sẽ được sử dụng ở chương sau. Nội dung của chương được trích dẫn chủ
yếu từ tài liệu tham khảo [1] và [3].
1.1. Tập lồi
Định nghĩa 1.1. Cho hai điểm a, b ∈ IR

n
: a
T
x = α},
trong đó a ∈ IR
n
là một vectơ khác 0 và α ∈ IR.
Định nghĩa 1.5. Cho a ∈ IR
n
là một vectơ khác 0 và α ∈ IR. Tập
{x : a
T
x ≥ α},
được gọi là nửa không gian đóng và tập
{x : a
T
x > α}
gọi là nửa không gian mở.
Định nghĩa 1.6. Một tập D được gọi là một tập lồi nếu
∀a, b ∈ D và 0 ≤ λ ≤ 1 ⇒ λa + (1 − λ)b ∈ D.
Định lí 1.1. Tập lồi là đóng với phép giao, phép cộng, phép nhân với một
số thực. Tức là, nếu C và D là hai tập lồi trong IR
n
thì C ∩D, λC + βD
cũng là các tập lồi.
Định nghĩa 1.7. Ta nói x là tổ hợp lồi của các điểm (vectơ) x
1
, , x
k
nếu

1
, , x
k
∈ D ⇒
k

j=1
λ
j
x
j
∈ D.
Định nghĩa 1.8. Một tập được gọi là tập lồi đa diện nếu nó là giao của
một số hữu hạn các nửa không gian đóng.
4
Định nghĩa 1.9. Bao lồi của một tập D là giao của tất cả các tập lồi
chứa D. Bao lồi của tập D được ký hiệu là coD.
Bao lồi của một tập D là tập lồi nhỏ nhất chứa D.
Định nghĩa 1.10. Thứ nguyên của một tập lồi D được cho bởi thứ nguyên
của đa tạp affine nhỏ nhất chứa D. Đa tạp affine này được gọi là bao affine
của D và được ký hiệu là aff D. Thứ nguyên của tập lồi D sẽ được ký hiệu
là dimD.
Định nghĩa 1.11. Một điểm a của một tập lồi D gọi là điểm trong tương
đối nếu với mọi x ∈ D đều có một số λ > 0 để cho a + λ(x −a) ∈ D. Tập
các điểm trong tương đối của D được ký hiệu riD.
Định nghĩa 1.12. Một tập D được gọi là nón nếu
∀λ > 0, ∀x ∈ D ⇒ λx ∈ D.
Một nón được gọi là nón nhọn nếu nó không chứa đường thẳng. Một nón
được gọi là nón lồi nếu nó đồng thời là tập lồi. Nếu nón lồi này lại là một
tập lồi đa diện thì ta nói nó là nón lồi đa diện.

0
) := {ω ∈ IR
n
: ω, x − x
0
 ≤ , ∀x ∈ D}
được gọi là nón pháp tuyến  của D tại x
0
.
Hiển nhiên 0 ∈ N
D
(x
0
) và dùng định nghĩa ta có N
D
(x
0
) là một nón lồi
đóng.
Trong chương 2 và chương 3, ta sẽ sử dụng các định lý tách tập lồi, đây
cũng là những định lý cơ bản nhất của giải tích lồi.
5
Định nghĩa 1.14. Cho hai tập C và D, ta nói rằng siêu phẳng
H := {x : v, x = λ}
(i) tách hai tập C và D nếu
v, a ≤ λ ≤ v, b, ∀a ∈ C, b ∈ D.
(ii) tách chặt C và D nếu:
v, a < λ < v, b, ∀a ∈ C, b ∈ D.
(iii) tách mạnh C và D nếu:
sup

x∈D
x − y.
Ta nói d
D
(y) là khoảng cách từ y đến D. Nếu tồn tại π ∈ D sao cho
d
D
(y) = y − π, thì ta nói π là hình chiếu (vuông góc) của y trên D và
ký hiệu là π = P
D
(y).
6
Theo định nghĩa, ta thấy rằng hình chiếu P
D
(y) của y trên D là
nghiệm của bài toán tối ưu
min
x∈D

1
2
x − y
2
: x ∈ D

.
Nói cách khác việc tìm hình chiếu của y trên D có thể đưa về việc tìm cực
tiểu của hàm toàn phương ||x − y||
2
trên D. Nếu D = ∅ thì d

D
(x)−P
D
(y)
2
≤ P
D
(x)−P
D
(y), x−y, ∀x, y ∈ IR
n
(tính đồng bức).
1.2. Hàm lồi
Trong phần này ta chỉ xét những hàm f không nhận giá trị −∞.
Định nghĩa 1.16. Một hàm số f xác định trên tập lồi D được gọi là
(i) lồi trên D nếu
f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y), ∀x, y ∈ D, 0 < λ < 1.
(ii) lồi chặt nếu
f(λx + (1 − λ)y) < λf(x) + (1 − λ)f(y), ∀x, y ∈ D, 0 < λ < 1.
(iii) lõm (lõm chặt) nếu −f là lồi (lồi chặt).
7
Định lí 1.4. Cho f và g là các hàm lồi trên tập lồi C và D tương ứng.
Khi đó các hàm số αf +βg, (∀α, β ≥ 0) và max{f, g} cũng lồi trên C ∩D.
Một hàm lồi có thể không liên tục tại một điểm trên biên miền xác
định của nó. Tuy nhiên, nó liên tục tại mọi điểm trong của tập đó theo
định lý sau:
Định lí 1.5. Một hàm lồi xác định trên tập lồi D thì liên tục tại mọi điểm
trong của D.
Tính chất sau đây đặc trưng cho một hàm lồi khả vi, và thuận lợi để
kiểm tra tính lồi của một hàm số. Ký hiệu f

n
nếu:
w, x −x
0
 ≤ f(x) − f(x
0
) + , ∀x ∈ IR
n
.
8
Tập hợp tất cả các −dưới gradient gọi là − dưới vi phân của hàm f tại
x
0
, kí hiệu là
∂

f(x
0
) := {w ∈ IR
n
: w, x − x
0
 ≤ f(x) − f(x
0
) + , ∀x ∈ IR
n
}.
Định nghĩa 1.18. Véctơ w ∈ IR
n
được gọi là dưới gradient của f tại

0
nếu ∂f(x
0
) = ∅.
Ví dụ 1.1. Cho D là một tập lồi, khác rỗng của không gian IR
n
. Xét hàm
chỉ trên tập D
δ
D
(x) :=

0 nếu x ∈ D,
+∞ nếu x /∈ D.
Với mọi x
0
∈ D ta có:
w ∈ ∂δ
D
(x
0
) ⇔ δ
D
(x) − δ
D
(x
0
) ≥ w, x − x
0
, ∀x ∈ D

n
thì nó có dưới vi phân tại mọi điểm, vì riIR
n
= IR
n
.
9
Định nghĩa 1.19. Ta gọi đạo hàm theo hướng d của một hàm số f (không
nhất thiết là lồi) tại điểm x là đại lượng
f

(x, d) := lim
λ→0
+
f(x + λd) − f(x)
λ
nếu giới hạn này tồn tại.
Định lí 1.8. Nếu f là một hàm lồi trên tập lồi D thì với mọi x ∈ D và
mọi d sao cho x + d ∈ D, đạo hàm theo hướng d của f tại x luôn tồn tại
và nghiệm đúng
f

(x, d) ≤ f(x + d) −f(x).
Ngoài ra với mỗi điểm x cố định, f

(x, .) là một hàm lồi trên tập lồi
{d : x + d ∈ D}.
Từ định lý này dễ dàng suy ra rằng nếu f khả vi thì
f



(f(¯x)) .
Ngược lại, nếu 0 ∈ ∂

(f(¯x)) thì ta có:
0, x − ¯x ≤ f(x) − f(¯x) + , ∀x ∈ D.
Chứng tỏ ¯x là − nghiệm của bài toán (P ).
Định nghĩa 1.21. Cho D là một tập lồi đóng khác rỗng trong IR
n
, x ∈ IR
n
và  ≥ 0 . Một điểm p
x
∈ D được gọi là  - chiếu của x trên D nếu p
x
là
một  - nghiệm của bài toán
min
y∈D

1
2
x − y
2

(Q)
nghĩa là:
1
2
x − p

x − y
2
⇔ min

1
2
x − y
2
+ δ
D
(y)

(1.3)
trong đó δ
D
(y) là hàm chỉ của y trên tập D. Đặt
f(y) :=
1
2
x − y
2
, x ∈ IR
n
.
11
Theo Định nghĩa 1.21, p
x
là  − nghiệm của bài toán (1.3). Từ Mệnh đề
1.4 ta được
0 ∈ ∂

0 ∈ {−x + p
x
} + N

D
(p
x
).
Suy ra
(x − p
x
) ∈ N

D
(p
x
) ⇔ x − p
x
, ω −p
x
 ≤ , ∀ω ∈ D.
Ngược lại, giả sử có (1.2). Ta có
x − P
D
(x)
2
= x − p
x

2


2
− 2.
Chứng tỏ p
x
là − chiếu của x trên D.
12
Chương 2
Điều kiện cực tiểu hàm lồi
Chương này trình bày một số kiến thức quan trọng phục vụ cho
chương 3. Đó là đối ngẫu Lagrange và áp dụng vào giải bài toán tối ưu lồi;
các định lý cơ bản như Định lý Karush - Kuhn - Tucker, Định lý Kuhn -
Tucker. Nội dung của chương chủ yếu được trích dẫn từ tài liệu tham khảo
[1].
2.1. Bài toán quy hoạch lồi
2.1.1. Các khái niệm
Cho D ⊆ IR
n
và f : IR
n
→ IR. Xét bài toán quy hoạch toán học
min{f(x) : x ∈ D}. (P )
Bài toán này được hiểu là hãy tìm một điểm x
∗
∈ D sao cho f(x
∗
) ≤ f(x)
với mọi x ∈ D. Mỗi điểm x
∗
∈ D được gọi là một phương án chấp nhận

∗
∈ D được gọi là lời giải tối ưu địa phương của
bài toán (P) nếu tồn tại một lân cận U của x
∗
sao cho
f(x
∗
) ≤ f(x), ∀x ∈ U ∩ D.
và x
∗
gọi là lời giải tối ưu toàn cục của (P) nếu
f(x
∗
) ≤ f(x), ∀x ∈ D.
2.1.2. Sự tồn tại nghiệm tối ưu
Xét bài toán tối ưu toàn cục (P ). Có 4 trường hợp tồn tại nghiệm tối
ưu của bài toán này
• D = ∅ (Không có nghiệm).
• f không bị chặn dưới trên D

inf
x∈D
f(x) = −∞

.
• inf
x∈D
f(x) < ∞ nhưng giá trị cực tiểu không đạt được trên D.
• tồn tại x
∗

+
(D) đóng, t
∗
∈ F
+
D nên tồn tại x
∗
∈ D sao cho f(x
∗
) = t
∗
. Chứng
tỏ x
∗
là một điểm cực tiểu của f trên D.
Định lí 2.2 (Weierstrass). Nếu D là tập compact và f nửa liên tục dưới
trên D, thì bài toán (P ) có nghiệm tối ưu.
Chứng minh. Đặt α := inf
x∈D
f(x). Theo định nghĩa có một dãy {x
k
} ⊂
D sao cho lim
k→+∞
f(x
k
) = α. Do D compact nên có một dãy con hội tụ
về x
0
∈ D, không giảm tính tổng quát có thể coi x

), (2.2)
trong đó N
D
(x
∗
) ký hiệu nón pháp tuyến của D tại x
∗
.
Chứng minh. ” ⇐ ” : Giả sử có (2.2). Khi đó tồn tại p
∗
sao cho
p
∗
∈ ∂f(x
∗
) ∩ (−N
D
(x
∗
)).
15
Do p
∗
∈ ∂f(x
∗
) nên
p
∗
, x −x
∗

∗
), x ∈ D}; G := {0} × D.
Cả E và G đều là tập lồi (do D và f lồi). Hơn nữa, G ∩ E = ∅. Áp dụng
định lý siêu phẳng tách tồn tại (u
0
, u) = 0 ∈ IR × IR
n
sao cho
u
0
t + u
T
x ≤ u
0
0 + u
T
y, ∀(t, x) ∈ E, y ∈ D (2.3)
Từ (2.3), cho t → +∞, ta thấy u
0
≤ 0. Cũng từ (2.3) nếu u
0
= 0 thì
u, x −y ≤ 0, ∀x, y ∈ D. (2.4)
Hiển nhiên, 0 ∈ D và bằng phép tịnh tiến ta có thể giả sử 0 ∈ intD. Theo
(2.4) ta có u = 0 (không xảy ra vì u
0
= 0). Do đó u
0
< 0. Chia cả 2 vế
của (2.3) cho −u

Do đó
f(x
∗
) − f(x) + u
T
(x − x
∗
) ≤ 0, ∀x ∈ D. (2.6)
Nếu x ∈ C, bằng cách lấy f(x) = ∞ nên từ (2.6) ta cũng nhận được
f(x
∗
) − f(x) + u
T
(x − x
∗
) ≤ 0, ∀x ∈ X.
nghĩa là u ∈ ∂f(x
∗
). Mặt khác, thay x = x
∗
vào (2.5), ta có
u
T
(y −x
∗
) ≥ 0, ∀y ∈ D.
Suy ra −u ∈ N
D
(x
∗

là tập lồi khác rỗng. Từ bài toán trên, ta định nghĩa
bài toán tối ưu khác có dạng
max{d(y) : y ∈ Y } (D)
trong đó Y ⊆ IR
m
.
Định nghĩa 2.2. Bài toán (D) được gọi là đối ngẫu của bài toán (P ) nếu
với mọi điểm chấp nhận được x của (P ) và mọi y chấp nhận được của
(D), ta có
f(x) ≥ d(y).
17
Bài toán (D) được gọi là đối ngẫu chính xác của bài toán (P ) nếu (D) là
bài toán đối ngẫu của (P ) và tồn tại x
∗
∈ (P ), y
∗
∈ (D) sao cho
f(x
∗
) ≤ d(y
∗
).
Từ Định nghĩa 2.2 ta thấy rằng, nếu bài toán (D) là đối ngẫu chính
xác của bài toán (P ) thì f(x
∗
) = d(y
∗
) và hiển nhiên (P ) cũng là đối ngẫu
chính xác của (D).
Xét bài toán (P ), ta định nghĩa hàm Lagrange


j=1
y
j
g
j
(x) ≤ f(x), ∀x ∈ X, ∀y ∈ Y.
Chứng tỏ (LD) là đối ngẫu của bài toán (P ).
Nhận xét 2.1. Nhìn chung, một cặp đối ngẫu chưa chắc đã là đối ngẫu
chính xác như ví dụ sau đây sẽ chỉ ra.
Ví dụ 2.1. Xét bài toán
min{f(x) = −x
2
, x ∈ X = [0, 2], x − 1 ≤ 0},
18
Ta thấy
f(1) = min f = −1.
Hàm Lagrange của bài toán là
L(x, y) = −x
2
+ y(x − 1), y ≥ 0, x ∈ X = [0, 2].
Ta thấy
max
y≥0
d(y) = 0.
Vậy cặp đối ngẫu là không chính xác.
Vậy cần thêm điều kiện gì để hai bài toán (P ) và (LD) là cặp đối ngẫu
chính xác? Ta có định lý sau:
Định lí 2.6 (Đối ngẫu chính xác). Giả sử
(i) (P ) có một lời giải tối ưu,

∗
), 0) ∈ A. Theo định lý tách tồn tại (α, y) = 0
thuộc IR × IR
n
sao cho:
αt + y
T
z ≥ αf(x
∗
), ∀(t, z) ∈ A. (2.7)
19
Do các hàm f và g
j
liên tục, bất đẳng thức trên đúng với mọi (t, z) ∈ A
(A là bao đóng của tập A). Mà (f(x), g(x)) ∈ A,
αf(x) + y
T
g(x) ≥ αf(x
∗
), ∀x ∈ X. (2.8)
Ta chỉ ra rằng (α, y) ≥ 0. Thực vậy, giả sử có chỉ số j thỏa mãn y
j
< 0.
Lấy (t
0
, z
0
) ∈ A. Điểm (t
0
, z) ≡ (t

Xét bài toán (P ) định nghĩa bởi
min f(x)
với điều kiện
x ∈ D := {x ∈ X : g
j
(x) ≤ 0, h
i
(x) = 0, j = 1, , m, i = 1, , k}.
trong đó ∅ = X ⊆ IR
n
và f, g
j
, h
i
: IR
n
→ IR (∀j, i). Ta gọi bài toán (P )
là bài toán lồi nếu X là tập lồi đóng và các hàm f, g
j
là lồi, h
i
là hàm
affine.
Định lí 2.7 (Karush-Kuhn-Tucker). Giả sử (P ) là bài toán lồi. Nếu x
∗
là một nghiệm tối ưu của bài toán (P ) thì tồn tại λ
∗
i
≥ 0 (i = 0, 1, , m)
20

(x
0
) < 0 (i = 1, , m)
được thỏa mãn và các hàm affine h
i
(i = 1, , k) độc lập tuyến tính trên
X thì λ
∗
0
> 0 và các điều kiện đạo hàm triệt tiêu và điều kiện bù là điều
kiện đủ để điểm chấp nhận được x
∗
là nghiệm tối ưu của bài toán (P ).
Chứng minh. Giả sử x
∗
là một nghiệm tối ưu của bài toán (P ). Đặt
C := {(λ
0
, λ
1
, ··· , λ
m
, µ
1
, ··· , µ
k
) : (∃x ∈ X) :
f(x)−f(x
∗
) < λ

j
(j = 1, , k) không đồng thời bằng 0 sao cho
m

i=0
λ
∗
i
λ
i
+
k

j=1
µ
∗
j
µ
j
≥ 0, ∀(λ
0
, ··· , λ
m
, µ
1
, ··· , µ
k
) ∈ C. (2.9)
Nếu λ
0

j
= h
j
(x)(i = 1, , k)
21
và thay vào (2.9), cho  → 0 ta được:
λ
∗
0
f(x)+
m

i=1
λ
∗
i
g
i
(x)+
k

i=1
µ
∗
i
h
i
(x) ≥ λ
∗
0

∗
, µ
∗
) ≤ L(x, λ
∗
, µ
∗
), ∀x ∈ X.
Điều kiện đạo hàm triệt tiêu được chứng minh. Để chứng minh điều kiện
bù, ta thấy, do x
∗
là điểm chấp nhận được, g
j
(x
∗
) ≤ 0 với mọi j. Nếu có
chỉ số i sao cho g
i
(x
∗
) = ξ < 0, thì với mọi  > 0, ta có
(, , ξ, , , , 0, , 0) ∈ C (ξ ở vị trí i + 1).
Thay vào (2.9) và cho  → 0, ta có λ
∗
i
ξ ≥ 0. Nhưng vì ξ < 0, nên λ
∗
i
≤ 0.
Do đó, λ

j
(x
∗
) ≤
m

i=1
λ
∗
i
g
i
(x) +
k

j=1
µ
∗
j
h
j
(x), ∀x ∈ X.
(2.11)
Do λ
∗
0
= 0, nên xảy ra 2 trường hợp:
• Trường hợp 1: Tồn tại chỉ số i sao cho λ
∗
i

∗
i
g
i
(x
0
) +
k

j=1
µ
∗
j
h
j
(x
0
) < 0 (vô lý).
• Trường hợp 2: λ
∗
i
= 0 với mọi i và tồn tại j sao cho µ
∗
j
> 0. Ta có
0 =
k

j=0
µ

j
độc lập tuyến tính trên X, nên µ
∗
j
= 0 với mọi
j. Điều này mâu thuẫn với giả thiết λ
∗
i
và µ
∗
j
không đồng thời bằng 0. Do
đó λ
∗
0
> 0 và chia cả hai vế của (2.10) cho λ
∗
0
> 0, ta có thể giả sử hàm
Lagrange của bài toán (P ) có dạng:
L(x, λ, µ) = f(x) +
m

i=1
λ
i
g
i
(x) +
k


j=1
µ
∗
j
h
j
(x
∗
)
≤ f
0
(x) +
m

i=1
λ
∗
i
g
i
(x) +
k

j=1
µ
∗
j
h
j

).
Khi f và mọi hàm g
j
(j = 1, 2, m) đều khả vi thì điều kiện trên trở thành
0 = λ
∗
0
∇f
0
(x
∗
) +
m

j=1
λ
∗
j
∇g
j
(x
∗
) +
k

i=1
µ
∗
i
∇h

). (2.12)
Chứng minh. Khai triển Taylor của f tại x
∗
là:
f(x
∗
+ λd) = f(x
∗
) + λ∇f(x
∗
), d + o(λ||d||). (2.13)
Do x
∗
là cực tiểu địa phương của bài toán (P) nên
f(x
∗
+ λd) − f(x
∗
) ≥ 0, ∀λ > 0 đủ nhỏ.
Từ (2.13) ta được:
d
T
∇f(x
∗
) +
o(λd)
λ
≥ 0, ∀λ > 0 đủ nhỏ.
Suy ra (2.12).
Một điểm x

0
) là tập nghiệm của hệ phương
trình tuyến tính sau

∇h
i
(x
0
), d = 0, i = 1, , k
∇g
j
(x
0
), d = 0, j ∈ A(x
0
)