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


ĐỖ THANH PHÚC

ĐIỀU KIỆN TỐI ƯU CẤP MỘT VÀ CẤP HAI CHO BÀI
TOÁN TỐI ƯU TRONG KHÔNG GIAN VECTƠ TÔPÔ LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành : Toán giải tích
Mã số : 60 46 01


2 của Ben Tal - Zowe [4] cho bài toán tối ưu đa mục tiêu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
2
với ràng buộc nón và ràng buộc bất đẳng thức dưới ngôn
ngữ nón các phương giảm cấp 2 của hàm mục tiêu, nón các
phương chấp nhận được cấp 2 cho ràng buộc nón và nón các
phương tiếp xúc cấp 2 cho ràng buộc đẳng thức. Khi các nón
cấp 2 lấy theo phương 0 ta sẽ nhận được các điều kiện tối
ưu cấp 1.
Luận văn này bao gồm phần mở đầu, ba chương, kết luận
và danh mục các tài liệu tham khảo.
Chương 1 trình bày điều kiện tối ưu cấp 2 tổng quát cho
cực tiểu địa phương của bài toán tối ưu đa mục tiêu trong
không gian vectơ tôpô thực dưới ngôn ngữ nón các phương
giảm cấp 2 của hàm mục tiêu, nón các phương chấp nhận
được cấp 2 của ràng buộc nón và nón các phương tiếp xúc
cấp 2 của ràng buộc đẳng thức. Các kết quả được trình bày
trong chương này là của Ben Tal - Zowe [4].
Chương 2 trình bày cách tiếp cận áp dụng điều kiện cần
cấp 2 tổng quát trong chương 1 bao gồm các kết quả tính
toán nón các phương giảm cấp 1 và cấp 2, nón các phương
chấp nhận được cấp 1 và cấp 2 và nón các phương tiếp xúc
cấp 1 và cấp 2, cùng với các điều kiện cần cấp 1 và cấp 2 cho
bài toán tổng quát (P) và bài toán với hữu hạn ràng buộc
bất đẳng thức (MP). Các kết quả trình bày trong chương
này là của Ben Tal - Zowe [4].
Chương 3 trình bày các điều kiện đủ tối ưu cấp 2 cho
bài toán tổng quát (P) trong trường hợp không gian X là
hữu hạn chiều của Ben Tal - Zowe [4] và X vô hạn chiều của
Maurer - Zowe.

1
> u
2
(u
2
< u
1
) nếu u
1
−u
2
∈ intC.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Khi đó, ≥ có tính chất bất biến với phép tịnh tiến và phép
nhân vô hướng dương.
Ta quan tâm tới bài toán tìm cực tiểu yếu địa phương,
tức là ta tìm điểm x
0
thuộc tập chấp nhận được F := {x ∈
X : −g(x) ∈ Kvà h(x)=0} mà tồn tại một lân cận N (x
0
)
của điểm x
0
sao cho
f(x) ∈ f(x
0
) − intC, với ∀x ∈ N(x
0

i
(x) ≤ 0, với i = 1, 2, · · · , n,
h(x) = 0,
x ∈ X.
Như là một ví dụ cho bài toán (P ), khi f không phải
là hàm thực, ta xét trường hợp U = R
n
và lấy C là nón
sắp thứ tự từ điển trong R
n
, nghĩa là C là tập tất cả các
vectơ trong R
n
mà thành phần khác không đầu tiên dương,
cùng với 0
R
n
. Ta kí hiệu cl C là bao đóng tôpô của C. Khi
đó, R
n
= (cl C) ∪ (−int C) và(cl C) ∩ (−int C) = ∅. Khi đó,
(1.1) tương đương với
f(x) ∈ f(x
0
) + cl C, với x ∈ N(x
0
) ∩ F.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
Định nghĩa 1.1.1. Một phương d ∈ X được gọi là phương

v, với mọi ¯z ∈ N(z), và 0 < t ≤ T.
(1.4)
Tập tất cả z thoả mãn (1.3) và (1.4) được kí hiệu lần lượt
là Q
f
(x, d) và Q
g
(x, d). Hiển nhiên, Q
f
(x, d) và Q
g
(x, d) là
các tập mở. Ta đặt
D
<
f
(x) := Q
f
(x, 0), D
<
g
(x) := Q
g
(x, d) (1.5)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
Định nghĩa 1.1.5. Vectơ z được gọi là phương tiếp xúc cấp
hai hàm h : X → W tại x tương ứng với d ∈ X nếu tồn tại
một số thực T > 0 và đường cong r(t) ∼ o(t
2

f
(x)). Tương tự, g
được gọi là chính quy tại x nếu g là d-chính quy tại x với
∀d ∈ D
g
(x), h được gọi là chính quy tại x nếu h là d-chính
quy tại x với ∀d ∈ T
h
(x).
Với tập con S của X, hàm tựa δ
∗
(.|S) xác đinh trên không
gian vectơ topô đối ngẫu X
∗
của X với giá trị trên đường
thẳng thực mở rộng R ∪ {∞} được định nghĩa như sau:
δ
∗
(x
∗
|S) = sup
x∈S
x
∗
x với x
∗
∈ X
∗
. (1.7)
(Nếu S = ∅, thì ta quy ước δ

δ
∗
(x
∗
|S) =

0, nếu x
∗
∈ Λ(S),
∞, nếu x
∗
∈ Λ(S).
(1.8)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
1.2 Điều kiện cần tổng quát cho cực
tiểu yếu địa phương
Định lý 1.2.1. Giả sử x
0
là nghiệm tối ưu địa phương của
bài toán (P ). Khi đó, với mọi
d ∈ D
f
(x
0
) ∩ D
g
(x
0
) ∩ T

+ l
g
+ l
h
= 0, (1.11)
và bất đẳng thức Legendre
δ
∗
(l
f
| Q
f
(x
0
, d)) + δ
∗
(l
g
| Q
g
(x
0
, d)) + δ
∗
(l
h
|V
h
(x
0

i=1
S
i
) = min{
n

i=1
δ
∗
(x
∗
i
|S
i
) : x
∗
= x
∗
1
+· · · +x
∗
n
∈ Λ(S
i
)}.
Bổ đề 1.2.3. Giả sử S
1
, · · · , S
n+1
là các tập con lồi, không

δ
∗
(x
∗
1
|S
1
) + δ(x
∗
2
|S
2
) + · · · + δ(x
∗
n+1
|S
n
+ 1) ≤ 0. (1.16)
Chú ý 1.2.4. Nếu ∩
n+1
i=2
S
i
= ∅ thì x
∗
1
= 0 trong bổ đề 1.2.3.
Hệ quả 1.2.5. Giả sử S
1
, S

n
= 0.
Bổ đề 1.2.6. Giả sử A : X −→ U là toán tử tuyến tính với
miền giá trị R(A) và S là tập con lồi không rỗng của U. Đặt
A
−1
S := {x ∈ X : AX ∈ S},
và giả sử x
∗
∈ Λ(A
−1
S). Giả sử một trong các điều kiện sau
đúng:
(i) R(A) ∩ intS = ∅. (điều kiện Slater),
(ii) A là tập mở .
Khi đó,
δ
∗
(x
∗
|A
−1
S) = min{δ
∗
(u
∗
|S) : x
∗
= u
∗

<
f
(x
0
)
+
, l
g
∈ D
<
g
(x
0
)
+
, l
h
∈ T
h
(x
0
)
+
, (1.17)
không đồng thời bằng không thoả mãn
l
f
+ l
g
+ l

Kí hiệu K
a
là bao đóng của bao nón của K + a tức là (kí
hiệu cone A là bao nón của A):
K
a
= cl cone(K + a) = cl{λ(k + a) : k ∈ K, λ ≥ 0}.
Với b ∈ V , ta kí hiệu K
a,b
là bao đóng của bao nón của K
a+b
,
tức là
K
a,b
= cl{(k
a
+ b) : k
a
∈ K
a
, λ ≥ 0}.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
Bổ đề 2.1.2. Cho a ∈ −K; b ∈ −K
a
. Khi đó,
K
a,b
= cl(K + {λa + µb : λ ≥ 0, µ ≥ 0}).

thì
K
g(x),g

(x)d
=
n

i=1
S
i
, trong đó S
i
=

R
+
, nếu i ∈ J(x, d),
R, nếu i ∈ J(x, d).
Ví dụ 2.1.4. Cho V = R
3
và K là nón,
K = {v ∈ R
3
: v
2
1
+ v
2
2

g(x) ∈ −K nếu và chỉ nếu q
i
(x) ≤ 0 với i = 1, 2. (2.1)
Giả sử intK = 0. Ta có kết quả sau đây về phần trong
của K
a
và K
a,b
.
Bổ đề 2.1.5. Cho a ∈ −K và b ∈ −K
a
. Khi đó,
intK
a
= intK + {λa : λ ≥ 0}, (2.2)
intK
a,b
= intK + {λa + µb : λ ≥ 0, µ ≥ 0}. (2.3)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
2.2 Tập các phương giảm và tập các
phương chấp nhận được
Ta bắt đầu với việc phân tích D
<
f
(x) và D
<
g
(x) dưới ngôn
ngữ đạo hàm theo phương


(x, d; z) tồn
tại với mọi z ∈ X. Giả sử f, g thoả mãn điều kiện Lipschitz
địa phương tại x. Khi đó,
(i) Nếu f

(x, d) ≤ 0,
Q
f
(x; d) = {z ∈ X : f

(x, d; z) ∈ −int C
f

(x;d)
};
(ii) Nếu g(x) ∈ −K và g

(x; d) ∈ cone(K + g(x)) (=
−K
g(x)
khi cone(K + g(x)) là đóng,
Q
g
(x, d) = {z ∈ X : g

(x, d, z) ∈ −intK
g(x),g

(x;d)

(ii) Nếu g(x) ∈ −K thì D
<
f
x = {d ∈ X : g

(x; d) ∈
−int K
g(x)
}.
Bổ đề 2.2.4. Giả sử f F- khả vi liên tục trong một lân cận
của x, với d cho trước hàm Φ
d
(t) := f (x + td) khả vi cấp hai
tại t = 0. Khi đó, f

(x, d; z) tồn tại với ∀z ∈ X, và
f

(x, d; z) = f

(x; z) +
1
2
Φ

d
(0). (2.4)
2.3 Tập các phương tiếp xúc
Bổ đề 2.3.1. Giả sử X và W là các không gian Banach,
h : X → W F- khả vi liên tục trong một lân cận của x,

i
)) + r(t
i
) = 0, ||r(t
i
)|| = o(||y(t
i
)||
k
).
Chú ý 2.3.2. Từ chứng minh trên ta thấy dạng liên tục
của bổ đề 2.3.1 cũng đúng, trong đó các dãy y(t
i
)
i=1,2,···
và
r(t
i
)
i=1,2,···
thay bởi các hàm y(t) và r(t) xác định trong
khoảng (0, t
0
] với số dương t
0
thích hợp. Ta sử dụng điều
này để chứng minh:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
14
Mệnh đề 2.3.3. Cho h là ánh xạ từ không gian Banach X


(x)d ≤ 0 và Q
f
(x, d) = ∅. Khi đó, với l
f
∈
Λ(Q
f
(x, d)), tồn tại u
∗
∈ C
+
sao cho
l
f
= u
∗
· f

(x), u
∗
f

(x)d = 0,
δ
∗
(l
f
|Q
f

∗
g

(x)d = 0, v
∗
g(x) = 0,
δ
∗
(l
g
|Q
g
(x, d)) =
−1
2
v
∗
g

(x)(d, d).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
(iii) Giả sử X và W là các không gian Banach, h

(x) là
ánh xạ lên, h(x) = 0 và h

(x)d = 0. Khi đó, với l
h
∈

là nghiệm tối ưu địa phương của
bài toán (P ); X và W là các không gian Banach, U và V là
không gian định chuẩn. Giả sử f, g và h là F-khả vi cấp 2.
Miền giá trị R(h

(x
0
)) của h

(x
0
) là đóng. Khi đó, với mọi
d thoả mãn
f

(x
0
)d ≤ 0, g

(x
0
)d ∈ −cone(K + g(x
0
)), h

(x
0
)d = 0,
(2.7)
tồn tại các hàm tuyến tính liên tục u

u
∗
· f

(x
0
) + v
∗
· g

(x
0
) + w
∗
· h

(x
0
) = 0, (2.9)
(u
∗
· f

(x
0
) + v
∗
· g

(x

,
h

(x
0
)z + h

(x
0
)(d, d) = 0.
Hệ quả 2.4.3. Nếu cho vectơ d trong (2.8) thoả mãn điều
kiện CQ(d) thì u
∗
tương ứng trong (2.9)-(2.11) khác 0
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
16
2.5 Điều kiện cần tối ưu cho bài
toán (MP)
Ta đặc biệt hoá định lý 1.2.1 cho bài toán (MP). Để làm
điều này ta ký hiệu D
g
i
(x) là tập của các phương tựa chấp
nhận được của thành phần g
i
của g (thay K bằng R
+
trong
định nghĩa), tương tự cho Q
g

bài toán (MP ), và giả sử f, h và g
i
, i ∈ I(x
0
) là chính quy
tại x
0
. Khi đó, với mọi
d ∈ D
f
(x
0
) ∩ ( ∩
i∈I(x
0
)
D
g
i
(x
0
)) ∩ T
h
(x
0
) (2.11)
tồn tại các hàm tuyến tính liên tục
l
f
∈ Λ(Q

l
g
i
+ l
h
= 0, (2.13)
δ
∗
(l
f
|Q
f
(x
0
, d))+

i∈J(x
0
,d)
δ
∗
(l
g
i
|Q
g
i
(x
0
, d))+δ

h
(x
0
)
+
,
Λ(Q
g
i
(x
0
, 0)) = −D
<
g
i
(x
0
)
+
(i ∈ J(x
0
, 0) = I(x
0
)),
và (2.15) trở thành bất đẳng thức tầm thường 0 ≤ 0. Ta có
hệ quả sau.
Hệ quả 2.5.2. Lấy x
0
là nghiệm tối ưu địa phương của
bài toán (MP) và giả sử D

h
(x
0
)
+
và l
g
i
∈ D
<
g
i
(x
0
)
+
với i ∈ I(x
0
), không đồng thời
bằng 0, sao cho
l
f
+

i∈I(x
0
)
l
g
i

(x
0
)d = 0, (2.15)
tồn tại các số thực y
0
≥ 0 và y
i
≥ 0 với i ∈ J(x
0
, d), và hàm
w
∗
∈ W
∗
không đồng thời bằng 0 sao cho
y
0
f

(x
0
) +

i∈J(x
0
,d)
y
i
g


0
) + w
∗
· h

(x
0
)

(d, d) ≥ 0. (2.17)
Chú ý 2.5.4. Với dimW < ∞, miền giá trị của h

(x) luôn
đóng và giả thiết này có thể là bỏ được.
Chú ý 2.5.5. Giả sử các giả thiết của định lý 2.5.3 và (2.36)
đúng với d. Khi đó, y
0
có thể chọn bằng 1 nếu điều kiện chính
quy sau đây đúng:
h

(x) là ánh xạ lên và tồn tại z ∈ X sao cho
(CQ(d)) g

i
(x
0
)z + g

i

, d) và
¯
w
∗
(chẳng hạn
khi CQ(d) thoả mãn với ít nhất một d trong (2.36)), thì tập
các phương d thoả mãn(2.36) sẽ nhận được từ (2.37) (đặt
y
i
= 0 với i ∈ J(x
0
) \ J(x
0
, d)):
{d|f

(x
0
)d ≤ 0, g

(x
0
)d ≤ 0 với i ∈ I(x
0
), h

(x
0
)d = 0} =
=

1
− x
2
2
, g
1
(x) = x
1
(x
2
−
1
2
x
1
),
g
2
(x) = −x
1
(
1
2
x
1
) + x
2
và g
3
(x) = −x

nghiệm tối ưu địa phương và giả sử một trong hai điều kiện
sau đúng
(i) (CQ1)
(ii) (CQ2), miền giá trị của h

(x
0
) là đóng và y
0
có thể lấy
bằng 1 với mọi d thoả mãn (2.16). Khi đó, tồn tại các
nhân tử y
i
với i ∈ I(x
0
) và w
∗
∈ W
∗
, sao cho
f

(x
0
) +

i∈I(x
0
)
y

) + w
∗
h

(x
0
)

(d, d) ≥ 0, (2.19)
với mọi d thoả mãn
g

(x
0
)d = 0, với i ∈ I(x
0
), y
i
> 0,
g

(x
0
)d ≤ 0, với i ∈ I(x
0
), y
i
= 0,
h


20
Chương 3
Điều kiện đủ tối ưu
3.1 Điều kiện đủ tối ưu cho bài toán
khả vi
Định lý 3.1.1.
Xét bài toán (P) trong không gian X hữu hạn chiều, C
là nón lồi đóng và f, g, h là các hàm F- khả vi cấp hai. Lấy
x
0
là điểm chấp nhận được của (P). Khi đó, x
0
là nghiệm
tối ưu địa phương chặt nếu một trong hai điều kiện sau đây
thoả mãn:
(i) Hệ sau không có nghiệm d
f

(x
0
)d ≤ 0, g

(x
0
)d ∈ −K
g(x
0
)
, h


)d = 0, v
∗
g(x
0
) = 0, (3.2)
u
∗
· f

(x
0
)d + v
∗
· g

(x
0
) + w
∗
· h

(x
0
) = 0, (3.3)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
u
∗
f


i
x
2
i
−

∞
i=1
x
4
i
.
3.2 Điều kiện đủ tối ưu cho trường
hợp vô hạn chiều
Với X vô hạn chiều, ta có điều kiện đủ cấp hai sau đây:
Định lý 3.2.1. Xét bài toán (P) với U = R, các không gian
Banach thực X, V, W và các hàm F- khả vi cấp hai. Lấy x
0
là điểm chấp nhận được bài toán (P) và giả sử tồn tại ánh
xạ x → d(x) của tập chấp nhận được F vào tập xấp xỉ tuyến
tính {d ∈ X : g

(x
0
)d ∈ −K
g(x
0
)
, h



(x
0
) + w
∗
· h

(x
0
) = 0,
(f

(x
0
) + v
∗
g

(x
0
) + w
∗
h

(x
0
))(d, d) ≥ δ||d||
2
với mọi
d ∈ {y ∈ X|g

xúc cấp 2 cho ràng buộc đẳng thức (theo phương d nào đó).
Chú ý rằng với d = 0, từ các nón cấp 2 ấy ta sẽ nhận được
nón các phương giảm, nón các phương chấp nhận được và
nón các phương tiếp xúc. Khi đó, từ điều kiện cần tối ưu cấp
2 ta nhận lại được điều kiện cần tối ưu cấp 1 của Dubovitskii
- Milyutin [5]. Khi các hàm mục tiêu và ràng buộc khả vi
Fréchet cấp 2 , từ kết quả tổng quát ta nhận lại được các
điều kiện tối ưu cấp 2 đã biết trước.
Điều kiện tối ưu cấp 2 và cấp cao cho bài toán tối ưu đa
mục tiêu là đề tài đã và đang được nhiều tác giả quan tâm
nghiên cứu.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên