1

MỤC LỤC

Mục lục
Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
2

1 Các điều kiện cần và đủ cực trị cho bài toán tối ưu
không ràng buộc
4
1.1. Các điều kiện tối ưu tổng quát . . . . . . . . . . . . . . . . . 4
1.2. Điều kiện tối ưu cho hàm một biến số và các ví dụ minh họa . 8
2 Các điều kiện cần và đủ cực trị cho bài toán
ràng buộc bất đẳng thức
2.1. Điều kiện tối ưu dạng hình học . . . . . . . . . .
2.2. Điều kiện tối ưu dạng Fritz John . . . . . . . . . .
2.3. Điều kiện tối ưu dạng Karush-Kuhn-Tucker . . . .

tối ưu với
13
. . . . . . 13
. . . . . . 17
. . . . . . 24

3 Các điều kiện cực trị cho bài toán tối ưu với ràng
đẳng thức và bất đẳng thức
3.1. Điều kiện tối ưu dạng hình học . . . . . . . . . . . . .
3.2. Điều kiện tối ưu dạng Fritz John . . . . . . . . . . . . .

32
36
43
44


2

MỞ ĐẦU

Nghiên cứu các điều kiện cần và đủ cực trị là một trong những hướng
nghiên cứu quan trọng của Lý thuyết tối ưu. Hướng nghiên cứu này hiện
nay vẫn đang được nhiều nhà toán học để ý đến. Điều kiện cần cực trị
cho phép chúng ta thu hẹp miền tìm kiếm nghiệm, trong khi đó các điều
kiện đủ lại chỉ ra các điểm cực trị (nếu điểm đó thoả điều kiện đủ). Hơn
thế, việc nghiên cứu các điều kiện tối ưu còn đưa đến những gợi ý tốt để
xây dựng các thuật giải tìm nghiệm tối ưu một cách hiệu quả.
Năm 1948, Fritz John thiết lập các điều kiện cần cực trị (FJ) cho bài
toán tối ưu với ràng buộc bất đẳng thức. Hạn chế lớn nhất của điều kiện
(FJ) là hàm mục tiêu (một yếu tố quan trọng của bài toán tối ưu) có
thể không có mặt trong điều kiện (FJ). Dưới một số điều kiện chính qui,
H. W. Kuhn và A. W. Tucker (1951) đã chứng minh được trong kết luận
của điều kiện Fritz John nhân tử Lagrange kết hợp với hàm mục tiêu là
dương và như vậy điều này cho phép hàm mục tiêu tham gia vào các điều
kiện cần. Thực ra các điều kiện tương tự như vậy đã được trình bày trong
luận văn thạc sỹ của Karush (1939). Tuy nhiên, vì các kết quả của Karush
không được công bố nên không được nhiều người biết đến. Chính vì thế,
các điều kiện đó vẫn được người ta gọi là điều kiện tối ưu Karush-KunhTucker (KKT). O. L. Mangasarian và S. Fromovitz (1967) đã phát triến
các điều kiện (FJ) và (KKT) cho bài toán tối ưu có ràng buộc đẳng thức
và bất đẳng thức (xem [3, 4]).

CHƯƠNG 1
CÁC ĐIỀU KIỆN CẦN VÀ ĐỦ CỰC TRỊ CHO BÀI TOÁN
TỐI ƯU KHÔNG RÀNG BUỘC

Trong chương này, chúng tôi hệ thống và nghiên cứu một số khái niệm,
tính chất liên quan đến điều kiện cần và đủ cực trị cho bài toán tối ưu
không ràng buộc.
1.1. Các điều kiện tối ưu tổng quát

1.1.1 Định nghĩa. Điểm x¯ được gọi là điểm cực tiểu (toàn cục) của f
nếu f (¯
x) f (x) với mọi x ∈ Rn . Nếu tồn tại một lân cận U của x¯ mà
f (¯
x) f (x) (f (¯
x) < f (x)) với mỗi x ∈ U , thì được gọi là điểm cực tiểu
địa phương (tương ứng, cực tiểu địa phương chặt ) của f .
1.1.2 Định lý. Giả sử f : Rn → R là một hàm số khả vi tại x¯ và
d ∈ Rn là một véctơ thoả mãn điều kiện ∇f (¯
x)T d < 0, ở đây ∇f (¯
x) là
ma trận Jacobian của f tại x¯ và ∇f (¯
x)T là ma trận chuyển vị của ma
trận ∇f (¯
x). Khi đó, tồn tại δ > 0 thoả mãn f (¯
x + λd) < f (¯
x) với mỗi
λ ∈ (0, δ).
Chứng minh. Vì f khả vi tại x¯ nên
f (¯
x + λd) = f (¯

x) = 0.
Chứng minh. Ta chứng minh bằng phương pháp phản chứng. Giả sử ngược
lại ∇f (¯
x) = 0. Lấy d = −∇f (¯
x). Ta có ∇f (¯
x)T d = − ∇f (¯
x) 2 < 0.
Theo Định lý 1.1.2, tồn tại δ > 0 sao cho f (¯
x + λd) − f (¯
x) < 0 với mỗi
λ ∈ (0, δ). Điều này mâu thuẫn với giả thiết x¯ là điểm cực tiểu địa phương
của f . Do đó ∇f (¯
x) = 0.
1.1.4 Định lý. Giả sử f : Rn → R là một hàm khả vi hai lần tại x¯.
Khi đó, nếu x¯ là một điểm cực tiểu địa phương của f thì ∇f (¯
x) = 0
và H(¯
x) là nửa xác định dương, ở đây H(¯
x) là ma trận Hessian của f
tại x¯.
Chứng minh. Lấy d ∈ Rn . Ta có
f (¯
x + λd) = f (¯
x) +λ∇f (¯
x)T d + 21 λ2 dT H(¯
x)d
+λ2

d



f (¯
x) với λ > 0 đủ nhỏ.

0

với mọi λ > 0 đủ nhỏ. Cho λ → 0, ta được dT H(¯
x)d 0 với d ∈ Rn bất
kỳ. Nghĩa là ma trận Hessian H(¯
x) là nửa xác định dương.


6

1.1.5 Định lý. Giả sử f : Rn → R là một hàm khả vi hai lần tại x¯.
Nếu ∇f (¯
x) = 0 và H(¯
x) là ma trận xác định dương, thì x¯ là một điểm
cực tiểu địa phương chặt của f .
Chứng minh. Do f là hàm khả vi hai lần tại x¯, với mỗi x ∈ Rn , ta có
f (x) = f (¯
x) + ∇f (¯
x)T (x − x¯) + 12 (x − x¯)T H(¯
x)(x − x¯)
2
+ x − x¯ α(¯
x; x − x¯),

(1.3)


với mọi x, y ∈ Rn và t ∈ [0, 1].
(ii) Cho f : Rn → R là một hàm khả vi tại x¯. Hàm f được gọi là giả lồi
tại x¯ nếu từ ∇f (¯
x)(x − x¯)

0 ta suy ra f (x)

f (¯
x). Ta nói f là giả lồi

chặt tại x¯ nếu f (x) > f (¯
x) với mọi x ∈ Rn thoả mãn ∇f (¯
x)(x − x¯) 0
và x = x¯. Hàm f được gọi là giả lõm (giả lõm chặt ) tại x¯ nếu −f là
giả lồi (tương ứng, giả lồi chặt ) tại x¯.
(iii) Cho S là một tập con mở trong Rn và f : S → R là một hàm số khả
vi. Hàm f được gọi là giả lồi nếu mỗi x1 , x2 ∈ S với ∇(x1 )T (x2 −x1 ) 0,
ta có f (x2 )

f (x1 ). Hàm f được gọi là giả lồi chặt nếu với x1 , x2 ∈


7

S, x1 = x2 thoả mãn ∇f (x1 )T (x2 − x1 ) 0, ta có f (x2 ) > f (x1 ). Hàm f
được gọi là giả lõm (giả lõm chặt ) nếu hàm −f là giả lồi (tương ứng,

giả lồi chặt).
(iv) Cho S là một tập con lồi của Rn và f : S → R. Ta nói rằng f là
hàm tựa lồi nếu

x).
b) Trường hợp x¯ = −1. Vì f (x) đạt giá trị nhỏ nhất tại điểm duy nhất
x¯ = −1 nên f (x) > f (¯
x).
c) Trường hợp x¯ > −1. Khi đó, ∇f (¯
x) > 0. Do đó, từ (1.1) ta suy ra
x > x¯ > −1. Vì f (x) là hàm tăng ngặt trên (−1, +∞) nên f (x) > f (¯
x).
Như vậy f (x) là hàm giả lồi chặt tại x¯. Bây giờ ta chứng minh f (x) không
lồi. Lấy x1 = −3, x2 = −5 và t = 1/2 ∈ [0, 1]. Ta có
f (1 − t)x1 + tx2 = f (−4) = −4e−4
>

1
2

− 3e−3 − 5e−5

= (1 − t)f (x1 ) + tf (x2 ).


8

Điều này chứng tỏ f (x) không phải là hàm lồi.
1.1.9 Chú ý. Hàm f (x) = xex ở trên được lấy từ [5, p. 92], ở đó f được
dùng để minh hoạ cho hàm giả lồi tại mọi điểm mà không lồi.
1.1.10 Ví dụ. Hàm f : R → R cho bởi f (x) = 0 với mọi x ∈ R là một
hàm lồi trên R, nhưng không giả lồi chặt tại bất kỳ x¯ ∈ R. Thật vậy, với
mọi x1 , x2 ∈ R và t ∈ [0, 1], ta có
f (1 − t)x1 + tx2 ) = 0 = (1 − t)f (x1 ) + tf (x2 ).

Chứng minh. Giả sử x¯ là một điểm cực tiểu địa phương của f và không xẩy
ra trường hợp f (j) (¯
x) = 0 với mọi j = 1, 2... Khi đó, tồn tại một số tự nhiên


9

n (n 2) sao cho f (n) (¯
x) = 0 và f (j) (¯
x) = 0 với mọi j = 1, 2, ..., n − 1.
Lấy h ∈ R bất kỳ. Khai triển Taylor trong lân cận của x¯, ta có
f (¯
x + th) − f (¯
x) =

f (n) (ξt )
(th)n ,
n!

với t > 0 đủ nhỏ và ξt nằm giữa x¯ và x¯ + th. Vì x¯ là một điểm cực tiểu
địa phương của f nên f (¯
x + th) − f (¯
x)
0 với mọi t > 0 đủ nhỏ. Do
đó f (n) (ξt )hn 0 với mọi t > 0 đủ nhỏ. Cho t → 0+ , f (n) (¯
x)hn 0 với
mọi h ∈ R. Từ đó ta suy ra n là chẵn và f (n) (¯
x) > 0. Định lý được chứng
minh.
Tiếp theo chúng ta sẽ chỉ ra rằng điều kiện f (j) (¯

2 − 2
f (x) = − 3 e x = P3 ( )e x .
x
x

Mặt khác,
1
e x2

1
,
x2

∀x = 0.

Do đó,
0

f (x) − f (0)
1/|x|
=
1
x−0
e x2

|x|,

∀x = 0.



P ( )e x2
nếu x = 0,
k+2
(k)
x
f (x) =



 0
nếu x = 0.
Khi đó, với x = 0, ta có
1
−
1
2
1
1
f (k+1) (x) = − 2 Pk ( ) + 3 Pk ( ) e x2
x
x
x
x
1
1 − 2
= Pk+3 ( )e x .
x
1
Vì e x2




11

1.2.3 Định lý. (Xem [1]). Cho hàm f : R → R có đạo hàm liên tục
đến cấp n (n chẵn, n > 0) trên một lân cận của điểm x¯. Khi đó, nếu
f (n) (¯
x) > 0 và f (j) (¯
x) = 0 với mọi j=1,2...,n-1, thì x¯ là điểm cực tiểu
địa phương chặt của hàm f .
Chứng minh. Vì f (¯
x) = f (¯
x) = ... = f (n−1) (¯
x) = 0 khai triển Taylor
hàm f trong lân cận U bất kỳ của x¯ ta có
f (n) (ξ)
(x − x¯)n ,
f (x) − f (¯
x) =
n!

x = x¯,

(1.5)

với ξ nằm giữa x¯ và x. Mặt khác, vì n chẵn nên (x − x¯)n > 0 với mọi
x = x¯. Vì f (n) (¯
x) > 0 và f (n) liên tục tại x¯ nên tồn tại một lân cận U của
x¯ sao cho f (n) (x) > 0 với mọi x ∈ U . Ta có thể chọn lân cận lồi U đủ nhỏ
để (1.5) đúng trong U . Với x ∈ U \{¯

4k
k
4k
k
√
1
2+2
k , ở đây xk :=
,
→ x¯ khi k → ∞. Do đó, x¯ không phải là
2
k
4k
điểm cực tiểu địa phương của hàm f . Lấy d = (d1 , d2 ) ∈ R2 . Ta sẽ chứng
minh ϕd đạt cực tiểu địa phương tại 0. Xét hai trường hợp sau:


12

Trường hợp 1: d1 = 0. Khi đó, ta có ϕd (t) = t4 d42 0 = ϕd (0) với mọi
t ∈ R. Do đó, ϕd đạt cực tiểu tại 0.
Trường hợp 2: d1 = 0. Khi đó, ϕd (t) = t4 d42 + t2 (2d21 − 3d1 d22 t) với mọi
t ∈ R. Vì lim(2d21 − 3d1 d22 t) = 2d21 > 0, nên tồn tại δ > 0 sao cho
2d21

t→0
2
3d1 d2 t >

−

được gọi là một hướng chấp nhận được.
(ii) Cho f : Rn → R và x¯ ∈ R. Tập hợp
F := d ∈ Rn | ∃δ > 0 : f (¯
x + λd) < f (¯
x), ∀λ ∈ (0, δ)

được gọi là nón các hướng giảm của hàm f tại x¯. Mỗi d ∈ F được gọi là
một hướng giảm của f tại x¯.


14

2.1.2 Nhận xét. Từ Định lý 1.1.2, ta suy ra rằng nếu ∇f (¯
x)T d < 0 thì
d là một hướng giảm của f tại x¯. Điều này có nghĩa là
F0 := d : ∇f (¯
x)T d < 0 ⊂ F.

2.1.3 Định lý. Cho f : Rn → R là một hàm số khả vi tại x¯ ∈ S . Khi
đó, nếu x¯ là một nghiệm địa phương của bài toán (PI ), nghĩa là tồn
tại U ∈ N (¯
x) sao cho f (x) f (¯
x) với mọi x ∈ U ∩ S , thì F0 ∩ D = ∅.
Ngược lại, nếu F0 ∩ D = ∅, f là giả lồi tại x¯ và tồn tại ε > 0 sao cho
d = (x − x¯) ∈ D với mọi x ∈ S ∩ Bε (¯
x), thì x¯ là một nghiệm địa phương
của bài toán (PI ).
Chứng minh. Ta sẽ chứng minh định lý bằng phương pháp phản chứng.
Giả sử tồn tại một véctơ d ∈ F0 ∩ D. Theo Định lý 1.1.2, tồn tại δ1 > 0
sao cho

2.1.4 Bổ đề. Cho f : Rn → R là một hàm số khả vi tại x¯ ∈ Rn . Khi
đó,
F 0 ⊂ F ⊂ F0 ,
ở đây F0 := d ∈ Rn \{0} : ∇f (¯
x)T d 0 . Hơn nữa, nếu f là một hàm
số giả lồi tại x¯ thì F = F0 ; nếu f là một hàm số giả lõm chặt tại x¯ thì
F = F0 .


15

Chứng minh. Theo Nhận xét 2.1.2, F0 ⊂ F . Bây giờ ta chứng minh
F ⊂ F0 . Thật vậy, lấy d ∈ F . Theo định nghĩa của tập F , ta có d = 0 và
tồn tại δ > 0 sao cho f (¯
x + λd) < f (¯
x) với mọi λ ∈ (0, δ). Từ đó ta suy
ra
f (¯
x + λd) − f (¯
x)
∇f (¯
x)T d = lim+
0,
λ
λ→0
tức là d ∈ F0 . Vậy F ⊂ F0 .
Giả sử f là giả lồi tại x¯. Vì F0 ⊂ F nên để chứng minh F = F0 , ta chỉ
cần chứng minh F ⊂ F0 . Lấy d ∈ F . Khi đó, tồn tại δ > 0 sao cho
f (¯
x + λd) < f (¯

định nghĩa của tập F0 ta suy ra d = 0 và ∇f (¯
x)T d 0. Vì f là một hàm
số giả lõm chặt nên nếu ∇f (¯
x)T (x − x¯) 0 và x = x¯ thì f (x) < f (¯
x).
Mặt khác, ∇f (¯
x)T (¯
x + λd) − x¯ = ∇f (¯
x)T (λd) = λ∇f (¯
x)T d
0 và
x¯ + λd = x¯ với mọi λ > 0. Do đó f (¯
x + λd) < f (¯
x) với mọi λ > 0. Điều
này chứng tỏ d ∈ F . Vậy F = F0 nếu f là một hàm số giả lõm chặt.
Tiếp theo ta xét tập
S = {x ∈ X : gi (x)

0,

∀i = 1, ..., m},

ở đây X là một tập con mở khác rỗng của Rn và gi : Rn → R (i = 1, ..., m).
Với x¯ ∈ S , ta gọi I := {i : gi (¯
x) = 0} là tập các chỉ số hoạt của S tại
điểm x¯.


16



∀λ ∈ (0, δ2 ) i ∈ I.

(2.6)

Hơn nữa, vì d ∈ G0 nên ∇gi (¯
x)T d < 0 với mọi i ∈ I và d = 0. Theo
Định lý 1.1.2, tồn tại δ3 > 0 sao cho
gi (¯
x + λd) < gi (¯
x) = 0,

∀λ ∈ (0, δ3 ), i ∈ I.

(2.7)

Từ (2.5), (2.6) và (2.7), ta suy ra x¯ + λd ∈ S với mọi λ ∈ (0, δ), ở đây
δ = min{δ1 , δ2 , δ3 } > 0. Điều này có nghĩa là d ∈ D. Vậy ta đã chứng
minh được G0 ⊂ D.
Tiếp theo chúng ta chứng minh D ⊂ G0 . Lấy d ∈ D. Ta sẽ chứng minh
d ∈ G0 bằng phương pháp phản chứng. Thật vậy, giả sử d ∈
/ G0 . Khi đó,
tồn tại i0 ∈ I sao cho ∇gi (¯
x)T d > 0. Vì thế nên gi0 (¯
x + λd) > gi0 (¯
x) = 0
với mọi λ > 0 đủ nhỏ. Từ đó ta suy ra x¯ + λd ∈
/ S với mọi λ > 0 đủ nhỏ.
Điều này mâu thuẫn với giả thiết d ∈ D. Vậy d ∈ G và do đó D ⊂ G0 .
Giả sử với mỗi i ∈ I , hàm số gi là giả lồi chặt tại x¯ và d ∈ D. Ta cần

x¯ + λd ∈ S với mọi λ > 0 đủ nhỏ. Vậy d ∈ D.
2.1.6 Định lý. Xét bài toán (PI ), trong đó S = {x ∈ X : gi (x) 0; i =
1, ..., m}. Giả sử x¯ ∈ S và I := {i ∈ 1, ..., m : gi (¯
x) = 0}. Giả sử f và
gi (i ∈ I) là các hàm số khả vi tại x¯ và gj (j ∈
/ I) là các hàm số liên
tục tại x¯. Khi đó, nếu x¯ là một nghiệm địa phương của bài toán (PI )
thì F0 ∩ G0 = ∅. Ngược lại, nếu F0 ∩ G0 = ∅, f là hàm số giả lồi tại x¯
và tồn tại ε > 0 sao cho gi (i ∈ I) là giả lồi chặt trên Bε (¯
x) thì x¯ là
một nghiệm địa phương của bài toán (PI ).
Chứng minh. Giả sử x¯ là một nghiệm địa phương của bài toán (PI ). Theo
Định lý 2.1.3, F0 ∩ D = ∅. Mặt khác, theo Bổ đề 2.1.5, G0 ⊂ D. Do đó,
F0 ∩ G0 = ∅.

(2.8)

Giả sử F0 ∩G0 = ∅, f giả lồi tại x¯ và tồn tại ε > 0 sao cho các hàm gi , i ∈ I
giả lồi chặt trên Bε (¯
x). Không mất tính tổng quát ta có thể giả thiết
n
S = {x ∈ R : gi (x) 0, i ∈ I}. Hơn thế, vì gi (i ∈ I ) là các hàm số giả
lồi chặt trên Bε (¯
x) nên các tập mức dưới lev0 gi := {x ∈ Rn : gi (x) 0}
(i ∈ I ) là lồi địa phương tại x¯, nghĩa là tồn tại ε > 0 sao cho lev0 gi ∩Bε (¯
x)
(i ∈ I ) là tập lồi. Do gi (i ∈ I ) là các hàm số giả lồi chặt tại x¯, theo
Bổ đề 2.1.5, G0 = D. Vì vậy ta có F0 ∩ D = ∅ và f giả lồi tại x¯. Theo
Định lý 2.1.3, x¯ là một nghiệm địa phương của bài toán (PI ).
2.2. Điều kiện tối ưu dạng Fritz John

Điều này mâu thuẫn với cT x > 0. Từ đó ta suy ra (h1 ) vô nghiệm nếu
(h2 ) có nghiệm.
Giả sử (h2 ) vô nghiệm. Ta sẽ chứng minh (h1 ) có nghiệm bằng cách sử
dụng Định lý tách các tập lồi. Thật vậy, Ω := x ∈ Rn : x = AT y, y 0
là một tập con lồi đóng khác rỗng của Rn và c ∈ Ω. Theo Định lý tách
các tập lồi, tồn tại p ∈ Rn và α ∈ R sao cho pT c > α và pT x α với mọi
x ∈ Ω. Vì 0 ∈ Ω nên α 0 và pT c > 0. Chú ý rằng
α

pT AT y = y T Ap,

∀y

0.

(2.9)

Vì y 0 là tuỳ ý nên từ (2.9) ta suy ra Ap 0. Vậy p ∈ Rn thoả mãn
cT p > 0 và Ap 0, nghĩa là p là một nghiệm của (h1 ).
2.2.2 Bổ đề. (Định lý Gordan). Cho A là một ma trận cấp m × n. Khi
đó, một và chỉ một trong hai hệ sau đây có nghiệm:
x ∈ Rn .

Ax < 0,
AT y = 0,

y

0,


m
T

A y¯ = 0,

y¯

0,

y¯i = 1,

y¯ ∈ Rm .

i=1

Từ đó ta suy ra y¯ là một nghiệm của (h4 ) và do đó mâu thuẫn với giả
thiết (h4 ) vô nghiệm. Vậy (h3 ) có nghiệm.
2.2.3 Định lý. (Điều kiện cần cực trị dạng Fritz John).(xem [2]) Cho
X là một tập con mở khác rỗng của Rn và f : Rn → R, gi : Rn → R
(i=1,...,m). Đặt
S = x ∈ X : gi (x)

0,

i = 1, ..., m .

Giả sử x¯ ∈ S , I := i ∈ {1, 2, ..., m} : gi (¯
x) = 0 , và f, gi (i ∈ I) là
các hàm khả vi tại x¯; gi (i ∈
/ I) là hàm liên tục tại x¯. Khi đó, nếu x¯ là

u0 , ui

0,

và (u0 , u) = (0, 0) (i = 1, ...m),
ở đây u = (u1 , u2 , ..., um ).


20

Chứng minh. Vì x¯ là nghiệm địa phương của bài toán (PI ) nên, theo
Định lý 2.1.6; F0 ∩G0 = ∅, tức là không tồn tại d ∈ Rn sao cho ∇f (¯
x)T d

chấp nhận được của bài toán ban đầu (P F ). Điều kiện
m

u0 ∇f (¯
x) +

ui ∇gi (¯
x) = 0,
i=1

(u0 , u)

(0, 0),

và (u0 , u) = (0, 0) (i = 1, ...m),


21

được gọi là điều kiện chấp nhận được của bài toán đối ngẫu (DF ). Điều
kiện ui gi (¯
x) = 0 với i = 1, ..., m được gọi là điều kiện độ lệch bù (CS).
Điều kiện bao gồm (P F ), (DF ) và (CS) được gọi là điều kiện Fritz John
(F J) cho bài toán (PI ). Điểm x¯ mà tồn tại nhân tử Lagrange (¯
u0 , u¯) sao
cho (¯
x, u¯0 , u¯) thoả mãn điều kiện (F J) được gọi là điểm Fritz John.
2.2.5 Nhận xét. Điều kiện Fritz John có thể viết dưới dạng sau
u0 ∇f (¯
x) + ∇g(¯

Chứng minh. (i) Giả sử các giả thiết trong (i) là đúng. Vì x¯ là một điểm
(F J) nên, theo Bổ đề 2.2.2, ta có F0 ∩ G0 = ∅. Hạn chế miền ràng buộc
là Bε (¯
x) ∩ S˜ và lập luận tương tự như trong Định lý 2.1.6, ta suy ra x¯ là
một nghiệm địa phương của (PI ).


22

(ii) Ta có F0 ∩ G0 = ∅. Theo Bổ đề 2.1.5, D = G0 . Do đó F0 ∩ D = ∅.
Giả sử x ∈ S = S˜. Vì gi (x)
gi (¯
x) với moi i ∈ I , nên từ giả thiết gi
(i ∈ I ) là tựa lồi tại x¯ ta có
gi x + λ(x − x¯) = gi (λx + (1 − λ)¯
x

max gi (x), gi (¯
x)} = gi (¯
x) = 0

với mọi λ ∈ [0, 1] và mọi i ∈ I . Điều này có nghĩa là d := (x − x¯) ∈ D.
Vì F0 ∩ D = ∅ nên ∇f (¯
x)T (x − x¯)
0. Vì f giả lồi tại x¯ nên ta suy
ra f (x) f (¯
x). Vậy x¯ là một nghiệm toàn cục của (PI ). Trong trường
hợp các giả thiết lồi đúng trên Bε (¯
x) ∩ S , lập luận tương tự trên với
x ∈ Bε (¯

−2
∇f (¯
x) = (2x1 − 6, 2x2 − 4)T = (−2, −2)T = −2 ,
4
∇g1 (x) = (2x1 , 2x2 ) =⇒ ∇g1 (¯
x) = (4, 2)T = 2 ,
1
∇g2 (x) = (1, 2) =⇒ ∇g2 (¯
x) = (1, 2)T = 2 .


23

Thay vào điều kiện Fritz John

x) + i∈I ui ∇gi (¯
x) = 0
u0 ∇f (¯
u0 , ui 0

(u0 , ui ) = (0, 0), i ∈ I,
ta có hệ

−2u0 + 4u1 + u2 = 0



−u0 + u1 + u2 = 0
u ,u ,u
0

0
2
3


(u0 , u2 , u3 ) = (0, 0, 0).
Vì hệ này vô nghiệm nên x¯ = (0, 2)T không phải là một điểm Fritz John.
Từ đó suy ra x¯ không phải là nghiệm tối ưu của bài toán (PI ).
√
c) Tương tự ta chứng minh được x¯ = (0, 0)T , x¯ = ( 5, 0)T , x¯ = (0, α)T
√
(α ∈ (0, 2)), x¯ = (α, 0)T (α ∈ (0, 5)), x¯ = (α, 2 − 21 α)T (α ∈ (0, 2)) và
x¯ = ( 5 − β 2 , β)T (β ∈ (0, 1)) đều không là điểm Fritz John và do đó
chúng không là nghiệm tối ưu của bài toán (PI ).
d) x¯ thỏa mãn gi (¯
x) < 0 (i = 1, 2, 3, 4). Khi đó, tập chỉ số hoạt I = ∅.
Do đó, x¯ là điểm Fritz John nếu và chỉ nếu ∇f (¯
x) = 0. Măt khác,
∇f (¯
x) = 0 ⇔ x¯ = (3, 2)T .

Rõ ràng x¯ = (3, 2)T không thoả mãn gi (¯
x) < 0 (i = 1, 2, 3, 4). Do đó, mọi
điểm x¯ thoả mãn gi (¯
x) < 0 (i = 1, 2, 3, 4) đều không là điểm Fritz John
và do đó chúng không phải là nghiệm địa phương của bài toán.
Như vậy, bài toán (PI ) có duy nhất một điểm Fritz John là x¯ = (2, 1)T .


24

x) = 0,
i∈I

0, i ∈ I.

ui

Ngoài các giả thiết nêu trên, nếu gi (i ∈ I) cũng khả vi tại x¯ thì các
điều kiện nêu trên có thể được viết tương đương dưới dạng sau:
ui ∇gi (¯
x) = 0,

∇f (¯
x) +
i∈I

ui gi (¯
x) = 0,
ui

0,

i = 1, ..., m,
i = 1, ..., m.


25

Chứng minh. Theo Định lý 2.2.3, tồn tại u0 ∈ R và ui ∈ R (i ∈ I) không
đồng thời bằng không sao cho

x) +

ui ∇gi (¯
x) = 0,
i∈I

ui gi (¯
x) = 0,

ui

0,

i = 1, ..., m,

x¯ ∈ S,

được gọi là điều kiện Karush-Kuhn-Tucker (KKT) cho bài toán (PI ).
Ta gọi điểm Karush-Kuhn-Tucker (KKT) là điểm x¯ sao cho tồn tại các
nhân tử Lagrange ui ∈ R (i ∈ I) thoả mãn điều kiện KKT.
2.3.3 Định lý. (Điều kiện đủ cực trị dạng Karush-Kuhn-Tucker).(xem [2])
Cho X là một tập con mở khác rỗng của Rn và f, gi : Rn → R
(i=1,...,m). Xét bài toán (PI ) với S = x ∈ X : gi (x)
0, i =
1, ..., m . Giả sử x¯ ∈ S là một điểm KKT của bài toán (PI ) và
I = i ∈ {1, 2, ..., m} : gi (¯
x) = 0 . Đặt
S˜ := x ∈ X : gi (x)

0,