ĐẠI HỌC THÁI NGUYÊN 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 TOÁN TỐI ƯU ĐA MỤC TIÊU VỚI CÁC HÀM ỔN ĐỊNH LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Ngun - 2013 Số hóa Trung tâm Học lieäu http://lrc.tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN 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 TOÁN TỐI ƯU ĐA MỤC TIÊU VỚI CÁC HÀM ỔN ĐỊNH Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 60 46 01 12 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 Ngun - 2013 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Mục lục Mở đầu 1 Hàm ổn định đạo hàm tiếp liên 1.1 Hàm ổn định đạo hàm tiếp liên 1.2 Các quy tắc tính đạo hàm tiếp liên 3 11 Điều kiện tối ưu 18 2.1 2.2 2.3 2.4 Jacobian suy rộng Clarke Các hàm vững Các điều kiện tối ưu Các quy tắc nhân tử Lagrange Kết luận 18 21 30 37 41 Tài liệu tham khảo 42 ii Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Mở đầu Lý thuyết điều kiện tối ưu vectơ phần quan trọng lý thuyết tối ưu hóa Người ta thiết lập điều kiện tối ưu cho tốn tối ưu khơng trơn với hàm Lipschitz địa phương ngôn ngữ vi phân khác nhau, chẳng hạn vi phân hàm lồi, vi phân Clarke, Michel Penot, Mordukhovich Lớp hàm ổn định điểm tập rộng lớp hàm Lipschitz địa phương tập Bài tốn tối ưu vectơ với hàm ổn định Jimenez - Novo [6] nghiên cứu thiết lập điều kiện tối ưu ngôn ngữ đạo hàm tiếp liên Jimenez - Novo [6] đạo hàm tiếp liên có nhiều tính chất phong phú lớp hàm ổn định Đây vấn đề thời nhiều tác giả quan tâm nghiên cứu Chính em chọn đề tài: " Điều kiện tối ưu cho nghiệm hữu hiệu toán tối ưu đa mục tiêu với hàm ổn định " Luận văn trình bày lý thuyết đạo hàm tiếp liên cho hàm ổn định, hàm vững điều kiện tối ưu Jimenez - Novo [6] cho toán tối ưu đa mục tiêu tổng quát khơng gian định chuẩn tốn tối ưu đa mục tiêu với ràng buộc nón ràng buộc đẳng thức không gian hữu hạn chiều Luận văn bao gồm phần mở đầu, hai chương, kết luận danh mục tài liệu tham khảo Chương Hàm ổn định đạo hàm tiếp liên Trình bày kết nghiên cứu Jimenez - Novo ([6], 2008) hàm ổn định đạo hàm tiếp liên hàm ổn định, quy tắc tính đạo hàm tiếp liên lớp hàm ổn định bao gồm: quy Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ tắc hàm hợp, đạo hàm tiếp liên tổng, tích, thương hai hàm max số hữu hạn hàm ổn định Chương Điều kiện tối ưu Trình bày kết Jimenez - Novo [6] 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 hàm vững, điều kiện tối ưu cho toán tối ưu vectơ tổng quát với hàm ổn định hàm vững ngôn ngữ đạo hàm tiếp liên Chương trình bày điều kiện cần đủ tối ưu dạng quy tắc nhân tử Lagrange cho toán tối ưu vectơ với ràng buộc nón ràng buộc đẳng thức không gian hữu hạn chiều, ngôn ngữ đạo hàm tiếp liên Luận văn hoàn thành trường Đại học Khoa học, Đại học Thái Nguyên hướng dẫn tận tình PGS TS Đỗ Văn Lưu Em xin bày tỏ lòng biết ơn chân thành sâu sắc tận tâm nhiệt tình Thầy suốt trình em thực 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 Quan hệ quốc tế, Khoa Toán - Tin trường Đại học Khoa học, Đại học Thái Nguyên quan tâm giúp đỡ em suốt thời gian học tập trường Em xin gửi lời cảm ơn đến gia đình, bạn bè đồng nghiệp động viên, giúp đỡ em trình học tập Do thời gian kiến thức hạn chế nên luận văn khơng tránh khỏi thiếu sót Em mong nhận góp ý thầy để luận văn hoàn thiện Em xin chân thành cảm ơn! Thái Nguyên, ngày 15 tháng năm 2013 Tác giả Trịnh Duy Bình Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Chương Hàm ổn định đạo hàm tiếp liên Chương trình bày kết nghiên cứu Jimenez - Novo ([6], 2008) hàm ổn định đạo hàm tiếp liên hàm ổn định, quy tắc tính đạo hàm tiếp liên lớp hàm ổn định bao gồm: quy tắc hàm hợp, đạo hàm tiếp liên tổng, tích, thương hai hàm max số hữu hạn hàm ổn định 1.1 Hàm ổn định đạo hàm tiếp liên Giả sử X, Y không gian định chuẩn, M tập X Ký hiệu B (x0 , δ) hình cầu mở tâm x0 , bán kính δ Kí hiệu intM , clM , coM , coneM tương ứng phần M, bao đóng M, bao lồi M, nón sinh M, Cone+ M = {αx : α > 0, x ∈ M } Nón D ⊂ Y gọi nón nhọn D ∩ (−D) = {0} Trong chương ta giả thiết D nón lồi đóng nhọn có phần khác rỗng Nón D sinh thứ tự khơng gian Y Định nghĩa 1.1.1 Giả sử M ⊂ X x0 ∈ X (a) Nón tiếp tuyến M x0 T (M, x0 ) = v ∈ X : ∃tn → 0+ , ∃vn → v cho x0 + tn ∈ M, ∀n ∈ N ; Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ (b) Nón phương đạt M x0 A(M, x0 ) = v ∈ X : ∀tn → 0+ , ∃vn → v cho x0 + tn ∈ M, ∀n ∈ N ; (c) Nón tiếp tuyến phần M điểm x0 IT (M, x0 ) = v ∈ X : ∃δ > cho x0 + tu ∈ M ∀t ∈ (0, δ] , ∀u ∈ B (v, δ) ; (d) Nón tiếp tuyến phần dãy M x0 ITs (M, x0 ) = v ∈ X : ∃δ > 0, ∃tn → 0+ cho x0 + tn u ∈ M ∀n ∈ N, ∀u ∈ B (v, δ) Chú ý ta ln có A (M, x0 ) ⊂ T (M, x0 ) Tập hợp M gọi khả dẫn xuất (derivable) điểm x0 (xem [10]) A(M, x0 ) = T (M, x0 ) Ta nói hàm f : X → Y khả dẫn xuất đồ thị (graph derivable) x0 theo phương v ∈ X với ∀y ∈ Y , (v, y) ∈ T (graphf , (x0 , f (x0 ))) ⇒ (v, y) ∈ A (graphf , (x0 , f (x0 ))), graphf = {(x, y) ∈ X × Y : y = f (x)} Hàm f khả dẫn xuất đồ thị x0 f khả dẫn xuất đồ thị x0 theo phương ∀v ∈ X T (graphf, (x0 , f (x0 ))) = A (graphf, (x0 , f (x0 ))) tức tập hợp graphf khả dẫn xuất điểm (x0 , f (x0 )) Sau ví dụ hàm khả dẫn xuất đồ thị Ví dụ 1.1.1 Giả sử f : R → R cho f (x) = x sin x = x f (0) = Khi f khả dẫn xuất đồ thị Đạo hàm Hadamard f : X → Y x0 theo phương v ∈ X f (x0 + tu) − f (x0 ) df (x0 , v) = lim+ (t,u)→(0 ,v) t Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ f hàm khả vi Hadamard x0 theo phương v df (x0 , v) tồn tại, f hàm khả vi Hadamard x0 df (x0 , v) tồn với v ∈ X Nếu f khả vi Frechet x0 , đạo hàm Frechet kí hiệu ∇f (x0 ) Nếu hàm f : X → R đạo hàm Hadamard f x0 định nghĩa df (x0 , v) = lim+ (t,u)→(0 tương ứng df (x0 , v) = inf (f (x0 + tu) − f (x0 )) ,v) t lim+ (t,u)→(0 sup (f (x0 + tu) − f (x0 )) ,v) t Định nghĩa 1.1.2 [1] Ta nói f : X → Y hàm ổn định x0 ∈ X tồn miền lân cận U x0 k > cho f (x) − f (x0 ) ≤ k x − x0 , ∀x ∈ U Nếu f (x) − f (x ) ≤ k x − x , ∀x, x ∈ U , ta nói f hàm Lipschitz địa phương x0 Nếu với x0 ∈ X, tồn lân cận U x0 cho f hàm Lipschitz địa phương x0 ta nói f hàm Lipschitz địa phương X Rõ ràng hàm f Lipschitz địa phương X kéo theo f hàm ổn định x0 ∈ X, điều ngược lại khơng Ví dụ hàm f Ví dụ (1.1.1) ổn định với x0 ∈ R f không hàm Lipschitz địa phương Chúng ta sử dụng đạo hàm theo phương sau cho ánh xạ đa trị (xem [8]) Định nghĩa 1.1.3 Giả sử f : X → Y x0 , v ∈ X Đạo hàm tiếp liên f x0 theo phương v tập hợp sau Y: ∂∗ f (x0 ) v = y ∈ Y : ∃ (tn , ) → (0+ , v) cho lim (f (x0 + tn ) − f (x0 )) /tn = y n→∞ Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Chú ý ∂∗ f (x0 )v gọi đạo hàm tiếp liên ánh xạ đa trị x → {f (x)} Do ∂∗ f (x0 )v tập hợp đóng ánh xạ đa trị v → ∂∗ f (x0 ) v dương Nếu f khả vi Hadamard x0 ∂∗ f (x0 )v = {df (x, v)} ∀v ∈ X Cho f : X → Y g : X → Z, Z khơng gian định chuẩn khác Hàm (f, g) : X → Y × Z xác định (f, g)(x) = (f (x), g(x)) Trong khơng gian Y × Z, ta lấy (y, z) = y + z Định lý sau (cách chứng minh đơn giản) cho ta số tính chất hàm (f, g) liên quan đến tính ổn định đạo hàm tiếp liên Mệnh đề 1.1.1 [6] (i) f g ổn định x0 ⇔ (f, g) ổn định x0 (ii) Với v ∈ X, ∂∗ (f, g) (x0 ) v ⊂ ∂∗ f (x0 ) v × ∂∗ g (x0 ) v Nếu f g khả vi Hadamard x0 theo phương v ta có dấu Bao hàm thức (ii) ví dụ 1.1.2 Nhận xét 1.1.1 (1) Rõ ràng f : X → Rp ổn định taị x0 ∂∗ f (x0 ) v = φ, ∀v ∈ X Thật với dãy tn → 0+ → v, (với n đủ lớn) ta có f (x0 + tn ) − f (x0 ) ≤ k ≤ k( v + 1) tn yn = (f (x0 + tn ) − f (x0 )) /tn dãy bị chặn, tồn dãy (ta kí hiệu cũ) cho yn → y ∈ ∂∗ f (x0 )v (2) Nếu f : X → Y ổn định taị x0 với số k lân cận x0 ∂∗ f (x0 )v ≤ k v Hơn nữa, Y = Rp , ∂∗ f (x0 )v tập hợp compact với v ∈ X Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ (3) Nếu Y = R df (x0 , v), df (x0 , v) hữu hạn {df (x0 , v), df (x0 , v)} ⊂ ∂∗ f (x0 )v ⊂ [df (x0 , v), df (x0 , v)] Chiều ngược lại bao hàm thức f liên tục lân cận x0 (4) Nếu Y = Rp ∂∗ f (x0 ) v ⊂ p i=1 ∂∗ fi (x0 ) v ⊂ p i=1 dfi (x0 , v) , dfi (x0 , v) ∂∗ f (x0 )v tập hợp lồi Y = R f liên tục lân cận x0 Điều không cho không gian định chuẩn tùy ý Y , chí f hàm Lipschitz địa phương x0 Ví dụ 1.1.2 (a) Giả sử A = {2−n : n ∈ N} ∪ {0} f : R → R xác định f (x) = dist(x, A) Khi f hàm Lipschitz toàn cục R số Nhưng f không khả vi Hadamard x0 = theo phương v = Thật vậy, ta có ≤ f (x) ≤ x , ∀x ∈ 0, , sn , ∀n ∈ N, sn điểm đoạn [2−n−1 , 2−n ], tức sn = · 2−n−2 1 Do df (x0 , v) = df (x0 , v) = Vì thế, ∂∗ f (x0 )v = [0, ] 3 (b) Giả sử ∞ −n −n B = {0} ·2 , ·2 n=1 f (2−n ) = f (sn ) = xác định g : R → R g(x) = 2dist(x, B) Khi đó, g Lipschitz tồn cục thỏa mãn ≤ g (x) ≤ f (x) ≤ x/3, ∀v ∈ [0, 1/2] Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Do v n → ψ (v), với k ∈ N, tồn nk ∈ N cho vnk ∈ ψ (v) + B (0, 1/k) Sử dụng (2.7) ta có vnk ∈ ψ (v) + ψ B 0, α−1 /k = ψ B v, α−1 /k Do đó, tồn vnk ∈ B v, α−1 /k cho ψ (vnk ) = vnk Với dãy (vnk )k∈N ta có lim vnk = v, (2.6) ta suy x→∞ g (ψ (x0 + tnk vnk )) − g (ψ (x0 )) → z tn k Điều kéo theo z ∈ ∂∗ (g ◦ ψ) (x0 ) v Ta cho ví dụ minh họa sau Ví dụ 2.2.1 (a) Giả sử ϕ : R → R cho ϕ (t) = − |t − 2| ≤ t ≤ 3, ϕ (t) = t ∈ / [1, 3] Trong R2 , ta xét chuẩn: x = max {|x1 | |x2 |}, x = (x1 , x2 ) Giả sử g : R2 → R cho   x + ϕ x2 /x31 x , < x31 ≤ x2 ≤ 3x31 , g (x) =  x , trường hợp khác Hàm g liên tục R2 , khả vi Hadamard x0 = (0, 0) với dg (x0 , v) = v , ∀v ∈ R2 , không Lipschitz địa phương x0 Để chứng minh tính khả vi Hadamard ta cần để ý g1 (x) := x ≤ g (x) ≤ g2 (x) := x + x , ∀x ∈ R2 , dg1 (x0 , v) = dg2 (x0 , v) = v , ∀v ∈ R2 Hàm g không Lipschitz địa phương x0 , ta xét dãy tn → 0+ pn := tn , t3n qn := tn , 2t3n , ta có pn → x0 , qn → x0 tn + t2n − tn |g (qn ) − g (pn )| = lim = +∞ lim n→∞ n→∞ q n − pn t3n 29 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ (b) Giả sử h := f ◦ g g hàm phần (a) f hàm Ví dụ 1.1.2(a) Khi đó, h liên tục R2 vững (xo , v) , ∀v ∈ R2 theo Định lý 2.2.1 Tuy nhiên, h không khả vi Hadamard x0 theo phương v = (1, 0), Lipschitz địa phương x0 Điều kiểm tra xét dãy (pn ) (qn ) phần (a) với tn = 2−n Sử dụng Định lý 2.2.1, ta có ∂∗ h (x0 ) v = ∂∗ f (g (x0 )) dg (x0 , v) = ∂∗ f (0) = 0, Điều chứng tỏ h không khả vi Hadamard x0 theo phương v theo Mệnh đề 1.1.3 (h ổn định x0 h hợp hàm ổn định) 2.3 Các điều kiện tối ưu Trong phần trình bày điều kiện cần đủ tối ưu cho toán tối ưu vectơ (P ) : {f (x) : x ∈ M } f : X → Y , X Y không gian định chuẩn, M ⊂ X, Y trang bị thứ tự nón lồi D ⊂ Y Điểm x0 ∈ M cực tiểu địa phương (cực tiểu địa phương yếu) toán (P ), ký hiệu x0 ∈ LM in (f, M ) (tương ứng x0 ∈ LWM in (f, M )), tồn lân cận U x0 cho (f (M ∩ U ) − f (x0 )) ∩ (−D) = {0} tương ứng (f (M ∩ U ) − f (x0 )) ∩ (−intD) = ∅ Nếu Y = R D = R+ hai trường hợp cho ta khái niệm cực tiểu địa phương thông thường Định lý 2.3.1 Xét toán (P ): {f (x) : x ∈ M } , 30 Soá hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ giả sử f : X → Y vững x0 ∈ M ⊂ X Nếu x0 ∈ LWM in (f, M ) ∂∗ f (x0 ) v ⊂ (−intD)c , ∀v ∈ A (M, x0 ) Chứng minh Giả sử tồn y ∈ ∂∗ f (x0 ) v ∩ −intD, v ∈ A (M, x0 ) Khi đó, từ định nghĩa ∂∗ f (x0 ) v, tồn (tn , ) → (0+ , v) cho lim (f (x0 + tn ) − f (x0 )) /tn = y n→∞ Vì v ∈ A (M, x0 ) , ∃v n → v thỏa mãn x0 + tn v n ∈ M Vì f vững (x0 , v), từ Bổ đề 2.2.1 suy lim (f (x0 + tn v n ) − f (x0 )) /tn = y n→∞ Vì y ∈ −intD, với n đủ lớn ta có (f (x0 + tn v n ) − f (x0 )) /tn ∈ −intD Điều tương đương với f (x0 + tn v n ) − f (x0 ) ∈ −intD Nhưng điều mâu thuẫn với x0 cực tiểu yếu địa phương Từ Định lí 2.3.1 ta nhận hệ sau Hệ 2.3.1 Giả sử f vững x0 x0 ∈ intD Nếu x0 ∈ LW M in(f, M ) ∂∗ f (x0 ) v ⊂ (−intD)c , ∀v ∈ X Hệ 2.3.2 Giả sử f khả vi Hadamard x0 Nếu x0 ∈ LW M in(f, M ) df (x0 , v) ∈ (−intD)c , ∀v ∈ A (M, x0 ) Hệ 2.3.3 Nếu f : Rn → Rp hàm Lipschitz địa phương x0 x0 ∈ LW M in (f, M ) ∂f (x0 ) v ∩ (−intD)c = ∅, ∀v ∈ A (M, x0 ) 31 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Hệ suy từ Mệnh đề 2.1.1 Định lý 2.3.1 Hệ 2.3.4 Nếu f : Rn → Rp hàm Lipschitz địa phương x0 , x0 ∈ intM x0 ∈ LW M in (f, M ), ∂f (x0 ) v ∩ (−intD)c = ∅, ∀v ∈ Rn Rõ ràng Hệ 2.3.1 tốt Hệ 2.3.4 chẳng hạn, f : R2 → R cho f (x1 , x2 ) = |x1 | − |x2 | , M = R2 x0 = (0, 0) Ta có ∂f (x0 ) = co {(1, 1) , (−1, 1) , (1, −1) , (−1, −1)} ∂∗ f (x0 ) v = {|v1 | − |v2 |} Rõ ràng x0 thỏa mãn điều kiện Hệ 2.3.4 không thỏa mãn điều kiện Hệ 2.3.1 Ví dụ sau Định lí 2.3.1 ta khơng thể thay A (M, x0 ) T (M, x0 ) Ví dụ 2.3.1 Giả sử f : R → R hàm Ví dụ 1.2.1(a) (sn ) dãy xác định Giả sử g : R → R xác định g (x) = f (x) − x/3, M = {sn ∈ R : n ∈ N} ∪ {0} Hiển nhiên x0 = cực tiểu yếu địa phương g M, g vững x0 (vì f hàm Lipschitz) A (M, x0 ) = {0} , T (M, x0 ) = R+ , ∂∗ g (x0 ) v = dg (x0 , v) , dg (x0 , v) = [−v/3, 0] Vì vậy, điều kiện ∂∗ g (x0 ) v ⊂ (−intD)c = [0, ∞) , ∀v ∈ T (M, x0 ) không thỏa mãn Nhận xét 2.3.1 Theo giả thiết Định lý 2.3.1, ta cần điều kiện quy 32 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ để có ∂∗ f (x0 ) v ⊂ (−intD)c , ∀v ∈ T (M, x0 ) Hiển nhiên, A (M, x0 ) = T (M, x0 ) (M khả dẫn xuất x0 ) Một điều kiện khác là, f khả dẫn xuất đồ thị x0 Thật vậy, ∂∗ f (x0 ) v = ∅ với v ∈ T (M, x0 ), df (x0 , v) tồn theo Mệnh đề 2.2.5 Do đó, ∂∗ f (x0 ) v = {df (x0 , v)} theo Mệnh đề 1.1.3, df (x0 , v) ∈ / −intD Trong khơng gian hữu hạn chiều, ta xét điều kiện cần đủ tối ưu Xét toán tối ưu vectơ (P ), khái niệm cực tiểu Pareto địa phương chặt cấp m đưa vào [[5], Định nghĩa 3.1] Định nghĩa 2.3.1 Giả sử m ≥ số nguyên Điểm x0 ∈ M gọi cực tiểu Pareto địa phương chặt cấp m toán (P ), ký hiệu x0 ∈ Strl (m, f, M ), tồn α > miền U x0 cho (f (x) + D) ∩ B (f (x0 ) , α x − x0 m ) = φ, ∀x ∈ M ∩ U \ {x0 } Chú ý cực tiểu Pareto địa phương chặt cấp m cấp j với j ≥ m, cực tiểu Pareto địa phương chặt cấp m cực tiểu địa phương, tức Strl (m, f, M ) ⊂ LM in (f, M ) Khái niệm mở rộng khái niệm cực tiểu địa phương chặt cấp m thông thường tối ưu vô hướng Định lý 2.3.2 Giả sử X Y hữu hạn chiều f : X → Y ổn định x0 ∈ M ⊂ X Nếu ∀v ∈ T (M, x0 ) \ {0} ∀y ∈ ∂∗ f (x0 ) v ta có y ∈ / −D (tức ∂∗ f (x0 ) v ⊂ (−D)c , x0 ∈ Strl (1, f, M )) Chứng minh Giả sử x0 ∈ / Strl (1, f, M ) Khi đó, theo Đinh nghĩa 2.3.1, tồn 33 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ dãy xn ∈ M ∩ B (x0 , 1/n) \ {x0 } dn ∈ D cho f (xn ) − f (x0 ) + dn = bn ∈ B (0, tn /n) , (2.8) tn = xn − x0 → 0+ Ta giả sử tồn dãy (xn ), mà ta kí hiệu (xn ), cho xn − x0 := → v ∈ T (M, x0 ) , với v = (2.9) tn Vì xn = x0 + tn từ (2.8) ta có f (x0 + tn ) − f (x0 ) −dn bn = + tn tn tn (2.10) Vì f ổn định x0 , nên dãy yn = (f (x0 + tn ) − f (x0 )) /tn bị chặn có dãy hội tụ ta kí hiệu dãy ban đầu, tức (f (x0 + tn ) − f (x0 )) /tn → y, với y ∈ Y Theo định nghĩa y ∈ ∂∗ f (x0 ) v, v ∈ T (M, x0 ) theo (2.9) từ giả thiết ta có y ∈ / −D Lấy giới hạn (2.10), −1 t−1 n bn → ta suy y = lim −tn dn ∈ −D D nón n→∞ đóng ta nhận mâu thuẫn Hệ 2.3.5 Giả sử f : Rn → Rp hàm Lipschitz địa phương x0 Nếu ∂f (x0 ) v ⊂ (−D)c , ∀v ∈ T (M, x0 ) \ {0} , x0 ∈ Strl (1, f, M ) Hệ 2.3.6 Giả sử f : Rn → Rp khả vi Hadamard x0 Nếu df (x0 , v) ∈ (−D)c , ∀v ∈ T (M, x0 ) \ {0} , x0 ∈ Strl (1, f, M ) Hệ 2.3.7 Giả sử f : Rn → Rp ổn định x0 x0 ∈ intM Nếu ∂∗ f (x0 ) v ⊂ (−D)c , ∀v ∈ Rn \ {0} , x0 ∈ Strl (1, f, M ) 34 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Hệ 2.3.8 Xét tốn {f (x) : x ∈ M } với X = Rn , Y = Rp D = Rp+ Nếu f = (f1 , f2 , , fp ) : Rn → Rp ổn định x0 ∈ M ⊂ Rn ∀v ∈ T (M, x0 ) \ {0} ∃i ∈ {1, 2, , p} cho dfi (x0 , v) > 0, x0 cực tiểu Pareto địa phương chặt cấp Định lý 2.3.3 Giả sử f : X → Y vững x0 Nếu x0 ∈ Strl (1, f, M ), ∂∗ f (x0 ) v ⊂ (−D)c , ∀v ∈ A (M, x0 ) \ {0} Chứng minh Giả sử ∃v ∈ A (M, x0 ) \ {0} y ∈ ∂∗ f (x0 ) v ∩ (−D) Theo định nghĩa ∂∗ f (x0 ) v tồn (tn , ) → (0+ , v) cho (f (x0 + tn ) − f (x0 )) /tn → y Khi v ∈ A (M, x0 ), tồn v n → v cho x n := x0 + tn v n ∈ M, ∀v ∈ N Bởi Bổ đề 2.2.1 ta có f (x0 + tn v n ) − f (x0 ) lim = y ∈ −D n→∞ tn (2.11) Theo giả thiết, ∃α > lân cận U x0 cho (f (x) + D)∩B (f (x0 ) , α x − x0 ) = ∅, ∀x ∈ M ∩U \ {x0 } (2.12) Do xn − x0 /tn → v = 0, ta có n0 ∈ N cho v tn / x0 − x0 ≤ 2, ∀n ≥ n0 (2.13) Từ (2.11), với β := α v tn /2, tồn n1 ∈ N, cho f (x0 + tn v n ) − f (x0 ) ∈ y + B (0, β) x0 + tn v n ∈ U ∀n ≥ n1 tn 35 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Do đó, theo (2.13) ta có βtn = α v tn /2 ≤ α x0 − x0 Vì vậy, f (x0 + tn v n ) − tn y ∈ f (x0 ) + B (0, βtn ) ⊂ B (f (x0 ) α x0 − x0 ) , ∀n ≥ max {n0 , n1 } Điều mâu thuẫn với (2.12), xn = x0 + tn v n ∈ M ∩ U \ {0} −tn y ∈ D Hệ 2.3.9 Giả sử f : Rn → Rp vững x0 , giả sử M khả dẫn xuất x0 , hoặcf khả dẫn xuất đồ thị x0 Khi đó, x0 ∈ Strl (1, f, M ) ⇔ ∂∗ f (x0 ) v ⊂ (−D)c , ∀v ∈ T (M, x0 ) \ {0} Chứng minh Giả sử f vững x0 Khi đó, chiều “⇐” suy từ Định lý 2.3.2, chiều “⇒” suy từ Định lý 2.3.3 M khả dẫn xuất, tức T (M, x0 ) = A (M, x0 ) Giả sử f khả dẫn xuất đồ thị x0 y ∈ ∂∗ f (x0 ) v ∩ (−D) với v ∈ T (M, x0 ) \ {0} Khi đó, Hệ 2.2.2 y = df (x0 , v) ∈ −D Nhưng x0 ∈ Strl (1, f, M ) kéo theo T (M, x0 ) ∩ {u ∈ Rn : df (x0 , u) ∈ −D} = {0} , theo [[7] Định lý 4.1] Do đó, v = ta nhận mâu thuẫn Chú ý ta cần f khả dẫn xuất đồ thị x0 theo phương v ∈ T (M, x0 ) \A (M, x0 ) Hệ mở rộng [Định lý 4.1 [7]] không gian hữu hạn chiều, giả sử f khả vi Hadamard 36 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ 2.4 Các quy tắc nhân tử Lagrange Trong phần này, ta giả sử f : Rn → Rp , thứ tự Rp trang bị nón lồi đóng nhọn có phần không rỗng tập chấp nhận M cho M = {x ∈ Rn : g (x) ∈ K, h (x) = 0} , g : Rn → Rm , h = (h1 , , hr ) : Rn → Rr , K tập lồi với phần không rỗng Rm Ta kí hiệu H = h−1 (0) = {x ∈ Rn : h (x) = 0} , G = g −1 (K) = {x ∈ Rn : g (x) ∈ K} , G0 = {x ∈ Rn : g (x) ∈ intK} Như vậy, M = G ∩ H Ta kí hiệu K + nón cực dương K, tức K + = {µ ∈ Rm : µ, z ≥ 0, ∀z ∈ K} N (K, z0 ) = −T (K, z0 )+ nón pháp tuyến K z0 Trong Định lý 2.4.1 đây, điều kiện cần tối ưu phát biểu dạng quy tắc nhân tử Lagrange, Định lý 2.4.2, điều kiện đủ tối ưu khác điều kiện cần chỗ thay bất đẳng thức bất đẳng thức chặt Bổ đề 2.4.1 Giả sử g vững x0 ∈ G, v ∈ Rm , giả sử ∂∗ f (x0 ) v ∩ IT (K, g (x0 )) = ∅ Khi đó, v ∈ ITs (G0 , x0 ) Chứng minh Lấy z ∈ ∂∗ g (x0 ) v ∩ IT (K, g (x0 )) Khi đó, tồn (tn , ) → (0+ , v) cho (g (x0 + tn ) − g (x0 )) /tn → v 37 Soá hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Giả sử v n dãy hội tụ đến v Vì g vững x0 , theo Bổ đề 2.2.1, (g (x0 + tn v n ) − g (x0 )) /tn → z Vì z ∈ IT (K, g (x0 )) = IT (intK, g (x0 )) , ∀ (sn , zn ) → 0+ , z , ta có g (x0 ) + sn zn ∈ intK Chọn zn = (g (x0 + tn v n ) − g (x0 )) /tn sn = tn , ta nhận g (x0 ) + tn g (x0 + tn v n ) − g (x0 ) = g (x0 + tn v n ) ∈ intK tn Do đó, x0 + tn v n ∈ G0 , v ∈ ITs (G0 , x0 ) Bổ đề 2.4.2 Giả sử g vững x0 ∈ M h liên tục lân cận x0 khả vi Frechet x0 với ∇h1 (x0 ) , , ∇hr (x0 ) độc lập tuyến tính Nếu v ∈ Ker∇h (x0 ) ∂∗ g (x0 ) v ∩ IT (K, g (x0 )) = ∅, v ∈ T (G ∩ H, x0 ) Chứng minh Theo [[4], Định lý 5.3.3], Ker∇h (x0 ) = A (H, x0 ) Theo Bổ đề 2.4.1 v ∈ ITs (G0 , x0 ) ITs (G0 , x0 ) ∩ A (H, x0 ) ⊂ T (G0 ∩ H, x0 ) , ta suy điều phải chứng minh Bổ đề 2.4.3 Giả sử f g vững x0 ∈ M h liên tục lân cân 38 Số hóa Trung tâm Học lieäu http://lrc.tnu.edu.vn/ x0 khả vi Frechet x0 với ∇h1 (x0 ) , , ∇hr (x0 ) độc lập tuyến tính Nếu x0 ∈ LWM in (f, M ) , ∀v ∈ Ker∇h (x0 ) ∀ (y, z) ∈ ∂∗ (f, g) (x0 ), ta có (y, z) ∈ / (−intD) × IT (K, g (x0 )) Chứng minh Giả sử ∃ (y, z) ∈ [(−intD) × IT (K, g (x0 ))] ∩ ∂∗ (f, g) (x0 ) v với v v ∈ Ker∇h (x0 ) Nếu ta định nghĩa f (x) = f (x) − f (x0 ), rõ ràng IT (−D, f (x0 )) = −intD, IT (−D) × K, f (x0 ) , g (x0 ) = (−intD) × IT (K, g (x0 )) Hơn nữa, ∂∗ f , g (x0 ) v = ∂∗ (f, g) (x0 ) v Theo Bổ đề 2.4.2, v ∈ T (F0 ∩ G0 ∩ H, x0 ), F0 = x ∈ Rn : f (x) ∈ −intD = {x ∈ Rn : f (x) − f (x0 ) ∈ −intD} Điều cho ta mâu thuẫn, x0 ∈ LWM in (f, M ) nghĩa F0 ∩ M ∩ U = ∅ với lân cận U x0 T (F0 ∩ M, x0 ) = T (F0 ∩ M ∩ U, x0 ) = ∅ T (F0 ∩ G0 ∩ H, x0 ) = ∅ T (F0 ∩ G0 ∩ H, x0 ) ⊂ T (F0 ∩ G ∩ H, x0 ) Định lý 2.4.1 Với giả thiết Bổ đề 2.4.3, x0 ∈ LWM in (f, M ) ∀v ∈ Ker∇h (x0 ) ∀ (y, z) ∈ ∂∗ (f, g) (x0 ) v, tồn (λ, µ) ∈ Rp × Rm , (λ, µ) = cho λ ∈ D+ , µ ∈ N (K, g (x0 )) , 39 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ (2.14) λ, y + µ, z ≥ (2.15) Định lý hệ trực tiếp Bổ đề 2.4.3 định lý tách tập lồi, tập hợp (−intD) × IT (K, g (x0 )) lồi intD IT (K, g (x0 )) = int cone (K − g (x0 )) tập hợp lồi Chú ý K nón lồi µ ∈ N (K, g (x0 )) ⇔ µ ∈ −K + µ, g (x0 ) = Định lý 2.4.2 Giả sử f g ổn định x0 ∈ M h vi phân Frechet x0 Nếu với v ∈ Ker∇h (x0 ) \ {0} ∀ (y, z) ∈ ∂∗ (f, g) (x0 ) v, tồn (λ, µ) ∈ Rp × Rm thỏa mãn (2.14) λ, y + µ, z > 0, (2.16) x0 ∈ Strl (1, f, M ) Chứng minh Như chứng minh Định lý 2.3.2, giả sử x0 ∈ / Strl (1, f, M ) Khi đó, tồn dãy xn ∈ M ∩ B (x0 , 1/n) \ {x0 } dn ∈ D thỏa mãn (2.8) (2.10) Do (f, g) ổn định x0 , ta giả sử (ta chọn dãy cần thiết) (f, g) (x0 + tn ) − (f, g) (x0 ) = (y, z) ∈ ∂∗ (f, g) (x0 ) v (2.17) n→∞ tn lim Vì v ∈ T (M, x0 ) ⊂ Ker∇h (x0 ), theo giả thiết tn ti (, à) Rp ì Rm tha (2.14) (2.16) Từ (2.17) suy (f (xn ) − f (x0 )) /tn → y Do (2.10) ta có y ∈ −D Từ (2.17) ta suy (g(xn ) − g(x0 )/tn ) → z Do đó, z ∈ cl cone (K − g (x0 )) = T (K, g (x0 )) Vì vậy, từ (2.14) ta suy λ, y + µ, z ≤ Điều mâu thuẫn với (2.16) 40 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Kết luận Luận văn trình bày lý thuyết đạo hàm tiếp liên cho hàm ổn định điều kiện tối ưu cho toán tối ưu đa mục tiêu với hàm ổn định hàm vững ngôn ngữ đạo hàm tiếp liên Các nội dung trình bày luận văn sau: - Hàm ổn dịnh số tính chất; - Đạo hàm tiếp liên hàm ổn định; - Quy tắc đạo hàm tiếp liên hàm hợp; - Đạo hàm tiếp liên tổng hai hàm; - Đạo hàm tiếp liên tích hai hàm; - Đạo hàm tiếp liên thương hai hàm; - Đạo hàm tiếp liên max hữu hạn hàm; - Hàm vững số tích chất; - Đạo hàm tiếp liên hàm vững; - Điều kiện tối ưu cho toán tối ưu tổng quát; - Quy tắc nhân tử Lagrange cho toán tối ưu đa mục tiêu với ràng buộc nón, ràng buộc đẳng thức khơng gian hữu hạn chiều Lý thuyết điều kiện tối ưu cho toán tối ưu vectơ với hàm ổn định ngôn ngữ đạo hàm tiếp liên vấn đề thời nhiều tác giả ngồi nước quan tâm nghiên cứu 41 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ Tài liệu tham khảo Tài liệu Tiếng Việt [1] Đỗ Văn Lưu (1999), Giải tích Lipschitz, NXB Khoa học Kỹ thuật [2] Đỗ Văn Lưu Phan Huy Khải (2000), Giải tích lồi, NXB Khoa học Kỹ thuật Tài liệu Tiếng Anh [3] F H Clarke (1983), Optimization and Nonsmooth Analysis, John Wiley and Sons, New York [4] M R Hestenes(1981), Optimization Theory The Finite Dimensional Case, Robert E Krieger Publishing Company New York [5] B Jimenez(2002), Strict efficiency in vector optimization, J Math Anal Appl 265(2) , pp.264-284 [6] B.Jimenez and V.Novo (2008),First order optimality condition in vector optimization invalving stable functions, Optimization 449 - 471 [7] B.Jimenez and V.Novo(2003), First and second order sufficient conditions for Strict minimality in nonsmooth vectơ optimization, J.Math Anal.Appl 284(2), 496 - 510 [8] D T Luc (1991),Contingent derivatives of set-valued maps and applications to vector optimization, Math Program 50 pp 99111 42 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ [9] P Michel and J P Penot (1992), A generalized derivative for calm and stable functions, Diff Integ Eq 5(2) , pp 433- 454 [10] R T Rockafellar and R J Wets.(1998) Variational Analysis, Berlin, Springer 43 Số hóa Trung tâm Học liệu http://lrc.tnu.edu.vn/ ... " Điều kiện tối ưu cho nghiệm hữu hiệu toán tối ưu đa mục tiêu với hàm ổn định " Luận văn trình bày lý thuyết đạo hàm tiếp liên cho hàm ổn định, hàm vững điều kiện tối ưu Jimenez - Novo [6] cho. .. HỌC TRINH DUY BÌNH ĐIỀU KIỆN TỐI ƯU CHO NGHIỆM HỮU HIỆU CỦA BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU VỚI CÁC HÀM ỔN ĐỊNH Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng... Novo [6] 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 hàm vững, điều kiện tối ưu cho toán tối ưu vectơ tổng quát với hàm ổn định hàm vững