TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN **************** NGUYỄN THỊ VÂN CẤU TRÚC VÀ TÍNH CỰC TIỂU SẮC YẾU CỦA TẬP NGHIỆM PARETO TRONG TỐI ƯU ĐA MỤC TIÊU TUYẾN TÍNH TỪNG KHÚC KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Giải tích Hà Nội - 2015 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN **************** NGUYỄN THỊ VÂN CẤU TRÚC VÀ TÍNH CỰC TIỂU SẮC YẾU CỦA TẬP NGHIỆM PARETO TRONG TỐI ƯU ĐA MỤC TIÊU TUYẾN TÍNH TỪNG KHÚC KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Giải tích Người hướng dẫn khoa học ThS Nguyễn Văn Tuyên Hà Nội - 2015 ii LỜI CẢM ƠN Em xin chân thành cảm ơn Thầy giáo Nguyễn Văn Tuyên đã tận tình hướng dẫn, giúp đỡ em trong suốt thời gian thực hiện khóa luận. Em xin chân thành cảm ơn các thầy, các cô trong tổ giải tích-khoa Toán, trường Đại học sư phạm Hà Nội 2 đã tạo mọi điều kiện giúp đỡ em hoàn thành khóa luận này. Em xin chân thành cảm ơn gia đình và bạn bè đã tạo mọi điều kiện thuân lợi cho em trong quá trình thực hiện khóa luận. Em xin chân thành cảm ơn. Hà Nội, tháng 05 năm 2015 Sinh viên Nguyễn Thị Vân i LỜI CAM ĐOAN Em xin cam đoan, dưới sự hướng dẫn của Thầy giáo Nguyễn Văn Tuyên khóa luận "Cấu trúc và tính cực tiểu sắc yếu của tập nghiệm Pareto trong tối ưu đa mục tiêu tuyến tính từng khúc" được hoàn thành không trùng với bất kỳ đề tài nào khác. Trong quá trình hoàn thành khóa luận, em đã thừa kế 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, tháng 05 năm 2015 Sinh viên Nguyễn Thị Vân ii Mục lục Mở đầu 1 1 3 Bài toán tối ưu vector 1.1. Một số khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Quan hệ hai ngôi và quan hệ thứ tự . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3. Điểm hữu hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4. Sự tồn tại của điểm hữu hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5. 14 Bài toán tối ưu vector (VOP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Cấu trúc và tính cực tiểu sắc yếu của tập nghiệm Pareto trong tối ưu đa mục tiêu tuyến tính từng khúc 16 2.1. Đặt bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2. Cấu trúc của tập nghiệm Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1. Trường hợp không lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2. Trường hợp lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3. Tính cực tiểu sắc yếu toàn cục . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Kết luận 30 Tài liệu tham khảo 31 iii MỞ ĐẦU Tối ưu đa mục tiêu tuyến tính được nghiên cứu rộng rãi và được áp dụng để giải quyết nhiều vấn đề khác nhau trong kinh tế, tổ chức khoa học, năng lượng ... Ta biết rằng họ các hàm tuyến tính từng khúc lớn hơn họ các hàm tuyến tính và tồn tại một lớp rộng các hàm có thể xấp xỉ bằng các hàm tuyến tính từng khúc. Vì thế việc nghiên cứu các bài toán tối ưu đa mục tiêu tuyến tính từng khúc càng có ý nghĩa quan trọng hơn. Một trong các vấn đề quan trọng nhất khi nghiên cứu một bài toán tối ưu vector đó là nghiên cứu cấu trúc của tập nghiệm của bài toán này. Định lí Arrow, Brakin và Blaclwell cổ điển (Định lí ABB) phát biểu rằng: “Với bài toán tối ưu đa mục tiêu tuyến tính bất kì trong không gian định chuẩn hữu hạn chiều, tập nghiệm Pareto và Pareto yếu là hợp của hữu hạn các đa diện và liên thông đoạn”. Gần đây Yang [14] đã đưa ra một số mở rộng cho định lý này cho bài toán tối ưu đa mục tiêu tuyến tính từng khúc không gian định chuẩn vô hạn chiều. Một vấn đề quan trọng khác khi nghiên cứu bài toán tối ưu vector đó là nghiên cứu các thuật toán để giải bài toán này. Như chúng ta đã biết, khái niệm cực tiểu sắc yếu toàn cục (global weak sharp minima) của bài toán tối ưu vô hướng được đề xuất bởi Burke và Ferris [8] và được sử dụng để chứng minh tiêu chuẩn dừng hữu hạn của một vài thuật toán, như thuật toán gradien và các thuật toán chiếu gradien. Sau này, khái niệm quan trọng này được phát triển và áp dụng trong nhiều lĩnh vực (xem [9, 10, 11]). Một khái niệm liên quan gọi là tính cực tiểu sắc cũng được một vài tác giả nghiên cứu (xem [12]). Tính cực tiểu sắc yếu toàn cục của tập nghiệm Pareto yếu của một bài toán tối ưu đa mục tiêu tuyến tính trong không gian định chuẩn hữu hạn chiều được nghiên cứu bởi Deng và Yang [13]. Kết quả này được mở Khoá luận tốt nghiệp Nguyễn Thị Vân rộng trong [14] cho bài toán lồi đa mục tiêu tuyến tính từng khúc trong không gian định chuẩn bằng cách sử dụng các tính chất đặc trưng của tập nghiệm Pareto yếu được thiết lập trong [1]. Mục đích của khóa luận này là trình bày các kết quả trong bài báo [19]. Các kết quả này là một mở rộng Định lí ABB cho trường hợp tập nghiệm Pareto của bài toán tối ưu đa mục tiêu tuyến tính từng khúc trong không gian định chuẩn hữu hạn chiều và áp dụng nó để thiết lập tính cực tiểu sắc yếu toàn cục cho một bài toán lồi đa mục tiêu tuyến tính từng khúc. Khóa luận được chia thành hai chương: Chương 1 giới thiệu một số kiến thức cơ bản về tối ưu vector. Chương 2 chúng ta chứng minh rằng tập nghiệm Pareto của bài toán tối ưu đa mục tiêu tuyến tính từng khúc trong không gian định chuẩn hữu hạn chiều là hợp của hữu hạn các đa diện nửa đóng. Cũng trong phần này ta chỉ ra rằng, nếu hàm mục tiêu là lồi theo nón, thì tập nghiệm Pareto là hợp của hữu hạn các đa diện và liên thông đoạn. Cuối cùng, chúng ta thiết lập tính cực tiểu sắc yếu toàn cục với tập nghiệm Pareto của bài toán lồi đa mục tiêu tuyến tính từng khúc. 2 Chương 1 Bài toán tối ưu vector 1.1. Một số khái niệm cơ bản Giả sử E là không gian tuyến tính, R là tập các số thực. Định nghĩa 1.1. Tập A ⊂ E được gọi là lồi, nếu: ∀x1 , x2 ∈ A; ∀λ ∈ R : 0 λ 1 ⇒ λx1 + (1 − λ)x2 ∈ A. Ví dụ 1.1. Các nửa không gian là các tập lồi. Hình tam giác, hình tròn trong mặt phẳng là các tập lồi. Hình cầu đơn vị trong không gian Banach là tập lồi... Định nghĩa 1.2. Giả sử A ⊂ X. Tương giao của tất cả các tập lồi chứa A được gọi là bao lồi của tập A, kí hiệu là coA. Nhận xét 1.1. a) coA là một tập lồi. Đó là tập lồi bé nhất chứa A; b) A lồi khi và chỉ khi A = coA. Định nghĩa 1.3. Tập C ⊂ E được gọi là nón có đỉnh tại 0 nếu: ∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C. C được gọi là nón có đỉnh tại x0 , nếu C − x0 là nón có đỉnh tại 0. Khoá luận tốt nghiệp Nguyễn Thị Vân Định nghĩa 1.4. Nón C có đỉnh tại 0 được gọi là nón lồi, nếu C là một tập lồi, nghĩa là: ∀x, y ∈ C, ∀λ, µ > 0 ⇒ λx + µy ∈ C. Ví dụ 1.2. Các tập sau đây trong Rn : {ξ1 , ξ2 , ..., ξn ∈ Rn : ξi 0, i = 1, ..., n} (nón orthant không âm) {ξ1 , ξ2 , ..., ξn ∈ Rn : ξi > 0, i = 1, ..., n} (nón orthant dương) là các nón lồi có đỉnh tại 0. Đó là nón lồi quan trọng trong Rn . Ngoài ra, nếu cho D ⊆ Rm là một nón lồi, nón cực dương của D được xác định bởi: D∗ := {x∗ ∈ Rm :< x∗ , x > Cho a, b ∈ Rm , a ai D 0, ∀x ∈ D} . b khi và chỉ khi a − b ∈ D; a m 0, i = 1, ..., m. Kí hiệu Rm + := {x ∈ R : x 0 khi và chỉ khi 0} và cho g : X → Rm . Hàm g được gọi là D- giống lồi trên S ⊆ X khi và chỉ khi : ∀x1 , x2 ∈ S, ∀α ∈ [0, 1], ∃x ∈ S. sao cho (1 − α)g(x1 ) + αg(x2 ) − g(x) ∈ D. Điều này được biết đến trong [13] rằng g là một hàm D- giống lồi khi và chỉ khi tập g(S) + D là lồi. Định nghĩa 1.5. Tập A ⊂ Rn được gọi là tập affine, nếu (1 − λ)x + λy ∈ A(∀x, y ∈ A, ∀λ ∈ R) 4 Khoá luận tốt nghiệp Nguyễn Thị Vân Định nghĩa 1.6. Tương giao của tất cả các tập affine chứa tập A ⊂ Rn được gọi là bao affine của A và kí hiệu là af f A. Định nghĩa 1.7. Phần trong tương đối của tập A ⊂ Rn là phần trong của A trong af f A (bao affine); kí hiệu là riA. Các điểm thuộc riA được gọi là điểm trong tương đối của tập A. Nhận xét 1.2. intA := {x ∈ Rn : ∃ > 0, x + B ⊂ A} , riA := {x ∈ af f A : ∃ > 0, (x + B) ∩ af f A ⊂ A} , trong đó B là hình cầu đơn vị đóng trong Rn . Tiếp theo chúng ta sẽ đi xem xét một số nón thường gặp Cho C là nón lồi trong không gian vector tôpô E. Kí hiệu l(C) := C ∩ (−C) (phần tuyến tính của C); clC (bao đóng của C); một tập con A ⊆ E, Ac là phần bù của A trong E, nghĩa là Ac = E\A. Định nghĩa 1.8. Chúng ta nói nón C là: (a) Nhọn nếu l(C) = 0; (b) Nón sắc nếu bao đóng của nó là nhọn; (c) Nón có giá chặt nếu C\l(C) là được chứa trong một nửa không gian mở thuần nhất; (d) Nón đúng nếu (clC) + C\l(C) ⊆ C, hoặc tương đương clC + C\l(C) ⊆ C\l(C). Ví dụ 1.3. theo định nghĩa 1.8 1. Cho Rn là không gian Euclid n-chiều. Khi đó, nón orthant không âm Rn+ gồm tất cả các vectơr của Rn với toạ độ không âm là nón lồi, sắc, đóng, có giá chặt và là nón đúng. 5 Khoá luận tốt nghiệp Nguyễn Thị Vân Tập {0} cũng là một nón, nhưng là nón tầm thường. Tập là hợp của 0 và các vector với toạ độ đầu tiên dương là một nón đúng, nhọn, có giá chặt nhưng không là nón sắc. Bất kì nửa không gian đóng thuần nhất là nón đúng, có giá chặt nhưng không là nón nhọn. 2. Cho Ω là không gian vectơr gồm tất cả dãy x = {xn } số thực. Cho C = {x ∈ Ω : xn 0, ∀n}, thì C là nón nhọn, lồi. Tuy nhiên, ta chưa biết nón C là nón đúng hoặc nón sắc vì ta chưa biết tôpô xác định trên không gian này. 3. Nón thứ tự từ điển: Cho 1 |xn |p ) p , 1 lp = x ∈ Ω : x = ( p < ∞. Kí hiệu C là hợp của 0 và các dãy mà số hạng đầu tiên khác không của dãy là dương. Đây là một nón lồi, còn gọi là nón thứ tự từ điển. Nó là nón nhọn nhưng không là nón đúng và cũng không phải là nón có giá chặt. Mệnh đề 1.1. Nón C là đúng khi và chỉ khi một trong các các điều kiện sau thoả mãn: (a) C là đóng; (b) C\l(C) là mở, khác rỗng; (c) C là hợp của 0 và giao của các nửa không gian mở và nửa không gian đóng trong E. Chứng minh. (a) Hiển nhiên, (b) Nếu C\l(C) mở thì intC = ∅ và intC = C\l(C). Do đó, ta có clC + C\l(C) = (clC) + intC ⊆ C, hay C là nón đúng. 6 Khoá luận tốt nghiệp Nguyễn Thị Vân (c) Giả sử C = {0} ∪ (∩ {Hλ : λ ∈ Λ}), ở đây Hλ là nửa không gian đóng hoặc mở trong E. Nếu tất cả Hλ là đóng thì điều này tương đương với C là đóng. Do đó, ta có thể giả sử ít nhất một nửa không gian là mở thì l(C) = {0} và b ∈ C\l(C) khi và chỉ khi b ∈ Hλ , ∀λ ∈ Λ. Hơn thế nữa, ta thấy a ∈ clC khi và chỉ khi a ∈ clHλ , ∀λ ∈ Λ nên clHλ + Hλ ∈ Hλ . Vậy Hλ là mở hoặc đóng thì a + b ∈ C, a ∈ C, b ∈ C\l(C). Mệnh đề được chứng minh. Định nghĩa 1.9. Cho một nón C trong không gian E. Một tập B ⊆ E sinh ra nón C và viết C = cone(B) nếu C = {tb : b ∈ B, t 0} . Hơn nữa, nếu B không chứa 0 và với mỗi c ∈ C, c = 0, tồn tại duy nhất b ∈ B, t > 0 sao cho c = tb thì B được gọi là cơ sở của C. Khi B là một tập hữu hạn, cone(conv(B)) được gọi là một nón đa diện. Nhận xét 1.3. Rõ ràng trong không gian hữu hạn chiều một nón có cở sở là lồi, đóng bị chặn khi và chỉ khi nó là nhọn, đóng. Tuy nhiên nó không đúng trong không gian vô hạn chiều. Mệnh đề 1.2. Nếu E là không gian Hausdorff thì một nón với một cơ sở lồi, đóng bị chặn là nón đóng, nhọn vì vậy nó là nón đúng. Chứng minh. Trước hết ta chỉ ra rằng C là đóng. Cho dãy {cα } là một lưới từ C hội tụ tới c. Do B là một cơ sở nên tồn tại một lưới {bα } từ B và một lưới {tα } các số dương mà cα = tα bα . Dễ thấy tα là bị chặn. Thật vậy, giả sử ngược lại limtα = ∞. Vì E là không gian Hausdorff nên lưới bα = cα tα hội tụ tới 0. Hơn thế nữa B là đóng, dẫn tới mâu thuẫn: 0 = limbα ∈ B. Bằng cách này, ta có thể giả sử {tα } hội tụ tới điểm to 0. Nếu to = 0 thì từ tính bị chặn của B, limtα bα = 0. Do đó c = 0 và hiển nhiên c ∈ C. Nếu to > 0, ta có thể giả sử tα > , ∀α, > 0. Từ bα = 7 cα tα hội tụ tới c to và Khoá luận tốt nghiệp hơn nữa B đóng nên vector Nguyễn Thị Vân c to ∈ B. Do đó c ∈ C và C đóng nên C nhọn là hiển nhiên. 1.2. Quan hệ hai ngôi và quan hệ thứ tự Cho một tập hợp E tuỳ ý, một quan hệ hai ngôi trong E được định nghĩa bởi một tập con B của tập hợp tích E × E. Điều này có nghĩa là một phần tử x ∈ E có quan hệ với y ∈ E nếu (x, y) ∈ B. Định nghĩa 1.10. Cho B là một quan hệ hai ngôi trong E. Ta nói quan hệ này là: (a) Phản xạ nếu (x, x) ∈ B với mọi x ∈ E; (b) Đối xứng nếu(x, y) ∈ B suy ra (y, x) ∈ B với mỗi x, y ∈ E; (c) Bắc cầu nếu (x, y) ∈ B,(y, z) ∈ B suy ra (x, z) ∈ B với x, y, z ∈ B; (d) Đầy đủ hoặc liên thông nếu (x, y) ∈ B hoặc (y, x) ∈ B với mỗi x, y ∈ E, x = y; (e) Tuyến tính trong trường hợp E là không gian vector thực nếu (x, y) ∈ B suy ra (tx + z, ty + z) ∈ B với mọi x, y, z ∈ E, t > 0; (f) Đóng trong trường hợp E là không gian vector tôpô, nếu nó là đóng như một tập con của không gian tích E × E. Để làm rõ định nghĩa này chúng ta xem xét một số ví dụ cổ điển sau. Cho E là một cộng đồng dân cư của một thành phố và chúng ta định nghĩa quan hệ hai ngôi như sau (số dân cư được gán bởi x, y, z,...) 1. (x, y) ∈ B1 nếu x, y là những người tuổi cao hoặc có tuổi. 2. (x, y) ∈ B2 nếu x, y là hai giới tính khác nhau. 3. (x, y) ∈ B3 nếu x, y là những người có họ. 8 Khoá luận tốt nghiệp Nguyễn Thị Vân Ta thấy rằng B1 là phản xạ, bắc cầu, không đối xứng, đầy đủ. B2 không phản xạ, đối xứng, không bắc cầu, không đầy đủ. B3 là phản xạ, không bắc cầu, đối xứng, không đầy đủ. Định nghĩa 1.11. Quan hệ hai ngôi là một quan hệ thứ tự nếu nó là phản xạ, bắc cầu. Thật vậy, nếu B là một quan hệ thứ tự mà là tuyến tính trong một không gian vector thì tập C = {x ∈ E : (x, 0) ∈ B} là một nón lồi. Hơn nữa, nếu B là không đối xứng thì C là nhọn. Ngược lại, mỗi nón lồi trong E cho một quan hệ hai ngôi BC = {(x, y) ∈ E × E : x − y ∈ C} là phản xạ, bắc cầu và tuyến tính. Ngoài ra, nếu C là nhọn thì BC là không đối xứng. Bây giờ, chúng ta sẽ xét một vài thứ tự sinh ra bởi các nón lồi. Đôi khi chúng ta viết: x C y thay cho x − y ∈ C; hoặc x y nếu nó chắc chắn là quan hệ hai ngôi được định nghĩa bởi C; x >C y nếu x C y và không phải là y hay là x ∈ y + C\l(C). Khi intC = 0, x C x, C y nghĩa là x >K y với K = {0} ∪ intC. Ví dụ 1.4. 1. Cho Rn và tập C = Rn+ . Thì BC là phản xạ, bắc cầu, tuyến tính, đóng, không đối xứng nhưng không đầy đủ. Cho x = (x1 , ..., xn ) , y = (y1 , ..., yn ) ∈ Rn : 9 Khoá luận tốt nghiệp x C Nguyễn Thị Vân y khi và chỉ khi xi x >C y khi và chỉ khi xi yi với i = 1,..., n; yi với i = 1,..., n và ít nhất một bất đẳng thức là ngặt; x C y khi và chỉ khi xi > yi với mọi i = 1,..., n. 2. Trong R2 . Nếu C = R1 , 0 thì BC là phản xạ, bắc cầu, tuyến tính, đóng và đối xứng. Trong trường hợp này x C y khi và chỉ khi hai thành phần của các vector trùng nhau. Thứ tự này không đầy đủ. 3. Nón thứ tự từ điển là một quan hệ phản xạ, bắc cầu, tuyến tính đầy đủ trong lp . 1.3. Điểm hữu hiệu Cho E là không gian vector tôpô thực với quan hệ thứ tự ( ) được sinh bởi một nón lồi C. Định nghĩa 1.12. Cho A là một tập con khác rỗng của E. Ta nói rằng: (a) x ∈ A là một điểm hữu hiệu lí tưởng (hoặc cực tiểu lí tưởng) của A tương ứng với C nếu y x, ∀y ∈ A; Tập các điểm cực tiểu lí tưởng của A được kí hiệu là IE(A|C); (b) x ∈ A là điểm hữu hiệu (cực tiểu-Pareto hoặc cực tiểu) của A tương ứng với C nếu x y, y ∈ A thì y x; Tập các điểm hữu hiệu của A kí hiệu là E(A|C); (c) x ∈ A là điểm hữu hiệu thực sự (toàn cục) của A tương ứng với C nếu tồn tại một nón lồi K = E với intK ⊇ C\l(C) sao cho x ∈ E(A|K); Tập các điểm hữu hiệu toàn cục của A được kí hiệu là P rE(A|C); (d) Giả sử intC = ∅, x ∈ A là một điểm hữu hiệu yếu của A tương ứng với 10 Khoá luận tốt nghiệp Nguyễn Thị Vân C nếu x ∈ E(A| {0} ∪ intC); Tập các điểm hữu hiệu yếu của A kí hiệu là W E(A|C). Ví dụ 1.5. Cho: A = (x, y) ∈ R2 : x2 + y 2 0 ∪ {(x, y) : x 1, y 0, 0 y −1} ; B = A ∪ {(−2, −2)}. Nếu cho C = R2+ , ta có: IE(B) = P rE(B) = E(B) = W E(B) = {(−2, −2)}; IE(A) = ∅, P rE(A) = (x, y) ∈ R2 : x2 + y 2 = 1, 0 > x, 0 > y , E(A) = P rE(A) ∪ {(0, −1)} ∪ {(−1, 0)}, W E(A) = E(A) ∪ {(x, y) : y = −1, x 0}. Bây giờ cho C = (R1 , 0) ⊆ R2 . Ta có : IE(B) = ∅, P rE(B) = E(B) = W E(B) = B, IE(A) = ∅, P rE(A) = E(A) = W E(A) = A. Từ định nghĩa của các điểm hữu hiệu, ta có mệnh đề sau: Mệnh đề 1.3. Cho A ⊆ E thì : (a) x ∈ IE(A) khi và chỉ khi x ∈ A và A ⊆ x + C; (b) x ∈ E(A) khi và chỉ khi A ∩ (x − C) ⊆ x + l(C) hoặc tương đương: ∃y ∈ A sao cho x > y. Đặc biệt khi C là nhọn, x ∈ E(A) khi và chỉ khi A ∩ (x − C) = {x}; (c) Khi C = E, x ∈ W E(A) khi và chỉ khi A ∩ (x − intC) = ∅ hoặc tương đương với ∃y ∈ A sao cho x y. Mệnh đề 1.4. Cho tập khác rỗng A ⊆ E có: 11 Khoá luận tốt nghiệp Nguyễn Thị Vân P rE(A) ⊆ E(A) ⊆ W E(A). Hơn nữa, nếu IE(A) = ∅ thì IE(A) = E(A) và nó là tập một điểm khi C là nhọn. Chứng minh. Lấy x ∈ P rE(A). Nếu x ∈ E(A) có y ∈ A và x − y ∈ C\l(C). Lâý nón lồi K, K = E với intK ⊆ C\l(C) và x ∈ E(A|K). Thì x − y ∈ intK ⊆ K\l(K). Điều này mâu thuẫn với x ∈ E(A|K) suy ra P rE(A) ⊆ E(A). Lấy x ∈ E(A). Nếu x ∈ W E(A) theo Mệnh đề 1.3 tồn tại y ∈ A sao cho x−y ∈ intC. Do C = E, intC ⊆ C\l(C) nên ta có x−y ∈ C\l(C).Điều này mâu thuẫn với x ∈ E(A). Vậy E(A) ⊆ W E(A). Rõ ràng IE(A) ⊆ E(A). Nếu IE(A) = ∅, cho x ∈ IE(A) thì x ∈ E(A). Cho y ∈ E(A) thì y ≥ x vì vậy x có z x vì x ∈ IE(A) suy ra z Ngoài ra, nếu C là nhọn x y. Lấy một điểm bất kì z ∈ A y là y ∈ IE(A). Do đó IE(A) = E(A). y và y ≥ x chỉ có thể xảy ra trường hợp x = y. Vậy IE(A) là tập một điểm. Định nghĩa 1.13. Cho x ∈ E. Tập A ∩ (x − C) được gọi là một nhát cắt A tại x và kí hiệu Ax . Mệnh đề 1.5. Cho x ∈ E với Ax = ∅. Ta có : (a) IE(Ax ) ⊆ IE(A) nếu IE(A) = ∅; (b) E(Ax ) ⊆ E(A) (tương tự cho W E). Chứng minh. (a) Cho y ∈ IE(Ax ) và z ∈ IE có Ax ⊆ y + C và A ⊆ z + C. Thì z ∈ Ax và z − y ∈ l(C) suy ra A ⊆ z + C = y + z − y + C = y + l(C) + C = y + C. Do đó y ∈ IE(A). 12 Khoá luận tốt nghiệp Nguyễn Thị Vân (b) Giả sử y ∈ E(Ax ). Theo Mệnh đề 1.4 có Ax ∩ (y − C) ⊂ y + l(C) suy ra y − C ⊆ x − C nên A ∩ y − C ⊆ A ∩ (y − C) ∩ (x − C) ⊆ Ax ∩ (y − C) ⊆ y + l(C). Do đó y ∈ E(A). Chứng minh tương tự cho W E. Nhận xét 1.4. Quan hệ P rE(Ax ) ⊆ P rE(A) nói chung không đúng trừ một số trường hợp đặc biệt. 1.4. Sự tồn tại của điểm hữu hiệu Định nghĩa 1.14. Cho lưới {xα : α ∈ I} từ E được gọi là lưới giảm (tương ứng với C) nếu xα >C xβ với α, β ∈ I; β > α. Định nghĩa 1.15. Cho A ⊆ E được gọi là C- đầy đủ (tương ứng Cđầy đủ mạnh) nếu nó không có phủ dạng {(xα − clC)c : α ∈ I} (tương ứng {(xα − C)c : α ∈ I}) với {xα } là một lưới giảm trong A. Định lý 1.1. Giả sử C là một nón lồi đúng và A là một tập khác rỗng trong E. Thì E(A|C) = ∅ khi và chỉ khi A có một nhát cắt C- đầy đủ và khác rỗng. Chứng minh. Nếu E(A|C) = ∅ thì mọi điểm của tập này cho ta một nhát cắt C- đầy đủ vì không tồn tại lưới giảm. Ngược lại, cho Ax khác rỗng là một nhát cắt C- đầy đủ của A. Theo Mệnh đề 1.5 thì ta chỉ cần chứng minh E(Ax |C) = ∅. Xét tập P bao gồm tất cả các lưới giảm trong A. Vì A = ∅ suy ra P = ∅. Với a, b ∈ P ta viết a b nếu b ⊆ a. Rõ ràng ( ) là quan hệ thứ tự trong P , và một xích bất kì trong P đều có cận trên. Thật vậy, giả sử {aλ ; λ ∈ Λ} là một xích trong P . Gọi B là tập tất cả các tập 13 Khoá luận tốt nghiệp Nguyễn Thị Vân con hữu hạn B của Λ được sắp thứ tự bởi bao hàm và đặt aB = ∪ {aα ; α ∈ B} . Và ao = ∪ {aB : B ∈ B} . Thì ao là một phần tử của P và ao aα với mọi α ∈ Λ nghĩa là ao là một cận trên của xích này. Áp dụng bổ đề Zorn, tồn tại phần tử lớn nhất của P , kí hiệu là a∗ = {xα : α ∈ I} ∈ P . Bây giờ, giả sử ngược lại E(Ax |C) = ∅. Chúng ta sẽ chứng minh {(xα − clC)c : α ∈ I} phủ Ax . Ta chỉ ra với mỗi y ∈ Ax có α ∈ I mà (xα − clC)c chứa y. Giả sử phản chứng y ∈ xα − clC, ∀α ∈ I. Vì E(Ax |C) = ∅ có z ∈ Ax với y >C z. Do tính đúng của C nên x − α >C z, (α ∈ I). Thêm z vào lưới a∗ ta thấy rằng lưới này không thể lớn nhất, dẫn tới mâu thuẫn. Vậy định lí được chứng minh. 1.5. Bài toán tối ưu vector (VOP) Cho X là một tập con khác rỗng của một không gian tôpô và F là một ánh xạ đa trị từ X vào E, ở đây E là không gian vector tôpô thực được sắp thứ tự bởi nón lồi C. Xét VOP : minF (x) với ràng buộc x ∈ X. Điểm x ∈ X được gọi là tối ưu (cực tiểu hoặc hữu hiệu) của VOP nếu F (x) ∩ E(F (X)|C) = ∅. Ở đây F (X) là hợp của các tập F (x) trên X. Các phần tử của E(F (x)|C) được gọi là giá trị tối ưu của VOP. Tập các điểm hữu hiệu của 14 Khoá luận tốt nghiệp Nguyễn Thị Vân VOP được kí hiệu là S(X; F ). Thay thế IE, P rE, W E cho E(F (X)|C) chúng ta có các khái niệm IS(X; F ), P rS(X; F ) và W S(X; F ). Quan hệ giữa các điểm hữu hiệu, hữu hiệu thực sự và hữu hiệu yếu của VOP được trình bày trong mệnh đề sau: Mệnh đề 1.6. Cho VOP, chúng ta có các bao hàm thức sau: P rS(X; F ) ⊆ S(X; F ) ⊆ W S(X; F ). Hơn nữa, nếu IS(X; F ) = ∅ thì IS(X; F ) = S(X; F ). Chứng minh tương tự Mệnh đề 1.4 Bổ đề 1.1. Giả sử C là lồi, X là tập compac khác rỗng và F là C- liên tục trên trong X với F (x) + C là C- đầy đủ, đóng với mọi x ∈ X thì F (X) là C- đầy đủ. Chứng minh. Giả sử phản chứng rằng F (X) không là C đầy đủ. Điều này có nghĩa là có một lưới giảm {aα : α ∈ I} của F (X) sao cho {(aα −cl(C))c : α ∈ I} là phủ của F (X). Lấy xα ∈ X với aα ∈ F (xα ). Không mất tính tổng quát, giả sử lim xα = x ∈ X. Khi đó, với mỗi lân cận V của F (x) trong E có một chỉ số β ∈ I sao cho aα ∈ V + C, ∀α β. aα ∈ aδ + C, ∀δ α. Do {aα } là dãy giảm, nên Từ đây suy ra: aα ∈ cl(F (x) + C) = F (x) + C, ∀α. Dẫn tới mâu thuẫn: F (x) + C không thể là C- đầy đủ. 15 Chương 2 Cấu trúc và tính cực tiểu sắc yếu của tập nghiệm Pareto trong tối ưu đa mục tiêu tuyến tính từng khúc 2.1. Đặt bài toán Cho ánh xạ f : X → Y từ không gian định chuẩn X vào không gian định chuẩn hữu hạn chiều Y . Như trong [1], f được gọi là một hàm tuyến tính từng khúc (hoặc một hàm affin từng khúc), nếu tồn tại các họ {P1 , ..., Pk }, {T1 , ..., Tk } và {b1 , ..., bk } của tập lồi đa diện trong X, các toán tử tuyến tính liên tục từ X vào Y và các điểm tương ứng trên Y sao cho X= k i=1 Pi và f (x) = fi (x) := Ti (x) + bi ∀x ∈ Pi , ∀i ∈ {1, ..., k}. (2.1) Để có (2.1), ta phải có fi (x) = fj (x) ∀x ∈ Pi ∩ Pj , ∀i, j ∈ {1, ..., k}. Cho một họ hữu hạn các hàm tuyến tính liên tục giá trị thực, dễ thấy rằng phép toán lấy cực đại và cực tiểu của các họ này cho ta một hàm tuyến tính liên tục từng khúc. Tổng quát hơn, cực đại hoặc cực tiểu của một họ Khoá luận tốt nghiệp Nguyễn Thị Vân hữu hạn các hàm tuyến tính liên tục từng khúc giá trị thực bất kì cũng là một hàm tuyến tính liên tục từng khúc giá trị thực. Thông thường, chúng ta gọi một tập con của một không gian là một tập lồi đa diện (gọi tắt là một đa diện), nếu nó là toàn bộ không gian hoặc nó là giao của hữu hạn các nửa không gian đóng. Chú ý rằng hàm tuyến tính liên tục từng khúc và bài toán tối ưu đa mục tiêu liên quan được nghiên cứu theo các quan điểm khác nhau. Ví dụ, Gowda và Szajder [2] nghiên cứu tính chất giả-Lipschitz của f −1 và chỉ ra rằng các kết quả thu được có thể áp dụng cho bất đẳng thức biến phân affin và bài toán bù tuyến tính. Đáng chú ý rằng định nghĩa của một hàm tuyến tính từng khúc được nhắc lại ở trên thì yếu hơn trong [2], trong đó giả thiết rằng với mọi cặp (i, j), Pi ∩ Pj bằng rỗng hoặc một mặt chung của Pi và Pj . Đối với bài toán quy hoạch tuyến tính hai cấp với cấu trúc mạng đặc biệt hoặc cấu trúc tài chính, tập nghiệm Pareto được khảo sát trong [3,4]. Cho D ⊂ X là một đa diện, cho C ⊂ Y là một nón lồi đa diện và f : X → Y là một hàm tuyến tính từng khúc. Xét bài toán tối ưu đa mục tiêu tuyến tính từng khúc dưới đây: (P ) min f (x) sao cho x ∈ D. C Cho u ∈ D. Nhắc lại rằng u được gọi là một nghiệm Pareto của (P ) nếu x ∈ D, f (u) − f (x) ∈ C\{0Y }. Một điểm u được gọi là một nghiệm Pareto yếu của (P ), nếu không tồn tại x ∈ D với f (u) − f (x) ∈ intC, ở đó intC kí hiệu phần trong của C. Tập tất cả các nghiệm Pareto (tương tự., tập tất cả các nghiệm Pareto yếu) được kí hiệu bởi S (tương tự., Sw ). Việc nghiên cứu các tính chất đặc trưng của tập nghiệm này rất hữu ích trong việc thiết kế các thuật toán để giải (P ). Theo [5, p. 341], chúng ta nói rằng f : X → Y là một C-lồi trên D 17 Khoá luận tốt nghiệp Nguyễn Thị Vân nếu với mọi x1 , x2 ∈ D và t ∈]0, 1[, thì (1 − t)f (x1 ) + tf (x2 ) − f ((1 − t)x1 + tx2 ) ∈ C. Trong trường hợp Y = Rn và C = Rn+ (nón orthant không âm trong Rn ), f = (f1 , ..., fn ) được gọi là một hàm lồi trên D khi đó nó là một C-lồi trên D. Vì vậy, tính lồi của f trên D thì tương đương với tính lồi của các fi trên D. Nếu f là một C-lồi trên D thì ta nói rằng (P ) là một bài toán lồi. 2.2. Cấu trúc của tập nghiệm Pareto 2.2.1. Trường hợp không lồi Một tập con của một không gian định chuẩn được gọi là một đa diện nửa đóng, nếu nó là giao của một họ bao gồm hữu hạn các nửa không gian đóng và hữu hạn các nửa không gian mở. Từ đây và về sau, giao của một họ rỗng các tập con trong không gian định chuẩn được quy ước là toàn bộ không gian. Định lý 2.1. Tập nghiệm Pareto S của (P ) là hợp của hữu hạn các đa diện nửa đóng. Chứng minh. Đặt M = k i=1 Mi , ở đó Mi := fi (Pi ∩ D) với i = 1, ..., k. Chúng ta kí hiệu tập nghiệm Pareto của Mi là E(Mi |C). Từ định nghĩa, ta có S = {x ∈ D : f (x) ∈ E(M |C)} = f −1 (E(M |C)) ∩ D. (2.2) Đẳng thức (2.2) cho phép chúng ta để sử dụng phương pháp tiếp cận không gian ảnh (xem [5, 15]) để chứng minh các khẳng định sau: thứ nhất, trong không gian ảnh Y tập E(M |C) là hợp của hữu hạn các đa diện nửa đóng; 18 Khoá luận tốt nghiệp Nguyễn Thị Vân thứ hai từ (2.2) và giả thiết f tuyến tính từng khúc thì S là hợp của hữu hạn các đa diện nửa đóng. Khẳng định 1. E(M |C) là hợp của hữu hạn các đa diện nửa đóng. Chú ý rằng E(M |C) ⊂ E(M1 |C) ∪ E(M2 |C) ∪ ... ∪ E(Mk |C). (2.3) Với i ∈ {1, ..., k} bất kì, Mi = {Ti (x) + bi : x ∈ Pi ∩ D} là một tập lồi đa diện trong Y . Từ Y là một không gian định chuẩn hữu hạn chiều và C ⊂ Y là một nón lồi đa diện, Định lí ABB khẳng định rằng E(Mi |C) là hợp của hữu hạn các đa diện (nó là các mặt của Mi ). Giả sử rằng mi E(Mi |C) = Qi,r , i = 1, ..., k, (2.4) r=1 ở đó mỗi Qi,r là một đa diện trong Y . Sử dụng (2.3) và (2.4), bây giờ chúng ta có thể mô tả một thuật toán cho việc tìm toàn bộ tập E(M |C). Bước 1. Xét tập nghiệm Pareto E(M1 |C). Từ (2.4) ta có, mi E(M1 |C) = Q1,r . (2.5) r=1 Rõ ràng, một điểm v ∈ Q1,r , với r ∈ {1, ..., m1 }, trong E(M |C) khi và chỉ khi v ∈ Mi + (C \{0Y }), ∀i ∈ {2, ..., k}. (2.6) Lấy v ∈ Q1,r bất kì. Cho i = 2. Nếu v ∈ M2 + C thì có hai khả năng: (a) v ∈ M2 + (C \{0Y }), (b) v ∈ M2 . Trong trường hợp (a) từ tiêu chuẩn (2.6), v không thể thuộc E(M |C) . Do đó chúng ta có thể loại trừ v từ Q1,r . Trong trường hợp (b) có hai trường hợp con: (b1 ) v ∈ E(M2 |C), (b2 ) 19 v ∈ E(M2 |C). Khoá luận tốt nghiệp Nguyễn Thị Vân Trường hợp (b1 ) sẽ được phân tích ở bước sau khi chúng ta nói về tập E(M2 |C). Trong trường hợp (b2 ) chúng ta có thể bỏ qua v này vì từ (2.3), v ∈ E(M2 |C). Vì thế nếu trường hợp (b2 ) xảy ra thì chúng ta có thể loại trừ v từ Q1,r . Bởi theo Định lí 19.1 trong [16], M2 + C là một tập lồi đa diện. Quan sát rằng, sau khi loại bỏ từ Q1,r tất cả các điểm đều thuộc M2 + C, chúng ta thu được hợp của hữu hạn các đa diện nửa đóng. Thật vậy, nếu M2 + C = l2 s=1 ở đó l2 là một số nguyên và mỗi s, s là một nửa không gian đóng, thì l2 (2) Q1,r := Q1,r \[M2 + C] = l2 Q1,r \ s=1 Khi đó, Q1,r ∩ (Y \ s) s Q1,r ∩ (Y \ = s=1 s ) . (s = 1, ..., l2 ) là các đa diện nửa đóng. Lặp lại quá trình làm cho i = 2 với i = 3 chúng ta thu được tập (3) (2) Q1,r := Q1,r \[M3 + C] nó là hợp của hữu hạn các đa diện nửa đóng. Tiếp tục quá trình đệ quy ở trên cho tới khi thu được tập (k) (k−1) Q1,r := Q1,r \[Mk + C]. (k) Chú ý rằng Q1,r được chứa trong E(M |C) và có thể được biểu diễn bằng hợp hữu hạn của các đa diện nửa đóng. Từ (2.5) và cách xây dựng ở trên chúng ta thấy rằng (k) m1 r=1 Q1,r ⊂ E(M |C). Bước 2. Chúng ta lặp lại quá trình làm cho E(M1 |C) với tập nghiệm Pareto E(M2 |C), thay i = 1 bằng i = 2 trong Bước 1. Chúng ta đặt (1) Q2,r := (Q2,r \[M1 + C]) ∪ Q2,r ∩ E(M1 |C)) (k) khi Q2,r ∩ E(M1 |C) = ∅. Do vậy, chúng ta thu được tập Q2,r (r = 1, ..., m2 ) sao cho mỗi tập này là hợp của hữu hạn các đa diện nửa đóng. Từ đẳng thức thứ 2 trong (2.4), chúng ta có (k) m2 r=1 Q2,r 20 ⊂ E(M |C). Khoá luận tốt nghiệp Nguyễn Thị Vân Bước j (j ∈ {3, ..., k − 1}). Thay i = 1 ( tương tự., i = 2, ..., i = j −1) bằng i = 2 ( tương tự., i = 3, ..., i = j) trong Bước 1. Chúng ta đặt (i) Qj,r := (Qj,r \[Mi + C]) ∪ Qj,r ∩ E(Mi |C)) khi Qj,r ∩ E(Mi |C) = ∅ với i ∈ {1, ..., j − 1}. Do vậy, chúng ta được bao hàm mj (k) r=1 Qj,r (k) ⊂ E(M |C), ở đó mỗi tập Qj,r là hợp của hữu hạn các đa diện nửa đóng. Bước k. Chúng ta thay i = 1 ( tương tự., i = 2, ..., i = k − 1) bằng i = 2 (tương tự., i = 3, ..., i = k ) trong Bước 1. Chúng ta đặt (i) Qk,r := (Qk,r \[Mi + C]) ∪ [Qk,r ∩ E(Mi |C)], khi Qk,r ∩ E(Mi |C) = ∅ với i ∈ {1, ..., k − 1}. Do vậy, chúng ta thu được bao hàm (k−1) mk r=1 Qk,r (k−1) ⊂ E(M |C), ở đó mỗi tập Qk,r là hợp của hữu hạn các đa diện nửa đóng. Sau khi hoàn thành k bước ở trên, chúng ta thu được bao hàm k−1 mi mk (k) Qi,r i=1 (k−1) ∪ r=1 Qk,r ⊂ E(M |C). r=1 Ngoài ra, từ (2.3) và từ quá trình xây dựng thì bao hàm cuối cùng là một đẳng thức nên k−1 mi mk (k) Qi,r E(M |C) = i=1 r=1 (k−1) ∪ Qk,r . (2.7) r=1 Rõ ràng, tập nằm bên phải của đẳng thức này là hợp của hữu hạn các đa diện nửa đóng. Khẳng định 2. S là hợp của hữu hạn các đa diện nửa đóng. Từ (2.2) và (2.7) chúng ta có thể suy ra rằng S là hợp của hữu hạn các đa diện nửa đóng. Bỏ qua chi tiết, chúng ta chỉ cần xét rằng, với mỗi nửa không gian mở Ω := {y ∈ Y : y ∗ , y < β} (y ∗ ∈ Y ∗ , β ∈ R) 21 Khoá luận tốt nghiệp Nguyễn Thị Vân và với ∀i ∈ {1, ..., k}, công thức fi−1 (Ω) ∩ Pi = {x ∈ Pi : fi (x) ∈ Ω} = {x ∈ Pi : y ∗ , Ti (x) + bi < β} = {x ∈ Pi : Ti∗ (y ∗ ), x < β − y ∗ , bi } chi ra rằng fi−1 (Ω) ∩ Pi là một đa diện nửa đóng trong X. Mệnh đề được chứng minh. Lược đồ chứng minh trên vẫn đúng cho Định lí 2.4 trong [1]. Ví dụ sau minh họa kết quả thu được trong Định lí 2.1. Ví dụ 2.1. Cho X = R, Y = R2 , D = {x : 0 ≤ x ≤ 1}, C = R2+ và   f1 (x) := (2x, 1 − 2x) nếu x ∈ P1 :=] − ∞, 1 ] 2 f (x) = 3 1  f2 (x) := ( − x, 0) nếu x ∈ P1 := [ , +∞[. 2 2 Ta có M1 := f1 (P1 ∩ D) = f1 0, 1 2 = conv{(0, 1), (1, 0)}, trong đó conv là phép toán lấy bao lồi. Vì vậy, E(f1 (P1 ∩ D)|R2+ ) = conv{(0, 1), (1, 0)}. Tương tự, M2 := f2 (P2 ∩ D) = f2 1 ,1 2 = conv (1, 0), 1 ,0 2 và E(f2 (P2 ∩ D)|R2+ ) = 1 ,0 2 . 1 ,0 2 , S = 0, Đặt M := M1 ∪ M2 = f (D), ta được E(M |R2+ ) = t t ,1 − 2 2 :0≤t 0 bất kì, chúng ta có thể tìm v ∈ f (S) sao cho f (x) − v ≤ d(f (x), f (S)) + ε. Bởi (2.9), tồn tại r ∈ {1, ..., q} sao cho v ∈ Qr . Lấy u ∈ S sao cho f (u) = v. Rõ ràng, δr = min y∈f (D)+C yr∗ , y = yr∗ , v = yr∗ , f (u) = ϕr (u). Vì thế, khi Xr ∩ D ⊂ S từ (2.12) và (2.13) chúng ta được 28 Khoá luận tốt nghiệp Nguyễn Thị Vân d(x, S) ≤ d(x, Xr ∩ D) ≤ τr d(x, Xr ) + d(x, D) ≤ τr γr ϕr (x) − δr + + d(x, D) ≤ τr γr (ϕr (x) − δr ) − (ϕr (u) − δr ) ≤ τr γr yr∗ , f (x) − f (u) + + + d(x, D) + d(x, D) ≤ τr γr ||yr∗ ||||f (x) − f (u)|| + d(x, D) ≤ γ ||f (x) − v|| + d(x, D) , điều đó kéo theo d(x, S) ≤ γ d(f (x), f (S)) + d(x, D) + ε . Từ ε > 0 có thể chọn nhỏ tuỳ ý, điều này suy ra (2.8). Định lý được chứng ✷ minh. Giả thiết rằng f là một C-lồi trong định lí trên thì không thể bỏ qua. Để thấy điều này, trong Ví dụ 3.1 của [14], lấy X = Y = R, C = R+ , D = R và  |x|, nếu x ∈] − 1, 1[ f (x) = 1, nếu x ∈] − ∞, −1] ∪ [1, +∞[. Từ Định lí 2.4 chúng ta thu được kết quả tương tự với Định lí 2.2 trong [13] trong đó trường hợp tập nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu tuyến tính trong không gian Euclide được xem xét. Định lý 2.5. Nếu f : X → Y là một toán tử tuyến tính liên tục thì tập nghiệm Pareto S của (P ) có tính cực tiểu sắc yếu toàn cục. Định lí này mô tả tính cực tiểu sắc yếu toàn cục của tập nghiệm Pareto của tối ưu đa mục tiêu tuyến tính trong không gian định chuẩn. 29 Khoá luận tốt nghiệp Nguyễn Thị Vân KẾT LUẬN Khóa luận trình bày một số khái niệm cơ bản về lý thuyết tối ưu vector và một số dạng mở rộng của Định lý ABB cho tập nghiệm Pareto của bài toán tối ưu đa mục tiêu tuyến tính từng khúc. Cụ thể: Chương 1 trình bày một số kiến thức cơ bản trong lý thuyết tối ưu vector như: tập lồi, nón, quan hệ thứ tự, các điểm hữu hiệu và sự tồn tại nghiệm của bài toán tối ưu vector. Chương 2 trình bày cấu trúc và tính cực tiểu sắc yếu của tập nghiệm Pareto trong tối ưu đa mục tiêu tuyến tính từng khúc. Mục 2.1 trình bày bài toán tối ưu đa mục tiêu tuyến tính từng khúc. Mục 2.2 nghiên cứu cấu trúc của tập nghiệm Pareto của bài toán tối ưu đa mục tiêu tuyến tính từng khúc trong hai trường hợp: Mục 2.2.1 khảo sát cấu trúc của tập nghiệm Pareto của bài toán tối ưu đa mục tiêu tuyến tính từng khúc tổng quát. Mục 2.2.2 nghiên cứu cấu trúc tập nghiệm Pareto của lớp bài toán tối ưu đa mục tiêu tuyến tính từng khúc lồi. Mục 2.3 khảo sát tính chất cực tiểu sắc yếu toàn cục của tập nghiệm Pareto của lớp bài toán lồi. Các ví dụ được đưa ra để phân tích các kết quả được trình bày trong khóa luận. 30 Tài liệu tham khảo [1] Zheng, X.Y., Yang, X.Q.: The structure of weak Pareto solution sets in piecewise linear multiobjective otimization in normed spaces. Sci. China, Ser. A, Math. 51, 1243-1256 (2008). [2] Gowda, M.S., Szajder, R.: On the pseudo-Lipschitzian behavior of the inverse of a piecewise affine function. In: Complementarity and Variational Problems, Baltimore, 1995, pp. 117-131. SIAM, Philadelphia (1997). [3] Aneja, Y.P., Nair, K.P.K.:Bicriteria transportation problem. Manag. Sci. 25, 73-78 (1979/1980). [4] Cai, X.Q., Teo, K.L., Yang, X.Q., Zhou, X.Y.: Portfolio otimization under a minimax rule. Manag. Sci. 46, 957-972 (2000). [5] Giannessi, F.: Theorem of the alternative and optimality conditions. J. Optim. Theory Appl. 42, 331-365 (1984). [6] Arrow, K.J., Barankin, E.W., Blackwell, D.: Admissible points of convex sets. In: Contributions to the Theoty of Games, vol. 2. Annals of Mathematics Studies, vol. 28, pp. 87-91. Princeton University Presss, Princeton (1953). [7] Luc, D.T.: Theory of Vector Optimization. Springer, Berlin, (1989). Khoá luận tốt nghiệp Nguyễn Thị Vân [8] Burke, J.V., Ferris, M.C.: Weak sharp minima in mathematical programming. SIAM J. Control Optim. 31, 1340-1359 (1993). [9] Studniarski, M., ward, D.E.: Weak sharp minima: characterizations and sufficient conditions. SIAM J. Control Optim. 38, 219-236 (1999). [10] Burke, J.V., Deng, S.: Weak sharp minima revisited, Part I: basic theory. Control Cybern. 31, 439-469 (2002). [11] Burke, J.V., Deng, S.: Weak sharp minima revisited, Part II: application to linear regularity and error bounds. Math. Program., Ser. B 104, 235-261 (2005). [12] Zheng, X. Y., Yang, X.M., Teo, K.L.: Sharp minima for multiobjective optimization in Banach spaces. Set-Valued Anal. 14, 327-345 (2006). [13] Deng, S., Yang, X.Q.: Weak Sharp minima in multicriteria linear programming. SIAM J. Optim. 15, 456-460 (2004). [14] Zheng, X. Y., Yang, X.Q.: Weak sharp minima for piecewise linear multiobjective optimization in normed spaces.Nonlinear Anal.68,37713779 (2008). [15] Giannessi, F.: Theorems of the alternative for multifunctions with applications to optimization: general results. J. Optim. Theory Appl. 55, 233-256 (1987). [16] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970). [17] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, New York (1998). [18] Zalinescu, C.: Sharp estimates for Hoffman’s constant for systems of linear inequalities and equalities. SIAM J. Optim. 14, 517-533 (2003). 32 Khoá luận tốt nghiệp Nguyễn Thị Vân [19] X.Q. Yang, N.D. Yen.:Strcture and Weak Sharp Minimum of the Pareto Solution Set for Piecewise Linear Multiobjective Optimization. J Optim Theory Appl (2010) 147: 113-124. 33 [...]... từng khúc Mục 2.2 nghiên cứu cấu trúc của tập nghiệm Pareto của bài toán tối ưu đa mục tiêu tuyến tính từng khúc trong hai trường hợp: Mục 2.2.1 khảo sát cấu trúc của tập nghiệm Pareto của bài toán tối ưu đa mục tiêu tuyến tính từng khúc tổng quát Mục 2.2.2 nghiên cứu cấu trúc tập nghiệm Pareto của lớp bài toán tối ưu đa mục tiêu tuyến tính từng khúc lồi Mục 2.3 khảo sát tính chất cực tiểu sắc yếu toàn... tối ưu đa mục tiêu tuyến tính từng khúc Cụ thể: Chương 1 trình bày một số kiến thức cơ bản trong lý thuyết tối ưu vector như: tập lồi, nón, quan hệ thứ tự, các điểm hữu hiệu và sự tồn tại nghiệm của bài toán tối ưu vector Chương 2 trình bày cấu trúc và tính cực tiểu sắc yếu của tập nghiệm Pareto trong tối ưu đa mục tiêu tuyến tính từng khúc Mục 2.1 trình bày bài toán tối ưu đa mục tiêu tuyến tính từng. .. tuyến tính liên tục thì tập nghiệm Pareto S của (P ) có tính cực tiểu sắc yếu toàn cục Định lí này mô tả tính cực tiểu sắc yếu toàn cục của tập nghiệm Pareto của tối ưu đa mục tiêu tuyến tính trong không gian định chuẩn 29 Khoá luận tốt nghiệp Nguyễn Thị Vân KẾT LUẬN Khóa luận trình bày một số khái niệm cơ bản về lý thuyết tối ưu vector và một số dạng mở rộng của Định lý ABB cho tập nghiệm Pareto của. .. nón lồi đa diện và f : X → Y là một hàm tuyến tính từng khúc Xét bài toán tối ưu đa mục tiêu tuyến tính từng khúc dưới đây: (P ) min f (x) sao cho x ∈ D C Cho u ∈ D Nhắc lại rằng u được gọi là một nghiệm Pareto của (P ) nếu x ∈ D, f (u) − f (x) ∈ C\{0Y } Một điểm u được gọi là một nghiệm Pareto yếu của (P ), nếu không tồn tại x ∈ D với f (u) − f (x) ∈ intC, ở đó intC kí hiệu phần trong của C Tập tất... các hàm tuyến tính liên tục giá trị thực, dễ thấy rằng phép toán lấy cực đại và cực tiểu của các họ này cho ta một hàm tuyến tính liên tục từng khúc Tổng quát hơn, cực đại hoặc cực tiểu của một họ Khoá luận tốt nghiệp Nguyễn Thị Vân hữu hạn các hàm tuyến tính liên tục từng khúc giá trị thực bất kì cũng là một hàm tuyến tính liên tục từng khúc giá trị thực Thông thường, chúng ta gọi một tập con của một... V của F (x) trong E có một chỉ số β ∈ I sao cho aα ∈ V + C, ∀α β aα ∈ aδ + C, ∀δ α Do {aα } là dãy giảm, nên Từ đây suy ra: aα ∈ cl(F (x) + C) = F (x) + C, ∀α Dẫn tới mâu thuẫn: F (x) + C không thể là C- đầy đủ 15 Chương 2 Cấu trúc và tính cực tiểu sắc yếu của tập nghiệm Pareto trong tối ưu đa mục tiêu tuyến tính từng khúc 2.1 Đặt bài toán Cho ánh xạ f : X → Y từ không gian định chuẩn X vào không gian... phân affin và bài toán bù tuyến tính Đáng chú ý rằng định nghĩa của một hàm tuyến tính từng khúc được nhắc lại ở trên thì yếu hơn trong [2], trong đó giả thiết rằng với mọi cặp (i, j), Pi ∩ Pj bằng rỗng hoặc một mặt chung của Pi và Pj Đối với bài toán quy hoạch tuyến tính hai cấp với cấu trúc mạng đặc biệt hoặc cấu trúc tài chính, tập nghiệm Pareto được khảo sát trong [3,4] Cho D ⊂ X là một đa diện,... hợp trong sơ đồ chứng minh của Zheng và Yang [14], Yang và Yen [19] nhận được kết quả sau Định lý 2.4 Nếu f là một C-lồi trên X thì tập nghiệm Pareto S của (P ) có tính cực tiểu sắc yếu toàn cục Trước hết ta nhắc lại một số kết quả trong [14, 17] được sử dụng để chứng minh Định lý 2.4 Bổ đề 2.1 ([17, Định lý 2.49]) Nếu ϕ : X → R là một hàm lồi và tuyến tính từng khúc thì tồn tại a∗1 , , a∗l ∈ X ∗ và. .. Giả thiết rằng f là một C-lồi trong định lí trên thì không thể bỏ qua Để thấy điều này, trong Ví dụ 3.1 của [14], lấy X = Y = R, C = R+ , D = R và  |x|, nếu x ∈] − 1, 1[ f (x) = 1, nếu x ∈] − ∞, −1] ∪ [1, +∞[ Từ Định lí 2.4 chúng ta thu được kết quả tương tự với Định lí 2.2 trong [13] trong đó trường hợp tập nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu tuyến tính trong không gian Euclide được... thì S là hợp của hữu hạn các đa diện và liên thông đoạn 25 Khoá luận tốt nghiệp 2.3 Nguyễn Thị Vân Tính cực tiểu sắc yếu toàn cục Chúng ta nói rằng tập nghiệm Pareto S của (P ) có tính cực tiểu sắc yếu toàn cục, nếu tồn tại hằng số γ ∈ [0, +∞] sao cho d(x, S) ≤ γ d(f (x), f (S)) + d(x, D) , ∀x ∈ X, (2.8) ở đó d(u, Ω) := inf {||u − ω|| : ω ∈ Ω} là khoảng cách từ u tới Ω Bằng cách đưa ra một vài sự cải ... tồn nghiệm toán tối ưu vector Chương trình bày cấu trúc tính cực tiểu sắc yếu tập nghiệm Pareto tối ưu đa mục tiêu tuyến tính khúc Mục 2.1 trình bày toán tối ưu đa mục tiêu tuyến tính khúc Mục. .. nghiên cứu cấu trúc tập nghiệm Pareto toán tối ưu đa mục tiêu tuyến tính khúc hai trường hợp: Mục 2.2.1 khảo sát cấu trúc tập nghiệm Pareto toán tối ưu đa mục tiêu tuyến tính khúc tổng quát Mục 2.2.2... HÀ NỘI KHOA TOÁN **************** NGUYỄN THỊ VÂN CẤU TRÚC VÀ TÍNH CỰC TIỂU SẮC YẾU CỦA TẬP NGHIỆM PARETO TRONG TỐI ƯU ĐA MỤC TIÊU TUYẾN TÍNH TỪNG KHÚC KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: