Mục lục Lời mở đầu 1 Cơ sở giải tích lồi 1.1 Tập lồi 1.2 Hàm lồi 1.3 Hàm liên hợp 1.4 Dưới vi phân 13 1.5 Đặc trưng hàm lồi 18 1.6 Một số ứng dụng vào toán tối ưu 21 Hàm véctơ lồi ứng dụng 34 2.1 Các khái niệm 34 2.2 Tính liên tục, liên tục theo nón 41 2.3 Dưới vi phân hàm véctơ lồi 47 2.4 Hàm liên hợp hàm véctơ lồi 52 2.5 Các đặc trưng hàm véctơ lồi 56 2.6 Một số ứng dụng vào toán tối ưu véctơ 70 Kết luận 75 Tài liệu tham khảo i 76 Lời mở đầu Rất nhiều toán thực tế đưa dạng: Tìm x ∈ D cho f (x) ≤ f (x), ∀x ∈ D, đó, D tập tập f : D → R hàm số thực Ta kí hiệu toán f (x) = f (x) x∈D (1) gọi toán tối ưu Bài toán đóng vai trò trọng tâm lý thuyết tối ưu có toán liên quan toán bất đẳng thức biến phân, toán cân bằng, toán minimax, toán điểm yên ngựa, Trong trường hợp f hàm số khả vi toán (1) gọi tối ưu khả vi hay tối ưu trơn Trong trường hợp ngược lại, toán (1) gọi tối ưu không trơn Đối với tối ưu trơn ta có điều kiện cần đủ cấp cấp 2, có phương pháp giải phương pháp Newton nhiều phương pháp khác Trong chục năm qua nhiều nhà toán học giới quan tâm nghiên cứu, tìm phương pháp giải toán tối ưu không trơn Năm 1947, nhà toán học người Mỹ, Danzig, tìm phương pháp đơn hình để giải toán quy hoạch tuyến tính: f hàm tuyến tính, D đa diện lồi Năm 1960 đến 1970, hai nhà toán học Mỹ Jean Jacques Moreau R T Ralph Tyrrell Rockafellar, đưa khái niệm vi phân hàm lồi từ hình thành môn Giải tích lồi để giải quy hoạch nói Những năm 1980 nhà toán học Mỹ, Clarke, đưa khái niệm vi phân hàm Lipschitz địa phương xây dựng nên môn Giải tích Lipschitz Nhiều nhà toán học khác J P Penot, Urruty, Mordukhovich, Nguyễn Văn Hiền, Strodiot, đưa khái niệm vi phân để giải toán (1) trường hợp khác Đặc biệt, Đinh Thế Lục Jeykumar, năm 1990-2010, đưa khái niệm Jacobian xấp xỉ để giải toán trường hợp tổng quát: f hàm liên tục D tập đóng Tiếp theo người ta cần phát triển toán (1) trường hợp f từ tập D vào không gian véctơ khác Để phát triển toán tối ưu, người ta cần quan hệ thứ tự, tương đương với điều kiện có nón không gian Từ thứ tự người ta phát biểu toán tối ưu khác tối ưu lý tưởng, tối ưu Pareto, tối ưu thực sự, tối ưu yếu Từ hình thành nên môn học mới: Tối ưu véctơ, công cụ để giải toán tối ưu véctơ Hơn thế, người ta nghiên cứu toán trường hợp f ánh xạ đa trị, đề tài phong phú hấp dẫn có nhiều ứng dụng thực tế Chính vậy, chọn đề tài cho luận văn thạc sĩ là: "Dưới vi phân hàm véctơ lồi ứng dụng." Ngoài phần mở đầu, phần kết luận danh mục tài liệu tham khảo, luận văn gồm hai chương: Chương Giải tích lồi trình bày số khái niệm kết tài liệu [2] tính chất giải tích lồi tập lồi, hàm lồi, tính chất liên tục, tính Lipschitz, hàm liên hợp, tính khả vi phân hàm lồi ứng dụng toán tối ưu lồi vô hướng Chương Dưới vi phân hàm véctơ lồi ứng dụng nội dung luận văn, trình bày mở rộng cho tính chất, kết hàm lồi vô hướng cho hàm véctơ lồi theo nón khái niệm nón, điểm hữu hiệu, tính liên tục theo nón, tính lồi, vi phân, hàm liên hợp, đặc trưng số ứng dụng vi phân vào toán tối ưu véctơ lồi Luận văn hoàn thành Viện Toán học thuộc Viện Hàn Lâm Khoa Học Công Nghệ Việt Nam, hướng dẫn tận tình GS TSKH Nguyễn Xuân Tấn Tôi muốn gửi tới Thầy lời biết ơn sâu sắc Tôi xin gửi lời cảm ơn chân thành tới Thầy, Cô cán bộ, nhân viên Viện Toán Học, bạn lớp Cao học K21 bạn lớp Cao học quốc tế K8 tạo điều kiện thuận lợi cho trình học cao học thực luận văn Hà Nội, ngày 26/08/2015 Tác giả luận văn Nguyễn Thị Phương Chương Cơ sở giải tích lồi Chương dành cho kiến thức giải tích lồi cần dùng cho toán tối ưu không trơn Khi muốn xét tồn nghiệm hay tìm thuật toán để giải toán tối ưu, ta phải trang bị cho tập ràng buộc hàm số cấu trúc đại số tôpô để mô tả tính chất đặc thù loại toán, từ tìm phương pháp giải Ta bắt đầu việc giới thiệu cấu trúc tập hợp Để khỏi phải nhắc lại nhiều lần, ta giới hạn trình bày số kiến thức giải tích lồi như: Tập lồi, hàm lồi, vi phân, Các kết lý thuyết, thuật toán, để giải toán (1) cho trường hợp không gian tôpô tuyến tính lồi địa phương Hausdorff Nhưng người đọc thấy trực quan, luận văn ta trình bày vấn đề không gian hữu hạn chiều 1.1 Tập lồi Ta kí hiệu R = R ∪ {±∞} tập số thực mở rộng, , tích vô hướng Rn Định nghĩa 1.1.1 Đường thẳng nối hai điểm (hai véctơ) a, b Rn tập tất véctơ x ∈ Rn có dạng x = αa + βb, α, β ∈ R, α + β = Đoạn thẳng nối hai điểm a b Rn tập {x ∈ Rn |x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1} Tương tự ta có kí hiệu [a, b) , (a, b], (a, b) Định nghĩa 1.1.2 Tập C ⊆ Rn gọi tập lồi, C chứa đoạn thẳng qua hai điểm Tức là, C lồi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ) y ∈ C Dưới số ví dụ tập lồi thường gặp Định nghĩa 1.1.3 Cho f ∈ Rn , α số thực cố định H = {x ∈ Rn : f, x = α} gọi siêu phẳng, H + = {x ∈ Rn : f, x ≥ α} gọi nửa không gian trên, H − = {x ∈ Rn : f, x ≤ α} gọi nửa không gian Ta dễ dàng thấy H, H + , H − tập lồi xác định f α Tiếp theo, ta nhắc lại số khái niêm liên quan đến tập lồi Định nghĩa 1.1.4 Cho A ⊂ Rn i) Bao lồi A giao tất tập lồi chứa A, kí hiệu coA; ii) Bao lồi đóng tập A giao tất tập lồi đóng chứa A, kí hiệu coA Định nghĩa 1.1.5 Tập hợp C ⊂ Rn gọi nón có đỉnh gốc, tx ∈ C, với x ∈ C t ≥ Tập C ⊂ Rn gọi nón có đỉnh x0 , tập C − {x0 } nón có đỉnh gốc Định nghĩa 1.1.6 i) Nón C gọi nón nhọn, l(C) := C ∩ (−C) = {0} ii) Nón cực nón C định nghĩa tập C := {ξ ∈ L(Rn , R) : ξ(x) ≥ 0, ∀x ∈ C} Khái niệm nón cho ta quan hệ thứ tự không gian Rn Định nghĩa 1.1.7 Với nón lồi C cho trước, ta định nghĩa quan hệ thứ tự phần C Rn sau: x, y ∈ Rn , x C y, x − y ∈ C Nếu nhầm lẫn, ta viết đơn giản x Cho x, y ∈ Rn , ta kí hiệu x y y, x − y ∈ C \ lC x y, x − y ∈ intC Trong lý thuyết tối ưu ta thấy có kết liên quan tới việc tách tập lồi, chúng làm tảng cho điều kiện cần đủ để tồn nghiệm toán tối ưu có ràng buộc Sau đây, ta đưa số khái niệm liên quan tới tách tập lồi Định nghĩa 1.1.8 Cho tập A, B ⊂ Rn Ta nói phiếm hàm tuyến tính liên tục f = tách A B, tồn số α cho f, y ≤ α ≤ f, x , ∀x ∈ A, ∀y ∈ B (1.1) Nếu bất đẳng thức (1.1) thực sự, tức là, f, y < α < f, x , ∀x ∈ A, ∀y ∈ B, ta nói f tách chặt A B Siêu phẳng H = {x ∈ Rn : f, x = α} gọi siêu phẳng tách A B Các tập A, B gọi tách Phần chứng minh kết sau tìm thấy [2] Định lý 1.1.9 (Định lý tách thứ nhất) Cho A B tập lồi Rn , A∩B = ∅ Khi đó, tồn phiếm hàm tuyến tính liên tục f = 0, f ∈ Rn tách A B Hệ 1.1.10 Cho A, B tập lồi Rn Khi đó, A, B tách (intA) ∩ B = ∅ Định lý 1.1.11 Giả sử A tập lồi đóng không gian Rn x0 ∈ / A Khi đó, tồn f ∈ Rn , f = tách chặt A x0 Hệ sau suy trực tiếp Định lý 1.1.11 Hệ 1.1.12 Cho A ⊂ Rn Ta có i) coA trùng với giao tất nửa không gian chứa A; ii) Nếu A tập lồi A đóng A đóng Định lý 1.1.13 (Định lý tách thứ hai) Cho A, B hai tập lồi đóng khác rỗng cho A ∩ B = ∅ Giả sử có hai tập compact Khi đó, hai tập tách mạnh siêu phẳng 1.2 Hàm lồi Trong mục ta đưa số tính chất hàm số liên quan tới cấu trúc đại số cấu trúc tôpô Định nghĩa 1.2.1 Cho C ⊆ Rn tập lồi f : C → R ∪ {±∞} Ta kí hiệu domf := {x ∈ C|f (x) < ∞} Tập domf gọi miền hữu hiệu f Tập epif := {(x, µ) ∈ C × R|f (x) ≤ µ} gọi đồ thị hàm f Tập lev (f, α) = {x ∈ C : f (x) ≤ α} gọi tập mức f α ∈ R Định nghĩa 1.2.2 1) Hàm f gọi hàm lồi, epif tập lồi không gian tích C × R; 2) Hàm f gọi hàm thường domf = ∅ f (x) > −∞, với x ∈ C Trong luận văn, để khỏi phải nhắc lại nhiều lần, ta giả thiết hàm lồi thường Mệnh đề 1.2.3 ([2]) Hàm f : C → R xác định tập lồi C ⊆ Rn gọi Hàm lồi ∀x1 , x2 ∈ C, ∀λ ∈ [0, 1] ta có f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ); Hàm lồi chặt, ∀x1 , x2 ∈ Rn , ∀λ ∈ (0, 1) ta có f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ)f (x2 ); Hàm lồi mạnh, với hệ số β > ∀x1 , x2 ∈ C, ∀λ ∈ (0, 1), ta có f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) − λ (1 − λ) β x1 − x2 ; Hàm lõm (lõm chặt), −f hàm lồi (lồi chặt); Hàm f tựa lồi lev (f + g, α) tập lồi ∀g, α ∈ R, (f + g) (x) = f (x) + g (x) Chú ý 1.2.4 1) Nếu f hàm lồi domf tập lồi; 2) Nếu f hàm lồi {x : f (x) < α} , {x : f (x) ≤ α} tập lồi ∀α ∈ [−∞, +∞] 1.2.1 Tính liên tục Tính chất lồi hàm kéo theo nhiều tính chất tôpô quan trọng, định nghĩa hàm lồi ta không đòi hỏi cách trực tiếp đến tính chất tôpô Trước hết, ta nhắc lại hàm f : D ⊂ Rn → R gọi nửa liên tục điểm x ∈ D, với dãy {xk } ⊂ D, xk → x ta có liminf f (xk ) ≥ f (x) k→∞ Hàm f gọi nửa liên tục điểm x ∈ D −f nửa liên tục x Hay với dãy {xk } ⊂ D, xk → x ta có limsup(xk ) ≤ f (x) Hàm f gọi k→∞ nửa liên tục x vừa nửa liên tục nửa liên tục x Hàm f gọi nửa liên tục dưới, nửa liên tục điểm thuộc D Tương tự, ta nói với hàm nửa liên tục hàm liên tục Các kết sau tìm thấy chứng minh tài liệu [2] Định nghĩa 1.2.5 i) Bao đóng hàm f hàm, kí hiệu clf, có đồ thị epi cl f = epif ; ii) Bao lồi đóng hàm f hàm, kí hiệu cof, có đồ thị epi(cof ) = co(epif ); iii) Hàm f gọi đóng epif tập đóng Rn × R Chú ý 1.2.6 Các khẳng định sau i) Hàm f lồi clf lồi; ii) Hàm f đóng f = clf Mệnh đề 1.2.7 Hàm f đóng lev (f, α) = {x : f (x) ≤ α} tập đóng với α ∈ R Mệnh đề 1.2.8 Hàm f đóng f nửa liên tục Định lý sau cho ta điều kiện để hàm lồi liên tục Định lý 1.2.9 ([2]) Cho f hàm lồi thường Rn khẳng định sau tương đương i) f bị chặn lân cận x0 ∈ Rn ; ii) f liên tục x0 ; iii) int(epif ) = ∅; vi) int(domf ) = ∅ f liên tục int(domf ) 1.2.2 Tính Lipschitz Tính Lipschitz hàm đóng vai trò quan trọng việc nghiên cứu toán tối ưu Trước tiên, ta đưa số khái niệm sau Định nghĩa 1.2.10 Hàm f : D ⊂ Rn → R gọi Lipschitz D tồn số L ≥ cho |f (x) − f (y)| ≤ L x − y , ∀x, y ∈ D L gọi số Lipschitz Hàm f gọi Lipschitz địa phương điểm x¯ ∈ D tồn lân cận U x¯ để f Lipschitz U ∩ D Hàm f gọi Lipschitz địa phương tập D ⊂ Rn Lipschitz địa phương điểm thuộc D Định lý 1.2.11 ([2]) Giả sử f hàm lồi thường Rn bị chặn lân cận điểm thuộc tập mở D ⊂ domf Khi đó, f Lipschitz địa phương tập D Hệ 1.2.12 ([2]) Giả sử f : D → R hàm lồi liên tục x0 thuộc tập lồi mở D Khi đó, f Lipschitz địa phương D 1.3 Hàm liên hợp Hàm liên hợp có vai trò quan trọng lý thuyết tối ưu, đặc biệt lý thuyết đối ngẫu Trong phần này, trước hết giới thiệu định nghĩa đưa ví dụ minh họa cho hàm liên hợp Tiếp đến khảo sát số tính chất quy tắc cho việc tính toán với hàm liên hợp 1.3.1 Phép biến đổi Young - Fenchel Ta cho tương ứng hàm cho trước với hàm lồi sau: Định nghĩa 1.3.1 Phép biến đổi Young - Fenchel hàm f : D ⊂ Rn → R hay hàm liên hợp hàm f hàm f ∗ : D∗ ⊂ Rn → R xác định: f ∗ (x∗ ) = sup { x∗ , x − f (x)} (1.2) x∈D Mệnh đề 1.3.2 f ∗ hàm lồi đóng Chứng minh Với x cố định, hàm g (x∗ ) := x∗ , x − f (x) hàm tuyến tính Rn Do đó, g (x∗ ) lồi đóng Trên đồ thị f ∗ (x∗ ) giao đồ thị hàm g (x∗ ), tức là, giao tập lồi đóng Vì vậy, epif ∗ lồi đóng Nhận xét Từ Định nghĩa 1.3.1 ta có f (x) + f ∗ (x∗ ) ≥ x∗ , x , ∀x, x∗ ∈ Rn Bất đẳng thức (1.3) gọi bất đẳng thức Young - Fenchel Ví dụ 1.3.3 Cho hàm f (x) = x0 ∗ , x + α, ∀x, x∗ ∈ Rn ∗ ∗ ∗ ∗ ⇒ f (x ) = sup x − x0 , x − α x =   −α, x∗ = x0 ∗ ,  ∞, x∗ = x0 ∗ (1.3) v) Cho {(Ai )}i họ tập lồi Rk cho ∩ Ai = ∅ Khi đó, i∈I ∩ (Ai )∞ ⊂ i∈I ∩ Ai i∈I ∞ Hơn nữa, Ai đóng với i ∈ I bao hàm thức ngược lại Cho f hàm véctơ lồi từ tập lồi khác rỗng D ⊆ Rn vào Rm Với x ∈ Rm , tập Sx := {u ∈ Rm |(x, u) ∈ (epif )∞ } Định nghĩa sau đưa từ khái niệm ánh xạ lùi xa hàm lồi vô hướng Định nghĩa 2.5.14 Ánh xạ lùi xa f , xác định   M inS , S = ∅, x x f∞ (x) :=  ∅, Sx = ∅ Ví dụ 2.5.15 Cho R2 thứ tự nón Orthant dương R2+ cho f : (0, +∞) → R2 , x −→ f (x) = (x, x + 12 ) Khi đó, f lồi R2 hàm thành phần lồi vô hướng (trên (0, +∞)) Từ tính toán ta có (epif )∞ = {(x, u1 , u2 ) ∈ R3 |x ≥ 0, u1 ≥ x, u2 ≥ x} Từ ta có Sx = {u = (u1 , u2 ) ∈ R2 |(x, u) ∈ (epif )∞ }   {(u , u )|u ≥ x, u ≥ x}, x ≥ 0, 2 =  ∅, x < Do đó, theo định nghĩa ánh xạ lùi xa     M inSx , x ≥ 0, {(x, x)}, x ≥ 0, f∞ (x) = =   ∅, ∅, x < x < 63 Mệnh đề 2.5.16 Giả sử nón C đóng, lồi nhọn Cho f hàm véctơ từ tập lồi khác rỗng D ⊆ Rn vào Rm Khi đó, dom f∞ = {x ∈ Rn | Sx = ∅} f∞ (x) = Sup {f (y + x) − f (y)| y ∈ D} , ∀x ∈ dom f∞ Chứng minh Lấy x ∈ Rn , u ∈ Rm tuỳ ý Theo định nghĩa Sx từ Bổ đề 2.5.13, ta có u ∈ Sx ⇔ (x, u) ∈ (epi f )∞ ⇔ (y, v) + (x, u) ∈ epi f , ∀ (y, v) ∈ epi f ⇔ f (y + x) ≺ v + u , ∀ (y, v) ∈ epi f ⇔ f (y + x) − f (y) ≺ u , ∀y ∈ D ⇔ u ∈ U b {f (y + x) − f (y)| y ∈ D} Do đó, Sx = U b {f (y + x) − f (y)| y ∈ D} (2.21) Cho nên, Sx = ∅ tập {f (y + x) − f (y)| y ∈ D} bị chặn Từ Định lý 2.1.22, điều tương đương với Sup {f (y + x) − f (y)| y ∈ D} = ∅ Khi đó, từ định nghĩa cận (2.21), Sx = ∅ ta có f∞ (x) = M in Sx = M in(U b {f (y + x) − f (y)| y ∈ D}) = Sup {f (y + x) − f (y)| y ∈ D} = ∅ Mệnh đề chứng minh Ta ý theo công thức Mệnh đề 2.5.16, ta có f∞ (0) = {0} Từ Định nghĩa 2.5.14 ta thấy ánh xạ lùi xa hàm véctơ lồi có cấu trúc 64 tập giá trị Để nghiên cứu nhiều cần thêm số khái niệm ánh xạ tập giá trị Cho F ánh xạ tập giá trị từ Rn vào Rm Ta định nghĩa đồ thị F nón C tập epi F := {(x, u) ∈ Rn × Rm | u ∈ F (x) + C} F gọi lồi (đóng) epiF lồi (đóng) F gọi dương F (λx) = λF (x) , ∀x ∈ dom F, λ ≥ Trong phần lại phần này, nón thứ tự C giả thiết lồi, đóng nhọn Mệnh đề 2.5.17 Cho f hàm véctơ lồi từ tập D ⊆ Rn vào D ⊆ Rm Khi đó, epi(f∞ ) = (epif )∞ Chứng minh Lấy (x, u) ∈ Rn × Rm tuỳ ý Từ Mệnh đề 2.5.13, (2.21) Định lý 2.1.22, ta có (x, u) ∈ epi(f∞ ) ⇔ u ∈ f∞ (x) + C ⇔ u ∈ Sup{f (y + x) − f (y)|y ∈ D} + C ⇔ u ∈ U b{f (y + x) − f (y)|y ∈ D} ⇔ u ∈ Sx ⇔ (x, u) ∈ (epif )∞ Mệnh đề chứng minh Chú ý từ Mệnh đề 2.5.17, domf∞ nón lồi domf∞ ⊂ D∞ Bao hàm thức ngược lại không trường hợp tổng quát Cho f : R → R xác định f (x) := x2 , ∀x ∈ R Khi đó, dom∞ = {0} khi, D∞ = R Từ mệnh đề ta thấy Định nghĩa 2.5.14 mở rộng khái niệm ánh xạ lùi xa với hàm lồi vô hướng trường hợp véctơ Bổ đề 2.5.18 Cho f hàm véctơ lồi từ tập lồi khác rỗng D ⊆ Rn vào Rm Giả sử x0 ∈ D, x ∈ D∞ tuỳ ý Khi đó, tập tính 65 f (x0 +λx)−f (x0 ) λ | λ > 0} thứ tự tuyến Chứng minh Cho λ ≥ λ > tuỳ ý Ta có x0 + λ x = (1 − λ λ )x0 + (x0 + λx) λ λ Khi đó, tính lồi f f (x0 + λ x) ≺ (1 − λ λ )f (x0 ) + f (x0 + λx) λ λ suy f (x0 + λ x) − f (x0 ) f (x0 + λx) − f (x0 ) ≺ λ λ Do đó, tập f (x0 +λx)−f (x0 ) λ | λ > 0} thứ tự tuyến tính Bổ đề chứng minh Nói chung, ánh xạ lùi xa hàm véctơ có cấu trúc tập giá trị Tuy nhiên, điều kiện biết ta bỏ ánh xạ đơn trị Chẳng hạn điều kiện tính đóng mệnh đề sau Mệnh đề 2.5.19 Cho f hàm véctơ lồi từ tập lồi khác rỗng D ⊆ Rn vào Rm Khi đó, ánh xạ lùi xa f∞ ánh xạ tập giá trị lồi dương Hơn nữa, f đóng, f∞ hàm đơn trị đóng với x0 ∈ D, f∞ cho công thức sau f∞ (x) = ISup f (x0 + λx) − f (x0 ) |λ > , ∀x ∈ domf∞ λ Chứng minh Tính lồi f suy từ Mệnh đề 2.5.17 Từ thích theo sau Mệnh đề 2.5.16 theo sau đẳng thức Sλx = λSx , ∀x ∈ Rn , λ > 0, M in(λA) = λM inA, ∀A ⊂ Rm , λ > 0, f∞ dương Bây giờ, giả sử f đóng Khi đó, theo Bổ đề 2.5.13 Mệnh đề 2.5.17 trên, epif∞ đóng, nên f∞ đóng Cuối cùng, cho x0 ∈ D, x ∈ Rn 66 u ∈ Rm tuỳ ý Từ tính lồi, đóng epif ta có u ∈ Sx ⇔ (x, u) ∈ (epif )∞ ⇔ (x0 , f (x0 )) + λ(x, u) ∈ epif, ∀λ > f (x0 + λx) − f (x0 ) ≺ u, ∀λ > λ f (x0 + λx) − f (x0 ) |λ > ⇔ u ∈ Ub λ ⇔ Do đó, Sx = U b f (x0 + λx) − f (x0 ) |λ > λ (2.22) Nếu x ∈ domf∞ , từ Mệnh đề 2.5.16, Sx = ∅ Từ (2.22), tập tập f (x0 +λx)−f (x0 ) λ f (x0 +λx)−f (x0 ) λ tồn ISup | λ > 0} bị chặn Mặt khác, theo Bổ đề 2.5.18, | λ > 0} thứ tự tuyến tính Khi đó, theo Mệnh đề 2.1.15, f (x0 +λx)−f (x0 ) λ | λ > Từ định nghĩa cận ánh xạ lùi xa với (2.22) ý sau Định nghĩa 2.1.11, ta có f∞ (x) = M inSx f (x0 + λx) − f (x0 ) |λ > λ f (x0 + λx) − f (x0 ) = Sup |λ > λ f (x0 + λx) − f (x0 ) = ISup |λ > λ = M in U b Vì C nón nhọn, ISup f (x0 +λx)−f (x0 ) |λ λ > tập phần tử Nên f∞ ánh xạ đơn trị Mệnh đề chứng minh Ví dụ 2.5.20 Cho R2 thứ tự nón Orthant dương R2+ cho f : (0, +∞) → R2 xác định Ví dụ 2.5.15, nghĩa f (x) = (x, x + x1 ) 67 Với tập mức khác rỗng leva f ta có leva f = {x ∈ (0, +∞)|f (x)≺ a} = x ∈ (0, +∞)|x ≤ a1 , x + ≤ a2 x = (0, a1 ] ∩ [α1 , α2 ], (trong đó, αi > 0, i = 1, 2, nghiệm phương trình x + x1 = a2 ) Do đó, leva f đóng Từ Bổ đề 2.2.2, f đóng Áp dụng Mệnh đề 2.5.19, với x ∈ domf∞ = R+ , ta có f∞ (x) = ISup = ISup f (1 + λx) − f (1) |λ > λ 1 x− + |λ > λ λ(1 + λx) Từ định nghĩa ISup, ta thử lại ISup (x, x − 1 + )|λ>0 λ λ(1 + λx) = {(x, x)} Do đó,   {(x, x)}, x ≥ 0, f∞ (x) =  ∅, x < Nó trùng với kết Ví dụ 2.5.15 Một hàm φ : A ⊂ R → Rm gọi giảm (đối với nón C) ∀r, s ∈ A, r > s ⇒ φ(r)≺ φ(s) Mệnh đề 2.5.21 Cho f hàm véctơ lồi từ tập lồi khác rỗng D ⊆ Rn vào Rm cho x0 ∈ D∞ Khi đó, f (y + λx0 ) hàm giảm λ(λ ≥ 0) với y ∈ D f∞ (x0 ) ∩ (−C) = ∅ Chứng minh ⇒) Vì f (y + x0 ) − f (y)≺ với y ∈ D, ta có ∈ U b{f (y + x0 ) − f (y) | y ∈ D} 68 Khi đó, theo Định lý 2.1.22, ta có Sup{f (y + x0 ) − f (y)|y ∈ D} ∩ (−C) = ∅ Theo Mệnh đề 2.5.16, suy f∞ (x0 ) ∩ (−C) = ∅ ⇐) Lấy y ∈ D tuỳ ý λ, λ ∈ R cho λ > λ ≥ Từ f∞ dương ta có f∞ ((λ − λ )x0 ) ∩ (−C) = ∅ (2.23) Theo Mệnh đề 2.5.16, f∞ ((λ − λ )x0 ) = Sup{f (z + (λ − λ )x0 ) − f (z)|z ∈ D} Điều với (2.23) định nghĩa cận suy f (z + (λ − λ )x0 ) − f (z)≺ 0, ∀z ∈ D Chú ý f (y + λx0 ) − f (y + λ x0 ) = f (y + λ x0 + (λ − λ )x0 ) − f (y + λ x0 ) Nên ta có f (y + λx0 ) − f (y + λ x0 )≺ Do đó, f (y + λx0 ) hàm giảm λ ∈ R+ Mệnh đề chứng minh Hệ 2.5.22 Cho f hàm véctơ lồi đóng từ tập lồi khác rỗng D ⊆ Rn vào Rm cho x0 ∈ D∞ Nếu có điểm y ∈ D có tính chất f (y + λx0 ) hàm giảm λ(λ ≥ 0), tính chất cho y ∈ D Chứng minh Vì f đóng lồi tập f (y+λx0 )−f (y) |λ λ >0 bị chặn 0, ta có Sx0 = ∅ theo (2.22), x0 ∈ domf ∞ Từ Mệnh đề 2.5.19 từ định nghĩa ISup, ta có f∞ (x0 ) = ISup f (¯ y + λx0 ) − f (¯ y) |λ > ≺ λ Áp dụng Mệnh đề 2.5.21, ta hoàn thành chứng minh 69 Tập tất véctơ x ∈ Rn cho f∞ (x) ∩ (−C) = ∅ gọi nón lùi xa f kí hiệu Rec(f ) Ta dễ thấy nón lồi Hướng véctơ Rec(f ) gọi hướng lùi xa f Mệnh đề 2.5.23 Cho f hàm véctơ lồi từ tập lồi khác rỗng D ⊆ Rn vào Rm Khi đó, tập tất tập mức khác rỗng f có nón lùi xa, nón lùi xa f , nghĩa là, với a ∈ Rm cho leva f = ∅ ta có (leva f )∞ = Rec(f ) Chứng minh Cho a ∈ Rm cho leva f = ∅ cho y ∈ leva f Khi đó, (y, a) ∈ epif Vì f đóng, từ Bổ đề 2.2.2, leva f đóng Nên với véctơ x ∈ Rn , ta có x ∈ (leva f )∞ ⇔ y + λx ∈ leva , ∀λ > ⇔ f (y + λx)≺ a, ∀λ > ⇔ (y, a) + λ (x, 0) ∈ epif, ∀λ > ⇔ (x, 0) ∈ (epif )∞ ⇔ (x, 0) ∈ epi(f∞ ), (Theo Mệnh đề 2.5.17 ) ⇔ ∈ f∞ (x) + C ⇔ f∞ (x) ∩ (−C) = ∅ ⇔ x ∈ Rec(f ) Ta có điều phải chứng minh 2.6 Một số ứng dụng vào toán tối ưu véctơ Phần ta trình bày số khảo sát toán cực trị hàm véctơ lồi Trước tiên, nghiên cứu toán không ràng buộc Thông qua khái niệm vi phân ánh xạ lùi xa đưa điều kiện cần đủ để tồn điểm cực tiểu để điểm điểm cực tiểu Đối với toán có ràng buộc, chúng đưa toán không ràng buộc cách thích hợp để thu điều kiện tối ưu Giả sử f hàm véctơ lồi từ tập lồi khác rỗng D ⊆ Rn vào Rm , Rm thứ tự nón lồi C Bài toán tối ưu véctơ f D phát 70 biểu    M inf (x), (VP)   S.t.x ∈ D Điều có nghĩa ta cần tìm điểm x∗ ∈ D, gọi nghiệm tối ưu (VP), cho f (x∗ ) ∈ M in(f (D)|C) Trong phần lại ta giả sử nón thứ tự C ⊆ Rm lồi, đóng nhọn với intC = ∅ Bổ đề 2.6.1 Cho c ∈ intC x ∈ Rm tuỳ ý Khi đó, tồn k ∈ N cho −kc ≺ x Chứng minh Vì ∈ −c+int C, tồn r > cho hình cầu mở B(0, r) ⊂ −c+intC Nên ta tìm số k ∈ N cho x k ∈ B(0, r) Từ suy x ∈ −kc + k intC ⊂ −kx + C Ta có điều cần chứng minh Định lý 2.6.2 Giả sử f lồi đóng Nếu f có phương lùi xa khác không, tức Rec (f ) = {0} , toán tối ưu hoá véctơ (VP) có phương án tối ưu Chứng minh Lấy y ∈ D tuỳ ý Tập B := (y − C) ∩ f (D) Rõ ràng, M inB ⊂ M inf (D) Để hoàn thành chứng minh định lý, ta cần M inB = ∅ Khi đó, giả sử S tập khác rỗng thứ tự B Ta S bị chặn Thật vậy, giả sử ngược lại S không bị chặn Lấy c ∈ intC Từ giả thiết, ta xây dựng dãy {yk }k ⊂ S cho −kc yk , (2.24) yk+1 yk , (2.25) với k Từ Rec(f ) = {0}, từ Mệnh đề 2.5.23, Bổ đề 2.2.1 Bổ đề 2.5.13, levyk f tập compact khác rỗng với k Do đó, từ (2.25), ta có levyk+1 ⊂ levyk f, ∀k 71 Do đó, ∞ ∩ levyk f = ∅ k=1 ∞ Cho x ∈ ∩ levyk f Khi đó, f (x) ≺ yk , với k Nên từ (2.24), k=1 −kc f (x), (2.26) Vì c ∈ intC, từ Bổ đề 2.5.13 tồn k0 cho −k0 c ≺ f (x), điều mâu thuẫn với (2.26) Do đó, S bị chặn Từ Mệnh đề 2.1.15 ý sau nó, IInf S tồn có dãy giảm {f (xk )}k ⊂ S hội tụ đến IInf S Vì levy f compact {xk }k ⊂ levy f Không tính tổng quát, ta giả sử {xk }k hội tụ đến số x0 ∈ levy f Từ tính đóng f , ta có (x0 , IInf S) ∈ epi f Do đó, S bị chặn f (x0 ) ∈ B Áp dụng Bổ đề Zorn ta có M inB = ∅ Định lý chứng minh Ví dụ 2.6.3 Cho R2 thứ tự nón Orthant dương R2+ Xét toán véctơ    M inf (x),   s.t.x ∈ (0, +∞), đó, f : (0, +∞) → R2 xác định Ví dụ 2.5.15 Vì f∞ (x) =   {(x, x)}, x ≥ 0,  ∅, x < nên ta có Rec (f ) = {0} Khi đó, từ Định lý 2.6.2 toán có phương án tối ưu Ta thấy x = nghiệm tối ưu toán Bây giờ, ta xét toán tối ưu hoá véctơ sau với tập ràng buộc tổng quát    M inf (x),    s.t.x ∈ D,      x ∈ E, (SVP) đó, E tập Rn , S tập khả thi (SVP), tức S = {x ∈ D | x ∈ E} Ta cần lưu ý f E đóng fD∩E đóng, đó, fD∩E hạn chế f D ∩ E 72 Hệ 2.6.4 Giả sử f E lồi, đóng tập khả thi S khác rỗng Nếu (f ) ∩ E∞ = {0} toán tối ưu hoá véctơ (SVP) có phương án tối ưu Chứng minh Ta cần Rec(f D∩E ) = Rec(f ) ∩ E∞ Khi đó, áp dụng Định lý 2.6.2 ta có điều phải chứng minh Lấy tuỳ ý x ∈ Rec(fD∩E ), y ∈ D ∩ E Khi đó, x ∈ (D ∩ E)∞ từ Mệnh đề 2.5.21, f (y + λx) hàm giảm λ(λ ≥ 0) Từ Hệ 2.5.22, x ∈ Rec(f ) Mặt khác từ tính đóng E, áp dụng Bổ đề 2.5.13, ta có x ∈ E∞ Ngược lại, giả sử x ∈ Rec(f ) ∩ E∞ y ∈ D ∩ E tuỳ ý Khi đó, x ∈ (D ∩ E)∞ (theo Bổ đề 2.6.1) f (y + λx) hàm giảm λ(λ ≥ 0) Từ Mệnh đề 2.5.21, x ∈ Rec(fD∩E ) Ta có điều cần chứng minh Cuối cùng, ta xét toán tối ưu véctơ với tất bất đẳng thức ràng buộc sau    M inf (x),    s.t.x ∈ D,      x ∈ Di , fi (x)≺ C 0, i ∈ I, i (IVP) đó, f : d ⊂ Rn → Rm , fi : Di ⊂ Rn → Rmi , i ∈ I, hàm véctơ với I tập số tuỳ ý với i ∈ I, Rmi thứ tự nón Ci đóng, nhọn, lồi với intCi = ∅ Tập Ei := {x ∈ Di | fi (x)≺Ci 0}, ∀i ∈ I, E := ∩ Ei i∈I Kí hiệu T tập khả thi (IVP), tức T = {x ∈ D | x ∈ Di , fi (x)≺C i 0, ∀i ∈ I} Hệ 2.6.5 Nếu tập khả thi T khác rỗng hàm f, fi , (i ∈ I), lồi đóng, f, fi , (i ∈ I) phương lùi xa chung khác không, tức Rec(f ) ∩ ( ∩ Rec(fi )) = {0} i∈I Thì toán (IVP) có phương án tối ưu 73 Chứng minh Từ Bổ đề 2.2.2, Ei đóng với i ∈ I Khi từ Bổ đề 2.5.13, ta có E∞ = ∩ (Ei )∞ i∈I Áp dụng Mệnh đề 2.5.23, ta E∞ = ∩ Rec(fi ) Khi đó, sử dụng Hệ 2.6.4 ta i∈i có điều cần chứng minh Ví dụ 2.6.6 Cho X = R2 thứ tự nón Orthant dương C = R2+ lấy X − = R2 thứ tự nón C1 = {α(1, 1) + β(−1, 1)|α, β ≥ 0} Xét toán véctơ bất đẳng thức với ràng buộc sau    M in(x),       s.t., x ∈ R2 ,   f1 (x)≺ C1 0,       f (x)≺ 0, C đó, f, f2 : R2 → X, f1 : R2 → X1 , xác định f (x, y) = (x + y, ex − y), f1 (x, y) = (−x, −2y), f2 (x, y) = (y − x, e−x − − y) Theo tính toán ta Rec(f ) = {α(−1, 0) + β(−1, 1) | α, β ≥ 0}, Rec(f1 ) = {α(−1, 21 ) + β(1, 12 ) | α, β ≥ 0}, Rec(f2 ) = {α(1, 0) + β(1, 1) | α, β ≥ 0} Do đó, Rec(f ) ∩ Rec(f1 ) ∩ Rec(f2 ) = {0} Từ Hệ 2.6.5, ta thấy toán có phương án tối ưu 74 Kết luận Bài toán tối ưu có vai trò quan trọng thực tiễn, đặc biệt ứng dụng vào lĩnh vực liên quan tới ngân hàng, giao thông, công nghệ thông tin, Đạo hàm, vi phân hàm lồi, cho phép ta xây dựng thuật toán để tìm nghiệm toán Vì thế, việc nghiên cứu vi phân hàm lồi vô hướng, hàm lôi véctơ ứng dụng chúng cần thiết Mục đích luận văn tổng kết kết quan trọng Giải tích lồi Giải tích lồi véctơ để thấy khả ứng dụng chúng lý thuyết tối ưu Cụ thể luận văn đề cập đến vấn đề sau: Nhắc lại số kiến thức giải tích lồi Giới thiệu vi phân đặc trưng hàm lồi trường hợp vô hướng Nghiên cứu vi phân hàm véctơ lồi số tính chất tính liên tục, hàm liên hợp hàm véctơ lồi đặc trưng hàm véctơ lồi Đưa số ứng dụng kết vào toán tối ưu véctơ lồi 75 Tài liệu tham khảo [A] Tài liệu tiếng Việt [1] Lê Dũng Mưu, Nguyễn Văn Hiền, Nguyễn Hữu Điển (2012), Giáo trình giải tích lồi ứng dụng, NXB Đại học Quốc gia Hà Nội [2] Nguyễn Xuân Tấn, Nguyễn Bá Minh (2007), Lý thuyết tối ưu không trơn, NXB Đại học Quốc gia Hà Nội [B] Tài liệu tiếng Anh [3] D T Luc, N.X.Tan and P.N.Tinh (1998), “Convex vector functions and their subdifferential”, Acta Mathematica VietNamMica, 23(1), 107-127 [4] D T Luc (1998) “Generalized convexity and some applications to vector optimization”, Viet J Math, 26, 95-110 [5] D T Luc (1989), “Theory of vector optimization”, Lecture notes in Economics and Mathematical Systems,(319), Springer, Berlin, 1-175 [6] N Papageorgiou (1987), “Nonsmooth analysis on partially ordered vector spaces : Part 1- convex case”, Pacific Journ of Math, 107(2), 403 - 458 [7] R T Rockafellar (1970), “Convex Analysis”, Princeton Univ Press, Princeton, New Jersey [8] T Tanino (1992), “Conjugate duality in vector optimization”, Journal of Mathematical Analysis and Applications, 167, 84-67 [9] P N Tinh and D S Kim (2013), “On generalized Fenchel- Moreau theorem and second-order characterization for convex vector functions”, Fixed Point Theory and Applications, 328, 1-12 76 [10] P N Tinh and N X Tan (2000), “On conjugate maps and directional derivatives os convex vecter functions”, Acta Math Viet.,25, 315-345 77 [...]... ; 16 m ii) Nếu tại x ∈ domfi tất cả các hàm fi i = 1, m liên tục (có thể trừ một hàm) i=1 thì ∂f1 (x) + ∂f2 (x) + + ∂fm (x) = ∂f (f1 + f2 + + fm ) (x) ¯ và x ∈ D Nếu Mệnh đề 1.4.16 Cho hàm lồi f từ một tập khác rỗng D ⊂ Rn vào R f khả vi dưới vi phân tại x thì domf (x, ) = T (D, x) ¯ và Mệnh đề 1.4.17 Cho f là một hàm lồi từ tập con lồi không rỗng D ⊆ Rn vào R x ∈ D, ξ ∈ L x, R Khi đó, ξ ∈ ∂f (x)... tục trên của ánh xạ dưới vi phân Mệnh đề 1.5.9 Cho f là một hàm lồi trên Rn Khi đó, ánh xạ dưới vi phân x → ∂f (x) nửa liên tục trên tại mọi điểm x ∈ (domf ) Chứng minh Ta có f lồi nên nó hữu hạn trên tập int(domf ) Áp dụng Mệnh đề 1.5.8, với U là một lân cận đủ nhỏ của x ∈ (domf ), ta suy ra ánh xạ dưới vi phân nửa liên tục trên tại điểm x Tiếp theo ta có một số kết quả sau, phần chứng minh có thể xem... nghiệm của bài toán (P6) 33 Chương 2 Hàm véctơ lồi và ứng dụng Mục đích của chương này là trình bày các vấn đề liên quan tới hàm véctơ lồi, đặc trưng cấp 1, cấp 2 của dưới vi phân của nó, khái niệm toán tử C−xác định từ Rn tới L(Rn , L(Rn , Rm )), (trong đó, L(Rn , Rm ) là kí hiệu không gian các ánh xạ tuyến tính liên tục từ Rn tới Rm và C ⊂ Rm là một nón lồi) Sử dụng khái niệm ma trận nửa xác định... bậc hai của tính lồi của hàm véctơ khả vi liên tục Đối với tính liên tục, ta chỉ ra rằng tính đóng là điều kiện đủ cho các hàm véctơ lồi là liên tục Cuối cùng, sử dụng ánh xạ lùi xa của các hàm véctơ lồi, ta tìm ra các điều kiện tồn tại nghiệm tối ưu của các bài toán véctơ không có ràng buộc và bài toán véctơ có ràng buộc Ta cũng đưa ra một số ví dụ minh họa Nội dung của chương này được vi t dựa trên... trưng cấp 2 của hàm lồi (xem trong [1]) Mệnh đề 1.5.11 Cho f : C → R khả vi hai lần Các điều kiện sau là tương đương: i) f là hàm lồi đóng chính thường; ii) Hessian của f xác định không âm 20 Kết quả này cũng được mở rộng cho trường hợp f không khả vi hai lần Ta giả thiết là f : C ⊆ Rn → R khả vi và f (.) : C ⊆ Rn → R là hàm lồi, với mỗi x ∈ C ta định nghĩa được dưới vi phân ∂f (x) và gọi tập này là... hạn và liên tục trên Rn Mệnh đề 1.4.10 Tại mỗi x ∈ D ta có T (D, x) là một nón lồi Mệnh đề 1.4.11 Cho f là một hàm lồi từ một tập con lồi không rỗng D ⊆ Rn vào ¯ và x ∈ D, d ∈ T (D, Rn ), khi đó: R 15 i) f có đạo hàm theo hướng d khi và chỉ khi tập f (x + λd) − f (x) , λ > 0, x + λd ∈ D λ bị chặn dưới và f (x, d) = inf f (x + λd) − f (x) , λ > 0, x + λd ∈ D ; λ ii) f (x, ) là hàm thuần nhất dương, lồi. .. 1.3.2, f ∗ là hàm lồi đóng nên theo Định lý 1.3.8 thì (f ∗ )∗∗ = f ∗ Vậy ta có f ∗ = (cof )∗ 1.4 Dưới vi phân Tính khả vi phân của hàm lồi đóng vai trò quan trọng trong các bài toán tối ưu, trong ¯ |f (x)| < +∞ các phương pháp tối ưu Cho D ⊂ Rn , f : D → R, Ta biết rằng trong trường hợp f khả vi tại x0 ∈ domf, thì tại lân cận của x0 , f được xấp xỉ một cách khá tốt bởi đạo hàm của nó Hàm lồi, nói chung... mà hàm f là hàm lồi Khi đó, tồn tại u ∈ (x, y) sao cho f (y) − f (x) ∈ {ξ(y − x) | ξ ∈ ∂f (u)} Mệnh đề dưới đây cho ta một định nghĩa khác tương đương với định nghĩa của dưới vi phân Mệnh đề 1.4.19 ([1], Chương 11, Mệnh đề 11.2) Cho f : Rn → R ∪ {+∞} lồi, chính thường i) x∗ ∈ ∂f (x) khi và chỉ khi f (x, y) ≥ x∗ , y , ∀y Nếu x ∈ ri(domf ) thì f (x, y) = sup x∗ , y , ∀y x∗ ∈∂f (x) ii) Nếu f là hàm lồi. .. Sau đây là đặc trưng của hàm lồi cho trường hợp khả vi Mệnh đề 1.5.3 ([1]) Cho f : Rn → R ∪ {+∞} khả vi và C ⊂ Rn Các điều kiện sau là tương đương: i) f lồi, chính thường trên C; ii) f (y) − f (x), y − x ≥ 0, ∀x, y ∈ domf Kết quả này được mở rộng cho trường hợp không khả vi như sau Mệnh đề 1.5.4 Giả sử S là một toán tử từ Rn vào Rn Điều kiện cần và đủ để tồn tại một hàm lồi, đóng, chính thường f... f lồi đóng Chứng minh Theo Hệ quả 1.1.12, A là tập lồi ⇒) Giả sử f = f ∗∗ theo Mệnh đề 1.3.2, f ∗∗ là hàm lồi đóng Vậy, f ∗∗ lồi đóng ⇐) Giả sử f lồi đóng +) Nếu f (x) = +∞ thì hiển nhiên f = f ∗∗ +) Nếu f (x) < +∞ theo Mệnh đề 1.3.4 f ∗∗ ≤ f Vì vậy, ta cần chứng minh, nếu f là hàm lồi chính thường, đóng thì f ≤ f ∗∗ Thật vậy, giả sử ∃x0 ∈ domf ∗∗ sao cho f (x0 ) > f ∗∗ (x0 ) Ta có epif là tập lồi