ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
Đặng Thị Khuyên
VỀ ĐIỀU KIỆN TỐI ƯU CẤP CAO
Chuyên ngành: TOÁN GIẢI TÍCH
Mã số: 60.46.01.02
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2013
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
Đặng Thị Khuyên
VỀ ĐIỀU KIỆN TỐI ƯU CẤP CAO
Chuyên ngành: TOÁN GIẢI TÍCH
Mã số: 60.46.01.02
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
PGS.TS ĐỖ VĂN LƯU
Thái Nguyên - Năm 2013
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, các kết
quả nghiên cứu nêu trong Luận văn này là hoàn toàn trung thực, chưa
từng được công bố trong bất kỳ một công trình của tác giả nào khác.
Thái Nguyên, tháng 4 năm 2013
Tác giả
Đặng Thị Khuyên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
LỜI CẢM ƠN
Luận văn này được hoàn thành tại trường Đại học Sư phạm - Đại học
Thái Nguyên. Tôi xin bày tỏ lòng biết ơn sâu sắc đối với thầy PGS.TS

2.1. Các kết quả bổ trợ . . . . . . . . . . . . . . . . . . . . . 20
2.2. Phân hoạch tập chỉ số của hàm mục tiêu . . . . . . . . . 22
2.3. Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . 28
2.4. Tiêu chuẩn điểm yên ngựa . . . . . . . . . . . . . . . . . 35
KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . 42
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
MỞ ĐẦU
1. Lí do chọn đề tài
Lý thuyết các điều kiện tối ưu nói chung và các điều kiện tối ưu cấp
cao nói riêng là các bộ phận quan trọng của lý thuyết các bài toán tối ưu.
Khái niệm cực tiểu chặt cấp cao đã được M. R. Hestenes nghiên cứu từ
năm 1966 trong [5] và sau đó phát triển bởi L. Cromme, A. Auslender,
M. Studniarski, B. Jiménez, V. Novo,
Mới đây, B. Jiménez và V. Novo ([7], 2008) đã thiết lập các điều kiện
tối ưu cấp cao cho cực tiểu địa phương chặt cấp cao của bài toán tối ưu
không trơn với ràng buộc nón và ràng buộc tập dưới ngôn ngữ các đạo
hàm Studniarski trên và dưới. A. Gupta, A. Mehra và D. Bhatia ([3],
2011) đã thiết lập các điều kiện cần và đủ tối ưu cấp cao cho nghiệm
hữu hiệu địa phương chặt cấp m của bài toán tối ưu đa mục tiêu lồi với
ràng buộc bất đẳng thức bằng cách phân hoạch tập chỉ số của hàm mục
tiêu, lập các bài toán con và thiết lập mối quan hệ của nghiệm hữu hiệu
địa phương chặt cấp m của bài toán gốc với nghiệm của một trong các
bài toán con.
Lý thuyết các điều kiện tối ưu cấp cao đã và đang được nhiều tác giả
quan tâm nghiên cứu. Chính vì thế tôi chọn đề tài: "Về điều kiện tối ưu
cấp cao". Đây là đề tài có tính thời sự.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2

tối ưu cấp cao cho nghiệm hữu hiệu địa phương chặt cấp cao của bài
toán tối ưu đa mục tiêu lồi có ràng buộc bất đẳng thức bằng cách phân
hoạch tập chỉ số của hàm mục tiêu, lập các bài toán con và thiết lập mối
quan hệ của nghiệm hữu hiệu địa phương chặt cấp m của bài toán gốc
với một trong các bài toán con, các tính chất đặc trưng điểm yên ngựa
cho nghiệm hữu hiệu địa phương chặt cũng được trình bày trong chương
này.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Chương 1
ĐIỀU KIỆN CẦN VÀ ĐỦ CHO
CỰC TIỂU ĐỊA PHƯƠNG CHẶT
CẤP CAO
Chương 1 trình bày các điều kiện cần tối ưu cấp cao cho cực tiểu địa
phương chặt cấp cao của bài toán tối ưu với ràng buộc nón và ràng buộc
tập dưới ngôn ngữ đạo hàm Studniarski trên và dưới. Các điều kiện đủ
tối ưu cấp cao dưới ngôn ngữ đạo hàm Studniarski dưới trong trường
hợp hữu hạn chiều cũng được trình bày trong chương này. Các kết quả
được trình bày trong chương này là của B. Jiménez và V. Novo [7].
1.1. Các định nghĩa và khái niệm
Giả sử X là không gian định chuẩn, f : X → R và M ⊂ X. Xét bài
toán tối ưu
min {f(x) : x ∈ M}.
Ta nhắc lại khái niệm cơ bản sau:
Điểm x
0
∈ M gọi là điểm cực tiểu địa phương của f trên M nếu tồn
tại lân cận U của x
0
sao cho f(x)  f(x

Ta nhắc lại các khái niệm cơ bản sau:
Tập K ⊆ X được gọi là tập lồi, nếu K chứa mọi đoạn thẳng đi qua
hai điểm bất kỳ của nó. Điều này có nghĩa là, K lồi khi và chỉ khi
∀x, y ∈ K, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ) y ∈ K.
Tập K ⊂ X được gọi là nón có đỉnh tại 0 nếu với
∀x ∈ K, ∀λ > 0 ⇒ λx ∈ K.
Nón K có đỉnh tại 0 được gọi là lồi nếu K là một tập lồi, tức là
∀x, y ∈ K, λ, µ > 0 ⇒ λx + µy ∈ K.
Với M là một tập con của X, ta kí hiệu intM, clM, coneM lần lượt là
phần trong của M, bao đóng của M, nón sinh bởi M và B(x
0
, ε) là hình
cầu mở có tâm tại x
0
, bán kính ε.
Định nghĩa 1.2. a) Nón tiếp liên của tập M tại x
0
∈ M là
T (M, x
0
) =

v ∈ X : ∃t
n
→ 0
+
, x
n
∈ M, x
n

f(x
0
, v) = lim inf
(t,u)→
(
0
+
,v
)
f (x
0
+ tu) − f(x
0
)
t
k
(tương ứng
d
k
f(x
0
, v) = lim sup
(t,u)→
(
0
+
,v
)
f(x
0

0
+
,v
)
f (x
0
+ tu) − f(x
0
) − tdf(x
0
, u)
t
2
/2
.
(Trong đó: r là radian)
Định nghĩa 1.4. Hàm chỉ I
M
được xác định bởi
I
M
(x) =

0 nếu x ∈ M ,
+∞ nếu x /∈ M.
Cho hàm f : X → R ∪ {+∞}, chúng ta xét bài toán tối ưu sau:
min f(x)
g(x) ∈ −K,
x ∈ Q,
(1.1)

dg (x
0
, v) = lim
(t,u)→(0
+
,v)
g (x
0
+ tu) − g (x
0
)
t
.
Bây giờ ta giả sử g là khả vi Hadamard tại x
0
, tức là dg (x
0
, v) tồn tại
với mọi v ∈ X.
Bổ đề 1.1. Giả sử f : X → R ∪ {+∞} hữu hạn tại x
0
∈ X và v ∈ X.
(i) Nếu k > 1 và d
f(x
0
, v) > 0 thì d
k
f (x
0
, v) = +∞.

ngữ đạo hàm dưới.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
Định lý 1.1. Cho k  1. Nếu x
0
∈ Strl (k, f, G ∩ Q) thì
d
k
f (x
0
, v) > 0 (∀v ∈ C
0
(G, x
0
) ∩ T (Q, x
0
) \{0}),
trong đó C
0
(G, x
0
) = {v ∈ X : dg (x
0
, v) ∈ int cone (−K − g (x
0
))}.
Chứng minh. Giả sử
d
k
f (x

n
v
n
) − f (x
0
)
t
k
n
 0
bởi vì d
k
f (x
0
, v)  0. Do đó, với mỗi j ∈ N, ∃n
j
∈ N sao cho
f

x
0
+ t
n
j
v
n
j

− f (x
0

n
j
∈ G với mọi j đủ lớn. Do đó, x
0
+t
n
j
v
n
j
∈ G∩Q.
Mặt khác, theo giả thiết tồn tại α > 0 và δ > 0 sao cho
f (x) > f(x
0
) + αx − x
0

k
, ∀x ∈ G ∩Q ∩B (x
0
, δ) \{x
0
}.
Nói riêng, với x = x
0
+ t
n
j
v
n


k
.
Lấy giới hạn khi j → ∞ ta được v = lim
j→∞


v
n
j


= 0, mâu thuẫn với
v = 0.
Bây giờ ta chứng minh bao hàm thức (1.3). Lấy v ∈ C
0
(G, x
0
) . Khi đó,
dg (x
0
, v) ∈ int cone (−K − g (x
0
)) .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
Theo mệnh đề 2.3(ii) của Jiménez và Novo [9],
int cone (−K − g (x
0
)) = IT (−K, g (x

0
) , ∀u ∈ B (v, δ
0
) .
Lấy δ = min {δ
0
, ε}, ta có
g (x
0
+ tu) = g (x
0
) + t
g (x
0
+ tu) − g (x
0
)
t
∈ −K,
∀t ∈ (0, δ) , ∀u ∈ B (v, δ) .
Điều này kéo theo v ∈ IT (G, x
0
) và ta có điều phải chứng minh.
Định lý 1.2. Lấy k  1. Nếu x
0
∈ Strl (k, f, G ∩ Q) thì
d
k
(f + I
Q

inf
t∈(0,δ), u∈B(v,δ)
(f + I
Q
) (x
0
+ tu) − f (x
0
)
t
k
 0,
ta có
inf
t∈(0,1/n), u∈B(v,1/n)
f (x
0
+ tu) + I
Q
(x
0
+ tu) − f (x
0
)
t
k
 0, ∀n ∈ N.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
Theo tính chất của cận dưới đúng, với mỗi n ∈ N, ∃t

n
) − f (x
0
)
t
k
n
<
1
n
.
Từ đó ta có x
n
:= x
0
+ t
n
v
n
∈ Q, t
n
→ 0
+
và v
n
→ v. Bởi vì
v ∈ C
0
(G, x
0

0
) ∩ T (Q, x
0
) \{0}) vì khi v /∈
T (Q, x
0
) ta có
d
k
(f + I
Q
) (x
0
, v) = +∞
(bổ đề 1.1(ii))
(5) Định lý 1.2 áp dụng đơn giản cho tập Q được xác định bởi các đẳng
thức Q = h(S) bởi vì (f + I
Q
)(x) = f(h(y)) với h(y) = x và y ∈ S.
Bên ngoài Q, (f + I
Q
)(x) = +∞.
(6) Với k > 1, định lý 1.2 chỉ có nghĩa với những v ∈ X thỏa mãn
df (x
0
, v)  0. Thật vậy, nếu df (x
0
, v) > 0 thì d (f + I
Q
) (x

0
) = {v ∈ X : dg (x
0
, v) ∈ cl cone (−K − g (x
0
))},
C (f, x
0
) = {v ∈ X : df (x
0
, v)  0}.
Các tập này là các nón đóng.
Định lý 1.3. Cho k > 1. Nếu với mọi v ∈ C (G, x
0
) ∩ T (Q, x
0
) ∩
C (f, x
0
) \{0}, ta có
d
k
(f + I
Q
) (x
0
, v) > 0,
thì x
0
∈ Strl (k, f, G ∩ Q) .

k
(f + I
Q
) (x
0
, v)  d
k
(f + I
M
) (x
0
, v) .
Trường hợp k = 1 được trình bày trong định lý dưới đây. Định lý
này được chứng minh tương tự như định lý trên, ta chỉ áp dụng định lý
2.1(ii) của Studniarski [10] thay cho định lý 2.1(i) của Studniarski [10].
Định lý 1.4. Nếu với mọi v ∈ C (G, x
0
) ∩ T (Q, x
0
) \{0}, ta có
d (f + I
Q
) (x
0
, v) > 0,
thì x
0
∈ Strl (1, f, G ∩ Q) .
Chú ý rằng định lý không bị chặt hơn nếu ta giả thiết đúng với mọi
v ∈ C (G, x

2
) ∈ R
2
, G =

x : x
2
 x
2
1

, Q = {x : x
2
 0}
và x
0
= (0, 0). Ta có
d
2
(f + I
Q
) (x
0
, v) = 0,
với v = (1, 0) ∈ C (G, x
0
) ∩ T (Q, x
0
) và x
0

. Khi đó,
d
2
(f + I
Q
) (x
0
, v) > 0, ∀v ∈ C
0
(G, x
0
),
nhưng x
0
/∈ Strl(2, f, G ∩ Q).
Bây giờ chúng ta trình bày các điều kiện đủ tối ưu với hàm Lagrange:
L
µ
(x) = f (x) + µ, g (x), (1.4)
trong đó µ ∈ Y
∗
.
Định lý 1.5. Giả sử rằng
(a) C (G, x
0
) ∩ T (Q, x
0
) ∩ kerdf (x
0
, ·) = {0},

} sao cho
α
n
→ 0
+
và
f (x
n
) − f (x
0
)
t
n
 α
n
. (1.5)
Với t
n
= x
n
− x
0
. Chọn một dãy con (nếu cần), ta có thể giả sử rằng
v
n
:=
x
n
− x
0

t
n
= dg (x
0
, v) ;
Do x
n
∈ G, tức là g(x
n
) ∈ −K, suy ra
dg(x
0
, v) ∈ cl cone(−K − g(x
0
)).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
Do đó, v ∈ C(G, x
0
). Từ (1.5) ta suy ra
df (x
0
, v)  lim inf
n→∞
f (x
n
) − f (x
0
)
t

, u), ∀u ∈ X. (1.6)
Bởi vì
dg (x
0
, v) ∈ cl cone (−K − g (x
0
))
và
µ ∈ (−K − g (x
0
))
−
= [cl cone (−K − g (x
0
))]
−
=

µ ∈ K
+
: µ, g (x
0
) = 0

,
ta suy ra
µ, dg (x
0
, v)  0.
Hơn nữa, do d

Chứng minh. Giả sử x /∈ Strl(k, f, G ∩ Q). Khi đó, tồn tại dãy α
n
> 0
và x
n
∈ G ∩ Q ∩ B (x
0
, α
n
) \{x
0
} sao cho
α
n
→ 0
+
và
f (x
n
) − f (x
0
)
t
k
n
 α
n
, (1.7)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15

(x
0
, v) > 0.
Ta có f (x)  L
µ
(x) , ∀x ∈ M = G ∩ Q.
Do đó,
d
k
(f + I
M
) (x
0
, v)  d
k
(L
µ
+ I
M
) (x
0
, v)  d
k
L
µ
(x
0
, v) > 0.
Từ công thức (1.7) ta suy ra
d

sao cho µ, g (x
0
) = 0, và
dL
µ
(x
0
, u)  0, ∀u ∈ T (Q, x
0
) , (1.8)
d
2
r
L
µ
(x
0
, v) > 0, (1.9)
thì x
0
∈ Strl(2, f, G ∩ Q).
Chứng minh. Giả sử x
0
/∈ Strl(2, f, G ∩Q). Khi đó tồn tại dãy α
n
→ 0
+
và x
n
∈ G ∩ Q ∩ B(x

, (1.10)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
trong đó t
n
= x
n
− x
0
. Cũng như trong chứng minh định lý 1.6, ta
giả sử rằng
v
n
:=
x
n
− x
0
t
n
→ v ∈ T (Q, x
0
) ∩ C(G, x
0
) ∩ C(f, x
0
)\{0}.
Khi đó x
n
= x

(x
0
, v
n
) = f (x
n
) − f (x
0
) + µ, g (x
n
)−
− dL
µ
(x
0
, x
n
− x
0
) .
(1.11)
Do x
n
∈ G, ta có
g(x
n
) ∈ −K và µ, g (x
n
)  0,
và bởi vì T (Q, x

0
, v)  lim inf
n→∞
L
µ
(x
n
) − L
µ
(x
0
) − t
n
dL
µ
(x
0
, v
n
)
t
2
n
/2
 lim inf
n→∞
f (x
n
) − f (x
0

, Y = R
m
× R
p
và K = R
m
+
× {0
p
}.
Thật vậy, nếu f và g là khả vi Fréchet tại x
0
thì
dL
µ
(x
0
, u) = ∇L
µ
(x
0
) u, ∀u ∈ R
n
,
trong đó ∇L
µ
(x
0
) là đạo hàm Fréchet của L
µ

(x
0
, v) = ∇
2
L
µ
(x
0
) (v, v) , ∀v ∈ X,
trong đó ∇
2
L
µ
(x
0
) là đạo hàm cấp 2 Fréchet của L
µ
tại x
0
.
Hệ quả 1.1. Giả sử Q là tập lồi và f, g là khả vi cấp 2 Fréchet tại x
0
.
Nếu
∀v ∈ C (G, x
0
)∩T (Q, x
0
)∩C (f, x
0

1
, x
2
) ∈ R
2
, Q = {x : x
2
 0}, x
0
=
(0, 0),
f(x) =

−4x
1
− x
2
nếu x
2
 0,
−4x
1
− x
2
sin
2
(
1
x
2

−4v
1
nếu v
2
< 0,
C(G, x
0
) = {v : v
1
= 0, v
2
 0}, T (Q, x
0
) = Q,
C(f, x
0
) =

v : −4v
1
− v
2
 0 hoặc v
1
 0

, trong đó v = (v
1
, v
2

) ∩ T (Q, x
0
) ∩ C (f, x
0
) \{0} = {(0, v
2
) : v
2
< 0},
điều kiện (1.9) thỏa mãn với µ = (0, 4) bởi vì
d
2
r
L
µ
(x
0
, v) = d
2
r
f (x
0
, v) + µ
1
∇
2
g
1
(x
0

, x
2
, x
3
) ∈ R
3
, f(x) = 2x
2
−x
2
3
, g(x) =
x
3
− x
2
+ x
2
1
,
Q =

x : x
3
 |x
1
|
3/2

và x

) = {v : v
2
= 0, v
3
= 0},
L
µ
(x) = (2 −µ) x
2
+ µx
3
+ µx
2
1
− x
2
3
với µ  0,
∇L
µ
(x
0
) u  0, ∀u ∈ T (Q, x
0
) nếu µ = 2, và
∇
2
L
µ
(x

Chương 2 trình bày các điều kiện tối ưu cấp cao cho nghiệm hữu hiệu
địa phương chặt cấp cao của bài toán quy hoạch đa mục tiêu lồi có ràng
buộc bất đẳng thức. Trước hết phân hoạch tập chỉ số của hàm mục tiêu,
rồi lập các bài toán con và mối quan hệ của nghiệm hữu hiệu địa phương
chặt cấp m của bài toán gốc với một trong các bài toán con. Trên cơ sở
đó, chúng tôi trình bày các điều kiện cần và đủ tối ưu cho nghiệm hữu
hiệu địa phương chặt cấp m cho bài toán gốc lồi, và các đặc trưng điểm
yên ngựa cho nghiệm hữu hiệu địa phương chặt cấp m cho bài toán gốc
lồi. Các kết quả trình bày trong chương này của A. Gupta, A. Mehra và
D. Bhatia [3].
2.1. Các kết quả bổ trợ
Trong chương này chúng ta xét bài toán tối ưu đa mục tiêu:
(MOP ) min (f
1
(x), , f
p
(x))
g
j
(x)  0, j ∈ Q = {1, , q}.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên