TRƯỜNG ĐẠI HỌC s ư PH Ạ M HÀ NỘI 2 KHOA TOÁN N G U Y ỄN TH Ị VÂN CẤU TRÚC VÀ TÍNH cực TIẾU SAC YEU CỦA TẬP NGHIỆM PARETO TRONG T ố i ưu ĐA MỤC TIÊU TUYẾN TÍNH TỪNG KHÚC K H Ó A L U Ậ N T Ố T N G H IỆ P Đ Ạ I H Ọ C C h u y ê n n g à n h : G iả i tíc h H à N ộ i - 2015 TRƯỜNG ĐẠI HỌC s ư P H Ạ M HÀ NỘI 2 KHOA TOÁN N G U Y ỄN T H Ị VÂN CẤU TRÚC VÀ TÍNH cực TIỂU SAC YEU c ủ a TẬP NGHIỆM PARETO TRONG T ố i ưu ĐA MỤC TIÊU TUYẾN TÍNH TỪNG KHÚC K H Ó A L U Ậ N T Ố T N G H IỆ P Đ Ạ I H Ọ C C h u y ê n n g à n h : G iả i tíc h Người hướng dẫn khoa học T hS N guyễn V ăn T uyên H à N ộ i - 2015 LỜI CẢM ƠN Em xin chân th àn h cảĩii ƠĨ1 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 àn h cảrri Ơ11 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 rriọi điều kiện giúp đỡ erri hoàn th àn h khóa luận Iiày. Em xin chân th àn h cảrri ơn gia đình và bạn bè đã tạo rriọi điều kiện th u ân lợi cho em trong quá trình thực hiện khóa luận. E m xin chân thành cảm ơn. Hà Nội, tháng 05 năm 2015 Sinh vicn Nguyễn Thị Vân 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 t r ú c v à t í n h cự c tiể u sắc y ế u c ủ a t ậ p n g h iệ m P a r e t o t r o n g tố i ư u đ a m ụ c tiê u tu y ế n t í n h từ n g k h ú c " được hoàn th àn h không trù n g với b ất kỳ dề tài nào khác. Trong quá trìn h hoàn th àn h khóa luận, em đã thừ a kế những th àn h tựu của các Iihà khoa học với sự trâ n trọng và biết ƠĨ1 . Hà Nội, tháng 05 năm 2015 Sinh viên Nguyễn Thị Vân M ục lục M ở đầu 1 1 3 2 B à i t o á n t ố i ưu v e c t o r 1.1. M ộ t số k h á i Iiiệm cơ b ả n .................................................................................................................. 3 1.2. Q u a n hộ h a i ngôi và q u a n hộ t h ứ tự ........................................................................................ 8 1.3. Đ iểm h ữ u h i ệ u ..................................................................................................................................... 10 1.4. Sự tồ n tạ i c ủ a đ iểm h ữ u h i ệ u ....................................................................................................... 13 1.5. B à i to á n tối Ưu v e c to r ( V O P ) 14 ....................................................................................................... C ấ u t r ú c và t ín h cự c t i ể u sắ c y ế u c ủ a t ậ p n g h i ệ m P a r e t o t r o n g t ố i Ưu đ a m ụ c t iê u t u y ế n t ín h t ừ n g k h ú c 16 2.1. Đ ặ t b à i to á n 16 2.2. C ấ u tr ú c của t ậ p n g h iệ m P a r e t o 2.3. ........................................................................................................................................ ............................................................................................... 18 2.2.1. T rư ờ n g hợ p k h ô n g lồi ........................................................................................................ 18 2.2.2. T rư ờ n g hợ p l ồ i ....................................................................................................................... ‘23 T í n h cực tiểu sắc yếu to à n cục ................................................................................................... 26 K ế t lu ậ n 30 Tài liệu t h a m k h ả o 31 MỞ ĐẦU Tối ưu đa mục ticu tuyến tính được nghicn 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àrri 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 Iihấ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 Iià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ôny 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ạừ\ 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 ticu 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 th u ậ 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ứĩig m inh tiêu chuẩn dừĩig hữu hạn của m ột vài th u ật toán, như th u ậ t toán gradien và các th u ậ t toán chiếu gradien. Sau Iiày, khái Iiiệm quan trọng này được p h át triển và áp dụng trong nhiều lĩnh vực (xem [9, 10, 11]). Một khái Iiiệm liên quan gọi là tính cực tiểu sắc cũng dược một vài tác giả nghicn 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 rnộ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 ticu 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 P areto 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ả Iiày là m ột mở rộng Định lí ABB cho trường hợp tập nghiệm P areto 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 Ĩ1 Ó dể th iế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 àn h 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 m inh rằng tập nghiệm Paret.o 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 P areto của bài toán lồi đa mục tiêu tuyến tính từng khúc. 2 C hươ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à Đ ịn h không gian tuyến tính, M là tập các sốthực. n g h ĩa 1.1. Tập A c E được gọi là lồi, nếu: Vx'i,x ' 2 € A\ VA 6 E : 0 ^ A ^ 1 =7* Ax‘x ~\~ (1—A)x‘ọ £ 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 phang là các tậ p lồi. Hình cầu đơn vị trong không gian Banach là tập lồi... Đ ịn h n g h ĩa 1.2. Giả sử A c 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à co Ả. N h ậ n x é t 1.1. a) coA là m ột tập lồi. Đó là tập lồi bé n h ất chứa A\ b) A lồi khi và chỉ khi A = COA. Đ ịn h n g h ĩa 1.3. Tập c c E được gọi là nón có đỉnh tại 0 nếu: V.T e c , VA > 0 => Xx e c. c được gọi là nón có đỉnh tại Xo, nếu c — Xo là nón cóđỉnh tại 0. Khoá luận tốt nghiệp Nguyễn Thị Vân Đ ịn h n g h ĩa 1.4. Nón c có đỉnh tại 0 được gọi là nón lồi, liến c là m ột tập lồi, nghĩa là: V.T, y EC, VA, n > 0 => Xx + ịẲ,y e c. V í d ụ 1.2. Các tập sau đây trong R n: { f i , Ỉ 2 , - , ỉ » e R " : í . > 0 , í = l , . . . , n} (nón o rth an t không âm) (nón o rth an t dương) là các nón lồi có đỉnh tại 0. Đó là nón lồi quan trọng trong R n. Ngoài ra, nếu cho D c là một nón lồi, nón cực dương của D được xác định bởi: D* := {x* e R m :< x \ x > ^ 0,Vx € D ) . Cho a j ) € Mm,a ^ D b khi và chỉ khi a —b G D ; a ^ 0 khi và chỉ khi (lị ^ 0, i = 1 , ra.Kí hiệu M™ := {x e M™ : .T ^ 0} và cho g : X —> R r". Hàrri g được gọilà D- giống lồi trên s c X khi và chỉ khi : Vx’i,x‘9 G s, Vtt £ [0,1], 6 5*. sao cho (1 - a )# (x i) + ac/(x2) - g(x) e D. Điều này đượcbiế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. Đ ịn h n g h ĩa 1.5. Tập A c R n được gọi là tập affine, nếu (1 — X^x -\- \ y Á ị \ ị x , y £ A, VA (E M) 4 Khoá luận tốt nghiệp Nguyễn Thị Vân Đ ịn h n g h ĩa 1.6. Tương giao của tấ t cả các tập affine chứa tập A c R n được gọi là bao affine của Ả và kí hiệu là a f f A . Đ ịn h n g h ĩa 1.7. P hần trong tương đối của tập A c M"' là phần trong của A trong a f f A (bao affine); kí hiệu là riA Các điểm thuộc riẨ được gọi là điểm trong tương đối của tập A. N h ậ n x é t 1.2. int A := {x £ Mn : > 0, X + e№ c Ả ) , r i A := {x e 0 , f f A : 36 > 0, (x + eB) n a f f A c Ả ) , trong đó B là hình cầu đơn vị đóng trong R n. 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 n ( - C ) (phần tuyến tính của C); clc (bao đóng của ơ ); rriột tập con A c E, A c là phần bù của A trong E , nghĩa là A c = E \ A . Đ ịn h n g h ĩa 1.8. Chúng ta nói I1 ÓĨ1 c là: (a) Nhọn Iiếu l(C) = 0; (b) Nón sắc nếu bao đóng của Ĩ1 Ó 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ở th u ần Iihất; (đ) Nón đúng Iiếu (clC) + C \ l ( C ) c c , hoặc tương đương clC + C \ l ( C ) C C\ l ( C) . V í d ụ 1.3. theo định nghĩa 1.8 1. Cho Mn là không gian Euclid n-chiều. Khi đó, nón orthant không ârri Wị gồm tấ t cả các vectơr của W l với t.oạ độ 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 t.oạ độ đầ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 n h ất là nón đúng, có giá chặt nhưng không là IIÓII nhọn. 2. Cho íì là không gian vectơr gồm tấ t cả dãy X = { x n} số thực. Cho c = {x e ũ : xn ^ 0,Vn}, thì c là nón nhọn, lồi. Tuy nhicn, 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 trcn không gian này. 3. Nón thứ tự từ điển: Cho lp = 51 ^ p < °°- € íỉ : ||a;|| = Kí hiệu c là hợp của 0 và các dãy rrià 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Ò11 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 ệ n h đ ề 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 ĨĨIỞ và nửa không gian đóng trong E. Chứng minh, (a) Hiển nhicn, (b) Nếu C \ l ( C ) mở thì i n t c Ỷ 0 và i n t c = C\ l ( C) . Do đó, ta có clC + C \ l ( C ) = (cl C) + i n t e C c , hay c là nón đúng. 6 Khoá luận tốt nghiệp Nguyễn Thị Vân (c) Giả sử С = {0} u (n { H \ : Л G Л}), ở dây H\ là nửa không gian dóng hoặc II1 Ở trong E. Nếu tấ t cả H\ là đóng thì điều này tươĩig đương với С là dóng. Do đó, ta có thể giả sử ít Iihất Iiiột nửa không gian là 1 I1 Ở thì 1(C) — {0} và b £ C \ l ( C ) khi và chỉ khi b G Hx, v \ £ Л. Hơn thế nữa, ta thấy a £ clC khi và chỉ khi a G c lH \,V A G A ncn cl Hx + H X G H\. Vậy H\ là mở hoặc đóng thì a + b e ơ , a £ с , h G C \ l ( C) . Mệnh đề được chứng minh. □ Đ ịn h n g h ĩa 1.9. Cho m ột nón с trong không gian E. Một tập в ç E sinh ra nón С và viết с — cone(B) nếu С — {tb : b G t ^ 0} . Hơn nữa, nếu В không chứa 0 và với mỗi с G с , с Ỷ 0) tồn tại duy nhất b E В, t > 0 sao cho с = tb thì в được gọi là cơ sỏ của с . Khi в là rnột tập hữu hạn, cone(conv(B)) được gọi là m ột nón đa diện. N h ậ 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 nhicn nó không đúng trong không gian vô hạn chiều. M ệ n h đ ề 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 с là đóng. Cho dãy {ca } là m ột lưới từ С hội tụ tới c. Do В là m ột cơ sở ncn tồn tại m ột lưới {ba } từ в và một lưới { t a } các số dương m à ca = taba . Dễ thấy t a là bị chặn. T h ật vậy, giả sử ngược lại l i mt a = (X). Vì E là không gian Hausdorff liên lưới |/ ; tt = 7^1 hội tụ tới 0. Hơn thế nữa в là đóng, dẫn tới m âu thuẫn: 0 = limba G в . Bằng cách này, ta có thề giả sử { t a } hội tụ tới điểrn t 0 ^ 0. Nếu t 0 = 0 thì từ tính bị chặn của £>, l i mt aba = 0. Do đó с = 0 và hiển nhiên с G с . Nếu t 0 > 0, ta có thể giả sử ta > 6, Va, 6 > 0. T ừ bn = 7*'ữ ^ hôi tu tới J*0 và 7 Khoá luận tốt nghiệp hơn nữa B đóng liên vector Nguyễn Thị Vân *0 G B. Do đó c G c và c đóng nêĩi c nhon 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ỳ ý, rriột quan hệ hai ngôi trong E được định nghĩa bởi rnột tập coil B của tập hợp tích E X E. Điều này có nghĩa là m ột phần tử X € E có quan hệ với y (E E liến 0 ,2 /) e B. Đ ịn h n g h ĩa 1.10. Cho B là m ột quan hệ hai ngôi trong E. Ta nói quan hệ này là: xạ Iiếu ( x, x) 6 B với mọi X G E ; (a) P hản (b) Đối xứng nếu(.T, y) £ B suy ra (?/, x) G B với mỗi .T, y £ E; (c) Bắc cầu nếu (x, y) G B , ( y , z) G B suy ra (x, z) G B với X, y, z 6 B; (d) Đầy đủ hoặc licn thông nếu {x, y) G B hoặc (y,x) G B với mỗi x , y G E , x Ỷ ỉ/; (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) 6 B với mọi X, y, z G E , t > 0; (f) Đóng trong trường hợp E là không gian vcctor tôpô, nếu nó là đóng như m ột tập COĨ1 của không gian tích E X E. Để làm rõ định nghĩa này chúng ta xem xét m ột sốví dụ cổ điển san. Cho E là rriột cộng đồng dân CƯ của m ột th àn h 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) G Bị nếu X, y là những người tuổi cao hoặc có tuổi. 2. (x, y ) (E B 2 nếu X, y là hai giới tính khác nhau. 3. (x, y) G B 3 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 Bị là phản xạ, bắc cầu, không đối xứng, đầy đủ. B 2 không phản xạ, đối xứng, không bắc cầu, không đầy đủ. E>3 là phản xạ, khôĩig bắc cầu, đối xứng, không đầy đủ. Đ ịn h n g h ĩa 1.11. Q uan hệ hai ngôi là m ột quan hệ th ứ tự nếu nó là phản xạ, bắc cầu. T h ậ t vậy, nếu B là m ột quan hệ th ứ tự m à là tuyến tính trong m ột khôĩig gian vector thì tập c = {x G E : (x-,0) 6 B } là rriột nón lồi. Hơn nữa, nếu B là không đối xứng thì c lại, là nhọn. Ngược mỗi nón lồi trong E cho m ột quan hệ hai ngôi B c = {(.T, y) e E X E : X - y e 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 rriột vài th ứ tự sinh ra bởi các nón lồi. Đôi khi chúng ta viết: X y th ay cho X — y E 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 y yà không phải là y hay là X (E y + C \ l ( C) . Khi ỉ n t c X, 0, x ^$>c y nghĩa là X >K y với K = {0} u i n t c . V í d ụ 1.4. 1. Cho R n và tập c = MỊ. 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 = (Xị , {yu-: Un) e IRn: 9 x n) , y = Khoá luận tốt nghiệp Nguyễn Thị Vân X ^ c y khi và chỉ khi Xi ^ ịji với i = 1,..., II; X >c y khi và chỉ khi Xi ^ Ui 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 > ĩji với mọi i = 1 ,..., II. 2. Trong R 2. Nếu c = (M ^o) thì B c 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 y khi và chỉ khi hai th àn h phần của các vector trùng nhau. T hứ 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 . Đ ịn h n g h ĩa 1.12. Cho A là m ột tập COĨ1 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 ^ V// £ 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ổrri hữu hiộu của A kí hiộu là E(A\C)\ (c) X G A là điểm hữu hiệu thực sự (toàn cục) của A tương ứng với c Iiếu tồn tại rriột nón lồi K Ỷ E V(3i i n t K D C \ l ( C ) sao cho X £ E( A\ K) ; Tập các điổrri hữu hiộu toàn cục của A được kí hiộu là Pr E( A\ C) ; ((1) Giả sử i n t c 7^ 0, X (E -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 G E ( A I {0} u i n t c ); 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 = { ( ^ ỉ/) e K2 : X2 + ỉ/2 < l,ỉ/ < 0} u { ( x, y) : X > 0,0 > y > - 1 } ; B = AU { ( - 2, - 2)}. Nếu cho c = M ị, ta có: I E( B) = Pr E( B) = E( B) = WE ( B ) = { ( - 2 , -2 ) } ; I E( A) = 0, P rE (A ) = { (x , ỳ) G M2 : X2 + ý 1 = E(A) = PrE( A) u {(0, -1)} u {(-1,0)}, WE(A) = E(A) X, 0 > y } , 1, 0 > u {(x,y) : y = - l , x }. > 0 Bây giờ cho c — (M1, 0) c R 2. Ta có : I E( B) = 0, P r E ( B ) = E( B) = W E ( B ) = B, I E ( A ) = 0, P r E ( 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 ệ n h đ ề 1.3. Cho A c E thì : (a) X € I E( Á) khi và chỉ khỉ X ^ A và A C x + C; (b) X 6 E( Á) khi và chỉ khi A n (x — C) c X+ l(C) hoặc tương đương: Ẹ y G A sao cho X > y. Đặc biệt khi c là nhọn, X GE( Á) A n (x —C) — khi và chỉ khi {a;}; (c) Khi c 7 ^ E , x G W E ( A ) khi và chỉ khi A c \ ( x — i n t c ) = 0 hoặc tương đương với Ịầy (E Ả sao cho X y. M ệ n h đ ề 1.4. Cho tẠp khác rỗng A c E có: 11 Khoá luận tốt nghiệp Nguyễn Thị Vân P r E ( A ) c E( A) c W E ( A ) . Hơn nữa, nếu I E( A) Ỷ 0 thì I E( A) — E( A) và nó là tập một điểm khi c là nhọn. Chứng minh. Lấy X (E Pr E ( A ) . Nếu X ị E( Á) có y ^ A v ầ x — y € C\ l { C ) . Lâý nón lồi K, K Ỷ E với i n t K c C \/(C ) và X e £ ( Ẩ |iO - Thì X — y £ i n t K c K \ l ( K ) . Điều này rnâu thuẫn với a: € ^(AỊìỷT) suy ra PrE( A) c £(Ấ). Lấy X G E(A). Nếu X Ệ W E ( A ) theo Mộnh đề 1.3 tồn tại y € A sao cho .X—y E i n t c . Do c Ỷ E, i n t c c C \ l ( C ) liên ta có X—7/ £ C \/(C ).Đ iều này m âu th u ẫn với X e E(A). Vậy i£(i4) c W E ( A ) . Rõ ràng I E ( Á ) c E( A) . Nếu I E ( Á ) Ỷ 05 ch° thì X G E(Á). Cho y 6 i£(-A) th ì ỉ/ > X vì vậy X ^ ỉ/. Lấy m ột điểm bất kì 2 € cổ z ^ X vì X G I E( A) suy ra z ^ y \k y E I E( A) . Do đó I E( A) = E(A). Ngoài ra, nếu c là nhọn X ^ ỉ/ và y > X chỉ có thể xảy ra trường hợp X — y. Vậy I E( A) là tập m ột điểm. □ Đ ịn h n g h ĩa 1.13. Cho X £ E. Tập Ẩ n ( x - C ) được gọi là rriột nhát cắt A tại X và kí hiệu Ax . M ệ n h đ ề 1.5. Cho X e E với Ax 7^ 0. Ta cỏ : (a) I E { A X) c /£ ( A ) nếu I E( A) Ỷ 0; (b) E ( A X) c ^ (A ) (tương tự cho W E ) . Chứng minh, (a) Cho J/ G I E ( A X) và 2 € I E cố Ax c y + c và Ẩ c 2 + c . Thì 2: £ i4a; vầ z — y € l ( C ) suy ra A C z -|-C = |/- |-2 — = Do đó y £ I E( A) . 12 — £/ H- C*. Khoá luận tốt nghiệp Nguyễn Thị Vân (b) Giả sử y 6 E ( A X). Theo Mệnh đề 1.4 có Ax n (y — C) c y + l(C) suy ra y —c A c X —c nên n y - c c Ả n (y - C) n (x - C) c Ax n (y - C) c y + l(C). Do đó y £ E(A). Chứng m inh tương tự cho w E . □ N h ậ n x é t 1.4. Q uan hệ P r E ( A x) c P r E ( 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 Đ ịn h n g h ĩa 1.14. Cho lưới { x a : a G 1} từ E được gọi là lưới giảm (tương ứng với C) nếu xa > c với a, Ị3 € I; Ị3 > a. Đ ịn h n g h ĩa 1.15. Cho Ả c E đitợc gọi là C- đầy đủ (tương ứng C- đầy đủ m ạnh) nếu nó không có phủ dạng {(.7;0: — CỈCỴ : a G 1} (tương ứng {(xtt — C Ỵ : a £ /} ) với {.Ttt} là một lưới giảm trong A. Đ ịn h 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) Ỷ 0 khi' và chỉ khỉ A có một nhát cắt C- đầy đủ và khác rỗng. Chứng minh. Nếu E( A\ C) Ỷ 0 thì mọi điểm của tập này cho ta m ột nhát cắt C- dầ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 n h át cắt C- đầy đủ của A. Theo Mệnh đề 1.5 thì ta chỉ cần chứng m inh E ( A X\C) Ỷ 0- Xét tập p bao gồm tấ t cả các lưới giảm trong A. Vì A Ỷ 0 suy ra p / 0. Với a, b G p ta viết a >- b nếu b c tí. Rõ ràng (>-) là quan hộ th ứ tự trong p , và một xích bất kì trong p đều có cận trcn. T h ậ 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 C0Ĩ1 hữu hạn B của A Nguyễn Thị Vân được sắp thứ tự bởi bao hàm và đặt aB = u {aa; a € B} . Và ữ0 = u ! jB G 5} . Thì a0 là m ột phần tử của p và a0 y aa với mọi a 6 A Iighĩa là a0 là m ột cậĩi trên của xích Iiày. Áp dụng bổ đề Zorn, tồn tại phần tử 1ỚĨ1 Iihất của p , kí hiệu là a* = {xữ : a G 1} G p . Bây giờ, giả sử ngược lại E ( A X\C) = 0. Chúng ta sẽ chứng minh {(xa — cl CỴ : a £ 1} phủ Ax. Ta chỉ ra với mỗi y € Ax có a G / m à (xa — cl CỴ chứa y. Giả sử phản chứng y G x a —c/C ,V a £ I. Vì E ( A X\C) = 0 có z € A x với y > c z. Do tính đúng của c ncn X — a > c z , (a G /). Them 2: 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à Iĩiột tập COĨ1 khác rỗng của m ột không gian tôpô và m ột ánh xạ đa trị từ F là 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 : min F(x) với ràng buộc X € X . Điểm X E X được gọi là tối ưu (cực ticu hoặc hữu hiệu) của VOP nếu F ( x ) n E { F ( X ) \ C ) ^ Q . Ỡ đâ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ế I E, P r E , W E cho E ( F ( X ) \ C ) chúng ta có các khái niệm I S ( X ; F), P r S ( X ; F) và w S ( X ; F ) . Q uan 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ìn h bày trong mệnh đề sau: M ệ n h đ ề 1.6. Cho VOP, chúng ta có các bao hàm thức sau: Pr S( X; F) c S ( X ; F ) c W S ( X ; F ) . Hơn nữa, nếu I S { X ; F) Ỷ 0 thì I S { X ; F ) = 5 (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) + C1 là C- đầy đủ, đóng với mọi X GX 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ó rriột lưới giảm {aa : a E 1} của F ( X ) sao cho {(aa —CẤ(C))C : a £ 1} là phủ của F ( X ) . Lấy x a e X với aa G F ( x a). Không m ất tính tổng quát, giả sử = X € X . Khi đó, với rriỗi lân cận V của F( x) trong E có rriột chỉ số Ị3 £ I sao cho aa £ V + c , Va ^ Ị3. Do {aa } là dãy giảm, nên 0,a £ ữỹ -\- c Vố ^ a. Từ đây suy ra: aa G d ( F ( x ) + C) — F(x) + c , Va. Dẫn tới m âu thuẫn: F(x) + c không thể là C- đầy đủ. 15 □ C hương 2 C ấu trúc và tín h cực tiểu sắc yếu của tập n gh iệm P a reto tron g tố i ưu đa m ục tiêu tu y ến tín h từ n g khúc 2.1. Đặt bài toán Cho ánh xạ / : 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], / đượ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ọ { P i , Pk}i { T i , T f c } và { & ! , 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 = uĩ-1 Pi và f(x) = fiịx) := Ti(x) + bi Vi e Pj, Vi e { 1, k}. (2.1) Đe có (2.1), ta phải có ỉ iix ) = f j i x ) Vx G Pịíl Pj, Vz, j G { 1 , Ả;}. Cho m ột họ hữu hạn các hàm tuyến tính licn 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àrri tuyến tín h 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 licn tục từng khúc và bài toán tối ưu đa mục ticu licn quan được nghicn cứu theo các quan điổm khác nhau. Ví dụ, Gowda và Szajdcr [2] nghicn cứu tính chất giả-Lipschitz của / -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 ở trcn thì yếu hơn trong [2], trong đó giả thiết rằng với rriọi cặp ( i , j ) , Pị n Pj bằng rỗng hoặc m ột m ặt chung của Pị và P j . Đố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 Paret.o được khảo sát trong [3,4]. Cho D c X là m ột đa diện, cho c c Y là m ột I1 ÓĨ1 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 ticu tuyến tính từng khúc dưới đây: (P) mi nf ( x ) sao cho X £ D. 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 e D, f (u) - f { x ) e c \{ 0 ỵ } . 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 6 D với f ( u ) — f ( x ) G i n t c , ở dó intc kí hiệu phần trong của c . Tập tấ t cả các nghiệm P areto (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ự., s w ). Việc nghiên cứu các tính chất dặc trưng của tập nghiệm Iiày rấ t hữu ích trong việc th iết kế các th u ậ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 Iiếu với mọi x 1ì x 2 6 D và t e]0,1[, thì (1 - ^ / ( x 1) + t f ( x 2) - /(( 1 - t ) x l + t x 2) e c . Trong trường hợp Y = Mw và c= MỊ (nón orthant không âm trong Rn), / = (/ij •••>/«) được gọi là một, hàm lồi trên D khi đó nó là một ơ -lồi trên D. Vì vậy, tính lồi của / trên D thì tương đirơng với tính lồi của các fi trên D. Nếu / là m ột ơ -lồi trcn 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 . T rư ờ n g h ợ p k h ô n g 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. Đ ịn h 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 — Ut=i Mị, ở đó Mị fi(Pị n D ) với ỉ — 1 Chúng ta kí hiộu tập nghiộm P arcto của Mị là E(Mị\C). Từ định nghĩa, ta có s = { x e D : f(x) e E(M\C)} = f - \ E { M \ C )) n 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ả th iết / 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 dóng. K h ẳ n g đ ịn h 1. E ( M \ C ) ỉ,à hợp của hữu hạn các đa diện nửa đỏng. Chú ý rằng E( M\ C) c E{ MX\C) u E ( M2\C) u ... u E ( Mk\C). (2.3) Với ỉ E { 1 , Ả;} b ất kì, Mị = {Tị(x) + bị : X G Pị n 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 c Y là m ột nón lồi đa diện, Định lí ABB khẳng định rằng E(MịịC) là hợp của hữu hạn các đa diện (nó là các m ặt của Mị). Giả sử rằng mi E(M, \ C) = { j Q , . r, i = l , . . . , k , (2.4) r=1 ở đó rriỗ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 th u ậ 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 P areto E( Mị \ C) . Từ (2.4) ta có, mi E ( M 1\C) = ỳ } Q Ur. ( 2 .5 ) r = l Rõ ràng, m ột điểm V G Qi,r, với r Ễ {1, ...,77ii}, trong E ( M \ C ) khi và chỉ khi V Ệ Mị + (C \ {0y}), V ie { 2 ,.., Ả;}. Lấy V € Qi.r bất. kì. Cho (a) 1 (2.6) = 2. Nếu V G M 2 + c thì có hai khả năng: V E M2 + (C * \{ 0y })5 (^) V € M2. Trong trường hợp (a) từ ticu chuẩn (2.6), V không thổ thuộc E ( M \ C ) . Do đó chúng ta có thổ loại trừ V từ Qi.r- Trong trường hợp (b) có hai trường hợp con: (&0 v e E ( M 2\C), (b2) 19 V ị E ( M 2\C). Khoá luận tốt nghiệp Nguyễn Thị Vân Trường hợp (bí) sẽ được phân tích ở bước sau khi chúng ta nói về tập E ( M 2\C). Trong trường hợp (b2) chúng ta có thể bỏ qua V Iiày vì từ (2.3), V ị E ( M 2\C). Vì thế Iiếu trường hợp (b2) xảy ra thì chúng ta có thể loại trừ V từ Qi.r- Bởi theo Định lí 19.1 trong [16], M 2 + c là m ột tập lồi đa diện. Q uan sát rằng, sau khi loại bỏ từ Qi r tấ t cả các điểm đều thuộc M 2 + c , chúng ta th u được hợp của hữu hạn các đa diện nửa đóng. T h ậ t vậy, Iiếu M 2 + c = n t i n „ ở đó l2 là rriột số nguycn và mỗi Yl ■là một nửa không gian đóng, thì h h Qu- ■■= Qí.r \[M2 + C} = ( j {Qi.r \ n . ) = Ú \.Qí- n «=1 Khi đó, Qi,r n (Y \ n ,) (s — 1 trìn h làm cho 1 \ n .) ] • S=1 , l2) là các đa diộn nửa đóng. Lặp lại quá — 2 với i — 3 chúng ta thu được tập Q {ỉ l ■■= Q ĩ{ l \ \ M , + 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 th u được tập Q u := \ W k + C]. Chú ý rằng Q\l;' được chứa trong E ( M \ C ) và có thể được biểu (liễ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 u r= i QĨ,r c E( M\ C) . Bước 2. Chúng ta lặp lại quá trình làm cho E( Mị \ C) với tập nghiộrn P arcto E ( M 2\C), thay i — 1 bằng 1 = 2 trong Bước 1. Chúng ta đặt Q{ỉ ì ■- (Q2.rxm + c\) u Q2.r n EiM.ịC)) khi Qi,r n E(M i \C) Ỷ 0- Do vậy, chúng ta thu được tập (r = 1 , mì) sao cho mỗi tập Iià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ó Ur=i QỈr ^ E( M\ C) . 20 Khoá luận tốt nghiệp Nguyễn Thị Vân Bước j (j G {3, k — 1}). Thay ỉ = 1 ( tương tự., ỉ = 2, bằng %= 2 ( tương tự., ỉ = 3 « i = j —1) = j ) trong Bước 1. Chúng ta đặt Q i l ■■= ( Q i - r \ Wi + C ] ) u Qj.r n E ( Mi ị c ) ) khi Qj r n E(Mị\C) Ỷ 0 với ỉ £ {1, •••, j — !}• Do vậy, chúng ta được bao hàm U ” =1 c E( M\ C ) , ở đó mỗi tậ p ọ ị ky 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 ỉ = 2 (tương tự., ỉ = 3, ỉ = k ) trong Bước 1. Chúng ta đặt Q t l ■■= {Qk,,\[M, + C]) u [Qk,. n E ( M , \ C ) l khi Qk.r n E(Mị\C) ^ 0 với i G { 1 , k — 1}. Do vậy, chúng ta thu được bao hàm ur=i Q Ĩ - ^ ^ E ( M\ C ) , ở đó rriỗi tập Q^., ^ là hợp của hữu hạn các đa diện nửa đóng. Sau khi hoàn th àn h k bước ở trôn, chúng ta thu được bao hàm k - 1 , VIi N u í u c ) i= 1 V=1 ' 1 , m k X u íŨ Q t^ c E iM ịC ) ^ r=l ' 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 liên (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. s là ìiỢp của hữu hạn các đa diện nửa đóng. (2.2) và (2.7) chúng ta có thổ suy ra rằng s là hợp của hữu hạn K h ắ n g đ ịn h 2. Từ 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ở n := { y e Y : ( y \ y ) < p } 21 (y* G Y \ p e R) Khoá luận tốt nghiệp Nguyễn Thị Vân và với Vz G { 1 , Ả;}, công thức f ịr í { n ) n P i = { x e P i : M x ) € Ũ } = {x e Pị : ( y \ Tị(x) + bị) < P} = {x e Pị : {T*(ĩ / ) , x) < (3 - {ĩ j \bi}} chi ra rằng / _1(fì) n Pị là m ột đa diện nửa đóng trong X . Mệnh đề được chứng rriinh. □ Lược đồ chứng m inh trên vẫn đúng cho Định lí 2.4 trong [1]. Ví dụ sau m inh họa kết quả thu được trong Định lí 2.1. V í d ụ 2.1. Cho X = R , Y = R 2,D = {x : 0 < í I j \ (x) : = (2x, 1— 2x) f ( x) = ị 1h ( x ) - z ,0 ) < 1}, c= M2+ và _ 6 P\ := ] — oo, —1] " 1 nếu X € Pj := [^, +oo[. nếu 3 ■= X X Ta có Mi := /i(P i n £>) = /i ^ 0, ^ ^ = com ;{(0,1), (1,0)}, trong đó conf là phép toán lấy bao lồi. Vì vậy, E i M P , n D ) |E 2+ ) = com ;{(0,1), (1, 0)}. Tương tự, M2 := /2(^2 n D) = /2 2’ = c o m ;ị(1,0), Ị 0 va E ( f 2(P2 n D ) \ R 2+ ) Đ ặt M := Mị u M 2 = f ( D ), ta được E(M|R*) = :0 < í < u u 22 0, U{1}, Khoá luận tốt nghiệp Nguyễn Thị Vân và £ u, ( M | R 2+ ) Chúng ta thấy rằng cả tập E ( M \ R \ ) và s đều không liên thông và không đóng. Tuy nhiên, mỗi tập là hợp của hai đa diện nửa đóng. 2 .2 .2 . T rư ờ n g h ợ p lồi Kết quả trong Định lí 2.1 có thể dược cải tiến Iiếu (p ) là m ột bài toán lồi. Đ ịn h lý 2.2. Nếu f là một hàm C-ỉồi trên D, thì tập nghiệm Pareto s của (p ) là ì i Ợp của hữu hạn các đa diện và liên thông đoạn. Chứng minh. Một lần nữa chúng ta sử dụng cách tiếp cận trong không gian ảnh, chúng ta sẽ phân tích trên m ột họ các tập con của không gian ảnh Y . Giả sử Mị (i = 1 , k) và M tương tự như trong chứng m inh Định lí 2.1. Đầu tiên chúng ta chỉ ra rằng E ( M \ C ) là hợp của hữu hạn các đa diện nửa đóng và liên thông đoạn. Rõ ràng, E ( M \ C ) = E ( M + C\C). Từ Định lí ABB, ta chỉ cần chỉ ra rằng M + c là m ột đa diện. Từ giả th iết / là m ột hàm C -lồi trên D thì M + c = f ( D) + c là rriột tập lồi. Từ c là m ột nón lồi đa diện và rriỗi Mị = fi(Pị n D ) là một đa diện, theo Định lí 19.1 trong [16], chúng ta có biểu diễn và Mị = : XlP) > 0 23 Ể = 1> /49) > 0 Vq Khoá luận tốt nghiệp với vr (r = 1, ố’), Nguyễn Thị Vân (Ii,p (p = 1, và Vị_q (q = 1, Ọị) dược lựa chọn m ột cách phù hợp. Khi dó, do tính lồi của M + c , ta có M+ c =( u M 0 Vz Vp, ^ q= 1 r = l = 1, ịi^ > 0 Vz Vợ, /v,r > 0 V r ị ^ t = i P=1 ^ = cơ |( ụ I = M + c. Điều Iiày có nghĩa là bao hàm trong biểu thức cuối phải là m ột đẳng thức. Ap dụng Định lí 19.1 trong [16] một lần nữa, chúng ta kết luận rằng M + C là m ột tập lồi đa diện. T ừ E ( M \ C ) có thể được biểu diễn như hợp của hữu hạn các đa diện, do (2.2) liên s có tính chất tương tự. Để chứng minh rằng s liên thông đoạn chúng ta cố định hai điểm ỈL, ũ £ s và đ ặt V = f ( u ) , v E ( M \ C ) liên thông đoạn, tồn tại = f(ũ). Vì £ Y sao cho V1 = v , v l = V và đoạn thẳng [v7\ vr+l] thuộc E ( M \ C ) với r = 1 , — 1. Các bao hàm thức k Ịu1, -«2] c E(M\C) c [ J m , i= l kéo theo tồn tại v l-v (p = 1, {1, + 1) trong Ị?;1, V2] và các chỉ số ?'i, ỉVl c sao cho ?;1-1 = v l ^v l-ĩ>i+l = v 2 ? và Ịv l . p j í ; l . p + l j Với mỗi p G {1, c y p e | 1 ; chúng ta có thể chọn u l-p G Pị thoả m ãn fi (u 1-p) = yi.p+ 1 rnộj. (Ịịểni ũl'p £ Pip+1 thoả m ãn fi ị (ũ1'1*) = v1-p+1. Khi đó (1 — t)u + t ulA G Pịl và ((1 — t)u + íii1,1) = (1 —t ) v ỈA + t v 1'2 G E( M\ C ) , Khoá luận tốt nghiệp Nguyễn Thị Vân với mỗi t € [0,1]. Điều đó kéo theo [iiij iii1,1] c s . Tương tự, P ' - ' V " * 1] e S, V p e { l , . . . ip i}. Với p € {1,b ất kì, bởi giả thiết / là m ột hàm C-lồi, v 1-”* 1 = (1 chúng ta có - f ( { l - tiu1-” + tĩi1-p) - + tf(ũìp) - /((1 - t)uL” + tũ1*) € c. Từ v l'v+l e E ( M \ C ), suy ra /( ( 1 - t )u1-p + t ũ1*) = v l -v+l Ví € [0,1]. Do đó [ul'p,ĩíl'p\ c s . Chúng ta phải chỉ ra rằng tồn tại m ột đường cong licn tục trcn s m à gồm m ột số hữu hạn các đoạn thẳng hợp nối u và u l'v\ ở đó f ( u ) — V — V1 và ) = V2. Lí luận tương tự chúng ta có thổ tìm một đường cong licn tục trcn s m à gồm một số hữu hạn các đoạn thẳng nối u l 'Pl và U2'P2 G s thoả mãn f ( u 2'p2) — V3. Chúng ta tiếp tục quá trình tới khi thu được m ột điểm ul~l 'Vl~x £ s thoả m ãn Ị{ĩi}~l'Vl- 1) = V1 = V. T ất nhiên ở bước cuối cùng chúng ta có thể chọn ul~Lpi- 1 = ũ. Chúng ta vừa chỉ ra rằng u có thể nối với ũ bởi m ột đường cong liên tục gồm một. số hữu hạn các đoạn thẳng trong s . Định lý được chứng minh. □ Dỗ thấy rằng nếu f : X —> Y là m ột toán tử tuyến tính licn tục thì với m ột nón lồi cc Y b ất kỳ, / là hàm C-lồi trcn X . Do đó từ Định lí 2.1 chúng ta có thổ suy ra cấu trúc của tập nghiộrn Pareto trong tối ưu vector tuyến tín h trong không gian định chuẩn vô hạn chiều. Đ ịn h lý 2.3. (Định lý A B B cho trường hợp không gian vô hạn chiều) Nếu f : X —> Y là một toán tử tuyến tính liên tục tỉâ s là ìiự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ố 7 E [0 , +00] sao cho d( x, S) < 7 [ d( f ( x) ì f ( S) ) + d( x, D ) ] , \fx G X, ở đó fi(u, Q) ( 2 .8 ) inf {\\u — cưII : cư £ Í2} là khoảng cách từ u tới Í2. Bằng cách đưa ra m ột vài sự cải bicn phù hợp trong sơ đồ chứng minh của Zheng và Yang [14], Yang và Yen [19] nhận được kết quả sau. Đ ịn h lý 2.4. Nếu f ì,à 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 tính từng khúc thì tồn tại aỊ, ip:X —»■R ỉ,à một hàm, lồi và tuyến £ X * và Oil, •••, r t ị ẽ l sao ip(x) = m ax \(a*,x) + aj] cho V;X £ X. 1) c f { D) + C và ốr (x) > = ( ỉ / * = m in 2/6/(D) +C (y% y) = )j < 7 [IIf(x) -w|| +d(x,D)}, điều đó kéo theo d( x, S) < 7 [ d ( f ( x) , f ( S) ) + d ( x, D) + e ] . Từ £ > 0 có thể chọn nhỏ tuỳ ý, điều này suy ra (2.8). Định lý được chứng □ minh. Giả th iết rằng / 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 = E , c = R + , D — R và 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. Đ ịn h 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 Định lí này của (p ) có tính cực tiểu sắc yếu toàn cục. II1Ô tả tính cực tiểu sắc yếu toàn cục của tập nghiệm P areto 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ìn h bày rriột số khái niệrri 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ìn h 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ìn h bày cấu trúc và tính cực tiễu sắc yếu của tập nghiệm P areto 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 da 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 P areto 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 P areto 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 nghicn cứu cấu trúc tập nghiộm Parcto của lớp bài toán tối ưu đa mục ticii 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 P arcto 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 th am khảo [1] Zheng, X.Y., Yang, X.Q.: The structure of weak Pareto solution sets in piecewise linear m ultiobjective otirnization in norrned spaces. Sci. China, Ser. A, M ath. 51, 1243-1256 (2008). [2] Gowda, M.S., Szajdcr, R.: On the psciulo-Lipschitzian behavior of the inverse of a piecewise affine function. In: C om plem entarity and Vari­ ational Problem s, Baltim ore, 1995, pp. 117-131. SIAM, Philadelphia (1997). [3] Aneja, Y.P., Nair, K .P.K .:B icriteria tran sp o rtatio n problem. Manag. Sci. 25, 73-78 (1979/1980). [4] Cai, X.Q., Teo, K.L., Yang, X.Q., Zhou, X.Y.: Portfolio otirnization under a m inim ax rule. Manag. Sci. 46, 957-972 (2000). [5] Giannessi, F.: Theorem of the alternative and optim ality conditions. J. Optirri. Theory Appl. 42, 331-365 (1984). [6] Arrow, K .J., B arankin, E.W ., Blackwell, D.: Admissible points of con­ vex sets. In: C ontributions to the Theoty of Garries, vol. 2. Annals of M athem atics Studies, vol. 28, pp. 87-91. Princeton University Presss, Princeton (1953). [7] Luc, D.T.: Theory of Vector O ptim ization. Springer, Berlin, (1989). Khoá luận tốt nghiệp Nguyễn Thị Vân [8] Burke, J.V ., Ferris, M.C.: Weak sharp m inim a in m athem atical pro­ gram ming. SIAM J. Control Optirri. 31, 1340-1359 (1993). [9] Studniarski, M., ward, D.E.: Weak sharp minima: characterizations and sufficient conditions. SIAM J. Control Optirri. 38, 219-236 (1999). [10] Burke, J.V ., Deng, S.: Weak sharp m inim a revisited, P art I: basic theory. Control Cybern. 31, 439-469 (2002). [11] Burke, J.V ., Deng, S.: Weak sharp m inim a revisited, P art II: appli­ cation to linear regularity and error bounds. M ath. Program ., Ser. B 104, 235-261 (2005). [12] Zheng, X. Y., Yang, X.M., Teo, K.L.: Sharp m inim a for m ultiobjective optim ization in Banach spaces. Set-Valued Anal. 14, 327-345 (2006). [13] Deng, S., Yang, X.Q.: Weak Sharp m inim a in m ulticriteria linear pro­ gram ming. SIAM J. Optirri. 15, 456-460 (2004). [14] Zheng, X. Y., Yang, X.Q.: Weak sharp m inim a for piecewise linear rrrultiobjective optim ization in norrrred spaces.Nonlinear A nal.68,37713779 (2008). [15] Giarrnessi, F.: Theorems of the alternative for rrrultifunctiorrs w ith ap­ plications to optim ization: general results. J. Optirrr. 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.: V ariational Analysis. Springer, New York (1998). [18] Zalinescu, C.: Sharp estim ates for Hoffm an’s constant for systems of linear inequalities and equalities. SIAM J. Optirrr. 14, 517-533 (2003). 32 [...]... cứu cấu trúc của tập nghiệm P areto 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 P areto 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 nghicn cứu cấu trúc tập nghiộm Parcto của lớp bài toán tối ưu đa mục ticii 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... này của (p ) có tính cực tiểu sắc yếu toàn cục II1Ô tả tính cực tiểu sắc yếu toàn cục của tập nghiệm P areto 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ìn h bày rriột số khái niệrri 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. .. từng khúc Cụ thể: Chương 1 trìn h 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ìn h bày cấu trúc và tính cực tiễu sắc yếu của tập nghiệm P areto 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 da mục tiêu tuyến tính từng khúc Mục 2.2 nghiên cứu cấu. .. hàm tuyến tính licn 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àrri tuyến tín h 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. .. 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 = E , c = R + , D — R và 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 Đ ịn h 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. .. 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 ở trcn thì yếu hơn trong [2], trong đó giả thiết rằng với rriọi cặp ( i , j ) , Pị n Pj bằng rỗng hoặc m ột m ặt chung của Pị và P j Đố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 Paret.o được khảo sát trong [3,4] Cho D c X là m ột đa. .. 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 ticu tuyến tính từng khúc dưới đây: (P) mi nf ( x ) sao cho X £ D 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 e D, f (u) - f { x ) e c \{ 0 ỵ } 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 6 D với f ( u ) — f ( x ) G i n t c , ở dó intc kí hiệu phần trong của. .. lý 2.3 (Định lý A B B cho trường hợp không gian vô hạn chiều) Nếu f : X —> Y là một toán tử tuyến tính liên tục tỉâ s là ìiự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ố 7 E [0 , +00] sao cho d( x, S) < 7 [ d( f ( x) ì f ( S) )... xạ / : 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], / đượ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ọ { P i , Pk}i { T i , T f c } và { & ! , 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 = uĩ-1 Pi và f(x) = fiịx) := Ti(x) + bi Vi e Pj, Vi... 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 licn tục từng khúc và bài toán tối ưu đa mục ticu licn quan được nghicn cứu theo các quan điổm khác nhau Ví dụ, Gowda và Szajdcr [2] nghicn cứu tính chất giả-Lipschitz của / -1 và chỉ ra rằng các kết quả thu được có ... tồn nghiệm toán tối ưu vector Chương trìn h bày cấu trúc tính cực tiễu sắc yếu tập nghiệm P areto 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 da mục tiêu tuyến tính khúc Mục. .. nghiên cứu cấu trúc tập nghiệm P areto 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 P areto 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... khái Iiiệm liên quan gọi tính cực tiểu sắc dược vài tác giả nghicn cứu (xem [12]) Tính cực tiểu sắc yếu toàn cục tập nghiệm Pareto yếu rnột toán tối ưu đa mục tiêu tuyến tính không gian định chuẩn