Tài liệu Phương pháp hàm phạt cho bài toán tối ưu

  • Số trang: 58 |
  • Loại file: PDF |
  • Lượt xem: 79 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 27125 tài liệu

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ LÊ PHƯƠNG PHÁP HÀM PHẠT CHO BÀI TOÁN TỐI ƯU LUẬN VĂN THẠC SỸ Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 60 46 36 Người hướng dẫn khoa học: GS- TSKH LÊ DŨNG MƯU THÁI NGUYÊN, 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mục lục Lời cảm ơn 4 Mở đầu 5 1 Các kiến thức cơ bản về tập lồi và hàm lồi 1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . 1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . 1.2.1 Định nghĩa và tính chất . . . . . . . 1.2.2 Tính liên tục . . . . . . . . . . . . . 1.2.3 Dưới vi phân . . . . . . . . . . . . . 1.2.4 Tính chất cực trị . . . . . . . . . . 2 Phương pháp hàm phạt 2.1 Bài toán tối ưu . . . . . . . . . 2.1.1 Phát biểu bài toán . . . . 2.1.2 Các điều kiện tối ưu . . . 2.2 Phương pháp hàm phạt . . . . . 2.2.1 Hàm phạt điểm ngoài . . 2.2.2 Hàm phạt điểm trong . . 2.2.3 Hàm phạt kiểu Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Hàm phạt chính xác và áp dụng 3.1 Hàm phạt chính xác cho bài toán tối ưu lồi. . . . . . . . . 3.2 Hàm phạt chính xác cho bài toán tối ưu trên tập Pareto . 3.2.1 Bài toán tối ưu vecto tuyến tính . . . . . . . . . . 3.2.2 Hàm phạt chính xác cho bài toán tối ưu trên tập Pareto . . . . . . . . . . . . . . . . . . . . . . . . 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn . . . . . . 7 7 11 11 13 14 15 . . . . . . . 17 17 17 19 23 24 26 31 42 . 42 . 49 . 49 . 53 Tài liệu tham khảo 58 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lời cảm ơn Trước khi trình bày nội dung chính của luận văn, em xin bày tỏ lòng biết ơn sâu sắc tới GS.TSKH Lê Dũng Mưu người đã tận tình hướng dẫn và giúp đỡ em trong suốt quá trình học tập và nghiên cứu để em có thể hoàn thành khóa luận này. Em cũng xin bày tỏ lòng biết ơn chân thành tới quý thầy, cô giáo trường Đại học Khoa học- Đại học Thái Nguyên và Viện Toán học - Viện Khoa học và Công nghệ Việt Nam đã giảng dạy và giúp đỡ em hoàn thành khóa học. Nhân dịp này em cũng xin chân thành cảm ơn Ban Giám hiệu, các bạn đồng nghiệp Trường Cao đẳng Công nghệ và Kinh tế công nghiệp, gia đình và bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện cho em về mọi mặt trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp. Mặc dù đã có nhiều cố gắng nhưng Luận văn khó tránh khỏi những thiếu sót. Tác giả rất mong nhận được ý kiến đóng góp của quý thầy, cô và bạn đọc để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn! Thái Nguyên, ngày 20 tháng 07 năm 2012 Tác giả Nguyễn Thị Lê 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mở đầu Bài toán tối ưu là bài toán tìm một phương án chấp nhận được để làm cực trị một hàm số hoặc một hàm vecto. Đây là bài toán có nhiều ứng dụng trong thực tế. Khó khăn chính trong việc nghiên cứu và giải quyết bài toán này là phải tìm được một phương án tối ưu trong miền chấp nhận được. Để giải quyết khó khăn này, phương pháp hàm phạt là một cách tiếp cận cơ bản để giải quyết bài toán tối ưu có ràng buộc. Ý tưởng chính của phương pháp này là chuyển bài toán có ràng buộc về một dãy các bài toán không ràng buộc hoặc có ràng buộc đơn giản hơn. Các loại hàm phạt thường được dùng là hàm phạt điểm ngoài, hàm phạt điểm trong và hàm phạt kiểu Lagrange (thưởng- phạt). Đối với phương pháp hàm phạt điểm ngoài, hàm phạt được xác định cả bên ngoài miền chấp nhận được và có tính chất là lượng phạt p(x) > 0 nếu x không thuộc miền chấp nhận được D, trái lại, nếu x ∈ D thì p(x) = 0. Một hàm phạt khác là hàm phạt kiểu Lagrange, hàm này cũng xác định cả bên ngoài miền ràng buộc như hàm phạt điểm ngoài, nhưng bên trong miền chấp nhận được, lượng phạt có thể nhận giá trị âm, tức là được thưởng tùy theo mức độ thỏa mãn miền ràng buộc. Phương pháp có hiệu quả hơn cả là phương pháp hàm phạt điểm trong, khác với hàm phạt điểm ngoài và hàm phạt kiểu Lagrange, hàm phạt này chỉ xác định tại miền trong của tập chấp nhận được, còn tại các điểm gần biên của miền chấp nhận được thì p(x) = +∞. Thông thường, người ta chỉ có thể chuyển việc một bài toán có ràng buộc về việc giải một dãy vô hạn các bài toán không có ràng buộc hoặc có ràng buộc đơn giản hơn. Tuy nhiên trong một số trường hợp cụ thể, với những điều kiện nhất định thì ta có thể chuyển về việc giải chỉ duy nhất một bài toán không ràng buộc. Hàm phạt cho tính chất này được gọi là hàm phạt chính xác. Bản luận văn này nhằm mục đích chủ yếu là hệ thống các kiến thức cơ bản về các loại phương pháp hàm phạt đã kể trên. Cụ thể, luận văn đã đề 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn cập đến các vấn đề sau: 1. Giới thiệu các kiến thức cơ bản về phương pháp hàm phạt điểm ngoài, phương pháp hàm phạt điểm trong và phương pháp hàm phạt kiểu Lagrange. 2. Trình bày một kết quả tương đối mới về hàm phạt chính xác cho bài toán tối ưu lồi. Ngoài ra, luận văn còn trình bày phương pháp hàm phạt chính xác cho bài toán tối ưu không lồi, đó là bài toán tối ưu một hàm tuyến tính trên tập nghiệm của một bài toán tối ưu vecto affin. Luận văn gồm 3 chương: Chương 1. Giới thiệu một số khái niệm và kiến thức cơ bản của giải tích lồi thường được dùng trong tối ưu hoá (tập afin, tập lồi, nón lồi, hàm lồi và các tính chất cơ bản của chúng). Chương 2. Trình bày ba phương pháp hàm phạt là: Phương pháp hàm phạt điểm trong, phương pháp hàm phạt điểm ngoài và hàm phạt kiểu Lagrange (thưởng- phạt). Chương 3. Trình bày khái niệm về hàm phạt chính xác, điều kiện đủ để tồn tại hàm phạt chính xác cho bài toán tối ưu lồi, bài toán tối ưu trên tập Pareto của một bài toán tối ưu vecto affine và áp dụng hàm phạt chính xác vào bài toán tối ưu trên tập này. 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 1 Các kiến thức cơ bản về tập lồi và hàm lồi Chương này nhằm giới thiệu một số khái niệm và kiến thức cơ bản của giải tích lồi thường được dùng trong tối ưu hoá (tập afin, tập lồi, nón lồi, hàm lồi và các tính chất cơ bản của chúng). Các khái niệm và kết quả trong chương này hầu hết được lấy từ các tài liệu: [1],[2], [3]. 1.1 Tập lồi Định nghĩa 1.1. Một đường thẳng nối hai điểm (hai vecto) trong không gian Rn là tập hợp tất cả các vecto x ∈ Rn có dạng {x ∈ Rn |x = αa + βb, α + β = 1} . Đoạn thẳng nối hai điểm trong không gian Rn là tập hợp tất cả các vecto x ∈ Rn có dạng {x ∈ Rn |x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1} . Một tập M được gọi là tập affine (đa tạp affine) nếu nó chứa đường thẳng đi qua hai điểm bất kỳ của nó, tức là ∀x, y ∈ M, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ M. Ví dụ 1.1. Các không gian con của Rn là các tập affine. Nhận xét 1.1. 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn • Nếu M là tập affine thì a + M = {a + x | x ∈ M } cũng là một tập affine với ∀a ∈ Rn . • M là tập affine chứa gốc khi và chỉ khi M là không gian con. Định nghĩa 1.2. Thứ nguyên của một đa tạp affine được cho bởi thứ nguyên của không gian con song song với nó. Siêu phẳng H trong Rn là một tập affine có số chiều bằng (n-1), hay chính là tập có dạng: H = {x ∈ Rn | aT x =α}, trong đó 0 6= a ∈ Rn và α ∈ R. Ví dụ 1.2. Trong không gian hai chiều, siêu phẳng là đường thẳng. Trong không gian 3 chiều, siêu phẳng là mặt phẳng. Định nghĩa 1.3. Trong Rn , siêu phẳng H = {x ∈ Rn | aT x =α}, với 0 6= a ∈ Rn và α ∈ R chia Rn thành hai nửa không gian đóng : H − = {x ∈ Rn | aT x ≤ α} và H + = {x ∈ Rn | aT x ≥ α}, mỗi nửa không gian này nằm về một phía của siêu phẳng và phần chung của chúng chính là siêu phẳng H . Tương tự, H cũng chia Rn thành hai nửa không gian mở: {x ∈ Rn | aT x < α} và {x ∈ Rn | aT x > α}. Một tập C trong Rn được gọi là tập lồi nếu C chứa mọi đoạn thẳng nối hai điểm thuộc nó, tức là tập C lồi khi và chỉ khi: ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C. Bao lồi của tập A là tập lồi nhỏ nhất chứa A, ký hiệu là CoA, đây chính là giao của tât cả các tập lồi chứa A. Cho hai tập A, B bất kỳ trong Rn , tổ hợp lồi của các tập A và B là tập các điểm thuộc Rn có dạng: x = λa + (1 − λ)b, a ∈ A, b ∈ B, 0 ≤ λ ≤ 1. 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lớp các tập lồi là đóng đối với phép giao, phép cộng đại số và phép nhân tích Decartes, cụ thể ta có định lý sau: Định lý 1.1. Nếu A, B là các tập lồi trong Rn , C là lồi trong Rm , thì các tập sau là tập lồi: 1. A ∩ B := {x |x ∈ A, x ∈ B }; 2. αA + βB := {x |x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R}; 3. A × C := {x ∈ Rn+m |x = (a, c), a ∈ A, c ∈ C }. Định nghĩa 1.4. Cho A là tập lồi, tập affine nhỏ nhất chứa A được gọi là bao affine của A, ký hiệu là af f A. Thứ nguyên của tập lồi A ký hiệu là dimA được cho bởi thứ nguyên của bao affin của A. Một điểm a ∈ A được gọi là điểm trong của A nếu tồn tại một lân cận mở U của a sao cho U ⊂ A, tập hợp các điểm trong của A ký hiệu là intA. Một tập lồi A trong Rn có thể không có điểm trong (khi xét trong Rn ), nhưng nó luôn có điểm trong khi xét trong af f A, điểm trong này gọi là điểm trong tương đối. Nếu ký hiệu riA là tập các điểm trong tương đối của A thì riA := {x ∈ affA |∃ U, U ∩ affA ⊂ A}, trong đó U là một lân cận mở của x. nếu A là tập lồi khác rỗng thì riA 6= ∅. Một tập hợp là giao của một số hữu hạn các nửa không gian đóng được gọi là tập lồi đa diện ( khúc lồi). Như vậy dạng tường minh của một tập lồi đa diện D được cho như sau: D = {x ∈ Rn < aj , x >≤ bj , j = 1, 2, .., m}. Một tập con A0 của A được gọi là một diện của A nếu hễ nó chứa một điểm trong của một đoạn thẳng thì nó chứa cả đoạn thẳng đó, tức là: ∀a, b ∈ A, nếu x = λa + (1 − λ)b, 0 < λ < 1, x ∈ A0 ⇒ a, b ∈ A0 . Một diện có thứ nguyên bằng 0 được gọi là đỉnh hay điểm cực biên. Cạnh là một diện có thứ nguyên bằng 1. Đối với một tập C bất kỳ, một điểm x ∈ C được gọi là điểm biên của C nếu không tồn tại a, b ∈ C, 0 < λ < 1 sao cho: 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn x = λa + (1 − λ)b và đoạn thẳng [a, b] ⊂ C . Với một tập lồi đa diện, một đỉnh của diện cũng chính là đỉnh của tập đó. Một tập C được gọi là nón lồi nếu ∀x, y ∈ C thì x + y ∈ C và tx ∈ C với mọi t ≥ 0. Ví dụ 1.3. Rn+ là một nón lồi. Cho C là một tập trong Rn , một vecto y 6= 0 được gọi là hướng lùi xa của C nếu mọi tia xuất phát từ một điểm bất kỳ của C theo hướng y đều nằm trọn trong C , tức là y 6= 0 là hướng lùi xa khi và chỉ khi x + λy ∈ C, ∀x ∈ C, ∀λ ≥ 0. Tập tất cả các hướng lùi xa của C cùng với điểm gốc được gọi là nón lùi xa của C , ký hiệu là reC . Cho C là một tập lồi trong Rn và x ∈ C , tập hợp: NC (x) = {w |hw, y − xi ≤ 0,∀y ∈ C} được gọi là nón pháp tuyến ngoài của C tại x, tập hợp −NC (x) = {w |hw, y − xi ≥ 0,∀y ∈ C} được gọi là nón pháp tuyến trong của C tại x, tập hợp C ∗ = {w |h w, xi ≤ 0, ∀x ∈ C} được gọi là nón đối cực của C . Cho C là một tập lồi khác rỗng và x thuộc C . Ta nói d ∈ Rn là một hướng chấp nhận được của C nếu tồn tại t0 > 0 sao cho x + td ∈ C với mọi 0 ≤ t ≤ t0 . Tập tất cả các hướng chấp nhận được của C tại x ký hiệu là C(x) và gọi là nón chấp nhận được của C tại x. Định lý tách các tập lồi dưới đây là những định lý cơ bản nhất của giải tích lồi, được dùng nhiều trong lý thuyết tối ưu. Cho hai tập C và D khác rỗng, ta nói siêu phẳng aT x = α tách C và D nếu aT x ≤ α ≤ aT y, ∀x ∈ C, ∀y ∈ D. 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ta nói siêu phẳng aT x = α tách chặt C và D nếu aT x < α < aT y, ∀x ∈ C, ∀y ∈ D. Ta nói siêu phẳng aT x = α tách mạnh C và D nếu sup aT x < α < inf aT y. y∈D x∈C Bổ đề 1.1. : Cho C ⊂ Rn là một tập lồi khác rỗng. Giả sử x0 ∈ / C . Khi n 0 đó tồn tại t ∈ R , t 6= 0 thỏa mãn ht, xi ≥ ht, x i, ∀x ∈ C. Định lý 1.2. (Định lý tách 1): Cho C và D là hai tập lồi đóng khác rỗng trong Rn và C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D. Định lý sau đây nói về việc tách mạnh hai tập lồi: Định lý 1.3. (Định lý tách 2):Cho C và D là hai tập lồi đóng khác rỗng trong Rn và C ∩ D = ∅. Giả sử có it nhất một tập compac. Khi đó hai tập này có thể được tách mạnh bởi một siêu phẳng. Một hệ quả rất quan trọng của định lý tách là bổ đề Farkas. Bổ đề này rất trực quan, dễ áp dụng trong nhiều lĩnh vực như tối ưu, điều khiển,.. Bổ đề 1.2. (Farkas) Cho a ∈ Rn và A là ma trận cỡ m × n. Khi đó ha, xi ≥ 0 với mọi x thỏa mãn Ax ≥ 0, khi và chỉ khi tồn tại y ≥ 0 thuộc Rm sao cho a = AT y . Ý nghĩa hình học của bổ đề này rất rõ: nó có nghĩa rằng siêu phẳng đi qua gốc tọa độ ha, xi = 0 để nón Ax ≥ 0 nằm về một phía của nó khi và chỉ khi vectơ pháp tuyến a của siêu phẳng nằm trong nón sinh bởi các hàng của ma trận A. 1.2 1.2.1 Hàm lồi Định nghĩa và tính chất Cho C ⊆ Rn là tập lồi và f : C → R ( R = R ∪ { ± ∞}) 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ta ký hiệu domf := {x ∈ C | f (x) < +∞} và gọi là miền hữu dụng của f . Nếu domf 6= ∅ và f (x) > −∞ thì f được gọi là hàm lồi chính thường. Tập epif := {(x, µ) ∈ C × R | f (x) ≤ µ} được gọi là trên đồ thị của hàm f f : Rn → R ∪ { + ∞} Định nghĩa 1.5. Cho ∅ = 6 C ⊆ Rn là một tập lồi và f : C → R Ta nói f là hàm lồi trên C nếu epif là một tập lồi trong Rn+1 . Từ đây ta luôn xét f : Rn → R ∪ { + ∞}.Khi đó định nghĩa trên tương đương với f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1). Hàm f được gọi là lồi chặt trên C nếu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1) Hàm f được gọi là hàm lõm (lõm chặt) trên C nếu −f là hàm lồi (lồi chặt) trên C. Hàm f được gọi là tựa lồi trên C nếu với mọi λ ∈ R, tập mức { x ∈ C |f (x) ≤ λ } là tập lồi. Hàm f được gọi là hàm tựa lõm trên C nếu −f là hàm tựa lồi trên C. Ta định nghĩa các hàm sau: (λf )(x) := λf (x); (f + g)(x) := f (x) + g(x). Lớp các hàm lồi là đóng đối với phép lấy tổ hợp tuyến tính không âm và phép lấy max, cụ thể: Định lý 1.4. Cho f là hàm lồi trên tập A và g là hàm lồi trên tập B . Khi đó các hàm sau là lồi trên tập A ∩ B : 1. αf + βg, ∀α, β > 0; 2. max{f, g}. 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định lý sau đây cho phép kiểm tra tính lồi của một hàm số: Định lý 1.5. Cho f : C → R là một hàm khả vi trên tập lồi mở C . Điều kiện cần và đủ để f lồi trên C là: f (x) + h∇f (x), y − xi ≤ f (y), ∀x, y ∈ C, trong đó ký hiệu f 0 (a) hoặc ∇f (a) là đạo hàm của f tại a. Nếu f khả vi hai lần thì điều kiện cần và đủ để f lồi trên C là với mọi x thuộc C , ma trận Hessian H(x) của f tại x xác định không âm, tức là: y T H(x)y ≥ 0, ∀x ∈ C, y ∈ Rn . Như vậy một dạng toàn phương xT Qx là một hàm lồi khi và chỉ khi Q xác định không âm. Tính khả vi của hàm lồi giữ vai trò quan trọng bậc nhất trong các phương pháp tối ưu hóa. 1.2.2 Tính liên tục Một hàm f xác định trên Rn được gọi là nửa liên tục dưới tại điểm x0 nếu với mọi ε > 0, tồn tại δ > 0, sao cho f (x) ≥ f (x0 ) − ε, với mọi x thỏa mãn x − x0 < δ. Hàm f được gọi là nửa liên tục trên tại x0 nếu−f nửa liên tục dưới tại x0 . Hàm f được gọi là liên tục tại điểm x0 nếu f vừa nửa liên tục trên vừa nửa liên tục dưới tại điểm này Hàm f được gọi là liên tục (nửa liên tục) trên X , nếu nó liên tục (nửa liên tục) tại mọi điểm trên X . Định lý 1.6. Đối với một hàm lồi chính thường trên Rn và x0 ∈ int(domf ), các khẳng định sau đây là tương đương: (i) f liên tục tại điểm x0 ; (ii) f bị chặn trong một lân cận của x0 ; (iii) int(epif ) 6= ∅; (iv) int(domf ) 6= ∅ và f liên tục trên tập int(domf ). Một hàm lồi có thể không liên tục trên biên miền xác định của nó nhưng liên tục tại mọi điểm trong của tập đó theo định lý sau: Định lý 1.7. Một hàm lồi liên tục trên C thì liên tục tại mọi điểm trong của C. 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1.2.3 Dưới vi phân Cho một hàm n biến, khi cố định một hướng và xét hàm nhiều biến trên hướng đó thì ta có hàm một biến. Giả sử y 6= 0 là một hướng cho trước xuất phát từ điểm x0 . Khi đó mọi điểm thuộc đường thẳng đi qua x0 và có hướng y đều có dạng: x = x0 + λy, với λ ∈ R. Cho f : Rn → R ∪ { + ∞} và x0 ∈ R sao cho f (x0 < +∞). nếu với một vecto y ∈ Rn mà giới hạn: f (x0 + λy) − f (x0 ) lim λ→0 λ tồn tại (hữu hạn hay vô hạn), thì ta nói f có đạo hàm theo hướng y tại điểm x0 , ký hiệu giới hạn này là f 0 (x0 , y). Ta biết rằng nếu hàm lồi khả vi tại một điểm nào đó thì tiếp tuyến của đồ thị tại điểm đó sẽ nằm dưới đồ thị hàm số. Nhưng hàm lồi có thể không khả vi tại một điểm nào đó, trong trường hợp này ta mở rộng khái niệm đạo hàm bằng dưới đạo hàm, sao cho vẫn giữ được tính chất cơ bản trên của đạo hàm của hàm lồi khả vi. Định nghĩa 1.6. Cho f : Rn → R ∪ { + ∞}. Ta nói x∗ ∈ Rn là dưới đạo hàm của f tại x nếu: hx∗ , z − xi + f (x) ≤ f (z), ∀z Tập hợp tất cả các dưới đạo hàm của f tại x được gọi là dưới vi phân của f tại x, ký hiệu là ∂f (x). Khi ∂f (x) 6= ∅ ta nói hàm f khả dưới vi phân tại x. Trong trường hợp tập ∂f (x) chỉ gồm duy nhất một điểm thì hàm f khả vi tại x. Cũng có trường hợp tập ∂f (x) là tập rỗng, tức là tại điểm x hàm số f không có dưới vi phân. Tuy nhiên đối với hàm lồi thì điều đó chỉ có thể xảy ra theo định lý sau: Định lý 1.8. Cho f : Rn → R ∪ { + ∞} là một hàm lồi, khi đó ∂f (x) 6= ∅ với mọi x thuộc ri(domf ) 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Từ định lý này suy ra rằng nếu hàm f là hàm lồi hữu hạn trên toàn không gian Rn thì nó khả dưới vi phân tại mọi điểm, vì riRn = Rn . Ví dụ 1.4. Hàm số f (x) = |x|, khả vi tại mọi điểm khác 0 nhưng không khả vi tại x = 0, tại đó ∂f (0) = {y ||x| ≥ hy, xi, ∀x} = [ − 1, 1] Cũng như trong trường hợp hàm một biến, bất đẳng thức hx∗ , z − xi + f (x) ≤ f (z), ∀z, có nghĩa là siêu phẳng đi qua điểm (x, f (x)) nằm dưới đồ thị của hàm số. 1.2.4 Tính chất cực trị Định nghĩa 1.7. Cho C ⊆ Rn là tập khác rỗng và f : C → R. Một điểm x∗ ∈ C được gọi là cực tiểu địa phương của f trên C nếu tồn tại một lân cận U của x∗ sao cho f (x∗ ) ≤ f (x), ∀x ∈ U ∩ C. Điểm x∗ ∈ C được gọi là cực đại địa phương nếu f (x) ≤ f (x∗ ), ∀x ∈ U ∩ C. Nếu f (x∗ ) ≤ f (x), ∀x ∈ C thì x∗ được gọi là cực tiểu toàn cục hay cực tiểu tuyệt đối của f trên C , và nếu f (x) ≤ f (x∗ ), ∀x ∈ C thì x∗ được gọi là cực đại toàn cục hay cực đại tuyệt đối của f trên C. Mệnh đề 1.1. Cho f : Rn → R ∪ { + ∞} là hàm lồi.Khi đó mọi điểm cực tiểu địa phương của f trên một tập lồi đều là cực tiểu toàn cục. Hơn nữa tập hợp các điểm cực tiểu của f là một tập lồi. Nếu f lồi chặt thì điểm cực tiểu nếu tồn tại sẽ là duy nhất. Mệnh đề 1.2. (i) Giả sử f là một hàm lồi chính thường trên Rn và C ⊆ Rn là một tập lồi. Khi đó nếu f đạt cực đại hữu hạn tại một điểm trong tương đối của C thì f là hằng số trên C. (ii) Nếu f là một hàm lồi, chính thường trên Rn và bị chặn trên trong một tập affine, thì nó là hằng số trên tập này . 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Hệ quả 1.1. Nếu một hàm lồi đạt cực đại trên một tập lồi có điểm cực biên, thì cực đại sẽ đạt được tại một điểm cực biên của tập lồi đó. Kết luận chương 1 Trong chương 1, chúng ta đã trình bày một số kiến thức cơ bản của giải tích lồi để sử dụng cho các chương tiếp theo như tập lồi, tập lồi đa diện, hàm lồi và một số kết quả quan trọng như bổ đề Farkas, định lý tách các tập lồi,.. 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương 2 Phương pháp hàm phạt Nói chung các bài toán không có ràng buộc thường dễ xử lý hơn các bài toán có ràng buộc. Một ý tưởng nảy sinh là chuyển bài toán tối ưu có ràng buộc về bài toán tối ưu không ràng buộc. Kỹ thuật cơ bản để thực hiện ý tưởng này là hàm phạt. Chương này gồm hai phần, phần 1 trình bày khái niệm về bài toán tối ưu và các điều kiện tối ưu, phần 2 trình bày ba phương pháp hàm phạt là: Phương pháp hàm phạt điểm trong, phương pháp hàm phạt điểm ngoài và hàm phạt kiểu Lagrange (thưởng- phạt). Các khái niệm và kết quả được lấy từ các tài liệu: [2],[3], [4],[5]. 2.1 2.1.1 Bài toán tối ưu Phát biểu bài toán Bài toán tối ưu được xét trong chương này có dạng sau: min {f (x) : x ∈ C} (P ), là bài toán tìm điểm x∗ ∈ C sao cho f (x∗ ) ≤ f (x) với mọi x ∈ C, trong đó C ⊆ X (X là không gian nào đó, thông thường X ≡ Rn ), f : C → R. Hàm f được gọi là hàm mục tiêu, tập C gọi là tập ràng buộc hay miền chấp nhận được. Một vecto x ∈ C được gọi là một phương án chấp nhận được. Vecto x∗ ∈ C thoả mãn điều kiện f (x∗ ) ≤ f (x) với mọi x ∈ C được gọi là một nghiệm tối ưu của bài toán và f (x∗ ) được gọi là giá trị cực tiểu hay giá trị tối ưu của f trên C . Trường hợp C ≡ Rn ta có bài toán tối ưu không ràng buộc min {f (x) : x ∈ Rn } 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Trái lại (P ) là bài toán tối ưu có ràng buộc. Thông thường tập C thường được cho bởi một hệ phương trình hoặc/và bất phương trình có dạng sau: C = {x ∈ X :gi (x) ≤ 0, hj (x) = 0, i = 1, .., m; j = 1, .., p} (2.1) với gi , hj : X → R là các hàm cho trước, gọi là các hàm ràng buộc. Dễ thấy rằng nếu các hàm f lồi, gi là lồi, liên tục trên X và các hàm hj là afin thì C là tập đóng. Khi ấy (P) được gọi là bài toán quy hoạch lồi Nhận xét 2.1. Do max {f (x) : x ∈ C} = −min{−f(x) : x ∈ C}, và tập nghiệm của các bài toán này trùng nhau nên bài toán tìm cực đại có thể đưa về bài toán tìm cực tiểu và ngược lại. Sau đây là một số ví dụ về bài toán tối ưu có ràng buộc Ví dụ 2.1. : bài toán xác định kế hoạch sản xuất tối ưu Một xí nghiệp sản xuất n loại sản phẩm và sử dụng m loại nguyên liệu khác nhau. Gọi xj , (j = 1, ..n) là lượng hàng thứ j cần sản xuất, cj , (j = 1, .., n) là lãi thu được khi sản xuất một đơn vị sản phẩm thứ j . Biết rằng để sản xuất một đơn vị sản phẩm thứ j cần dung đến aij loại nguyên liệu thứ i, (i = 1, .., m; j = 1, .., n.). Gọi bi là số lượng nguyên liệu thứ i mà xí nghiệp có thể cung cấp được. Bài toán đặt ra là xác định lượng sản xuất cho mỗi loại sản phẩm để tổng số lãi thu được là lớn nhất. Bài toán này có mô hình toán học như sau Tìm xj ≥ 0, (j = 1, .., n) sao cho f (x1 , .., xn ) = n X cj xj → max j=1 Với điều kiện n X aij xj ≤ bi , i = 1, .., m (2.2) j=1 Ví dụ 2.2. Bài toán vận tải Cần chở hàng từ m nơi sản xuất đến n nơi tiêu thụ. Biết trước lượng hàng có ở mỗi nơi sản xuất và lượng hàng cần thiết ở mỗi nơi tiêu thụ, biết cước phí.Tìm phương án vận chuyển sao cho thoả mãn tiêu thụ và cước phí vận chuyển thấp nhất. Gọi xij : Lượng hàng cần chuyển từ i đến j 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn cij : Cước phí vận chuyển một đơn vị hàng hoá từ i đến j aj : Lượng hàng cần chở ở điểm j bi : Lượng hàng có ở nơi sản xuất i Mô hình toán học của của bài toán như sau Tìm xij ≥ 0, (j = 1, .., n; i = 1, .., m) sao cho f (xij ) = m X n X cij xij → min i=1 j=1 Với các điều kiện n X xij = bi j=1 m X xij = aj i=1 m X n X i=1 j=1 bi = 2.1.2 aj Các điều kiện tối ưu Xét bài toán (P). Đối với nghiệm tối ưu tuyệt đối, bốn khả năng sau có thể xảy ra: 1. C là tập rỗng (bài toán không có phương án chấp nhận được) 2. f không bị chặn dưới trên C 3. inf f (x) > −∞ nhưng giá trị nhỏ nhất không đạt được trên C x∈C 4. Tồn tại x∗ ∈ C sao cho f (x∗ ) = min f (x) x∈C Câu hỏi đặt ra là: Làm thế nào kiểm tra được sự tồn tại nghiệm của bài toán? Ta xét các định lý sau đây: Định lý 2.1. Điều kiện cần và đủ để hàm f đạt cực tiểu trên C là tập F + (C) := {t ∈ R : f (x) ≤ t, x ∈ C} đóng và bị chặn dưới Định lý sau là một điều kiện đủ cho sự tồn tại nghiệm, dựa ngay trực tiếp từ các dữ liệu của bài toán: 19 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Định lý 2.2. (Weistrass) Nếu C là tập compact và f nửa liên tục dưới trên C thì f đạt cực tiểu trên C Một vấn đề quan trọng khi nghiên cứu các bài toán tối ưu là việc tìm kiếm những điều kiện tối ưu. Những điều kiện ấy cho phép hiểu biết được các tính chất của lời giải, từ đó có thể xây dựng phương pháp giải. Chúng ta xét các định lý sau về điều kiện tối ưu: Định lý 2.3. Giả sử C là tập lồi,f là hàm lồi khả dưới vi phân trên C . Khi đó x∗ là nghiệm tối ưu của (P) khi và chỉ khi 0 ∈ ∂f (x∗ ) + NC (x∗ ), (2.3) trong đó NC (x∗ ) là nón pháp tuyến của C tại x∗ Chứng minh: i) Điều kiện đủ: Giả sử điều kiện (2.3) được thỏa mãn, khi đó tồn tại ∗ p sao cho p∗ ∈ ∂f (x∗ ) ∩ (−NC (x∗ )). Do p∗ ∈ ∂f (x∗ ) nên hp∗ , x − x∗ i ≤ f (x) − f (x∗ ), ∀x. Ta lại có hp∗ , x − x∗ i ≥ 0, ∀x do p∗ ∈ −NC (x∗ ), suy ra f (x) − f (x∗ ) ≥ 0, ∀x ∈ C. (ii) Điều kiện cần: Giả sử x∗ là một nghiệm tối ưu của bài toán. Do tính afin của C nên ta có thể coi C có thứ nguyên đầy đủ. Do C là tập lồi, int(C) 6= ∅. Xét hai tập sau: E := {(t, x) ∈ R × Rn : t > f (x) − f (x∗ ), x ∈ C} , G := {0} × C. Dễ thấy cả E và G đều là tập lồi (do C và f là lồi) . Hơn nữa G ∩ C = ∅. Theo định lý tách thì tồn tại vectơ (u0 , u) 6= 0 ∈ Rn+1 sao cho u0 t + uT x ≤ u0 0 + uT y, ∀(t, x) ∈ E, y ∈ C. ⇔ u0 t ≤ hu, y − xi, ∀(t, x) ∈ E, y ∈ C. 20 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (2.4)
- Xem thêm -