BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
NGUYỄN THỊ TƯƠI
ĐẠO HÀM THEO HƯỚNG CỦA HÀM
GIÁ TRỊ TRONG QUY HOẠCH PHI TUYẾN
CÓ THAM SỐ
LUẬN VĂN THẠC SĨ TOÁN HỌC
HÀ NỘI, 2017
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
NGUYỄN THỊ TƯƠI
ĐẠO HÀM THEO HƯỚNG CỦA HÀM
GIÁ TRỊ TRONG QUY HOẠCH PHI TUYẾN
CÓ THAM SỐ
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. NGUYỄN QUANG HUY
HÀ NỘI, 2017
LỜI CẢM ƠN
Trước khi trình bày nội dung chính của luận văn, tôi xin bày tỏ lòng biết ơn sâu
sắc tới PGS.TS.Nguyễn Quang Huy người đã định hướng chọn đề tài và tận tình hướng
dẫn để tôi có thể hoàn thành luận văn này.
Tôi cũng xin bày tỏ lòng biết ơn chân thành tới phòng Sau đại học, các thầy cô
giáo giảng dạy chuyên ngành Toán giải tích trường Đại học Sư phạm Hà Nội 2 đã giúp
đỡ tôi trong suốt quá trình học tập và làm luận văn.
Cuối cùng, tôi xin được gửi lời cảm ơn chân thành tới gia đình và bạn bè đã động
viên, giúp đỡ và tạo điều kiện về mọi mặt trong quá trình học tập để tôi hoàn thành
bản luận văn này.
Hà Nội, ngày 01 tháng 06 năm 2017
Tác giả
Nguyễn Thị Tươi
LỜI CAM ĐOAN
Dưới sự hướng dẫn của PGS.TS. Nguyễn Quang Huy, luận văn Thạc sỹ chuyên
ngành Toán Giải tích với đề tài "Đạo hàm theo hướng của hàm giá trị trong quy hoạch
phi tuyến có tham số" được hoàn thành bởi chính sự nhận thức của bản thân, không
trùng với bất cứ luận văn nào khác.
Trong khi nghiên cứu luận văn, tôi đã kế thừa những thành tựu của các nhà
khoa học với sự trân trọng và biết ơn.
Hà Nội, ngày 01 tháng 06 năm 2017
Tác giả
Nguyễn Thị Tươi
BẢNG KÝ HIỆU
Tập số thực
R
n
R
Không gian Euclide n− chiều
∅
Tập rỗng
dom F
Miền hữu hiệu của F
gr F
Đồ thị của F
lim sup
Giới trên cho dãy số
lim inf
Giới dưới cho dãy số
Lim sup
Giới trên theo tôpô
Lim inf
Giới dưới theo tôpô
D+ F (z; x)
¯
Đạo hàm Dini dưới của ánh xạ đa trị F
tại điểm z theo hướng x
¯
+
D F (z, x)
¯
Đạo hàm Dini trên của ánh xạ đa trị F
tại điểm z theo hướng x
¯
2
D+ F (z, z1 ; x2 )
¯ ¯
Đạo hàm Dini dưới bậc hai của ánh xạ đa trị F
tại điểm z đối với z1 theo hướng x2
¯
¯
D+2 F (z, z1 ; x2 ) Đạo hàm Dini trên bậc hai của ánh xạ đa trị F
¯ ¯
tại điểm z đối với z1 theo hướng x2
¯
¯
Mục lục
Mở đầu
1
1 Đạo hàm theo hướng và các điều kiện chính quy
3
1.1
Đạo hàm theo hướng . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Các điều kiện chính quy . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 Đạo hàm theo hướng của hàm giá trị
13
2.1
Đạo hàm theo hướng bậc nhất của hàm giá trị . . . . . . . . . . . . . .
13
2.2
Đạo hàm theo hướng bậc hai của hàm giá trị . . . . . . . . . . . . . . .
20
Kết luận
28
Tài liệu tham khảo
28
1
MỞ ĐẦU
1. Lý do chọn đề tài
Đạo hàm theo hướng của hàm giá trị có vai trò quan trọng trong việc phân tích
tính ổn định và độ nhạy của bài toán quy hoạch toán học đối với tham số nhiễu. Sự
tồn tại và phép tính các đạo hàm theo hướng của hàm giá trị luôn được các nhà toán
học quan tâm nghiên cứu. V. F. Demyanov là người đầu tiên đề xuất nghiên cứu đạo
hàm theo hướng của hàm giá trị thông qua các khái niệm đạo hàm theo hướng của ánh
xạ đa trị, xem [4]. Việc tính các đạo hàm theo hướng đã được nghiên cứu bởi A. V.
Fiacco, V. F. Demyanov, A. M. Rubinov, R. T. Rockafellar, A. Shapiro, J. F. Bonnans,
A. D. Ioffe, A. Auslender, R. Cominetti, L. Michenko, A. Tarakanov và nhiều tác giả
khác, xem [1, 3, 4, 5, 6, 10, 11, 14, 15] và các tài liệu trích dẫn trong đó. Chúng ta
biết rằng các tính chất khả vi của hàm giá trị của các bài toán tối ưu có ràng buộc
với nhiễu có mối quan hệ gắn kết với các điều kiện chính quy ràng buộc hoặc các điều
kiện chính quy. Chẳng hạn, một trong các cách tiếp cận thành công nhất để nghiên
cứu đạo hàm theo hướng của hàm giá trị là đặt lên bài toán đang xét điều kiện chính
quy Mangasarian - Fromovitz.
Đề tài "Đạo hàm theo hướng của hàm giá trị trong quy hoạch phi tuyến có tham
số" nhằm mục đích nghiên cứu sự tồn tại và và các phép tính đạo hàm theo hướng bậc
nhất và bậc hai của hàm giá trị trong các bài toán quy hoạch phi tuyến có tham số.
2. Mục đích nghiên cứu
Nghiên cứu sự tồn tại đạo hàm theo hướng bậc nhất và bậc hai của hàm giá trị
trong các bài toán quy hoạch phi tuyến có tham số.
2
3. Nhiệm vụ nghiên cứu
Nghiên cứu các khái niệm đạo hàm theo hướng, các điều kiện chính quy, sự tồn
tại và quy tắc tính đạo hàm theo hướng bậc nhất và bậc hai của hàm giá trị trong các
bài toán quy hoạch phi tuyến có tham số.
4. Đối tượng và phạm vi nghiên cứu
+ Đối tượng nghiên cứu: Các bài toán quy hoạch phi tuyến có tham số, các khái
niệm đạo hàm theo hướng, các điều kiện chính quy và sự tồn tại đạo hàm theo
hướng bậc nhất và bậc hai của hàm giá trị.
+ Phạm vi nghiên cứu: Nghiên cứu đối với lớp bài toán quy hoạch phi tuyến có
tham số.
5. Phương pháp nghiên cứu
Sử dụng các phương pháp nghiên cứu của Giải tích hàm, Giải tích đa trị, Lý
thuyết tối ưu, phương pháp phân tích, tổng hợp,...
6. Đóng góp của luận văn
Hệ thống hóa các khái niệm đạo hàm theo hướng, tính chất, điều kiện chính quy.
Áp dụng để chứng minh sự tồn tại và tính đạo hàm theo hướng của hàm giá trị trong
quy hoạch phi tuyến có tham số. Minh họa các khái niệm, tính chất, phương pháp tính
đạo hàm của hàm giá trị thông qua các ví dụ cụ thể.
3
Chương 1
Đạo hàm theo hướng và các điều
kiện chính quy
Trong chương này chúng ta trình bày các khái niệm về đạo hàm theo hướng và
các điều kiện chính quy theo tài liệu [14].
1.1
Đạo hàm theo hướng
Trước tiên ta sẽ đưa ra một số khái niệm về đạo hàm theo hướng. Cho ϕ: Rn → R
là một hàm số. Giả sử x ∈ Rn .
¯
Định nghĩa 1.1. Đạo hàm Dini dưới và trên của hàm ϕ tại điểm x0 theo hướng x,
¯
tương ứng, được xác định bởi
D+ ϕ(x0 ; x) = lim inf t−1 (ϕ(x0 + t¯) − ϕ(x0 )),
¯
x
t↓0
D+ ϕ(x0 ; x) = lim sup t−1 (ϕ(x0 + t¯) − ϕ(x0 )).
¯
x
t↓0
Định nghĩa 1.2. Đạo hàm theo hướng x của hàm ϕ tại điểm x0 , kí hiệu ϕ (x0 , x), xác
¯
¯
định bởi ϕ (x0 , x) = limt↓0 t−1 (ϕ(x0 + t¯) − ϕ(x0 )).
¯
x
Định nghĩa 1.3. Đạo hàm ϕ (x0 ; x) được gọi là đạo hàm Hadamard theo hướng x
¯
¯
nếu ϕ (x0 , x) = limt↓0,ν→¯ t−1 (ϕ(x0 + tν) − ϕ(x0 )).
¯
x
Định nghĩa 1.4. Lấy x1 , x2 ∈ Rn . Đạo hàm cấp hai của hàm ϕ tại điểm x0 theo hướng
¯ ¯
x1 , x2 được kí hiệu bởi:
¯ ¯
ϕ (x0 ; x1 , x2 ) = limt↓0 2t−2 (ϕ(x0 + tx1 + t2 x2 ) − ϕ(x0 ) − tϕ (x0 ; x1 )).
¯ ¯
¯
¯
¯
4
Tương tự, sử dụng các giới hạn tôpô trên và dưới chúng ta giới thiệu đạo hàm
Dini trên và dưới của ánh xạ đa trị.
Định nghĩa 1.5. Đạo hàm Dini dưới và trên của ánh xạ đa trị F : Rn → Rm tại điểm
z = (x, y) ∈ gr F theo hướng x, tương ứng, được xác định bởi
¯
D+ F (z; x) = Lim inft↓0
¯
F (x + t¯) − y
x
,
t
D+ F (z; x) = Lim supt↓0
¯
F (x + t¯) − y
x
.
t
Định nghĩa 1.6. Lấy z = (x, y) ∈ gr F . Đạo hàm Dini dưới và trên của ánh xạ đa trị
F tại điểm z = (x, y) đối với z1 = (x1 , y1 ) theo hướng x2 ∈ Rn được xác định bởi:
¯
¯ ¯
¯
2
¯ ¯
¯
¯
¯
D+ F (z, z1 ; x2 ) = {y2 ∈ Rm | ∃o(t) : y + ty1 + t2 y2 + o(t2 )
∈ F (x + tx1 + t2 x2 ), ∀t ≥ 0},
¯
¯
D+2 F (z, z1 ; x2 ) = {y2 ∈ Rm | ∃o(t), ∃tk ↓ 0 : y + tk y1 + t2 y2 + o(t2 )
¯ ¯
¯
¯
k¯
∈ F (x + tk x1 + t2 x2 )}.
¯
k ¯
Chú ý 1.1. Nếu D+ F (z; x) = D+ F (z; x) thì ta kí hiệu chung là DF (z; x) và gọi đó
¯
¯
¯
là đạo hàm của F tại điểm z = (x, y) ∈ gr F theo hướng x.
¯
2
¯ ¯
¯ ¯
Nếu D+ F (z, z1 ; x2 ) = D+2 F (z, z1 ; x2 ) thì ta kí hiệu chung là
D2 F (z, z1 ; x2 ) và gọi đó là đạo hàm bậc hai của F tại điểm z = (x, y) đối với z1 =
¯ ¯
¯
(x1 , y1 ) theo hướng x2 ∈ Rn .
¯ ¯
¯
Sau đây ta đưa ra một ví dụ về đạo hàm theo hướng.
Ví dụ 1.1. Tính đạo hàm theo hướng của hàm f (x, y) = x2 y 3 −4y tại điểm z = (2; −1)
theo hướng v = (2; 5).
f (x, y) = 2xy 3 i + (3x2 y 2 − 4)j.
√
f (2; −1) = −4i + 8j. Ta có |v| = 29 nên vector đơn vị theo hướng
Ta có
Suy ra
u=
v
2
5
= √ i + √ j.
|v|
29
29
Ta có
Df (z; v) =
.
2
5
32
f (2; −1).u = (−4i + 8j) √ i + √ j = √ .
29
29
29
5
1.2
Các điều kiện chính quy
Trong mục này chúng ta trình bày một số điều kiện chính quy được sử dụng trong
chương sau. Ta xét bài toán P (x) phụ thuộc vào tham số x ∈ Rn :
f (x, y) → min
h (x, y) ≤ 0, i ∈ I = {1, ..., s}
i
h (x, y) = 0, i ∈ I = {s + 1, ..., p}.
i
0
Các hàm f, hi , i = 1, ..., p là các hàm khả vi liên tục trên Rn × Rm . Xét ánh xạ
đa trị F :
x → F (x) = {y ∈ Rm | hi (x, y) ≤ 0, i ∈ I, h(x, y) = 0, i ∈ I0 }.
Giả sử
dom F = {x ∈ Rn | F (x) = ∅}, gr F = {(x, y) | y ∈ F (x), x ∈ Rn }.
Ta giả sử F (x0 ) = ∅. Ánh xạ đa trị F được gọi là bị chặn trong lân cậncủa x0 nếu tồn
tại một lân cận X0 của điểm x0 và tập bị chặn Y0 ⊂ Rm sao cho F (X0 ) ⊂ Y0 . Xét hàm
giá trị
ϕ(x) = inf{f (x, y) | y ∈ F (x)}
và tập nghiệm tối ưu ω(x) = {y ∈ F (x) | f (x, y) = ϕ(x)}.
Ta kí hiệu z = (x, y), λ = (λ1 , ..., λp ), h = (h1 , ..., hp ),I(z) = {i ∈ I | hi (z) = 0}.
Kí hiệu gradient từng phần của hàm g(x, y) với biến số y là
y g.
Hàm Lagrange
của bài toán P (x) được ký hiệu bởi L(z, λ) = f (z) + λ, h(z) .
Giả sử Λ(z) = {λ ∈ Rp |
y L(z, λ)
= 0, λi ≥ 0, λi hi (z) = 0, i ∈ I} là tập các
nhân tử Lagrange tại điểm z của bài toán P (x). Điều kiện chính quy được biết đến
nhiều nhất là điều kiện Mangasarian-Fromovitz [13].
Định nghĩa 1.7. Điều kiện chính quy Mangasarian-Fromovitz thỏa mãn tại điểm
z = (x, y) ∈ grF nếu hệ các vector
¯
y hi (x, y), y0
y hi (x, y), i
= 0, i ∈ I0 ,
∈ I0 độc lập tuyến tính và ∃¯0 :
y
¯
y hi (x, y), y0
< 0, i ∈ I(x, y).
Định nghĩa 1.8. Điều kiện chính quy Mangasarian-Fromovitz nới lỏng thỏa mãn tại
điểm z = (x, y) ∈ gr F nếu hạng của {
cận của điểm y.
y hi (x, y), i
∈ I0 ∪ I(x, y)} là hằng số trong lân
6
Kết quả đầu tiên về sự tồn tại đạo hàm bậc hai theo hướng ϕ (x0 ; x1 , x2 ) được
¯ ¯
chỉ ra trong [4] cho trường hợp bài toán P (x) lồi theo y, ma trận
2
yy f (x, y)
xác định
dương và F (x) thỏa mãn điều kiện chính quy Slater.
Trong [15], A. Shapiro đã chỉ ra rằng dưới điều kiện chính quy Mangasarian Fromovitz tại z0 = (x0 , y0 ) ∈ {x0 } × ω(x0 ),ϕ (x0 ; x) và ϕ (x0 ; x1 , x2 ) tồn tại nếu điều
¯
¯ ¯
kiện đủ tối ưu cấp hai mạnh
sup
y,
¯
λ∈Λ2 (z0 ;x1 )
¯
2
y
yy L(z0 , λ)¯
>0
được thỏa mãn đốivới mọi vector y ∈ D(z0 ) = {¯ ∈ Γ(z0 ; 0) |
¯
y
Γ(z; x) = {¯ ∈ Rm |
¯
y
hi (z), z ≤ 0, i ∈ I(z),
¯
Λ2 (z; x) = {λ ∈ Λ(z) |
¯
¯
x L(z, λ), x
¯
y f (z0 ), y
≤ 0}, ở đó
hi (z), z = 0, i ∈ I0 },
¯
= max
λ∈Λ(z)
¯
x L(z, λ), x
}.
Kết quả tương tự cũng được tìm thấy trong [1] dưới điều kiện chính quy MangasarianFromovitz theo hướng (xem trong [8]).
Giả sử ν ∈ Rm , C ⊂ Rm , B là hình cầu đơn vị có tâm O trong không gian tương
ứng. Ta kí hiệu ρ(ν, C) = inf y∈C |ν − y|, ở đó |y| là chuẩn Euclid của vector y.
Định nghĩa 1.9. Điều kiện chính quy (LI) thỏa mãn tại điểm z0 ∈ gr F hay ánh xạ
F là (LI)-chính quy tại điểm z0 nếu hệ các vector {
y hi (z0 ), i
∈ I(z0 ) ∪ I0 } độc lập
tuyến tính.
Định nghĩa 1.10. Ánh xạ đa trị F được gọi là R-chính quy ( đối với một tập S ⊂
dom F ) tại điểm z0 = (x0 , y0 ) ∈ gr F nếu ∃α > 0, δ1 > 0, δ2 > 0 sao cho:
ρ(y, F (x)) ≤ α max{0, hi (x, y), i ∈ I, |hi (x, y)|, i ∈ I0 }
với mọi x ∈ x0 + δ1 B(x ∈ (x0 + δ1 B) ∩ S), y ∈ y0 + δ2 B.
Định nghĩa 1.11. Tập F (x0 ) được gọi là R-chính quy tại điểm y0 ∈ F (x0 ) nếu
∃α > 0, δ > 0 sao cho:
ρ(y, F (x0 )) ≤ α max{0, hi (x0 , y), i ∈ I, |hi (x0 , y)|, i ∈ I0 }
với mọi y ∈ y0 + δB.
7
Định nghĩa 1.12. Ta định nghĩa
h+ = max{hi (z), i = 1, ...., r, |hi (z)|, i = r + 1, ..., p},
h0 = max{0, hi (z), i = 1, ...., r, |hi (z)|, i = r + 1, ..., p}.
Bổ đề 1.1. Giả sử F không là R-chính quy tại điểm z0 = (x0 , y0 ). Khi đó tồn tại dãy
δk ↓ 0, yk → 0 và xk → x0 sao cho h+ (xk , yk ) > 0 và
|h+ (xk , y)| − |h+ (xk , yk )| ≥ −δk |y − yk |
(1.1)
vơí mọi y ∈ Rm .
Bổ đề 1.2. Giả sử hàm f : X → r đạt cực tiểu hoặc cực đại trên tập M ⊂ X tại điểm
x0 ∈ M . Khi đó với mọi hướng x ∈ γM (x0 ) ta có
¯
D+ f (x0 ; x) ≥ 0
¯
D+ f (x0 ; x) ≤ 0.
¯
Định lý 1.1. Giả sử hàm f nửa liên tục trên là trên khả vi đều yếu theo hướng x tại
¯
mọi điểm của tập {x0 } × Ω(x0 ). Khi đó hàm Φ = max{f (x, y) | y ∈ F (x)} là khả vi
theo hướng x tại điểm x0 và
¯
Φ (x0 ; x) = max f (x0 , y0 ; x).
¯
¯
y0 ∈Ω(x0 )
Định lý 1.2. Giả sử ánh xạ đa trị F là Mangasarian-Fromovitz chính quy tại điểm
z0 = (x0 , y0 ) ∈ grF . Khi đó ánh xạ F là R-chính quy tại z0 .
Chứng minh. Giả sử điều kiện Mangasarian-Fromovitz thỏa mãn tại điểm z0 và ánh
xạ F không là chính quy tại điểm z0 . Khi đó theo Bổ đề 1.1, tồn tại dãy δk ↓ 0, yk →
y0 , xk → x0 sao cho h+ (xk , yk ) > 0 và bất đẳng thức (1.1) đúng. Ta kí hiệu gk (y) =
|h+ (xk , y)|. Theo bất đẳng thức (1.1) ta có:
gk (y) − gk (yk ) ≥ −δk |y − yk |,
hàm gk (y) = gk (y) + δk |y − yk | đạt cực tiểu tại yk . Do |h+ (xk , yk )| = h+ (xk , yk ) > 0,
nên trong lân cận đủ bé của yk , ta có:
|h+ (xk , y)| = h+ (xk , y).
8
Do đó gk (y) = h+ (xk , y) + δk |y − yk |. Áp dụng điều kiện đủ cực tiểu (xem trong Bổ đề
¯
¯
1.2) cho gk (y) tại điểm yk , ta được gk (yk ; y ) ≥ 0 với mọi y ∈ Rm . Điều này dẫn tới
0 ≤ h+ (xk , yk ; y ) + δk |¯|.
¯
y
(1.2)
Giả sử ta tìm được giá trị của h+ (xk , yk ; y ). Ta kí hiệu
¯
I(zk ) = {i ∈ I | hi (zk ) = h+ (zk )}
I0 (zk ) = {i ∈ I0 | hi (zk ) ≤ h+ (zk )}.
Với |hi (zk )| = h+ (zk ) > 0 ta có
¯
hi (zk ; y ) =
|hi (zk )|y =
¯
¯
y hi (zk ), y
hi (zk )
|hi (zk )|
, i ∈ I(zk ),
, i ∈ I0 (zk ).
¯
y hi (zk ), y
Áp dụng Định lí 1.1 ta được
h+ (zk ; y ) = max{
¯
hi (zk )
|hi (zk )|
¯
y hi (zk ), y
σi (zk )λi
, i ∈ I(zk ),
¯
y hi (zk ), y
¯
y hi (zk ), y
,
i ∈ I0 (zk )}
p
r
=
max
λ∈Λ(zk )
λi
y hi (zk )
+
i=1
i=r+1
với A(zk ) = {λ ∈ Rp | λi ≥ 0, i = 1, ..., p;
p
i=1
λi = 1, λi hi (zk ) = λi h0 (zk ), i =
1, ..., r, λi |hi (zk )| = λi h0 (zk ), i = r + 1, ..., p} và σi (zk ) =
hi (zk )
,i
|hi (zk )|
= r + 1, ..., p. Kết hợp
bất đẳng thức (1.2) ta viết điều kiện này về dạng
p
r
0∈{
λi
y hi (zk )
i=1
+
λi σi (zk )
y hi (zk )
¯
| λ ∈ A(zk )} + δk B,
i=r+1
hay
p
r
λi (zk )
0=
y hi (zk )
+
i=1
λi σi (zk )
y hi (zk )
+ δk ξk
(1.3)
i=r+1
với λ(zk ) ∈ A(zk ), σi (zk ), ξk ∈ B. Do dãy {λ(zk )}, {σi (zk )}, {ξk } bị chặn nên không mất
tính tổng quát, giả sử λ(zk ) → λ, σi (zk ) → 1, ξk → ξ. Kiểm tra giới hạn trong đẳng
thức (1.3) ta được:
p
0=
λi
y hi (z0 )
i=1
với λ = (λ1 , ..., λp ) = 0, λi ≥ 0, λi hi (z0 ) = 0, i = 1, ..., r. Mặt khác Λ0 (z0 ) = {0} nên
điều kiện Mangasarian-Fromovitz không thỏa mãn tại z0 . Từ đó ánh xạ F phải là
R-chính quy.
9
Nhận xét 1.1. Các điều kiện chính quy có mối quan hệ chặt chẽ với nhau:
(LI) =⇒ (M F ) =⇒ (R).
Điều kiện chính quy Mangasarian-Fromovitz kéo theo điều kiện chính quy MangasarianFromovitz nới lỏng, điều kiện chính quy Mangasarian-Fromovitz tại điểm z = (x, y) ∈
gr F kéo theo R-chính quy của ánh xạ đa trị F tại z. Nhưng điều ngược lại không
đúng. Bổ đề bên dưới đưa ra một ví dụ quan trọng về ánh xạ đa trị R-chính quy.
Bổ đề 1.3. [12] Giả sử ai ∈ Rm , các hàm bi (x) liên tục với i = 1, ..., p. Khi đó ánh xạ
F được xác định bởi
F (x) = {y ∈ Rm | ai , y + bi (x) ≤ 0, i = 1, ..., p}
(1.4)
là R-chính quy tại mỗi điểm z0 = (x0 , y0 ) ∈ gr F sao cho x0 ∈ int dom F . Hơn nữa,
tính R-chính quy thỏa mãn với mọi y ∈ Y và x ∈ int dom F .
Chứng minh. Giả sử hi (z) = ai , y + bi (x), h(z) = max{hi (z) | i = 1, ..., p}.
Ta lấy tùy ý một điểm biên y từ F (x), với x ∈ V (x0 ) ⊂ int dom F . Tập các phần
tử y ∈ F (x) sao cho ρ(˜, F (x)) = |˜ − y| trùng với tập {y = y(t) | y(t) = y + tl, l ∈
˜ /
y
y
NF (x) (y), |l| = 1} với t = ρ(y(t), F (x)) ( ở đó NF (x) (y) là nón pháp tuyến của tập F (x)
tại điểm y ). Với y(t) như trên ta có:
h(x, y(t)) ≥ t max { ai y + tl + bi (x)}
i∈I(x,y)
≥
max
max ai , l
tβ(x, y).
l∈NF (x) (y) i∈I(x,y)
Giả sử β(x, y) ≤ 0. Khi đó với l0 ∈ NF (x) (y), |l0 | = 1, bất đẳng thức
max ai , l0 ≤ 0
i∈I(x,y)
thỏa mãn. Từ đó với t đủ nhỏ, t > 0 ta có:
0 < h(x, y + tl0 ) = max{ ai , y + bi (x) + t ai , l0 }
= t max ai , l0 = tβ(x, y) ≤ 0.
i∈I(x,y)
Mâu thuẫn này chứng tỏ β(x, y) > 0. Mặt khác,
β(x, y) =
max
max ai , l = max
i∈NF (x) (y),|l|=1 i∈I(x,y)
max ai ,
¯
λ∈Λ(x,y) i∈I(x,y)
λj aj ,
j∈I(x,y)
10
với
p
¯
Λ(x, y) = {λ ∈ Rp | λj ≥ 0, j ∈ I(x, y), λj = 0, j ∈ I(x, y),
/
λj aj = 1}.
j=1
Do β(x, y) xác định bởi tập I(x, y) và chỉ tồn tại một số hữu hạn các tập con của tập
I = {1, ..., p}, khi đó β(x, y) ≥ β > 0 với y thuộc biên của F (x) và x tùy ý thuộc
V (x0 ). Do y ∈ F (x), y = y + lt, với t > 0, l ∈ NF (x) (y), |l| = 1, y là một điểm biên của
˜/
˜
F (x), khi đó với bất kì y ∈ F (x), ta có:
/
h(x, y ) ≥ βt ≥ βρ(˜, F (x))
˜
y
thỏa mãn với mọi x ∈ V (x0 ).
Ví dụ sau đây cho thấy ánh xạ F xác định bởi (1.4) không thỏa mãn điều kiện
Mangasarian-Fromovitz.
Ví dụ 1.2. Giả sử F (x) = {y ∈ R2 | y1 + y2 ≤ x1 , y1 + y2 ≥ x2 , y1 ≥ 0, y2 ≥ 0}, x ∈
1
X = R2 . Ta chọn điểm y0 = ( 1 , 2 ), x0 = (1, 1).
2
Điều kiện Mangasarian-Fromovitz không thỏa mãn tại điểm z0 .
Trong số các tính chất Lipschitz khác của ánh xạ đa trị, các tính chất đóng vai
trò quan trọng được nói đến là liên tục giả Lipschitz (xem trong [2]) và liên tục giả
Lipschitz trên (xem trong [9], [11]).
Định nghĩa 1.13. Hàm F được gọi là giả Lipschitz (đối với tập S ⊂ Rn ) tại điểm
z0 = (x0 , y0 ), với y0 ∈ F (x0 ) nếu tồn tại lân cận V (x0 ) và V (y0 ) của các điểm x0 , y0 và
một số l > 0 sao cho:
F (x) ∩ V (y0 ) ⊂ F (x2 ) + l|x2 − x1 |B
với mọi x1 , x2 ∈ V (x0 )(V (x0 ) ∩ S).
Định nghĩa 1.14. Hàm F được gọi là giả Lipschitz trên tại điểm z0 = (x0 , y0 ) ∈ gr F
(đối với tập S ⊂ Rn ) nếu tồn tại lân cận V (x0 ) và V (y0 ) của các điểm x0 , y0 và một số
l > 0 sao cho:
F (x) ∩ V (y0 ) ⊂ F (x0 ) + l|x − x0 |B
với mọi x ∈ V (x0 ) ∩ (V (x0 ) ∩ S).
11
Định nghĩa 1.15. Hàm F được gọi là liên tục Lipschitz trên địa phương tại điểm
z0 = (x0 , y0 ) ∈ gr F , nếu tồn tại lân cận V (x0 ) và V (y0 ) của các điểm x0 , y0 và một số
l > 0 sao cho:
F (x) ∩ V (y0 ) ⊂ y0 + l|x − x0 |B
với mọi x ∈ V (x0 ).
Giả sử z0 = (x0 , y0 ) ∈ gr F, z = (¯, y ). Ta xét tập
¯
x ¯
Γ(z0 ; x) = {¯ ∈ Rm |
¯
y
hi (z0 ), z ≤ 0, i ∈ I(z0 ),
¯
hi (z0 ), z = 0, i ∈ I0 }.
¯
Giả sử
z1 = (x1 , y1 ), z2 = (x2 , y2 ),
¯
¯ ¯ ¯
¯ ¯
I 2 (z0 , z1 ) = {i ∈ I(z0 ) |
¯
hi (z0 ), z1 = 0}
¯
với y1 ∈ Γ(z0 ; x1 ). Ta đưa vào tập
¯
¯
Γ2 (z0 , z1 ; x2 ) = {y2 ∈ Rm |
¯ ¯
¯
i ∈ I 2 (z0 , z1 ),
¯
hi (z0 ), z2 +
¯
hi (z0 ), z2 +
¯
1
z1 ,
¯
2
2
1
z1 ,
¯
2
2
hi (z0 )z1 ≤ 0,
¯
hi (z0 )z1 = 0, i ∈ I0 }.
¯
Bổ đề 1.4. [12] Giả sử ánh xạ đa trị F là R-chính quy tại điểm z0 = (x0 , y0 ) ∈ gr F .
Khi đó các khẳng định bên dưới thỏa mãn:
(1) F là R-chính quy bất kì điểm thuộc lân cận của z0 ;
(2) F là giả Lipschitz tại z0 ;
(3) F khả vi tại z0 với bất kì hướng x ∈ Rn và DF (z0 ; x) = Γ(z0 ; x) = ∅ ;
¯
¯
¯
(4) Với mọi x1 , x2 ∈ Rn và y1 ∈ Γ(z0 ; x1 ), tồn tại đạo hàm bậc hai của ánh xạ đa trị
¯ ¯
¯
¯
F và D2 F (z0 , z1 ; x2 ) = Γ2 (z0 , z1 ; x2 ) = ∅.
¯ ¯
¯ ¯
Bổ đề 1.5. [12] Giả sử ánh xạ đa trị F là R-chính quy tại điểm z0 = (x0 , y0 ) ∈
{x0 } × ω(x0 ). Khi đó các khẳng định sau thỏa mãn:
(1) Ánh xạ nghiệm ω : x → ω(x) là nửa liên tục trên tại x0 với xk → x0 , yk ∈
ω(xk ), yk → y kéo theo y ∈ ω(x0 );
12
(2) Hàm ϕ(x) là Lipschitz trong lân cận của x0 ;
(3) Tồn tại một lân cận V (z0 ) của z0 và M > 0 sao cho:
Λ(z) ∩ {λ ∈ Rp |
p
i=1
|λi | ≤ M } = ∅ với mọi z = (x, y) ∈ V (z0 ) ∩ grω.
Bổ đề 1.6. Giả sử tập F (x0 ) là R-chính quy tại y0 ∈ F (x0 ). Khi đó ánh xạ đa trị F
là giả Lipschitz trên tại z0 = (x0 , y0 ).
Chứng minh. Giả sử V (x0 ) là lân cận đủ nhỏ của điểm x0 . Do tập F (x0 ) là R-chính
quy nên ∃α > 0, δ > 0 sao cho với mọi y ∈ F (x) ∩ V (y0 ), với V (y0 ) = y0 + δB, bất
đẳng thức
ρ(y, F (x0 )) ≤ α max{0, hi (x0 , y), i ∈ I, |hi (x0 , y)|, i ∈ I0 }
thỏa mãn. Theo tính liên tục của các hàm số, không mất tính tổng quát ta giả sử
ρ(y, F (x0 )) ≤ α max{0, hi (x0 , y) − hi (x, y), i ∈ I(x0 , y0 ),
|hi (x0 , y) − hi (x, y)|, i ∈ I0 }
Do đó
ρ(y, F (x0 )) ≤ α max{0, l0 |x0 − x|, i ∈ I(x0 , y0 ), l0 |x0 − x|, i ∈ I0 }
≤ αl0 |x − x0 |
với l0 = max{|
x hi (x, y)|
: y ∈ V (y0 ), x ∈ V (x0 ), i ∈ I(x0 , y0 ) ∪ I0 }.
Điều kiện cuối tương đương với bao hàm
F (x) ∩ V (y0 ) ⊂ F (x0 ) + αl0 |x − x0 |B
với mọi x ∈ V (x0 ). Do đó F là giả Lipschitz trên.
Trong chương này, chúng ta đã trình bày hệ thống các khái niệm về đạo hàm
theo hướng, các quy tắc tính, các điều kiện chính quy và mối quan hệ giữa chúng. Dưới
các điều kiện chính quy, chúng ta sẽ thiết lập được các điều kiện đủ cho sự tồn tại đạo
hàm bậc nhất, bậc hai theo hướng của hàm giá trị được trình bày trong chương sau.
13
Chương 2
Đạo hàm theo hướng của hàm giá
trị
Trong chương này ta sẽ trình bày các định lí và bổ đề liên quan tới sự tồn tại và
cách tính đạo hàm theo hướng bậc nhất, bậc hai của hàm giá trị. Các tài liệu tham
khảo chủ yếu được sử dụng trong chương này là [3, 12, 14].
2.1
Đạo hàm theo hướng bậc nhất của hàm giá trị
Bây giờ ta sẽ trình bày về đạo hàm theo hướng bậc nhất của hàm giá trị (xem
trong [14]). Nhưng trước tiên ta có bổ đề sau:
Bổ đề 2.1. Giả sử ánh xạ đa trị F là R-chính quy tại z0 = (x0 , y0 ) ∈ gr ω. Khi đó
với bất kì x ∈ Rn và mọi dãy tk ↓ 0, {xk }, {yk }, {y0k } sao cho xk = x0 + tk x + o(tk ),
¯
¯
yk ∈ ω(xk ) và yk → y0 ∈ ω(x0 ) khi k → ∞,, y0k ∈ ω(x0 ), |y0k − yk | ≤ M |xk − x0 |, M =
const > 0. Bắt đầu với k = k0 , ta có khai triển
yk = y0k +tk y1k +o(tk ), ϕ(xk )−ϕ(x0 ) = tk
¯
f (z0k ), z1k +o(tk ), với z0k = (x0 , y0k ), z1k =
¯
¯
(¯, y1k ), {¯1k } là dãy bị chặn sao cho y1k ∈ Γ(z0k ; x).
x ¯
y
¯
¯
Chứng minh. Theo các điều kiện của bổ đề cho dãy yk ∈ ω(xk ), k = 1, 2, ... và y0k ∈
ω(x0 ), k = 1, 2, ..., tồn tại một dãy {νk } sao cho yk − y0k = tk νk , k = 1, 2, ....
Giả sử zk = (xk , yk ), z0k = (x0 , y0k ), ta có:
hi (zk ) − hi (z0k ) ≤ 0 với mọi i ∈ I(z0k ) và hi (zk ) − hi (z0k ) = 0 với mọi i ∈ I0 . Tiếp theo,
14
vì
x hi (z0k ), xk
− x0 +
x hi (z0k ), xk
y hi (z0k ), yk
− x0 +
− y0k + o(tk ) ≤ 0, ∀i ∈ I(z0k ),
y hi (z0k ), yk
− y0k + o(tk ) = 0, ∀i ∈ I0
nên
¯
x hi (z0k ), x
+
y hi (z0k ), νk
¯
x hi (z0k ), x
+
+ µi (tk ) ≤ 0, i ∈ I(z0k ),
y hi (z0k , νk
+ µi (tk ) = 0, i ∈ I0 ,
với µi (tk ) → 0 khi k → ∞. Do đó tồn tại dãy µ(tk ) → 0 sao cho µ(tk ) > 0 và
¯
x hi (z0k ), x
|
+
¯
x hi (z0k ), x
y hi (z0k ), νk
+
≤ µ(tk ), i ∈ I(z0k ),
y hi (z0k ), νk
| ≤ µ(tk ), i ∈ I0 .
Vì ánh xạ đa trị F là R-chính quy tại điểm z0 = (x0 , y0 ) ∈ gr ω trong lân cận
của z0 nên Γ(z0k ; x) = ∅. Tiếp theo, theo Bổ đề 1.3 ta có:
¯
ρ(νk , Γ(z0k ; x) ≤ α max{0, tk M1 } = αµ(tk ),
¯
với α và M1 là những số dương. Do đó, tồn tại dãy {qk } sao cho qk → 0 khi k → ∞ và
y1k = νk − qk ∈ Γ(z0k ; x). Mặt khác νk = y1k + qk với y1k ∈ Γ(z0k ; x).
¯
¯
¯
¯
¯
Do đó yk = y0k + tk y1k + o(tk ) với y1k ∈ Γ(z0k ; x). Bằng cách giả sử z1k = (¯, y1k ),
¯
¯
¯
¯
x ¯
ta tìm được
ϕ(xk ) − ϕ(x0 ) = f (xk , yk ) − f (x0 , y0k )
=
= tk
f (z0k ), (xk − x0 , yk − y0k ) + o(tk )
f (z0k ), z1k + o(tk ).
¯
Định lý 2.1. Giả sử ánh xạ đa trị F là R-chính quy và ánh xạ nghiệm ω là giả Lipschitz
trên tại mọi điểm z0 = (x0 , y0 ) ∈ {x0 } × ω(x0 ). Khi đó tồn tại đạo hàm Hadamard
ϕ (x0 ; x) theo bất kì hướng x ∈ Rn và
¯
¯
ϕ (x0 ; x) =
¯
inf
min
y0 ∈ω(x0 ) y ∈Γ(z0 ;¯)
¯
x
f (z0 ), z =
¯
inf
max
y0 ∈ω(x0 ) λ∈Λ(z0 )
¯
x L(z0 , λ), x
.
Chứng minh. (1) Giả sử y0 ∈ ω(x0 ) và z0 = (x0 , y0 ). Theo Bổ đề 1.4 ta có DF (z0 ; x) =
¯
Γ(z0 ; x) = ∅. Giả sử y ∈ Γ(z0 ; x). Khi đó, theo định nghĩa của đạo hàm DF (z0 ; x), tồn
¯
¯
¯
¯
tại một hàm o(t) sao cho y0 + t¯ + o(t) ∈ F (x0 + t¯) với mọi t ≥ 0. Do đó
y
x
1
1
(ϕ(x0 + t¯) − ϕ(x0 )) ≤
x
(f (x0 + t¯, y0 + t¯ + o(t)) − f (x0 , y0 ))
x
y
t
t
=
f (z0 ), z + o(t)/t.
¯
(2.1)
- Xem thêm -