ĐẠI HỌC THÁI NGUN
TRƯỜNG ĐẠI HỌC KHOA HỌC
TRỊNH DUY BÌNH
ĐIỀU KIỆN TỐI ƯU CHO NGHIỆM
HỮU HIỆU CỦA BÀI TỐN TỐI ƯU
ĐA MỤC TIÊU VỚI CÁC HÀM ỔN
ĐỊNH
LUẬN VĂN THẠC SĨ TỐN HỌC
Thái Ngun - 2013
Số hóa bởi Trung tâm Học liệu />ĐẠI HỌC THÁI NGUN
TRƯỜNG ĐẠI HỌC KHOA HỌC
TRINH DUY BÌNH
ĐIỀU KIỆN TỐI ƯU CHO NGHIỆM
HỮU HIỆU CỦA BÀI TỐN TỐI ƯU
ĐA MỤC TIÊU VỚI CÁC HÀM ỔN
ĐỊNH
Chun ngành : TỐN ỨNG DỤNG
Mã số : 60 46 01 12
LUẬN VĂN THẠC SĨ TỐN HỌC
Người hướng dẫn khoa học:
PGS.TS ĐỖ VĂN LƯU
Thái Ngun - 2013
Số hóa bởi Trung tâm Học liệu />Mục lục
Mở đầu 1
1 Hàm ổn định và đạo hàm tiếp liên 3
1.1 Hàm ổn định và đạo hàm tiếp liên . . . . . . . . . . . 3
1.2 Các quy tắc tính đạo hàm tiếp liên . . . . . . . . . . 11
2 Điều kiện tối ưu 18
2.1 Jacobian suy rộng Clarke . . . . . . . . . . . . . . . . 18
2.2 Các hàm vững . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Các điều kiện tối ưu . . . . . . . . . . . . . . . . . . 30

1
Số hóa bởi Trung tâm Học liệu />tắc hàm hợp, đạo hàm tiếp liên của một tổng, một tích, một thương
hai hàm và max của một số hữu hạn hàm ổn định.
Chương 2. Điều kiện tối ưu
Trình bày các kết quả của Jimenez - Novo [6] về hàm vững, mối
quan hệ với hàm ổn định, hàm khả vi Hadamard, hàm Lipschitz địa
phương, đạo hàm tiếp liên của hàm vững, và các điều kiện tối ưu
cho bài tốn tối ưu vectơ tổng qt với các hàm ổn định và hàm
vững dưới ngơn ngữ đạo hàm tiếp liên. Chương 2 cũng trình bày các
điều kiện cần và đủ tối ưu dưới dạng các quy tắc nhân tử Lagrange
cho bài tốn tối ưu vectơ với ràng buộc nón và ràng buộc đẳng thức
trong khơng gian hữu hạn chiều, dưới ngơn ngữ đạo hàm tiếp liên.
Luận văn này được hồn thành tại trường Đại học Khoa học, Đại
học Thái Ngun dưới sự hướng dẫn tận tình của PGS TS. Đỗ Văn
Lưu. Em xin bày tỏ lòng biết ơn chân thành và sâu sắc về sự tận
tâm và nhiệt tình của Thầy trong suốt q trình em thực hiện luận
văn.
Em xin chân thành cảm ơn Ban Giám hiệu, phòng Đào tạo Khoa
học và Quan hệ quốc tế, Khoa Tốn - Tin trường Đại học Khoa học,
Đại học Thái Ngun đã quan tâm và giúp đỡ em trong suốt thời
gian học tập tại trường.
Em cũng xin gửi lời cảm ơn đến gia đình, bạn bè và các đồng
nghiệp đã động viên, giúp đỡ em trong q trình học tập của mình.
Do thời gian và kiến thức còn hạn chế nên luận văn khơng tránh
khỏi những thiếu sót. Em rất mong nhận được sự góp ý của các
thầy cơ để luận văn được hồn thiện hơn. Em xin chân thành cảm ơn!
Thái Ngun, ngày 15 tháng 7 năm 2013
Tác giả
Trịnh Duy Bình
2

0
) =

v ∈ X : ∃t
n
→ 0
+
, ∃v
n
→ v
sao cho x
0
+ t
n
v
n
∈ M, ∀n ∈ N

;
3
Số hóa bởi Trung tâm Học liệu />(b) Nón các phương đạt được của M tại x
0
là
A(M, x
0
) =

v ∈ X : ∀t
n
→ 0

s
(M, x
0
) =

v ∈ X : ∃δ > 0, ∃t
n
→ 0
+
sao cho
x
0
+ t
n
u ∈ M ∀n ∈ N, ∀u ∈ B (v, δ)

.
Chú ý rằng ta ln có A (M, x
0
) ⊂ T (M, x
0
) .Tập hợp M được
gọi là khả dẫn xuất (derivable) tại điểm x
0
(xem [10]) nếu
A(M, x
0
) = T (M, x
0
).

0
, f(x
0
)).
Sau đây là một ví dụ về hàm khả dẫn xuất đồ thị.
Ví dụ 1.1.1
Giả sử f : R → R được cho bởi f(x) = x sin

1
x

nếu x = 0 và
f(0) = 0. Khi đó f là khả dẫn xuất đồ thị tại 0.
Đạo hàm Hadamard của f : X → Y tại x
0
theo phương v ∈ X là
df(x
0
, v) = lim
(t,u)→(0
+
,v)
f(x
0
+ tu) − f(x
0
)
t
.
4

))
t

tương ứng df (x
0
, v) = lim
(t,u)→(0
+
,v)
sup (f (x
0
+ tu) − f (x
0
))
t

.
Định nghĩa 1.1.2. [1]
Ta nói rằng f : X → Y là một hàm ổn định tại x
0
∈ X nếu tồn
tại một miền lân cận U của x
0
và k > 0 sao cho
f(x) − f(x
0
) ≤ kx − x
0
, ∀x ∈ U.
Nếu f(x) − f(x

0
, v ∈ X. Đạo hàm tiếp liên của f tại x
0
theo phương v là tập hợp sau đây trong Y:
∂
∗
f (x
0
) v =

y ∈ Y : ∃ (t
n
, v
n
) → (0
+
, v) sao cho
lim
n→∞
(f (x
0
+ t
n
v
n
) − f (x
0
)) /t
n
= y

Định lý sau (cách chứng minh rất đơn giản) cho ta một số tính
chất của hàm (f, g) liên quan đến tính ổn định và đạo hàm tiếp liên.
Mệnh đề 1.1.1. [6]
(i) f và g ổn định tại x
0
⇔ (f, g) ổn định tại x
0
.
(ii) Với mỗi v ∈ X, ∂
∗
(f, g) (x
0
) v ⊂ ∂
∗
f (x
0
) v × ∂
∗
g (x
0
) v. Nếu f
hoặc g khả vi Hadamard tại x
0
theo phương v thì ta có dấu bằng.
Bao hàm thức trong (ii) có thể đúng như ví dụ 1.1.2 dưới đây.
Nhận xét 1.1.1.
(1) Rõ ràng là nếu f : X → R
p
là ổn định taị x
0

0
+ t
n
v
n
) − f (x
0
)) /t
n
là một dãy bị chặn, tồn
tại một dãy con (ta vẫn kí hiệu như cũ) sao cho
y
n
→ y ∈ ∂
∗
f(x
0
)v.
(2) Nếu f : X → Y là ổn định taị x
0
với hằng số k trên một lân
cận của x
0
thì ∂
∗
f(x
0
)v ≤ kv. Hơn nữa, nếu Y = R
p
, thì

thì
∂
∗
f (x
0
) v ⊂

p
i=1
∂
∗
f
i
(x
0
) v ⊂

p
i=1

df
i
(x
0
, v) , df
i
(x
0
, v)


2

,
f(2
−n
) = 0 và f(s
n
) =
s
n
3
, ∀n ∈ N, trong đó s
n
là điểm giữa
của đoạn [2
−n−1
, 2
−n
], tức là s
n
= 3 · 2
−n−2
.
Do đó df(x
0
, v) = 0 và df(x
0
, v) =
1
3

n
) = s
n
/3 ∀n ∈ N.
Các đạo hàm Hadamard dưới và trên theo phương v = 1 là
dg (x
0
, v) = 0 và dg (x
0
, v) =
1
3
.
Do đó, ∂
∗
g(x
0
)v =

0,
1
3

.
(c) Giả sử h = (f, g). Khi đó, h là Lipschitz tồn cục và ta có
∂
∗
h(x
0
)v =

, 0) = 0.
Chứng minh.
(=⇒) Ta suy ra trực tiếp từ những định nghĩa bởi vì với δ > 0 nào
đó,
f (x
0
+ tu) − f (x
0
)
t
≤ k u , ∀t ∈ (0, δ) , ∀u ∈ B (0.1) .
(⇐= ) Giả sử  > 0 cố định. Theo giả thiết ∃δ
1
, δ
2
> 0 sao cho
f(x
0
+ tu) − f(x
0
)
t
<  ∀t ∈ (0, δ
1
), u ∈ B(v, δ
2
). (1.1)
Chọn a cố định, η ∈ (0, δ
2
) và δ = η · δ

1
), u = η
8
Số hóa bởi Trung tâm Học liệu />Do đó,
f (x) − f (x
0
)
x − x
0

=
f (x
0
+ w) − f (x
0
)
w
=
f (x
0
+ tu) − f (x
0
)
t
·
1
u
< ε
1
n

+ t
n
v
n
) − f(x
0
))/t
n
→ y, ∀(t
n
, v
n
) → (0
+
, v)
thì df(x
0
, v) = y. Bởi vì f ổn định tại x
0
dãy (y
n
) bị chặn,
tức là y
n
∈ clB(0, r), ∀n ∈ N với r > 0, nào đó. Với mỗi k ∈ N ta
xác định
n(k) = max{n ∈ N : y
n
∈ B(y,
1

Cho f : R → R được cho bởi
f(x) =





1
n
, nếu x =
1
n
, n ∈ N \ {0}

| x |, nếu x =
1
n
, n ∈ N \ {0}
Ta có ∂
∗
f(0)1 = {1}, nhưng f khơng khả vi Hadamard tại 0 theo
phương 1.
Kết quả tiếp theo là hệ quả trực tiếp của Mệnh đề 1.1.2 và 1.1.3(i).
Hệ quả 1.1.1.
Khi f : X → Y là ổn định tại x
0
thì ∂
∗
f(x
0

n
− x
0
, ∀n ∈ N. (1.2)
Đặt t
n
= f(x
n
) − f(x
0
) > 0 và v
n
= (x
n
− x
0
)/t
n
. Vì f liên tục tại
x
0
, ta có t
n
→ 0
+
, và từ (1.2), ta suy ra v
n
→ 0.
Lấy dãy con nếu cần thiết, ta có thể giả sử rằng
y

0
.
Chẳng hạn f : R → R, f(x) =

| x |, x
0
= 0. Lấy t
n
= 1/n và
v
n
= 1/n, ta có lim
x→∞
f (t
n
v
n
) /t
n
= 1 ∈ ∂
∗
f (x
0
) 0.
10
Số hóa bởi Trung tâm Học liệu />Hệ quả 1.1.2.
f : X → R
p
liên tục tại x
0

thì g ◦ f ổn
định tại x
0
và có đẳng thức trong (1.3).
Chứng minh.
Giả sử y ∈ ∂
∗
f(x
0
)v. Khi đó, ∃(t
n
, v
n
) → (0
+
, v) sao cho
y
n
:= (f (x
0
+ t
n
v
n
) − f (x
0
)) /t
n
→ y.
Bởi vì g khả vi Hadamard tại f(x

) + t
n
y
n
, và ta
có
g (f (x
0
+ t
n
v
n
)) = g (f (x
0
) + t
n
y
n
)
= g (f (x
0
)) + t
n
dg (f (x
0
) , y) + t
n
α (t
n
, y

0
) do Mệnh đề 1.1.2.
Giả sử z ∈ ∂
∗
(g ◦ f)(x
0
)v. Khi đó tồn tại (t
n
, v
n
) → (0
+
, v)
sao cho
g(f(x
0
+ t
n
v
n
)) − g(f(x
0
))
t
n
→ z. (1.4)
Do f ổn định tại x
0
và Y hữu hạn chiều, ta có thể giả sử rằng:
(lấy một dãy con nếu cần)

) + t
n
y
n
và sử dụng (1.4) và (1.5) ta suy ra
dg (f (x
0
) , y) = lim
n→∞
g (f (x
0
) + t
n
y
n
) − g (f (x
0
))
t
n
= lim
x→∞
g (f (x
0
+ t
n
v
n
)) − g (f (x
0

∗
(ψ ◦ f)(x
0
)v, ∀v ∈ X. (1.6)
Hơn nữa, nếu Y hữu hạn chiều và f ổn định tại x
0
thì ψ ◦ f là ổn
định tại x
0
và đẳng thức xảy ra trong (1.6).
12
Số hóa bởi Trung tâm Học liệu />Chú ý rằng khi Y hữu hạn chiều và ψ : Y → Z là một hàm affine
thì ψ liên tục trên Y .
Mệnh đề 1.2.1. (Quy tắc tổng)
Giả sử f, g là hai hàm từ X vào Y . Khi đó,
{y + z : (y, z) ∈ ∂
∗
(f, g) (x
0
) v} ⊂ ∂
∗
(f + g) (x
0
) v.
Nếu Y hữu hạn chiều và f (hoặc g) ổn định tại x
0
thì
∂
∗
(f + g)(x

, y
0
), (v, u) ∈ X × Y .
Nếu f ổn định tại x
0
thì
∂
∗
h(x
0
, y
0
)(v, u) ⊂ ∂
∗
f(x
0
)v + ∂
∗
g(y
0
)u,
và đẳng thức xảy ra nếu f khả vi Hadamard tại x
0
theo phương v.
Để chứng minh điều này, ta xét f và g từ X × Y vào R
p
f(x, y) = f(x) và g(x, y) = g(y) và khi đó áp dụng Mệnh đề 1.2.1
cho h = f + g, ta nhận được
∂
∗

(f, g)(x
0
)v} ⊂ ∂
∗
(fg)(x
0
)v. (1.8)
Nếu f ổn định tại x
0
, và hoặc f(x
0
) = 0 hoặc g liên tục tại x
0
, thì
∂
∗
(fg)(x
0
)v ⊂ g(x
0
)∂
∗
f(x
0
)v + f(x
0
)∂
∗
g(x
0

, z
0
)(u, w) = z
0
u + y
0
w. Chú ý rằng fg = h ◦ (f, g)
và áp dụng Định lý 1.2.1 để nhận được phần 1, tức là bao hàm thức
(1.8).
Giả sử rằng f ổn định tại x
0
.
Giả sử x
n
= x
0
+ t
n
v
n
, với (t
n
, v
n
) → (o
+
, v). Khi đó,
w
n
: =

n
.
(1.11)
Nếu (w
n
) hội tu tới w ∈ ∂
∗
(fg)(x
0
)v, thì do Nhận xét 1.1.1(1)
(ta lấy thêm 1 dãy con nếu cần thiết), ta nhận được
y
n
:= (f(x
n
) − f(x
0
))/t
n
→ y ∈ ∂
∗
f(x
0
)v.
Nếu f(x
0
) = 0, do f(x
n
) → f(x
0

g(x
0
)v.
14
Số hóa bởi Trung tâm Học liệu />Nếu f(x
0
) = 0 và g liên tục tại x
0
, vì y
n
= f(x
n
)/t
n
→ y, ta suy
ra
w
n
=
f(x
n
)
t
n
g(x
n
) → w = g(x
0
)y ∈ g(x
0

0
)z : (y, z) ∈ ∂
∗
(f, g)(x
0
)v}
= g(x
0
)∂
∗
f(x
0
)v + f(x
0
)∂
∗
g(x
0
)v.
Vì thế mà ta có đẳng thức trong (1.8) và (1.9).
Đối với phần cuối, đẳng thức trong (1.8) và tính ổn định của fg
được chứng minh như trong phần đầu tiên bằng cách áp dụng phần
thứ hai của Định lý 1.2.1 vì (f, g) ổn định bởi mệnh đề 1.1.1(i).
Để chứng minh đẳng thức (1.10) ta hãy xét phiếm hàm tuyến tính
ψ : R
2
→ R được định nghĩa bởi : ψ(y, z) = g(x
0
)y + f(x
0

∗
(f, g) (x
0
) v}
= ∂
∗
(fg) (x
0
) v
như chúng ta vừa chỉ ra và chứng minh được hồn thành.
Ví dụ sau đây cho thấy bao hàm thức trong Mệnh đề 1.2.2 có thể
là chặt.
Ví dụ 1.2.1
Giả sử f : R → R, g : R → R, x
0
= 0 và v = 1. Để cho ngắn gọn,
15
Số hóa bởi Trung tâm Học liệu />ta xét
A = {g(x
0
)y + f(x
0
)z : (y, z) ∈ ∂
∗
(f, g)(x
0
)v},
B = ∂
∗
(fg) (x

A = C = D = {1} và B = [−1, 1].
Các bao hàm thức (1.9) và (1.10) khơng thỏa mãn và (1.8) chặt.
(b) f(x) = x sin(1/x), nếu x = 0, f(0) = 0; g(x) = sin(1/x),
nếu x = 0, g(0) = 1. Khi đó, f ổn định tại x
0
, nhưng khơng
khả vi Hadamard tại x
0
theo phương v, A = {1}, B = [0, 1] và
C = D = [−1, 1]. (1.9) thỏa mãn với bao hàm thức chặt, nhưng
(1.10) lại khơng thỏa mãn.
(c) f(x) = 1 +x sin(1/x), g(x) = 1 −x sin(1/x), và f(0) = g(0) = 0.
Khi đó, f và g ổn định tại x
0
,
∂
∗
(f, g)(x
0
)v = {(y, −y) : −1 ≤ y ≤ 1},
∂
∗
f(x
0
)v = ∂
∗
g(x
0
)v = [−1, 1], A = B = D = {0} và C = [- 2,2];
(1.8) và (1.10) thỏa mãn đẳng thức, và (1.9) thỏa mãn với bao

(hoặc f ổn định tại x
0
, và hoặc f(x
0
) = 0 hoặc
g liên tục tại x
0
) thì
∂
∗
(f/g)(x
0
)v ⊂
g(x
0
)∂
∗
f(x
0
)v − f(x
0
)∂
∗
g(x
0
)v
g(x
0
)
2

0
)v.
Mệnh đề 1.2.4. (Quy tắc hàm max)
Giả sử f = (f
1
, f
2
, . . . , f
p
) : X → R
p
và g : X → R được xác định
bởi
g(x) = max {f
i
(x) : i = 1, 2, . . . , p} .
Khi đó,

α ∈ R : ∃y = (y
1
, y
2
, . . . , y
p
) ∈ ∂
∗
f (x
0
) v.
sao cho α = max {y

, y
2
, . . . , y
p
) = max {y
i
: i = 1, 2, . . . , p}.
Hiển nhiên rằng g = h ◦ f. Hàm h khả vi Hadamard tại y
0
∈ R
p
với
dh (y
0
, u) = max {u
i
: i ∈ I (y
0
)}
ta áp dụng Định lý 1.2.1 và nhận được điều phải chứng minh.
17
Số hóa bởi Trung tâm Học liệu />Chương 2
Điều kiện tối ưu
Chương 2 trình bày các kết quả của Jimenez - Novo [6] về hàm
vững, mối quan hệ với hàm ổn định, hàm khả vi Hadamard, hàm
Lipschitz địa phương, đạo hàm tiếp liên của hàm vững, và các điều
kiện tối ưu cho bài tốn tối ưu vectơ tổng qt với các hàm ổn định
và hàm vững dưới ngơn ngữ đạo hàm tiếp liên. Trong chương này,
chúng tơi cũng trình bày các điều kiện cần và đủ tối ưu dưới dạng
các quy tắc nhân tử Lagrange cho bài tốn tối ưu vectơ với ràng

định nghĩa như sau:
∂f (x) := co {lim Jf (x
i
) : x
i
→ x, x
i
/∈ Ω
f
}
Ta xét khơng gian các m × n- ma trận R
m×n
với chuẩn:
M
m×n
=

m

i=1
r
i

2

1/2
trong đó r
i
là hàng thứ i của M. Ký hiệu B
m×n

, thì
f Lipschitz địa phương tại x với hằng số K = (K
1
, . . . , K
m
)
và ∂f (x) ⊂ KB
m×n
;
(v) ∂f (x) ⊂ ∂f
1
(x) × ∂f
2
(x) × . . . × ∂f
m
(x), trong đó
∂f
1
(x) × . . . × ∂f
m
(x)
là tập tất cả m × n- ma trận có hàng thứ i thuộc ∂f
i
(x) , ∀i.
Nếu m = 1 thì ∂f (x) = ∂f
1
(x) (tức là Jacobian suy rộng trùng với
gradient suy rộng).
19
Số hóa bởi Trung tâm Học liệu />Định lý 2.1.2. (Định lí về giá trị trung bình cho hàm vectơ) [1]

Quan hệ giữa Jacobian suy rộng Clarke và ∂
∗
f (x
0
) v được đưa ra
trong Mệnh đề 2.1.1. Trước hết ta cần một kết quả sau.
Bổ đề 2.1.1.
Giả sử f : R
n
→ R
p
là một Lipschitz địa phương tại x
0
và v ∈ R
n
.
Nếu lim
n→∞
(x
n
− x
0
) /t
n
= v với t
n
→ 0
+
, thì (ta chọn một dãy con
nếu cần thiết)

) = A
n
t
n
v
n
20
Số hóa bởi Trung tâm Học liệu />với A
n
∈ co {∂f (x) : x ∈ [x
0
, x
n
]}. Do ánh xạ đa trị x → ∂f (x) là
nửa liên tục trên, lồi và giá trị compact, ta có dãy A
n
hội tụ tới
A ∈ ∂f (x
0
).
Mệnh đề 2.1.1.
Nếu f : R
n
→ R
p
là một Lipschitz địa phương tại x
0
thì
∂
∗

∈ X theo phương v ∈ X,
hay nói gọn là f vững tại (x
0
, v) nếu
lim
(t,u)→(0
+
,v)
f (x
0
+ tu) − f (x
0
+ tv)
t
= 0.
Đẳng thức trên tương đương với
lim
(t,v

,v

)→(0
+
,v,v)
f (x
0
+ tv

) − f (x
0

0
, v) với v = 0 khơng phụ thuộc vào giá trị của f
tại x
0
, tức là nếu f vững tai (x
0
, v) với v = 0, g (x) = f (x) , ∀x = x
0
và g (x
0
) = y với y tùy ý y ∈ Y thì g vững tại (x
0
, v).
Nếu f : X → Y và g : X → Z. Rõ ràng là f và g vững tại (x
0
, v)
nếu và chỉ nếu (f, g) vững tại (x
0
, v).
Đối với các hàm giá trị trong R, ta biết rằng tổng, cận trên đúng
và cận dưới đúng của một số hạng hữu hạn của các hàm vững là
hàm vững. Ta hãy xem các tính chất của một tích, một thương và
hợp của các hàm vững.
Mệnh đề 2.2.1.
Giả sử f, g là hai hàm từ X vào R. Nếu f và g là các hàm vững
tại (x
0
, v) và bị chặn trên
Γ (x
0

+ tv)
g (x
0
+ tu) − g (x
0
+ tv)
t
và sau đó chuyển qua giới hạn khi (t, u) → (0
+
, 0), ta được điều phải
chứng minh.
Chứng minh tương tự ta nhận được mệnh đề sau đây.
22
Số hóa bởi Trung tâm Học liệu />