Đăng ký Đăng nhập
Trang chủ Tính compact và tính liên thông của tập nghiệm trong bài toán tối ưu pareto...

Tài liệu Tính compact và tính liên thông của tập nghiệm trong bài toán tối ưu pareto

.PDF
54
702
50

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC Nguyễn Thị Loan TÍNH COMPACT VÀ TÍNH LIÊN THÔNG CỦA TẬP NGHIỆM TRONG BÀI TOÁN TỐI ƯU PARETO LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội – Năm 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC Nguyễn Thị Loan TÍNH COMPACT VÀ TÍNH LIÊN THÔNG CỦA TẬP NGHIỆM TRONG BÀI TOÁN TỐI ƯU PARETO Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Tạ Duy Phượng Hà Nội – Năm 2015 Mục lục Mở đầu 3 Danh mục kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . 3 Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1 Kiến thức chuẩn bị 1.1 1.2 7 Giải tích lồi . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.1 Không gian metric và không gian vectơ . . . . . . . 7 1.1.2 Hàm lõm 9 1.1.3 Hàm lõm suy rộng . . . . . . . . . . . . . . . . . . . 11 1.1.4 Hàm vectơ lõm và hàm vectơ lõm suy rộng . . . . . 14 . . . . . . . . . . . . . . . . . . . . . . . Tính liên thông của ánh xạ đa trị nửa liên tục . . . . . . . 24 1.2.1 Tính liên thông của các tập hợp . . . . . . . . . . . 24 1.2.2 Ánh xạ đa trị nửa liên tục . . . . . . . . . . . . . . 27 2 Tính compact và tính liên thông của tập nghiệm trong bài toán tối ưu Pareto 2.1 32 Tối ưu Pareto . . . . . . . . . . . . . . . . . . . . . . . . . 32 1 2.2 Tính compact và tính liên thông của tập nghiệm trong bài toán tối ưu Pareto . . . . . . . . . . . . . . . . . . . . . . . 34 Kết luận 50 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . 51 2 Danh mục kí hiệu R R+ Rn Rn+ Rn++ x∈M y∈ /M ∅ 2X M ⊆N M ⊂N M 6⊂ N M ∩N M \N M ×N M +N λM ∀x ∃x inf x∈K f (x) supx∈K f (x) Im(f) đường thẳng thực nửa đường thẳng thực không âm không gian Euclide n-chiều tập các vectơ các thành phần không âm của Rn tập các vectơ các thành phần dương của Rn phần tử x thuộc M phần tử y không thuộc M tập rỗng tập tất cả các tập con của X M là tập con của N M là tập con thực sự của N M không là tập con thực sự của N giao của hai tập M và N tập các điểm thuộc M nhưng không thuộc N tích Descartes của hai tập M và N tổng của hai tập M và N vị tự tập M theo tỉ số λ ∈ R trong không gian vectơ với mọi x tồn tại x infimum của tập {f (x) : x ∈ K} supremum của tập {f (x) : x ∈ K} ảnh của tập f 3 Mở đầu Tối ưu đa mục tiêu là chuyên ngành quan trọng của toán ứng dụng. Về mặt toán học, tối ưu đa mục tiêu là tối ưu với nhiều hàm mục tiêu, thường là độc lập với nhau, thậm chí đối nghịch nhau trên một miền chấp nhận được X ⊆ Rn . Hai nhà kinh tế Edgeworth và Pareto từ cuối thế kỷ 19 đã đưa ra khái niệm nghiệm hữu hiệu hay điểm Pareto. Đây là những khái niệm nền tảng của tối ưu đa mục tiêu. Tuy nhiên phải đến những năm 50 của thế kỷ 20, tối ưu đa mục tiêu mới trở thành một chuyên ngành toán học và được phát triển mạnh mẽ trong vòng 30 năm qua. Những vấn đề chính của tối ưu đa mục tiêu đang được quan tâm nghiên cứu là: i) Nghiên cứu định tính; ii) Xây dựng thuật toán xác định tập Pareto; iii) Tối ưu trên tập Pareto. Cho đến nay, lý thuyết tối ưu đa mục tiêu tuyến tính gần như hoàn chỉnh. Một số thuật toán xây dựng tập Pareto và Pareto yếu đã được công bố. Tuy nhiên các thuật toán này mới chỉ hữu hiệu với các bài toán có số chiều n nhỏ. Bài toán tối ưu đa mục tiêu là mô hình của nhiều bài toán thực tế. Thí dụ trong sản xuất ta cần tìm phương thức đạt chất lượng sản phẩm cao nhất, giá thành rẻ nhất, ô nhiễm môi trường thấp nhất, đồng thời đem lại lợi nhuận cao nhất, đầu tư thấp nhất,... Đôi khi trong thực tế một phương án có thể là tốt cho mục tiêu này nhưng lại không tốt cho mục tiêu khác, từ đó hình thành khái niệm tối ưu Pareto. Phương án tối ưu Pareto là 4 phương án mà không tồn tại phương án nào khác có tất cả các mục tiêu không kém hơn nhưng có ít nhất một mục tiêu là tốt hơn. Các bài toán thực tế thường đòi hỏi tìm không chỉ một hoặc một số, mà toàn bộ các phương án tối ưu. Điều này dẫn đến việc nghiên cứu cấu trúc của toàn bộ tập nghiệm, thậm chí cả trong trường hợp khi chưa biết được một phương án tối ưu cụ thể nào. Vì cần tối ưu nhiều mục tiêu cùng một lúc, nên hàm mục tiêu của bài toán là một hàm vectơ. Trong thực tế, các mục tiêu thường là các hàm thuộc một lớp hàm nào đó (hàm liên tục, hàm tuyến tính, hàm phân thức tuyến tính, hàm lồi (lõm), hàm tựa lồi (tựa lõm), hàm tựa lồi ngặt (tựa lõm ngặt), hàm nửa tựa lồi ngặt (nửa tựa lõm ngặt),...). Trong nghiên cứu định tính một số vấn đề cần được nghiên cứu để làm sáng tỏ cấu trúc của tập nghiệm là: +) Tính đóng của tập nghiệm; +) Tính compact của tập nghiệm; +) Tính liên thông, liên thông đường, liên thông đường gấp khúc của tập nghiệm;... Mục đích của luận văn này là trình bày một số nghiên cứu về tính compact và tính liên thông của tập nghiệm trong bài toán tối ưu Pareto; Chủ yếu dựa trên tài liệu [14]. Luận văn trình bày tính compact và tính liên thông của tập nghiệm trong bài toán tối ưu Pareto, trong đó hàm mục tiêu và hàm ràng buộc là tựa lõm. Do tính chất tựa lõm của hàm mục tiêu và hàm ràng buộc không đủ để khẳng định tính chất tôpô của tập nghiệm nên ta cần thêm một vài điều kiện để chứng minh tính compact và tính liên thông của tập nghiệm trong bài toán tối ưu Pareto. Luận văn được chia làm hai chương với nội dung như sau. 5 Chương 1 trình bày một số kiến thức cơ bản về giải tích lồi và ánh xạ đa trị, là các kiến thức chuẩn bị cho Chương 2. Chương 2 trình bày tính compact và tính liên thông của tập nghiệm trong bài toán tối ưu Pareto và mối quan hệ giữa tính compact và tính liên thông, dựa theo bài báo [14], có tham khảo thêm một số tài liệu khác. Luận văn được hoàn thành dưới sự hướng dẫn, chỉ bảo tận tình của thầy PGS. TS. Tạ Duy Phượng, cùng với sự nỗ lực của bản thân và sự động viên của bạn bè. Tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn PGS. TS. Tạ Duy Phượng, tới các thầy cô trong Viện Toán học đã giảng dạy và tạo mọi điều kiện thuận lợi cho tôi để hoàn thành luận văn này. Tôi cũng xin cảm ơn tất cả bạn bè đặc biệt là các bạn lớp cao học K21 Viện Toán học đã luôn quan tâm, động viên và giúp đỡ tôi trong suốt thời gian học tập và làm luận văn. Cuối cùng tôi xin cảm ơn gia đình đã luôn quan tâm và động viên trong suốt quá trình học và làm luận văn. Hà Nội, ngày 20 tháng 08 năm 2015 Tác giả luận văn Nguyễn Thị Loan 6 Chương 1 Kiến thức chuẩn bị Trong chương này, chúng tôi giới thiệu một số kiến thức cơ bản của giải tích vô hạn chiều như: các không gian metric, không gian vectơ, các hàm lồi, hàm vectơ lồi, hàm lõm, hàm lõm suy rộng và khái niệm liên thông, ánh xạ đa trị, tính liên tục của ánh xạ đa trị,... cần thiết cho việc trình bày các nội dung của chương sau. 1.1 1.1.1 Giải tích lồi Không gian metric và không gian vectơ Định nghĩa 1.1. Cho tập X 6= ∅, ánh xạ d từ tích Descartes X × X vào tập các số thực R được gọi là metric trên X nếu các tiên đề sau thỏa mãn: i) d(x, y) > 0 nếu x 6= y, d(x, y) = 0 nếu x = y; ii) d(x, y) = d(y, x), ∀x, y ∈ X; iii) d(x, y) ≤ d(x, z) + d(z, y), ∀x, y, z ∈ X . Tập X với metric d trang bị trên X được gọi là không gian metric, kí hiệu 7 là (X, d) hay thường được viết là X . Số d(x, y) được gọi là khoảng cách giữa hai phần tử x và y . Các phần tử của X được gọi là các điểm. Định nghĩa 1.2. Cho X là một không gian metric, một điểm a ∈ X và B là tập con của X . Khoảng cách từ một điểm a đến tập B được xác định bởi: d(a, B) := inf d(a, b). b∈B Định nghĩa 1.3. Một tập M trong không gian R được gọi là compact nếu mọi dãy {xn } ⊂ M đều chứa một dãy con {xnk } hội tụ tới một điểm thuộc M. Định nghĩa 1.4. Một tập X được gọi là không gian vectơ trên R nếu trên đó xác định phép cộng hai phần tử với nhau và phép nhân một số với một phần tử được định nghĩa sao cho thỏa mãn 8 tiên đề, tức là với mọi x, y ∈ X và α ∈ R thì x + y và αx thỏa mãn 8 tiên đề sau: 1) x + y = y + x (tính chất giao hoán của phép cộng vectơ); 2) (x + y) + z = x + (y + z) (tính chất kết hợp của phép cộng vectơ); 3) Tồn tại một phần tử 0 sao cho x + 0 = x, với mọi x ∈ X (tính chất phép cộng vectơ có phần tử trung hòa); 4) Với mỗi x ∈ X có phần tử −x ∈ X sao cho x + (−x) = 0 (phần tử −x gọi là phần tử đối của x) (tính chất phép cộng vectơ có phần tử đối); 5) 1 · x = x (tính chất phần tử đơn vị với phép nhân vô hướng); 6) α (βx) = (αβ) x (α, β là những số bất kỳ) (tính chất phép nhân vô hướng tương thích với phép nhân trong trường các số vô hướng); 7) (α + β) x = αx + βx (tính chất phép nhân vectơ phân phối với phép cộng vô hướng); 8) α(x + y) = αx + αy (tính chất phép nhân vô hướng phân phối với phép cộng vectơ). 8 1.1.2 Hàm lõm Với mọi a, b ∈ Rm ta kí hiệu đoạn thẳng [a, b] và khoảng (a, b) như sau: [a, b] = {x|x ∈ Rn , x = λa + (1 − λ)b, λ ∈ [0, 1]} ; (a, b) = {x|x ∈ Rm , x = λa + (1 − λ)b, λ ∈ (0, 1)} . Định nghĩa 1.5. Giả sử X là một tập khác trống nào đó trong không gian Euclide hữu hạn chiều Rm . Tập X được gọi là lồi nếu X chứa mọi đoạn thẳng nối hai điểm của nó, tức là λx1 + (1 − λ)x2 ∈ X với mọi cặp điểm x1 , x2 của X và mọi số thực λ ∈ [0, 1]. Định nghĩa 1.6. Giả sử X là một tập khác trống trong Rm . Tập X được gọi là mở trong Rm nếu với mọi x ∈ X tồn tại một hình cầu mở tâm x với bán kính dương nằm trọn trong X . Định nghĩa 1.7. Cho X là một tập khác trống, lồi trong không gian Euclide hữu hạn chiều Rm . Hàm số f : X → R được gọi là lõm trong X nếu với mỗi cặp điểm x1 , x2 của X và mọi số thực λ ∈ [0, 1] ta có f (λx1 + (1 − λ)x2 ) ≥ λf (x1 ) + (1 − λ)f (x2 ). Định nghĩa 1.8. Hàm f : X → R được gọi là lồi trong X nếu −f lõm trong X , tức là f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) với mỗi cặp điểm x1 , x2 của X và mọi số thực λ ∈ [0, 1]. Trong một số bài toán, ví dụ như khi nghiên cứu bài toán tối ưu, hàm lõm (lồi) chưa đủ để chứng minh tính duy nhất nghiệm. Vì vậy người ta phải xét một lớp hàm hẹp hơn lớp hàm lõm, đó là lớp hàm lõm ngặt. Định nghĩa 1.9. Hàm f : X → R được gọi là lõm ngặt trên X nếu f (λx1 + (1 − λ)x2 ) > λf (x1 ) + (1 − λ)f (x2 ) với mọi x1 , x2 ∈ X, x1 6= x2 và λ ∈ (0, 1). 9 Cho f là một hàm xác định trên X . Ta xét bài toán tìm cực đại của hàm f trên X , tức là tìm x̄ ∈ X sao cho f (x̄) ≥ f (x) với mọi x ∈ X . Định nghĩa 1.10. Điểm x̄ ∈ X được gọi là điểm cực đại địa phương của hàm f nếu tồn tại một hình cầu mở Bε (x̄) tâm x̄, bán kính ε > 0 sao cho f (x̄) ≥ f (x) với mọi x ∈ Bε (x̄) ∩ X . Tính chất 1.1.1. Giả sử f (x) là hàm lõm. Khi đó f (x) đạt cực đại địa phương tại điểm x̄ khi và chỉ khi f (x) đạt cực đại toàn cục tại x̄. Chứng minh. Điều kiện đủ là hiển nhiên, vì mỗi điểm cực đại toàn cục cũng là điểm cực đại địa phương. Ta chứng minh điều kiện cần bằng phản chứng. Giả sử x̄ là điểm cực đại địa phương của f nhưng x̄ không là điểm cực đại toàn cục, dựa vào tính lõm của hàm f để chỉ ra mâu thuẫn. Giả sử D là miền xác định của hàm f . Do x̄ là điểm cực đại địa phương của f nên tìm được ε > 0 sao cho f (x̄) ≥ f (x) với mọi x ∈ D thỏa mãn kx − x̄k < ε. Nếu x̄ không là điểm cực đại toàn cục của f trên D thì tìm được x0 ∈ D sao cho f (x0 ) > f (x̄) hay f (x0 ) − f (x̄) > 0. Đặt xλ = λx0 + (1 − λ)x̄ với λ ∈ [0, 1]. Khi đó xλ ∈ D (vì x̄ ∈ D, x0 ∈ D và theo giả thiết D là lồi). Hơn nữa kxλ − x̄k = kλ (x0 − x̄)k = λ kx0 − x̄k < ε với λ > 0 đủ nhỏ, tức là xλ ∈ D ∩ B(x̄, ε). Do f là hàm lõm nên với λ > 0 đủ nhỏ ta có: f (xλ ) ≥ λf (x0 ) + (1 − λ)f (x̄) = f (x̄) + λ(f (x0 ) − f (x̄)) > f (x̄) (vì f (x0 ) − f (x̄) > 0 và λ > 0). Suy ra f (xλ ) > f (x̄) (trái với giả thiết x̄ là điểm cực đại địa phương). Vậy nếu x̄ là điểm cực đại địa phương của f thì x̄ phải là điểm cực đại toàn cục. Tính chất 1.1.2. Nếu x̄ ∈ X là điểm cực đại của hàm lõm ngặt f trên tập lồi X thì nó là điểm cực đại duy nhất. 10 Chứng minh. Ta chứng minh bằng phản chứng. Giả sử x̄ là điểm cực đại của f nhưng x̄ không duy nhất. Khi đó tìm được điểm x0 6= x̄ sao cho f (x0 ) = f (x̄). Đặt xλ = λx + (1 − λ)x̄ với λ ∈ (0, 1), vì hàm f là hàm lõm ngặt nên f (xλ ) = f (λx0 + (1 − λ)x̄) > λf (x0 ) + (1 − λ)f (x̄) với mọi λ ∈ (0, 1). Do f (x0 ) = f (x̄) nên bất đẳng thức trên cho thấy f (xλ ) > λf (x0 )+(1−λ)f (x̄) = f (x̄) với mọi λ ∈ (0, 1). Do vậy f (xλ ) > f (x̄) (vô lí với x̄ là điểm cực đại của hàm lõm ngặt trên tập lồi X ). Vậy điểm cực đại của hàm lõm ngặt là duy nhất. 1.1.3 Hàm lõm suy rộng Định nghĩa 1.11. Hàm f xác định trên một tập lồi X ⊂ Rm được gọi là tựa lõm (quasi-concave) trên X , nếu với mỗi cặp điểm x1 , x2 của X và mọi số thực λ ∈ [0, 1] thì f (λx1 + (1 − λ)x2 ) ≥ min {f (x1 ), f (x2 )} . Hàm f được gọi là tựa lồi nếu −f là tựa lõm, tức là f (λx1 + (1 − λ)x2 ) ≤ max {f (x1 ), f (x2 )} . Nhận xét 1.1. Hàm đơn điệu f : R → R vừa tựa lõm, vừa tựa lồi. Chứng minh. Giả sử f : R → R là hàm đơn điệu. Lấy λ ∈ [0, 1] và x1 < x2 . Khi ấy x1 ≤ xλ ≤ x2 . Nếu f là hàm giảm thì min {f (x1 ), f (x2 )} = f (x2 ) ≤ f (xλ ) ≤ f (x1 ) = max {f (x1 ), f (x2 )} . Với f là hàm tăng suy ra min {f (x1 ), f (x2 )} = f (x1 ) ≤ f (xλ ) ≤ f (x2 ) = max {f (x1 ), f (x2 )} . Vậy min {f (x1 ), f (x2 )} ≤ f (xλ ) ≤ max {f (x1 ), f (x2 )} hay hàm đơn điệu f vừa tựa lõm, vừa tựa lồi. Định nghĩa 1.12. Hàm f xác định trên một tập lồi X ⊂ Rm được gọi là tựa lõm ngặt (strictly quasi-concave) trên X nếu với mỗi cặp điểm x1 , x2 của X và x1 6= x2 , λ ∈ (0, 1) thì f (λx1 + (1 − λ)x2 ) > min {f (x1 ), f (x2 )}. 11 Nhận xét 1.2. (Tính lõm kéo theo tính tựa lõm) Hàm lõm là hàm tựa lõm. Hàm lõm ngặt là hàm tựa lõm ngặt. Chứng minh. Giả sử f : X → R là hàm lõm. Lấy bất kì x1 , x2 ∈ X , không mất tính tổng quát ta xem f (x1 ) ≥ f (x2 ). Từ định nghĩa hàm lõm, đặt xλ := λx1 +(1−λ)x2 thì f (xλ ) ≥ λf (x1 )+(1− λ)f (x2 ), với mọi λ ∈ [0, 1] hay f (xλ ) ≥ f (x2 ) + λ(f (x1 ) − f (x2 )) ≥ f (x2 ), với mọi λ ∈ [0, 1] (vì λ ≥ 0 và f (x1 ) ≥ f (x2 )). Suy ra f (xλ ) ≥ f (x2 ) = min {f (x1 ), f (x2 )} hay f (xλ ) ≥ min {f (x1 ), f (x2 )}, với mọi λ ∈ [0, 1]. Chứng tỏ hàm lõm f là tựa lõm. Tương tự, ta thay dấu ≥ bởi dấu > thì ta cũng chứng minh hàm lõm ngặt f là tựa lõm ngặt. Định nghĩa 1.13. Hàm f : X ⊂ Rm → R được gọi là tựa lõm nửa ngặt (semi-strictly quasi-concave) trên X nếu f là tựa lõm và với mọi x1 , x2 của X , f (x1 ) 6= f (x2 ) và λ ∈ (0, 1) thì f (λx1 + (1 − λ)x2 ) > min {f (x1 ), f (x2 )} . Nhận xét 1.3. 1) Hàm tựa lõm ngặt là tựa lõm nửa ngặt nhưng ngược lại không đúng. 2) Hàm tựa lõm nửa ngặt là tựa lõm nhưng ngược lại không đúng. Chứng minh. 1) Giả sử f : X → R là tựa lõm ngặt. Khi ấy f (xλ ) = f (λx1 + (1 − λ)x2 ) > min {f (x1 ), f (x2 )}, với mọi x1 , x2 ∈ X và x1 6= x2 với mọi λ ∈ (0, 1). Suy ra f (xλ ) ≥ min {f (x1 ), f (x2 )} . Chứng tỏ f là tựa lõm trên X . Hơn nữa, nếu f (x1 ) 6= f (x2 ) thì x1 6= x2 . Suy ra f (xλ ) = f (λx1 + (1 − λ)x2 ) > min {f (x1 ), f (x2 )} với mọi λ ∈ (0, 1). Vậy f là tựa lõm nửa ngặt. Ngược lại không đúng được chỉ ra ở ví dụ sau: 12  x, nếu x ∈ [0, 1]; 1, nếu x ∈ (1, 2]. Hàm f là tựa lõm nửa ngặt trên X nhưng không tựa lõm ngặt trên X . Ví dụ 1.1.1. Cho X = [0, 2] và f (x) = Hình 1.1 Vì f là hàm không giảm nên theo nhận xét 1.1 thì hàm f là tựa lõm. Với x1 , x2 ∈ X . Giả sử f (x1 ) 6= f (x2 ). Khi ấy hoặc 0 ≤ x1 < x2 ≤ 1 hoặc 0 ≤ x1 < 1 ≤ x2 ≤ 2. Với 0 ≤ x1 < x2 ≤ 1 thì f (x1 ) = x1 < f (x2 ) = x2 và f (xλ ) = xλ > x1 = min {f (x1 ), f (x2 )} với mọi λ ∈ (0, 1) . Với 0 ≤ x1 < 1 ≤ x2 ≤ 2 thì f (x1 ) = x1 < 1 = f (x2 ). Vậy min {f (x1 ), f (x2 )} = min {x1 , 1} = x1 < f (xλ ) với mọi λ ∈ (0, 1) . Vậy f (x) là tựa lõm nửa ngặt trên X . Nhưng f không là tựa lõm ngặt trên X . Lấy x1 = 1 6= x2 = 2 và λ = 1 2 thì f (1) = 1 = f (2) và xλ = λx1 + (1 − λ)x2 = 12 · 1 + 21 · 2 = 32 . Mà  f 23 = 1 = min {f (1), f (2)} . Vậy f không là tựa lõm ngặt. 2) Giả sử hàm f là tựa lõm nửa ngặt. Theo định nghĩa tựa lõm nửa ngặt thì hàm f là tựa lõm. Ngược lại không đúng được chỉ ra ở ví dụ sau đây: 13   0, nếu x ∈ [−2, 0] Ví dụ 1.1.2. Cho X = [−2, 2] và f (x) = x, nếu x ∈ (0, 1]  1, nếu x ∈ (1, 2] Hàm f liên tục và tựa lõm trên X . Nhưng hàm f không tựa lõm nửa ngặt trên X . Hình 1.2 Ta thấy hàm f (x) là liên tục và đồng biến trên [−2, 2] . Nên hàm f là tựa lõm trên X = [−2, 2] (theo Nhận xét 1.1). Lấy x1 = −2 6= x2 = 2 và λ = 1 2 thì f (−2) = 0 < f (2) = 1 và xλ = λx1 +(1−λ)x2 = 12 ·(−2)+ 12 ·2 = 0. Ta có f (0) = 0 = min {f (−2), f (2)} . Vậy hàm f không là tựa lõm nửa ngặt trên X = [−2, 2] . 1.1.4 Hàm vectơ lõm và hàm vectơ lõm suy rộng Định nghĩa 1.14. Một tập D ⊆ Rm được gọi là nón nếu λ ≥ 0 và x ∈ D thì λx ∈ D. Giả sử Rm là không gian Euclide hữu hạn chiều. Ta đưa vào các kí hiệu sau: m Rm + = {x = (x1 , x2 , ...., xm ) ∈ R : xi ≥ 0, i = 1, ..., m} ; 14 m Rm ++ = {x = (x1 , x2 , ..., xm ) ∈ R : xi > 0, i = 1, 2, ..., m} . m m Rm + được gọi là nón octant không âm của R , còn R++ được gọi là nón octant dương của Rm . Chúng ta xây dựng khái niệm thứ tự trong Rm sinh bởi nón Rm + như sau: Giả sử a = (a1 , a2 , ..., am )T và b = (b1 , b2 , ..., bm )T là những vectơ trong không gian Euclide m-chiều Rm . Ta viết a ≤ b (tương ứng a < b) nếu ai ≤ bi (tương ứng ai < bi ) với mọi i = 1, 2, ..., m. Như vậy, a ≤ b ⇔ b − a ≥ 0, b − a ∈ Rm +; a < b ⇔ b − a > 0, b − a ∈ Rm ++ . Định nghĩa 1.15. Tập D ⊆ Rm được gọi là nón lồi nếu D là nón và D là tập lồi. Ví dụ 1.1.3. Rm + là một nón lồi. Một nón không nhất thiết là một tập lồi.  Ví dụ 1.1.4. D = x ∈ R2 \R2++ là nón nhưng không lồi. Hình 1.3 15 Mệnh đề 1.1. Một tập D là nón lồi khi và chỉ khi có các tính chất sau: (i) λD ⊆ D, ∀λ ≥ 0. (ii) D + D ⊆ D. Chứng minh. Giả sử D là nón lồi. Ta phải chứng minh D thỏa mãn hai tính chất (i) và (ii). Vì D là một nón nên theo định nghĩa nón ta có (i). Do D là một tập lồi, nên với mọi x, y ∈ D và chọn λ = 1 2 thì 21 (x+y) ∈ D. Vậy theo (i) ta có (x + y) ∈ D. Ngược lại, giả sử có (i) và (ii). Ta phải chứng minh D là nón lồi. Từ (i) suy ra D là một nón. Giả sử x, y ∈ D và λ ∈ [0, 1], từ (i) suy ra λx ∈ D và (1 − λ)y ∈ D. Theo (ii) ta có λx + (1 − λ)y ∈ D. Vậy D là nón lồi. Giả sử X là một tập lồi khác trống trong Rm và fi : X → Rn , i = 1, ..., n. Định nghĩa 1.16. Hàm f = (f1 , f2 , ..., fn )T : X → Rn , i = 1, ..., n được gọi là lõm (concave) trên X nếu mọi hàm fi là lõm trên X , tức là nếu với mỗi cặp điểm x1 , x2 của X , mọi số thực λ ∈ [0, 1] thì fi (λx1 + (1 − λ)x2 ) ≥ λfi (x1 ) + (1 − λ)fi (x2 ), với mọi i = 1, ..., n. Định nghĩa 1.17. Hàm f = (f1 , f2 , ..., fn )T : X → Rn , i = 1, ..., n được gọi là tựa lõm (quasi-concave) trên X nếu mọi hàm fi là tựa lõm trên X , tức là với mỗi cặp điểm x1 , x2 của X và λ ∈ (0, 1) thì fi (λx1 + (1 − λ)x2 ) ≥ min {fi (x1 ), fi (x2 )} , với mọi i = 1, ..., n. Định nghĩa 1.18. Hàm f = (f1 , f2 , ..., fn )T : X → Rn , i = 1, ..., n được gọi là tựa lõm ngặt (strictly quasi-concave) trên X nếu mọi hàm fi là tựa 16 lõm ngặt trên X , tức là với mỗi cặp điểm x1 , x2 ∈ X và x1 6= x2 , λ ∈ (0, 1) thì fi (λx1 + (1 − λ)x2 ) > min {fi (x1 ), fi (x2 )} , với mọi i = 1, ..., n. Định nghĩa 1.19. Hàm f = (f1 , f2 , ..., fn ): X → Rn được gọi là tựa lõm nửa ngặt (semi-strictly quasi-concave) trên X nếu mọi hàm fi là tựa lõm nửa ngặt trên X , tức là {fi }ni=1 là tựa lõm và với mọi x1 , x2 ∈ X , fi (x1 ) 6= fi (x2 ) với mọi i = 1, 2, ..., n và λ ∈ (0, 1) thì fi (λx1 + (1 − λ)x2 ) > min {fi (x1 ), fi (x2 )} , với mọi i = 1, 2, ..., n. Chúng ta nhận xét rằng khái niệm hàm vectơ lõm nêu trên đòi hỏi khá ngặt: mọi hàm thành phần phải có tính chất lõm tương ứng. Mặt khác, các định nghĩa trên không thể hiện mối quan hệ tổng thể giữa các hàm thành phần tạo nên hàm vectơ. Định nghĩa hàm lõm dưới đây của Wantao và Kunping trong [11] về hàm F -tựa lõm ngặt, đã thể hiện rõ hơn mối quan hệ tổng thể giữa các hàm thành phần của hàm vectơ. Định nghĩa 1.20. Hàm f = (f1 , f2 , ..., fn )T : X → Rn được gọi là F lõm (concave) trên X nếu với mỗi cặp x1 , x2 ∈ X , tồn tại một chỉ số i0 ∈ {1, 2, ..., n} sao cho với mọi λ ∈ [0, 1] thì fi0 (λx1 + (1 − λ)x2 ) ≥ λfi0 (x1 ) + (1 − λ)fi0 (x2 ). Định nghĩa 1.21. Hàm f = (f1 , f2 , ..., fn )T : X → Rn được gọi là F -tựa lõm (quasi-concave) trên X nếu với mọi x1 , x2 ∈ X , tồn tại một chỉ số i0 := i0 (x1 , x2 ) ∈ {1, 2, ..., n} sao cho với mọi λ ∈ [0, 1] thì fi0 (λx1 + (1 − λ)x2 ) ≥ min{fi0 (x1 ), fi0 (x2 )}. Nhận xét 1.4. Hàm lõm là hàm F -tựa lõm. Tuy nhiên khái niệm hàm F -lõm là yếu hơn, vì với mỗi cặp x1 , x2 ∈ X cụ thể chỉ cần tồn tại một chỉ 17 số i0 ∈ {1, 2, ..., n} sao cho với mọi λ ∈ [0, 1] để bất đẳng thức fi0 (λx1 + (1 − λ)x2 ) ≥ λfi0 (x1 ) + (1 − λ)fi0 (x2 ) được thỏa mãn với mọi λ ∈ [0, 1] mà thôi. Định nghĩa 1.22. Hàm f = (f1 , f2 , ..., fn )T : X → Rn được gọi là F -tựa lõm ngặt (strictly quasi-concave) trên X nếu với mỗi cặp x1 , x2 ∈ X và x1 6= x2 , tồn tại một chỉ số i0 ∈ {1, 2, ..., n} sao cho với mọi λ ∈ (0, 1) thì fi0 (λx1 + (1 − λ)x2 ) > min{fi0 (x1 ), fi0 (x2 )}. Ví dụ 1.1.5. Giả sử X = [−2, 2]. Hàm mục tiêu f =(f1 , f2 ) được xác định x, nếu − 2 ≤ x ≤ 0 0, nếu − 2 ≤ x ≤ 0 như sau: f1 (x) = , f2 (x) = 0, nếu 0 < x ≤ 2 −x, nếu 0 < x ≤ 2 Hàm f là tựa lõm trên X = [−2, 2], cả hai hàm f1 (x) và f2 (x) đều không là tựa lõm ngặt. Nhưng nó là F -tựa lõm ngặt trên [−2, 2]. Hình 1.4a Hình 1.4b 18
- Xem thêm -

Tài liệu liên quan