Tài liệu đạo hàm theo hướng của hàm giá trị trong quy hoạch phi tuyến có tham số

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)