ĐẠ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�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 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 tố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 ... 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... đầ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... 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