Phương pháp chia đôi giải bài toán tối ưu trên tập Pareto tuyến tính

Kỷ yếu công trình khoa học 2015 - Phần I<br /> <br /> PHƯƠNG PHÁP CHIA ĐÔI GIẢI BÀI TOÁN TỐI ƯU TRÊN TẬP<br /> PARETO TUYẾN TÍNH<br /> Nguyễn Lâm Tùng<br /> Bộ môn Toán Đại học Thăng Long<br /> Email: nguyenlamtung01@gmail.com<br /> Tóm tắt. Báo cáo trình bày một số cải tiến trong thuật toán chia đôi giải bài<br /> toán tối ưu một hàm tuyến tính trên tập Pareto [1]. Bài toán được phát biểu như<br /> sau:<br /> max ⟨d, x⟩,<br /> (P)<br /> x∈E(C,X)<br /> <br /> trong đó d ∈ R , E(C, X) là tập Pareto của bài toán tối ưu đa mục tiêu tuyến<br /> tính:<br /> V max Cx,<br /> (LP)<br /> n<br /> <br /> x∈X<br /> <br /> với C là ma trận p × n, p là số hàm mục tiêu tuyến tính, X là đa diện lồi bị<br /> chặn trong R n .<br /> Báo cáo trình bày các tính chất quan trọng của bài toán (LP), cở sở lý thuyết,<br /> điều kiện dừng của thuật toán chia đôi. Cuối cùng báo cáo nêu một ví dụ minh<br /> họa cho thuật toán.<br /> Từ khóa: đa diện lồi, tập Pareto, tối ưu, hàm tuyến tính, thuật toán chia đôi,<br /> nghiệm tối ưu.<br /> <br /> 1 Mở đầu<br /> Định nghĩa 1. Cho R n = {x ∈ R n |xi ≥ 0, ∀i = 1, n} là nón các phần<br /> +<br /> n<br /> tử không âm của R . Ta nói điểm x ∈ X cực đại Pareto của bài toán (LP)<br /> nếu: Cy − Cx ∈ R n , ∀y ∈ X, y ̸= x, tập tất cả các điểm cực đại Pareto<br /> / +<br /> của bài toán (LP) ký hiệu là E(C,X), gọi tắt là tập Pareto hay tập hữu hiệu.<br /> Định lý 1.Tập Pareto E(C, X) của bài toán (LP) là đóng, liên thông đường<br /> và bao gồm một số diện của X.<br /> Định lý 2. Điểm x0 là điểm Pareto của bài toán tối ưu p mục tiêu tuyến tính<br /> ¯<br /> (LP) khi và chỉ khi tồn tại λ ∈ Λ0 sao cho:<br /> ¯<br /> ¯<br /> λT Cx0 ≥ λT Cx, ∀x ∈ X<br /> với Λ = {λ = (λ1 , . . . , λp ) | λ1 + · · · + λp = 1, λi ≥ 0, ∀i = 1, p}<br /> Λ0 là phần trong tương đối của Λ.<br /> Trường Đại học Thăng Long<br /> <br /> 141<br /> <br /> Kỷ yếu công trình khoa học 2015 - Phần I<br /> <br /> Nhận xét: Theo định lý trên, bài toán (P ) có thể mô tả thành bài toán sau:<br /> max{dT x |λT Cx ≥ g(λ), x ∈ X, λ ∈ Λ0 }<br /> trong đó g(λ) = max{λT Cy |y ∈ X}.<br /> Định lý 3.[Philip] Điểm x0 là điểm Pareto của bài toán tối ưu p mục tiêu tuyến<br /> ¯<br /> tính (LP) khi và chỉ khi tồn tại M > 0 và λ ∈ ΛM sao cho:<br /> ¯<br /> ¯<br /> λT Cx0 ≥ λT Cx, ∀x ∈ X<br /> với ΛM = {λ = (λ1 , . . . , λp ) | λ1 +· · ·+λp ≤ M, λi ≥ 1, ∀i = 1, p}.<br /> Trong bài báo [1], tác giả đã sử dụng định lý 3 để đưa ra thuật toán tìm kiếm<br /> chia đôi, tuy nhiên thuật toán đó có nhược điểm là:<br /> Thứ nhất, trong định lý 3 chỉ khẳng định sự tồn tại của M chứ không đưa cách<br /> xác định M, do đó khi áp dụng vào ví dụ cụ thể, việc lấy giá trị M nào đó là thiếu<br /> chặt chẽ.<br /> Thứ hai, thuật toán hội tụ chậm và chưa đưa ra được nghiệm chính xác.<br /> Bài báo cáo này chỉ dùng định lý 2, không sử dụng định lý 3 nên thuật toán chặt<br /> chẽ hơn, đồng thời đưa ra điều kiện dừng của thuật toán làm cho thuật toán dừng<br /> rất nhanh và có nghiệm chính xác.<br /> <br /> 2 Thuật toán tìm kiếm chia đôi<br /> Đặt:<br /> <br /> d∗ =<br /> <br /> max ⟨d, x⟩, γ0 = min⟨d, x⟩, β0 = max⟨d, x⟩<br /> <br /> x∈E(C,X)<br /> <br /> x∈X<br /> <br /> x∈X<br /> <br /> trong đó E(C, X) là tập Pareto của bài toán đa mục tiêu tuyến tính (LP), X là<br /> đa diện lồi bị chặn.<br /> Dễ thấy γ0 ≤ d∗ ≤ β0 , ý tưởng của thuật toán là áp dụng một sơ đồ chia đôi<br /> miền giá trị của hàm mục tiêu để định vị giá trị d∗ . Bắt đầu từ đoạn [γ0 , β0 ]<br /> chứa d∗ , qua mỗi bước lặp k sẽ co ngắn đoạn γk , βk còn một nửa bằng cách<br /> giải bài toán:<br /> Tìm x ∈ E(C, X) sao cho dT x ≥ αk với αk = (γk + βk )/2<br /> (Pk )<br /> • Nếu bài toán (Pk ) có nghiệm là xk thì đặt γk+1 = dT xk , βk+1 = βk<br /> • Nếu bài toán (Pk ) vô nghiệm thì đặt γk+1 = γk , βk+1 = αk<br /> Sau khi giải bài toán (Pk ) ta có d∗ ∈ [γk+1 , βk+1 ], quá trình này sẽ kết thúc<br /> khi βk − γk ≤ ϵ cho trước. Cho α ∈ R , ký hiệu:<br /> E α = {x ∈ E(C, X) | ⟨d, x⟩ ≥ α}<br /> Trường Đại học Thăng Long<br /> <br /> 142<br /> <br /> Kỷ yếu công trình khoa học 2015 - Phần I<br /> <br /> Ta có:<br /> E α = {x ∈ X |∃λ ∈ Λ0 : λT Cx ≥ λT Cy, ∀y ∈ X, ⟨d, x⟩ ≥ α}<br /> = {x ∈ X |∃λ ∈ Λ0 : λT Cx ≥ g(λ), ⟨d, x⟩ ≥ α}<br /> trong đó g(λ) = max{λT Cy | y ∈ X}.<br /> Đặt: hα (λ) = max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α}.<br /> Dễ dàng chứng minh được hα (λ) là hàm lồi theo λ.<br /> Xây dựng các tập:<br /> Λ = {(λ1 , λ2 , . . . , λp ) | λ1 + λ2 + · · · + λp = 1, λi ≥ 0, ∀i = 1, ..., p}<br /> Λ0 = {(λ1 , λ2 , . . . , λp ) | λ1 +λ2 +· · ·+λp = 1, λi > 0, ∀i = 1, ..., p}<br /> Ω = {(λ, t) | λ ∈ Λ0 , t ≥ g(λ)}<br /> Ωα = {(λ, t) | λ ∈ Λ0 , t > hα (λ)}<br /> ¯<br /> Ωα = {(λ, t) | λ ∈ Λ0 , t ≥ hα (λ)}<br /> Mệnh đề 1. a. Ω và Ωα là hai tập lồi,<br /> ¯<br /> b. Ω ⊂ Ωα ,<br /> c. E α (C, X) ̸= ∅ khi và chỉ khi Ω \ Ωα ̸= ∅.<br /> Chứng minh:<br /> a. Các Ω và Ωα lồi do nó là trên đồ thị của các hàm lồi g(λ) và hα (λ).<br /> b. Hiển nhiên do g(λ) ≥ hα (λ).<br /> c. Giả sử x ∈ E α (C, X) khi đó tồn tại λ ∈ Λ0 sao cho g(λ) ≤ λT Cx.<br /> Lấy t = g(λ) suy ra (λ, t) ∈ Ω. Hơn nữa:<br /> t ≤ λT Cx, x ∈ X, ⟨d, x⟩ ≥ α<br /> nên:<br /> t ≤ max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α} = hα (λ)<br /> do đó t − hα (λ) ≤ 0 suy ra (λ, t) ∈ Ωα .<br /> /<br /> Do vậy (λ, t) ∈ Ω \ Ωα hay Ω \ Ωα ̸= ∅ .<br /> Ngược lại, giả sử (λ, t) ∈ Ω \ Ωα , theo định nghĩa ta có:<br /> t ≥ g(λ), λ ∈ Λ0 , t ≤ hα (λ)<br /> Trường Đại học Thăng Long<br /> <br /> 143<br /> <br /> Kỷ yếu công trình khoa học 2015 - Phần I<br /> <br /> Gọi x∗ là nghiệm tối ưu của bài toán:<br /> max{λT Cx | x ∈ X, ⟨d, x⟩ ≥ α}<br /> ta có:<br /> <br /> t ≤ hα (λ) = λT Cx∗ , ⟨d, x∗ ⟩ ≥ α, x∗ ∈ X<br /> <br /> suy ra g(λ) ≤ λT Cx∗ , λ ∈ Λ, ⟨d, x∗ ⟩ ≥ α, x∗ ∈ X, tức là<br /> x∗ ∈ E α (C, X) hay E α (C, X) ̸= ∅.<br /> Giả sử x0 ∈ X và Sk = {(λ, t) | λ ∈ Λ, t ≥ λT Cx0 , }, khi đó Sk là<br /> đa diện lồi chứa Ω và Sk có hướng lùi xa duy nhất là u = (0, . . . , 0, 1) ∈<br /> R p × R . Gọi Vk là tập đỉnh của Sk và ta định nghĩa Wk như sau:<br /> Wk = {(λ, t) ∈ Vk | t − hα (λ) ≤ 0}<br /> Hệ quả 1. Nếu Wk = ∅ thì Ω \ Ωα = ∅.<br /> Chứng minh: Do tập Sk có hướng lùi xa duy nhất là vecto u nên hàm φ(λ, t) =<br /> t − hα (λ) bị chặn dưới trên tập Sk , đồng thời φ(λ, t) là hàm lõm. Do đó:<br /> min{t − hα (λ) | (λ, t) ∈ Sk } = min{t − hα (λ) | (λ, t) ∈ Vk }<br /> Do vậy nếu Wk = ∅ thì: min{t − hα (λ) | (λ, t) ∈ Vk } > 0, tức là:<br /> min{t − hα (λ) | (λ, t) ∈ Sk } > 0<br /> Vì Ω ⊂ Sk nên ∀(λ, t) ∈ Ω ta có t − hα (λ) > 0 tức là (λ, t) ∈ Ωα , suy<br /> ra Ω ⊂ Ωα , nghĩa là Ω \ Ωα = ∅.<br /> Như vậy nếu Wk = ∅ thì E α (C, X) = ∅, tức là bài toán (Pk ) vô nghiệm.<br /> Ngược lại, nếu Wk ̸= ∅ ta có điểm (λk , tk ) ∈ Wk .<br /> Nhận xét:<br /> • Nếu (λk , tk ) ∈ Ω, tức là λk ∈ Λ và g(λk ) ≤ tk , thì (λk , tk ) ∈ Ω\Ωα .<br /> Gọi xk là một nghiệm tối ưu của bài toán quy hoạch tuyến tính:<br /> max{(λk )T Cx | x ∈ X, ⟨d, x⟩ ≥ α}<br /> theo chứng minh mệnh đề 1, ta có xk ∈ E α (C, X).<br /> • Nếu (λk , tk ) ∈ Ω, tức là g(λk ) − tk > 0, gọi y k là nghiệm tối ưu của<br /> /<br /> bài toán quy hoạch tuyến tính:<br /> max{(λk )T Cy | y ∈ X}<br /> suy ra g(λk ) = (λk )T Cy k , do đó (λk )T Cy k − tk = g(λk ) − tk > 0.<br /> Mặt khác, ∀(λ, t) ∈ Ω ta có λT Cy k − t ≤ g(λ) − t ≤ 0<br /> Trường Đại học Thăng Long<br /> <br /> 144<br /> <br /> Kỷ yếu công trình khoa học 2015 - Phần I<br /> <br /> Như vậy siêu phẳng {(λ, t) | λT Cy k − t = 0} tách chặt đỉnh (λk , tk )<br /> với tập Ω. Ta xây dựng đa diện Sk+1 chứa Ω như sau:<br /> Sk+1 = Sk ∩ {(λ, t) | λT Cy k − t ≤ 0}<br /> Mệnh đề 2. Giả sử tất cả các đỉnh của Sk là v1 , v2 , . . . , vm , đồng thời φ(v1 ) =<br /> 0, φ(v2 ) > 0, . . . , φ(vm ) > 0. Khi đó φ(x) > 0, ∀x ∈ Sk , x ̸= v1 .<br /> Chứng minh: Do Sk có hướng lùi xa duy nhất là u = (0, . . . , 0, 1) nên<br /> với mọi x ∈ Sk tồn tại các số thực không âm q1 , q2 , . . . , qm , r sao cho<br /> q1 + q2 + · · · + qm = 1 và x − r.u = q1 v1 + · · · + qm vm . Do<br /> φ(x) = φ(λ, t) = t − hα (t) là hàm lõm và tăng theo t nên φ(x) ≥<br /> φ(x − ru) ≥ q1 φ(v1 ) + · · · + qm φ(vm ) ≥ 0, dễ thấy dấu bằng xẩy ra chỉ<br /> khi x = v1 , do đó ta có điều phải chứng minh.<br /> Hệ quả 2. Giả sử (λ1 , t1 ), . . . , (λm , tm ) là tất cả các đỉnh của Sk , đồng thời<br /> φ(λ1 , t1 ) = 0, φ(λ2 , t2 ) > 0, . . . φ(λm , tm ) > 0, (λ1 , t1 ) ∈ Ω. Khi đó<br /> /<br /> φ(λ, t) > 0, ∀(λ, t) ∈ Ω.<br /> Chứng minh: Suy ra trực tiếp từ mệnh đề 2 do Ω ⊂ Sk và (λ1 , t1 ) ∈ Ω.<br /> /<br /> Từ các tính chất và nhận xét trên ta có thủ tục OA như sau:<br /> Khởi tạo: Lấy v ∈ X sao cho Cv ̸= 0. Đặt S0 = {(λ, t) | λ ∈<br /> Λ, λT Cv ≤ t}, V0 là tập đỉnh của S0 và đặt k = 0.<br /> Vòng lặp k:<br /> Bước 1: Giải bài toán: θ = min{t−hα (λ) | (λ, t) ∈ Vk } ta được θ, λk , tk .<br /> • TH1: Nếu θ > 0 hoặc θ = 0 nhưng φ(λ, t) > 0, ∀(λ, t) ∈<br /> V (Sk ), (λ, t) ̸= (λk , tk ) thì dừng thuật toán: E α (C, X) = ∅, nói<br /> cách khác bài toán Pk không có nghiệm.<br /> • TH2: Nếu θ < 0 hoặc θ = 0 và có λk ∈ Λ0 thì chuyển sang bước 2.<br /> • TH3: Nếu θ = 0 và không thuộc TH1 và TH2 thì chọn ε > 0 đủ nhỏ và<br /> đặt:<br /> ε<br /> ε<br /> Sk = Sk ∩ {(λ, t)|λi ≥ ε}, Vkε = V (Sk )<br /> Giải bài toán:<br /> θ = min{t − hα (λ) | (λ, t) ∈ Vkε }<br /> ta được nghiệm θε , λk , tk<br /> ε ε<br /> – Nếu θε > 0 thì dừng thuật toán, bài toán Pk không có nghiệm.<br /> – Nếu θε = 0 đặt λk = λk , tk = tk , chuyển sang bước 2.<br /> ε<br /> ε<br /> Trường Đại học Thăng Long<br /> <br /> 145<br /> <br />