ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TÔ MINH QUYẾT PHƯƠNG PHÁP HÀM PHẠT MINIMAX CHÍNH XÁC CHO BÀI TỐN TỐI ƯU KHƠNG TRƠN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TÔ MINH QUYẾT PHƯƠNG PHÁP HÀM PHẠT MINIMAX CHÍNH XÁC CHO BÀI TỐN TỐI ƯU KHƠNG TRƠN Chun ngành: TỐ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 ĐỖ VĂN LƯU Thái Nguyên - 2017 i Mục lục Lời cảm ơn ii Bảng ký hiệu Mở đầu Cận tham số phạt phương pháp hàm phạt minimax xác cho tốn tối ưu đơn mục tiêu khơng khả vi 1.1 Các khái niệm kết liên quan 1.2 Phương pháp hàm phạt minimax xác 1.3 Sự tương đương toán tối ưu có ràng buộc tốn tối ưu phạt 4 Phương pháp hàm phạt minimax xác định yên ngựa cho toán tối ưu véc - tơ lồi không trơn 2.1 Các khái niệm kết bổ trợ 2.2 Phương pháp hàm phạt minimax xác định lí yên ngựa cho tốn tối ưu véc - tơ khơng trơn 2.3 Trường hợp đặc biệt lí điểm 22 22 điểm 25 42 Kết luận 44 Tài liệu tham khảo 45 ii Lời cảm ơn Tơi xin bày tỏ lịng biết ơn sâu sắc tới thầy PGS.TS Đỗ Văn Lưu, người trực tiếp hướng dẫn luận văn, tận tình bảo hướng dẫn tơi tìm hướng nghiên cứu, tìm kiếm tài liệu, giải vấn đề, nhờ tơi hồn thành luận văn cao học Từ tận đáy lịng, tơi xin bày tỏ lòng biết ơn chân thành sâu sắc tới Thầy cố gắng để xứng đáng với công lao Thầy Tôi xin chân thành cảm ơn Ban giám hiệu, phòng Đào tạo trường Đại học Khoa học - Đại học Thái Nguyên quan tâm giúp đỡ suốt thời gian học tập trường Tôi xin cảm ơn quý thầy Khoa Tốn - Tin đặc biệt PGS.TS Nguyễn Thị Thu Thủy, trưởng Khoa Toán - Tin, ln quan tâm, động viên, trao đổi đóng góp ý kiến q báu suốt q trình học tập, nghiên cứu hoàn thành luận văn Cuối cùng, tơi muốn bày tỏ lịng biết ơn sâu sắc tới người thân gia đình, đặc biệt bố mẹ Những người động viên, chia sẻ khó khăn tơi suốt thời gian qua đặc biệt thời gian tơi theo học khóa thạc sỹ trường Đại học Khoa học - Đại học Thái Nguyên Thái Nguyên, ngày 24 tháng năm 2017 Tác giả luận văn Tô Minh Quyết Bảng ký hiệu R Rn Rm + T KKT B ∂fi (x) ∧ ∨ I(¯ x) + gi L(x, µ, ν) P∞ (x, c) (P∞ (c)) V P∞ (x, c) (V P∞ (c)) trường số thực không gian Euclide n-chiều orthant không âm Rm chuyển vị véc - tơ Karush-Kuhn-Tucker hình cầu đơn vị mở Rn vi phân hàm lồi fi x tập số ràng buộc tích cực gi (x) ≤ 0, gi (x) gi (x) > hàm Lagrange hàm phạt minimax xác tốn tối ưu phạt hàm phạt minimax xác véc - tơ toán tối ưu véc - tơ phạt Mở đầu Phương pháp hàm phạt xác cho phép đưa toán tối ưu phi tuyến có ràng buộc tốn tối ưu khơng có ràng buộc cho nghiệm tốn tối ưu phạt nghiệm toán tối ưu có ràng buộc ban đầu Antczak ([2], 2013) nghiên cứu mối quan hệ nghiệm toán tối ưu vơ hướng có ràng buộc nghiệm tốn tối ưu khơng có ràng buộc với hàm mục tiêu hàm phạt minimax xác cận tham số phạt để hai tốn tương đương Jayswall Choudhury ([7], 2016) thiết lập định lí điểm n ngựa cho tốn tối ưu véc - tơ có ràng buộc phương pháp hàm phạt minimax xác xác định điều kiện để toán tối ưu véc - tơ có ràng buộc tương đương với tốn khơng có ràng buộc phương pháp hàm phạt minimax xác Đây đề tài nhiều tác giả quan tâm nghiên cứu Chính vậy, tơi chọn đề tài: "Phương pháp hàm phạt minimax xác cho tốn tối ưu khơng trơn" Mục đích luận văn trình bày phương pháp hàm phạt minimax xác định lí điểm yên ngựa cho toán tối ưu đơn mục tiêu T Antczak (đăng Tạp chí J Optim Theory Appl 159 (2013), 437 - 453) cho toán tối ưu véc - tơ A Jayswal - S Choudhury (đăng Tạp chí J Optim Theory Appl 169 (2016), 179 - 199) có ràng buộc đẳng thức bất đẳng thức Bố cục luận văn gồm phần mở đầu, hai chương trình bày nội dung luận văn, phần kết luận danh mục tài liệu tham khảo Chương 1: "Cận tham số phạt phương pháp hàm phạt minimax xác cho tốn tối ưu đơn mục tiêu khơng khả vi" trình bày kết Antczak [2] phương pháp hàm phạt minimax xác, tương đương tốn tối ưu có ràng buộc tốn tối ưu khơng có ràng buộc phạt chứng minh tham số phạt lớn giá trị cận Chương 2: "Phương pháp hàm phạt minimax xác định lí điểm n ngựa cho tốn tối ưu véc - tơ lồi khơng trơn" trình bày kết Jayswal - Choudhury [7], phương pháp hàm phạt minimax xác định lí điểm yên ngựa cho toán tối ưu véc - tơ lồi không trơn với hàm Lipschitz địa phương Chương Cận tham số phạt phương pháp hàm phạt minimax xác cho tốn tối ưu đơn mục tiêu không khả vi Chương trình bày phương pháp hàm phạt minimax xác tương đương tốn tối ưu có ràng buộc tốn tối ưu phạt khơng có ràng buộc Các kết trình bày chương T Antczak [2] 1.1 Các khái niệm kết liên quan Hàm f : X → R xác định tập lồi X ⊂ Rn gọi lồi với ∀z, x ∈ R λ ∈ [0, 1], ta có f (λz + (1 − λ)x) ≤ λf (z) + (1 − λ)f (x) Định nghĩa 1.1.1 Dưới vi phân hàm lồi f : Rn → R x ∈ Rn xác định sau: ∂f (x) := {ξ ∈ Rn : f (z) − f (x) ≥ ξ T (z − x), ∀z ∈ Rn } Định nghĩa 1.1.2 Trên vi phân hàm lõm f : Rn → R x ∈ Rn xác định sau: ∂f (x) := {ξ ∈ Rn : f (z) − f (x) ≤ ξ T (z − x), ∀z ∈ Rn } Nhận xét 1.1.3 Từ định nghĩa hàm lồi f : Rn → R x, suy ra: f (z) − f (x) ≥ ξ T (z − x), ∀ξ ∈ ∂f (x), (1.1) với ∀z ∈ Rn , ∂f (x) kí hiệu vi phân f x Tương tự, với hàm lõm f : Rn → R x, ta có bất đẳng thức: f (z) − f (x) ≤ ξ T (z − x), ∀ξ ∈ ∂f (x), (1.2) với ∀z ∈ Rn Trước chứng minh kết cho toán (P ), ta cần bổ đề sau đây: Bổ đề 1.1.4 Giả sử ϕk , k = 1, , p, hàm giá trị thực xác định X ⊂ Rn Với x ∈ X, ta có p αk ϕk (x), max ϕk (x) = max 1≤k≤p α∈Ω k=1 p Ω := {α = (α1 , , αp ) ∈ Rp+ αk = 1} : k=1 Bài toán cực trị xét tốn tối ưu phi tuyến tổng qt có ràng buộc đẳng thức bất đẳng thức: (P ) f (x), x ∈ D = {x ∈ X : gi (x) ≤ 0, i ∈ I, hj (x) = 0, j ∈ J}, I = {1, , m}, J = {1, , s}, f : X → R gi : X → R, i ∈ I, hj : X → R, j ∈ J hàm Lipschitz địa phương tập khác rỗng X ∈ Rn D tập chấp nhận toán (P ) Để đơn giản ta đưa vào số kí hiệu: g := (g1 , , gm ) : X → Rm h := (h1 , , hs ) : X → Rs Hơn nữa, ta kí hiệu tập số ràng buộc bất đẳng thức tích cực x∈D I(¯ x) := {i ∈ I : gi (¯ x) = 0} Định lý 1.1.5 [9] Giả sử x¯ nghiệm tốn (P ) điều kiện quy thích hợp thỏa mãn x¯ Khi tồn nhận tử Lagrange ¯ ∈ Rm µ λ ¯ ∈ Rs cho m s ¯ i ∂gi (¯ λ x) + ∈ ∂f (¯ x) + i=1 (1.3) µ ¯i ∂hj (¯ x), j=1 ¯ i gi (¯ λ x) = 0, (1.4) i ∈ I, ¯ ≥ λ (1.5) Định nghĩa 1.1.6 Điểm x¯ ∈ D gọi điểm Karush-Kuhn-Tucker ¯ ∈ Rm µ tốn (P ) tồn nhân tử Lagrange λ ¯ ∈ Rs cho điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3) − (1.5) 1.2 Phương pháp hàm phạt minimax xác Năm 1978 Charalambous [4] đưa vào lớp hàm phạt xác không khả vi sau: [αi gi+ (x)]p + Pp (x, α, β, c) := f (x) + c i=1 p s m p [βj |h+ j (x)|] j=1 c tham số phạt, p ≥ 1, αi > 0, i = 1, , m, βj > 0, j = 1, , s Với ràng buộc bất đẳng thức gi (x) ≤ 0, hàm gi+ (x) định nghĩa gi+ (x) := 0, gi (x) ≤ 0, gi (x), gi (x) > (1.6) với x thỏa mãn ràng buộc có giá trị dương ràng buộc bị vi phạm Hơn nữa, vi phạm lớn gi (x) ≤ đạt giá trị gi+ (x) Như hàm gi+ (x) có điểm phạt liên quan với ràng buộc gi (x) ≤ Với p = xét tham số αi , i = 1, , m, βj , j = 1, , s 1, ta nhận hàm phạt xác khơng khả vi gọi hàm phạt xác l1 (ta gọi hàm phạt giá trị tuyệt đối) Phương pháp hàm phạt xác l1 đưa vào Pietrzykowski [8] Đa số tài liệu phương pháp hàm phạt xác khơng khả vi nghiên cứu điều kiện đảm bảo nghiệm tối ưu toán có ràng buộc cho cực tiểu địa phương tốn với hàm phạt xác khơng có ràng buộc 31 Ví dụ 2.2.5 Xét toán tối ưu véc - tơ sau: (VP1) f (x) = (x21 + |x1 | + x22 , 2x21 + x2 ) g1 (x) = x22 − x2 ≤ 0, g2 (x) = x22 (x21 − 3x1 + 2) ≤ 0, h(x) = x1 (x1 − x2 − 1) = fi : X → R, i = 1, 2, gj : X → R, j = 1, 2, h : X → R hàm Lipschitz địa phương X = (−1.2) × (− , 1) Tập điểm chấp nhận (V P 1) D = {x = (x1 , x2 ) ∈ X : ≤ x2 ≤ ∧ {x2 = ∨ ≤ x1 ≤ 2} ∧ {x1 = ∨ x1 = x2 + 1}} Bài tốn tối ưu véc - tơ khơng ràng buộc phạt (V P 1∞ (c)) với hàm phạt minimax xác xây dựng sau: V P∞ (x, c) =(x21 + |x1 | + x22 + c max{max{0, x22 − x2 }, max{0, x22 (x21 − 3x1 + 2)}, |x1 (x1 − x2 − 1)|}, 2x21 + x2 + c max{max{0, x22 − x2 }, max{0, x22 (x21 − 3x1 + 2)}, |x1 (x1 − x2 − 1)|}) Rõ ràng, x¯ = (0, 0) điểm chấp nhận toán tối ưu véc - tơ (V P 1) Hàm Lagrange véc - tơ cho L(x, µ, ν) =(x21 + |x1 | + x22 + µ1 (x22 − x2 ) + µ2 x22 (x21 − 3x1 + 2) + νx1 (x1 − x2 − 1), 2x21 + x2 + µ1 (x22 − x2 ) + µ2 x22 (x21 − 3x1 + 2) + νx1 (x1 − x2 − 1)) µ = (µ1 , µ2 ) ∈ R2+ , ν ∈ R e = (1, 1) Dễ kiểm tra (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) toán tối ưu véc - tơ (V P 1), ≤ µ ¯1 ≤ 1, µ ¯2 = −1 ≤ ν¯ ≤ Vì vậy, theo Định lý 2.2.4, với c ≥ µ ¯j + |ν| = 2, j=1 x¯ nghiệm hữu hiệu yếu tốn khơng ràng buộc phạt (V P 1∞ (c)) với hàm phạt minimax xác 32 Mệnh đề 2.2.6 Giả sử x¯ nghiệm hữu hiệu yếu tốn tối ưu véc tơ khơng ràng buộc phạt (V P∞ (¯ c)) với hàm phạt minimax xác Khi đó, khơng tồn x ∈ D cho f (x) < f (¯ x) Chứng minh Vì x¯ nghiệm hữu hiệu yếu toán tối ưu véc - tơ không ràng buộc phạt (V P∞ (¯ c)) với hàm phạt minimax xác, không tồn x ∈ X cho V P∞ (x, c¯) < V P∞ (¯ x, c¯) Từ định nghĩa (V P∞ (c)), bất đẳng thức kéo theo không tồn x ∈ X cho x), |hk (¯ x)|}e x) + c¯ max {gj+ (¯ f (x) + c¯ max {gj+ (x), |hk (x)|}e < f (¯ 1≤j≤m 1≤k≤q 1≤j≤m 1≤k≤q Khi đó, ta suy không tồn x ∈ X cho fi (x) + c¯ max {gj+ (x), |hk (x)|} 1≤j≤m 1≤k≤q < fi (¯ x) + c¯ max {gj+ (¯ x), |hk (¯ x)|}, ∀i ∈ I 1≤j≤m 1≤k≤q Vì D ⊆ X, bất đẳng thức kéo theo không tồn x ∈ D cho fi (x) + c¯ max {gj+ (x), |hk (x)|} 1≤j≤m 1≤k≤q x), |hk (¯ x)|}, ∀i ∈ I < fi (¯ x) + c¯ max {gj+ (¯ 1≤j≤m 1≤k≤q Điều tương đương với x ∈ D, tồn i ∈ I cho x), |hk (¯ x)|} x) + c¯ max {gj+ (¯ fi (x) + c¯ max {gj+ (x), |hk (x)|} ≥ fi (¯ 1≤j≤m 1≤k≤q 1≤j≤m 1≤k≤q Vì x ∈ D, sử dụng (2.4), ta có với x ∈ D, tồn i ∈ I cho x), |hk (¯ x)|} fi (x) ≥ fi (¯ x) + c¯ max {gj+ (¯ 1≤j≤m 1≤k≤q 33 Từ (2.4), ta suy với x ∈ D, tồn i ∈ I cho fi (x) ≥ fi (¯ x) Một cách tương đương, không tồn x ∈ X cho f (x) < f (¯ x) Mệnh đề chứng minh Định lý 2.2.7 Giả sử x¯ nghiệm hữu hiệu yếu tốn tối ưu véc tơ khơng ràng buộc phạt (V P∞ (¯ c)) với hàm phạt minimax xác Giả sử (i) D tập compact Rn , (ii) V P∞ (x, c) ≮ V P∞ (¯ x, c) thỏa mãn với x ∈ D c > c¯ Khi đó, x¯ nghiệm hữu hiệu yếu toán tối ưu véc - tơ (V P ) Hơn nữa, giả sử hàm mục tiêu f ràng buộc bất đẳng thức gj , j ∈ J(¯ x), ràng buộc đẳng thức hk , k ∈ K + (¯ x) = {k ∈ K : ν¯k > 0} lồi X, hàm ràng buộc hk , k ∈ K − (¯ x) = {k ∈ K : ν¯k < 0} lõm X Khi đó, (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) toán tối ưu véc - tơ (V P ) Chứng minh Vì x¯ nghiệm hữu hiệu yếu tốn tối ưu véc - tơ không ràng buộc phạt (V P∞ (¯ c)) với hàm phạt minimax xác, cho nên, từ Mệnh đề 2.2.6, không tồn x ∈ D cho f (x) < f (¯ x) (2.19) Một cách tương đương, với x ∈ D, tồn i ∈ I cho fi (x) ≥ fi (¯ x) (2.20) Trước hết, ta x¯ điểm chấp nhận toán tối ưu véc - tơ (V P ) Giả sử, ngược lại, x¯ điểm khơng chấp nhận tốn (V P ) Từ (2.4), ta suy x), |hk (¯ x)|} > (2.21) max {gj+ (¯ 1≤j≤m 1≤k≤q 34 Giả sử xˆ điểm chấp nhận tốn tối ưu (V P ) Từ giả thiết (ii), với c > c¯, ta có V P∞ (ˆ x, c) ≮ V P∞ (¯ x, c) Từ định nghĩa (V P∞ (¯ c)), ta suy f (ˆ x) + c max {gj+ (ˆ x), |hk (ˆ x)|}e ≮ f (¯ x) + c max {gj+ (¯ x), |hk (¯ x)|}e 1≤j≤m 1≤k≤q 1≤j≤m 1≤k≤q Từ đó, suy tồn i ∈ I cho fi (ˆ x) + c max {gj+ (ˆ x), |hk (ˆ x)|} 1≤j≤m 1≤k≤q x), |hk (¯ x)|} ≥ fi (¯ x) + c max {gj+ (¯ 1≤j≤m 1≤k≤q (2.22) Mặt khác, ta lấy c > max fi (x) − fi (¯ x) , c¯; x ∈ D, i ∈ I + max {gj (¯ x), |hk (¯ x)|} (2.23) 1≤j≤m 1≤k≤q Vì D tập compact Rn , từ (2.20), (2.21) (2.23) ta suy c số thực dương hữu hạn Như vậy, x), |hk (¯ x)|} > fi (ˆ x) − fi (¯ x), ∀i ∈ I c max {gj+ (¯ 1≤j≤m 1≤k≤q Khi đó, x), |hk (¯ x)|} > fi (ˆ x), ∀i ∈ I fi (¯ x) + c max {gj+ (¯ 1≤j≤m 1≤k≤q (2.24) Sử dụng tính chấp nhận xˆ toán tối ưu véc - tơ (V P ) (2.4), ta có c max {gj+ (ˆ x), |hk (ˆ x)|} = (2.25) 1≤j≤m 1≤k≤q 35 Từ (2.24) (2.25), ta suy fi (¯ x) + c max {gj+ (¯ x), |hk (¯ x)|} 1≤j≤m 1≤k≤q > fi (ˆ x) + c max {gj+ (ˆ x), |hk (ˆ x)|}, ∀i ∈ I 1≤j≤m 1≤k≤q Điều mâu thuẫn với (2.22) Vì vậy, x¯ điểm chấp nhận toán tối ưu véc - tơ (V P ) Như vậy, từ (2.19), ta kết luận x¯ nghiệm hữu hiệu yếu toán (V P ) Bây giờ, ta (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) tốn (V P ) Vì x¯ nghiệm hữu hiệu yếu toán tối ưu véc - tơ (V P ), tồn ¯ ∈ Rp+ , µ ¯ ∈ Rm ¯ ∈ Rq cho điều kiện KKT nhân tử Lagrange λ + ν thỏa mãn x¯ Từ điều kiện KKT (2.2) tính chấp nhận x¯ (V P ), ta có µT g(¯ x) ≤ µ ¯T g(¯ x), ∀µ ∈ Rm + Khi đó, ta có f (¯ x) + µT g(¯ x)e + ν T h(¯ x)e ≦ f (¯ x) ¯ ∈ Rq +¯ µT g(¯ x)e + ν¯T h(¯ x)e, ∀µ ∈ Rm +, ν Từ định nghĩa hàm Lagrange véc - tơ, bất đẳng thức kéo theo (2.26) q L(¯ x, µ, ν) ≦ L(¯ x, µ ¯, ν¯), ∀µ ∈ Rm + , ∀ν ∈ R Ta chứng minh Định nghĩa 2.1.10 (ii) điểm yên ngựa (Pareto) (V P ) Giả sử ngược lại L(x, µ ¯, ν¯) < L(¯ x, µ ¯, ν¯), ∀x ∈ X Từ định nghĩa hàm Lagrange véc - tơ, ta nhận f (x) + µ ¯T g(x)e + ν¯T h(x)e < f (¯ x) + µ ¯T g(¯ x)e + ν¯T h(¯ x)e, ∀x ∈ X Khi đó, ta có q m µ ¯j gj (x) + fi (x) + j=1 µ ¯j gj (¯ x) + ν¯k hk (x) < fi (¯ x) + k=1 q m j=1 ν¯k hk (¯ x), k=1 36 với x ∈ X i ∈ I Nhân hai vế bất đẳng thức với ¯ i , i ∈ I, ta λ q m ¯ i fi (x) + λ ¯i λ ¯i µ ¯j gj (x) + λ j=1 ν¯k hk (x) k=1 q m ¯i µ ¯j gj (¯ x) + λ ¯ i fi (¯ ¯i ≤λ x) + λ , j=1 ν¯k hk (¯ x), k=1 với x ∈ X i ∈ I, bất đẳng thức chặt với i ∈ I p ¯ i = 1, ta suy λ Lấy tổng theo i ∈ I sử dụng điều kiện KKT i=1 p q m ¯ i fi (x) + λ i=1 j=1 p k=1 i=1 q m ¯ i fi (¯ λ x) + < ν¯k hk (x) µ ¯j gj (x) + ν¯k hk (¯ x) µ ¯j gj (¯ x) + j=1 (2.27) k=1 với x ∈ X Mặt khác, theo giả thiết, fi , i ∈ I, gj , j ∈ J(¯ x), hk , k ∈ K + (¯ x) lồi − X, hk , k ∈ K (¯ x) lõm X Do đó, ta có x), i ∈ I, fi (x) − fi (¯ x) ≥ ξiT (x − x¯), ∀ξj ∈ ∂fi (¯ (2.28) x), j ∈ J(¯ x), gj (x) − gj (¯ x) ≥ ξˆjT (x − x¯), ∀ξˆj ∈ ∂gj (¯ (2.29) hk (x) − hk (¯ x) ≥ ξ˜kT (x − x¯), ∀ξ˜k ∈ ∂hk (¯ x), k ∈ K + (¯ x), (2.30) x), k ∈ K − (¯ x) hk (x) − hk (¯ x) ≤ ξ˜kT (x − x¯), ∀ξ˜k ∈ ∂hk (¯ (2.31) với x ∈ X ¯ i , i ∈ I, µ Nhân (2.28) − (2.31) với nhân tử Lagrange tương ứng λ ¯j , j ∈ J(¯ x), ν¯k , k ∈ K + (¯ x) ∪ K − (¯ x), ta có ¯ i fi (x) − λ ¯ i fi (¯ ¯ i ξ T (x − x¯), ∀ξi ∈ ∂fi (¯ λ x) ≥ λ x), i ∈ I, i (2.32) µ ¯j gj (x) − µ ¯j gj (¯ x) ≥ µ ¯j ξˆjT (x − x¯), ∀ξˆj ∈ ∂gj (¯ x), j ∈ J(¯ x), (2.33) ν¯k hk (x) − ν¯k hk (¯ x) ≥ ν¯k ξ˜kT (x − x¯), ∀ξ˜k ∈ ∂hk (¯ x), k ∈ K + (¯ x) ∪ K − (¯ x) (2.34) 37 với x ∈ X Lấy tổng theo i ∈ I, j ∈ J(¯ x), k ∈ K + (¯ x) ∪ K − (¯ x) hai vế (2.32) − (2.34), tương ứng, sau cộng bất đẳng thức, ta ¯ i fi (¯ λ x) + ¯ i fi (x) − λ i∈I i∈I µ ¯j gj (x) − j∈J(¯ x) + µ ¯j gj (¯ x) j∈J(¯ x) ν¯k hk (x) − k∈K + (¯ x)∪K − (¯ x) i∈I ν¯k ξ˜kT (x − x¯), µ ¯j ξˆjT + ¯iξ T + λ i ≥ ν¯k hk (¯ x) k∈K + (¯ x)∪K − (¯ x) k∈K + (¯ x)∪K − (¯ x) j∈J(¯ x) ξi ∈ ∂fi (¯ x), i ∈ I, ξˆj ∈ ∂gj (¯ x), j ∈ J(¯ x), ξ˜k ∈ ∂hk (¯ x), k ∈ K + (¯ x) ∪ K − (¯ x), x ∈ X Sử dụng nhân tử Lagrange bất đẳng thức kéo theo p p m ¯ i fi (¯ λ x) + ¯ i fi (x) − λ i=1 i=1 q − µ ¯j gj (x) − j=1 p ν¯k hk (¯ x) ≥ ν¯k ξ˜kT (x − x¯), ∀x ∈ X + j=1 i=1 k=1 k=1 q µ ¯j ξˆjT + ν¯k hk (x) µ ¯j gj (¯ x) + j=1 m ¯iξ T λ i q m k=1 Bằng cách sử dụng điều kiện KKT (2.1), ta thu p p m ¯ i fi (¯ λ x) + ¯ i fi (x) − λ i=1 i=1 j=1 q q m j=1 ν¯k hk (¯ x) ≥ ν¯k hk (x) − µ ¯j gj (¯ x) + − µ ¯j gj (x) k=1 k=1 Khi đó, bất đẳng thức sau tương đương p ¯ i fi (x)+ λ i=1 k=1 i=1 q m ¯ i fi (¯ λ x)+ ν¯k hk (x) ≥ µ ¯j gj (x)+ j=1 p q m ν¯k hk (¯ x) µ ¯j gj (¯ x)+ j=1 k=1 với x ∈ X, mâu thuẫn với (2.27) Vì vậy, ta kết luận (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) toán tối ưu véc - tơ (V P ) Định lý chứng minh 38 Mệnh đề 2.2.8 Giả sử x¯ nghiệm hữu hiệu tốn khơng ràng buộc phạt (V P∞ (¯ c)) với hàm phạt minimax xác Khi đó, không tồn x ∈ D cho f (x) ≤ f (¯ x.) Chứng minh Chứng minh tương tự Mệnh đề 2.2.6 Định lý 2.2.9 Giả sử x¯ nghiệm hữu hiệu yếu tốn khơng ràng buộc phạt (V P∞ (¯ c)) với hàm phạt minimax xác Giả sử (i) D tập compact Rn , (ii) V P∞ (x, c) ≮ V P∞ (¯ x, c) thỏa mãn với x ∈ D c > c¯ Khi đó, x¯ nghiệm hữu hiệu toán tối ưu véc - tơ (V P ) Hơn nữa, giả sử hàm mục tiêu f ràng buộc bất đẳng thức gj , j ∈ J(¯ x), ràng buộc đẳng thức hk , k ∈ K + (¯ x) = {k ∈ K : ν¯k > 0} lồi − X, hàm ràng buộc hk , k ∈ K (¯ x) = {k ∈ K : ν¯k < 0} lõm X Khi đó, (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) toán tối ưu véc - tơ (V P ) Chứng minh Chứng minh tương tự Định lý 2.2.7 Ví dụ 2.2.10 Xét tốn tối ưu véc - tơ sau: (VP1) f (x) = (x21 + 2|x1 | + 4, ex2 + 2|x2 | + 1) g1 (x) = 3x21 − x1 ≤ 0, g2 (x) = 4x22 − x2 ≤ 0, h(x) = x1 − x2 = fi : X → R, i = 1, 2, gj : X → R, j = 1, 2, h : X → R hàm Lipschitz địa phương X = (−1, 1) × (−1, 1) Tập tất điểm chấp nhận (V P 2) cho D = {x = (x1 , x2 ) ∈ X : ≤ x1 ≤ D compact X 1 ∧ ≤ x2 ≤ ∧ x1 = x2 } 39 Bài toán tối ưu véc - tơ không ràng buộc phạt (V P 2∞ (¯ c)) với hàm phạt minimax xác xây dựng sau: V P∞ (x, c¯) =(x21 + 2|x1 | + + c¯ max{max{0, 3x21 − x1 }, max{0, 4x22 − x2 }, |x1 − x2 |}, ex2 + 2|x2 | + + c¯ max{max{0, 3x21 − x1 }, max{0, 4x22 − x2 }, |x1 − x2 |}) Rõ ràng, x¯ = (0, 0) nghiệm hữu hiệu toán tối ưu véc - tơ không ràng buộc phạt (V P 2∞ (¯ c)) với hàm phạt minimax xác, c¯ = Khi đó, với x ∈ D c > c¯, V P∞ (x, c) = (x21 + 2|x1 | + 4, ex2 + 2|x2 | + 1) V P∞ (¯ x, c) = (4, 2) Như vậy, ta suy V P∞ (x, c) ≮ V P∞ (¯ x, c), ∀x ∈ D c > c¯ Do đó, theo Định lý 2.2.9, x¯ = (0, 0) nghiệm hữu hiệu toán tối ưu véc - tơ gốc (V P 2) Hàm Lagrange véc - tơ cho L(x, µ, ν) =(x21 + 2|x1 | + + µ1 (3x21 − x1 ) + µ2 (4x22 − x2 ) + ν(x1 − x2 ), ex2 + 2|x2 | + + µ1 (3x21 − x1 ) + µ2 (4x22 − x22 ) + ν(x1 − x2 )) µ = (µ1 , µ2 ) ∈ R2+ , ν ∈ R e = (1, 1) Vì giả thiết Định lý 2.2.9 thỏa mãn, nên (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) toán tối ưu véc - tơ (V P 2), µ ¯1 = ν¯ + 1, µ ¯2 = − ν¯ −1 ≤ ν¯ ≤ Định lý 2.2.11 Giả sử x¯ điểm chấp nhận toán tối ưu véc - tơ (V P ) cho điều kiện cần KKT (2.1)−(2.3) thỏa mãn x¯ với nhân tử ¯ ∈ Rk , µ Lagrange λ ¯ ∈ Rm ν¯ ∈ Rq Giả sử hàm mục tiêu f ràng buộc bất đẳng thức gj , j ∈ J(¯ x), ràng buộc đẳng thức hk , k ∈ K + (¯ x) = {k ∈ K : − ν¯k > 0} lồi X, hàm ràng buộc hk , k ∈ K (¯ x) = {k ∈ K : ν¯k < 0} lõm X 40 m Hơn nữa, tham số phạt c giả định đủ lớn (tức c ≥ µ ¯j + j=1 q |¯ νk |), x¯ nghiệm hữu hiệu yếu tốn tối ưu véc - tơ khơng ràng k=1 buộc phạt (V P∞ (c)) với hàm phạt minimax xác Chứng minh Trước hết, ta (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) toán tối ưu véc - tơ (V P ) Vì x¯ điểm chấp nhận toán tối ưu véc - tơ (V P ) thỏa mãn điều kiện cần KKT, thế, từ điều kiện KKT (2.2) tính chấp nhận x¯ (V P ), ta có µT g(¯ x) ≤ µ ¯T g(¯ x), ∀µ ∈ Rm + Từ đó, ta suy f (¯ x) + µT g(¯ x)e + ν T h(¯ x)e ≦ f (¯ x) ¯ ∈ Rq +¯ µT g(¯ x)e + ν¯T h(¯ x)e, ∀µ ∈ Rm +, ν Từ định nghĩa hàm Lagrange véc - tơ, bất đẳng thức kéo theo (2.35) q L(¯ x, µ, ν) ≦ L(¯ x, µ ¯, ν¯), ∀µ ∈ Rm + , ∀ν ∈ R Vì fi , i ∈ I, gj , j ∈ J(¯ x), hk , k ∈ K + (¯ x) lồi X, hk , k ∈ K − (¯ x) lõm X, cho nên, tương tự Định lý 2.2.7, ta có p p m i=1 i=1 q k=1 µ ¯j gj (x) − j=1 p i=1 k=1 q ν¯k ξ˜kT (x − x¯), ∀x ∈ X µ ¯j ξˆjT + j=1 ν¯k hk (x) µ ¯j gj (¯ x) + j=1 m ¯iξ T + λ i ν¯k hk (¯ x) ≥ − q m ¯ i fi (¯ λ x) + ¯ i fi (x) − λ k=1 Từ giả thiết, điều kiện cần KKT (2.1) − (2.3) thỏa mãn x¯ Như vậy, sử dụng điều kiện KKT (2.1), bất đẳng thức kéo theo 41 p p m ¯ i fi (¯ λ x) + ¯ i fi (x) − λ i=1 i=1 j=1 q q m − µ ¯j gj (x) j=1 ν¯k hk (¯ x) ≥ 0, ν¯k hk (x) − µ ¯j gj (¯ x) + k=1 k=1 p ¯ i = 1, λ với x ∈ X Bây giờ, sử dụng điều kiện KKT (2.3), tức là, i=1 bất đẳng thức viết sau p q m ¯ i (fi (x) + λ i=1 j=1 k=1 q m ν¯k hk (¯ x)) µ ¯j gj (¯ x) + −(fi (¯ x) + ν¯k hk (x)) µ ¯j gj (x) + j=1 ≥ 0, ∀x ∈ X k=1 ¯ i > với phần tử i ∈ I Từ điều kiện KKT (2.3), ta suy λ Từ suy q m fi (x) + ν¯k hk (x) µ ¯j gj (x) + j=1 k=1 q m − fi (¯ x) + ν¯k hk (¯ x) µ ¯j gj (¯ x) + j=1 ≥ 0, k=1 với i ∈ I với x ∈ X Như vậy, ta nhận f (x) + µ ¯T g(x)e + ν¯T h(x)e ≮ f (¯ x) + µ ¯T g(¯ x)e + ν¯T h(¯ x)e, ∀x ∈ X Từ định nghĩa hàm Lagrange véc - tơ, ta suy L(x, µ ¯, ν¯) ≮ L(¯ x, µ ¯, ν¯), ∀x ∈ X (2.36) Từ (2.35) (2.36), ta suy (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) toán tối ưu véc - tơ (V P ) Vì vậy, sử dụng Định lý 2.2.4, ta kết luận x¯ nghiệm hữu hiệu yếu toán tối ưu véc - tơ không ràng buộc phạt (V P∞ (c)) Định lý chứng minh 42 Hệ 2.2.12 Giả sử x¯ nghiệm hữu hiệu yếu toán tối ưu véc - tơ (V P ) cho điều kiện cần KKT (2.1)−(2.3) thỏa mãn x¯ với nhân tử ¯ ∈ Rk , µ Lagrange λ ¯ ∈ Rm ν¯ ∈ Rq Giả sử hàm mục tiêu f ràng buộc bất đẳng thức gj , j ∈ J(¯ x), ràng buộc đẳng thức hk , k ∈ K + (¯ x) = {k ∈ K : − ν¯k > 0} lồi X, hàm ràng buộc hk , k ∈ K (¯ x) = {k ∈ K : ν¯k < 0} lõm X m Hơn nữa, tham số phạt c giả định đủ lớn (tức c ≥ µ ¯j + j=1 q |¯ νk |), x¯ nghiệm hữu hiệu yếu tốn tối ưu véc - tơ không ràng k=1 buộc phạt (V P∞ (c)) với hàm phạt minimax xác Chứng minh Kết suy trực tiếp từ Định lý 2.2.11, nghiệm hữu hiệu yếu điểm chấp nhận 2.3 Trường hợp đặc biệt Trong phần này, ta xét trường hợp tuyến tính tốn tối ưu véc - tơ (V P ), có nghĩa hàm fi (x), i ∈ I tuyến tính gj (x), j ∈ J hk (x), k ∈ K affine Trong trường hợp giả thiết lồi/ lõm hàm toán tối ưu véc - tơ (V P ) thỏa mãn Ví dụ sau minh họa cách tiếp cận hàm phạt minimax xác để tìm nghiệm tốn tối ưu véc - tơ tuyến tính Ví dụ 2.3.1 Xét tốn tối ưu véc - tơ tuyến tính sau (VP3) f (x) = (x1 + x2 , 2x1 − 3x2 ) g1 (x) = − x1 ≤ 0, g2 (x) = x1 − ≤ 0, g3 (x) = − x2 ≤ 0, g4 (x) = x2 − ≤ 0, h(x) = x1 − x2 + = fi : X → R, i = 1, 2, gj : X → R, j = 1, 2, 3, h : X → R hàm Lipschitz địa phương X = (0, 3) × (0, 3) Tập điểm chấp nhận (V P 3) cho D = {x = (x1 , x2 ) ∈ X : ≤ x1 ≤ ∧ ≤ x2 ≤ ∧ x2 = x1 + 1} D compact Bây giờ, toán tối ưu véc - tơ không ràng buộc phạt 43 (V P 3∞ (¯ c)) với hàm phạt minimax xác xây dựng sau: V P∞ (x, c¯) =(x1 + x2 + c¯ max{max{0, − x1 }, max{0, x1 − 2}, max{0, − x2 }, max{0, x2 − 3}, |x1 − x2 + 1|}, 2x1 − 3x2 + c¯ max{max{0, − x1 }, max{0, x1 − 2}, max{0, − x2 }, max{0, x2 − 3}, |x1 − x2 + 1|}) Rõ ràng, x¯ = (1, 2) nghiệm hữu hiệu toán tối ưu véc - tơ không ràng buộc phạt (V P 3∞ (¯ c)) với hàm phạt minimax xác, c¯ = Khi đó, với x ∈ D c > c¯, V P∞ (x, c) = (x1 + x2 , 2x1 − 3x2 ) V P∞ (¯ x, c) = (3, −4) Như vậy, ta suy V P∞ (x, c) ≮ V P∞ (¯ x, c), ∀x ∈ D c > c¯ Do đó, theo Định lý 2.2.9, x¯ = (1, 2) nghiệm hữu hiệu toán tối ưu véc - tơ gốc (V P 3) Hàm Lagrange véc - tơ cho L(x, µ, ν) =(x1 + x2 + µ1 (1 − x1 ) + µ2 (x1 − 2) + µ3 (2 − x2 ) + µ4 (x2 − 3) + ν(x1 − x2 + 1), 2x1 − 3x2 + µ1 (1 − x1 ) + µ2 (x1 − 2) + µ3 (2 − x2 ) + µ4 (x2 − 3) + ν(x1 − x2 + 1)), µ = (µ1 , µ2 , µ3 , µ4 ) ∈ R4+ , ν ∈ R e = (1, 1) Bởi giả thiết Định lý 2.2.9 thỏa mãn, nên (¯ x, µ ¯, ν¯) điểm yên ngựa (Pareto) toán tối ưu véc - tơ (V P 3), µ ¯ = (1, 0, 1, 0), ν¯ = Tương tự, nghiệm hữu hiệu điểm yên ngựa véc - tơ nhiều toán tối ưu véc - tơ tuyến tính phức tạp tìm phương pháp hàm phạt minimax xác 44 Kết luận Luận văn trình bày phương pháp hàm phạt minimax xác định lý điểm yên ngựa Antczak [2] cho toán tối ưu đơn mục tiêu có ràng buộc, Jayswall - Choudhury [7] cho toán tối ưu véc - tơ lồi khơng trơn có ràng buộc Luận văn bao gồm nội dung sau đây: - Phương pháp hàm phạt minimax xác T Antczak [2] cho tốn tối ưu đơn mục tiêu khơng khả vi có ràng buộc đẳng thức bất đẳng thức; - Sự tương đương toán tối ưu đơn mục tiêu có ràng buộc tốn tối ưu phạt khơng có ràng buộc tham số phạt lớn ngưỡng thích hợp; - Phương pháp hàm phạt minimax xác A Jaywall S Choudhury [7] cho tốn tối ưu véc - tơ lồi khơng trơn có ràng buộc đẳng thức bất đẳng thức; - Định lý điểm yên ngựa cho toán tối ưu véc - tơ lồi khơng trơn; - Các ví dụ minh họa cho kết trình bày Phương pháp hàm phạt minimax xác cho tốn tối ưu không trơn đề tài nhiều tác giả quan tâm nghiên cứu 45 Tài liệu tham khảo Tiếng Việt [1] Đỗ Văn Lưu (2000), Giải tích lồi, NXB Khoa Học Kỹ Thuật, Hà Nội Tiếng Anh [2] Antczak T (2013), "A lower bound for the penalty parameter in the exact minimax penalty function method for solving nondifferentiable extremum problems", J Optim Theory Appl 159, pp 437 – 453 [3] Antczak T (2013), "Saddle point criteria and the exact minimax penalty function method in nonconvex programming", Taiwan J Math 17, pp 559 – 581 [4] Charalambous, Ch (1978), "A lower bound for the controlling parameters of the exact penalty functions", Math Program 15, pp 278 – 290 [5] Craven, B.D (1989), "Nonsmooth multiobjective programming", Numer Funct Anal Optim 10, pp 49 – 64 [6] Kim, M.H (2005), "Duality theorem and vector saddle point theorem for nonsmooth vector optimization problem", J Appl Math Comput 18, pp 539 – 551 [7] Jayswal A., Choudhury S (2016) , "An exact minimax penalty function method and saddle point criteria for nonsmooth convex vector optimization problems", J Optim Theory Appl 169 , pp 179 – 199 [8] Pietrzykowski, T (1969), "An exact potential method for constrained maxima ", SIAM J Numer Anal 6, pp 294 – 304 [9] Rockafellar, R.T (1970), Convex Analysis, Princeton University Press Princeton, New Jersey ... Lagrange hàm phạt minimax xác tốn tối ưu phạt hàm phạt minimax xác véc - tơ tốn tối ưu véc - tơ phạt Mở đầu Phương pháp hàm phạt xác cho phép đưa tốn tối ưu phi tuyến có ràng buộc tốn tối ưu khơng... minimax toán tối ưu phạt với hàm phạt minimax xác Ý tưởng phương pháp hàm phạt minimax xác giải tốn tối ưu có ràng buộc phi tuyến (P ) qua toán tối ưu khơng có ràng buộc (P∞ (c)) Hàm phạt minimax xác. .. phương pháp hàm phạt minimax xác định lí điểm n ngựa cho tốn tối ưu véc - tơ lồi không trơn với hàm Lipschitz địa phương 4 Chương Cận tham số phạt phương pháp hàm phạt minimax xác cho tốn tối ưu