Luận văn Thạc sĩ Toán học: Phương pháp hàm phạt minimax chính xác cho bài toán tối ưu không trơn

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:49

Thêm vào BST

Báo xấu

36
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của luận văn trình bày phương pháp hàm phạt minimax chính xác và các định lí điểm yên ngựa cho bài toán tối ưu đơn mục tiêu của T. Antczak (đăng trong Tạp chí J. Optim. Theory Appl. 159 (2013), 437 - 453) và cho bài toán tối ưu véc - tơ của A. Jayswal - S. Choudhury (đăng trong Tạp chí J. Optim. Theory Appl. 169 (2016), 179 - 199) có ràng buộc đẳng thức và bất đẳng thức. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Phương pháp hàm phạt minimax chính xác cho bài toán tối ưu không trơn

ĐẠ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 TOÁ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 TOÁN TỐI ƯU KHÔNG TRƠN 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. ĐỖ 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 1 Mở đầu 2 1 Cận dưới của tham số phạt của phương pháp hàm phạt min- imax chính xác cho bài toán tối ưu đơn mục tiêu không khả vi 4 1.1 Các khái niệm và kết quả liên quan . . . . . . . . . . . . . . . 4 1.2 Phương pháp hàm phạt minimax chính xác . . . . . . . . . . . 6 1.3 Sự tương đương của bài toán tối ưu có ràng buộc và bài toán tối ưu phạt . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Phương pháp hàm phạt minimax chính xác và định lí điểm yên ngựa cho bài toán tối ưu véc - tơ lồi không trơn 22 2.1 Các khái niệm và kết quả bổ trợ . . . . . . . . . . . . . . . . . 22 2.2 Phương pháp hàm phạt minimax chính xác và định lí điểm yên ngựa cho bài toán tối ưu véc - tơ không trơn . . . . . . . . 25 2.3 Trường hợp đặc biệt . . . . . . . . . . . . . . . . . . . . . . . 42 Kết luận 44 Tài liệu tham khảo chính 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 tôi PGS.TS. Đỗ Văn Lưu, người đã trực tiếp hướng dẫn luận văn, đã tận tình chỉ bảo và hướng dẫn tôi tìm ra hướng nghiên cứu, tìm kiếm tài liệu, giải quyết vấn đề,... nhờ đó tôi mới có thể hoàn thành luận văn cao học của mình. Từ tận đáy lòng, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới Thầy của tôi và tôi sẽ cố gắng hơn nữa để xứng đáng với công lao của 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 và giúp đỡ tôi trong suốt thời gian học tập tại trường. Tôi xin cảm ơn quý thầy cô Khoa Toán - Tin và đặc biệt là PGS.TS. Nguyễn Thị Thu Thủy, trưởng Khoa Toán - Tin, đã luôn quan tâm, động viên, trao đổi và đóng góp những ý kiến quý báu trong suốt quá trình học tập, nghiên cứu và 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 những người thân trong gia đình, đặc biệt là bố mẹ. Những người luôn động viên, chia sẻ mọi khó khăn cùng tôi trong suốt thời gian qua và đặc biệt là trong thời gian tôi theo học khóa thạc sỹ tại trường Đại học Khoa học - Đại học Thái Nguyên. Thái Nguyên, ngày 24 tháng 4 năm 2017 Tác giả luận văn Tô Minh Quyết
1 Bảng ký hiệu R trường số thực Rn không gian Euclide n-chiều Rm + orthant không âm của Rm T chuyển vị của véc - tơ KKT Karush-Kuhn-Tucker B là hình cầu đơn vị mở trong Rn ∂fi (x) dưới vi phân của hàm lồi fi tại x ∧ và ∨ hoặc I(¯x) tập các chỉ số ràng buộc tích cực + gi bằng 0 nếu gi (x) ≤ 0, bằng gi (x) nếu gi (x) > 0 L(x, µ, ν) hàm Lagrange P∞ (x, c) hàm phạt minimax chính xác (P∞ (c)) bài toán tối ưu phạt V P∞ (x, c) hàm phạt minimax chính xác véc - tơ (V P∞ (c)) bài toán tối ưu véc - tơ phạt
2 Mở đầu Phương pháp hàm phạt chính xác cho phép đưa một bài toán tối ưu phi tuyến có ràng buộc về một bài toán tối ưu không có ràng buộc sao cho nghiệm của bài toán tối ưu phạt cũng là nghiệm của bài toán tối ưu có ràng buộc ban đầu. Antczak ([2], 2013) đã nghiên cứu mối quan hệ giữa nghiệm của bài toán tối ưu vô hướng có ràng buộc và nghiệm của bài toán tối ưu không có ràng buộc với hàm mục tiêu là một hàm phạt minimax chính xác và chỉ ra cận dưới của tham số phạt để hai bài toán đó tương đương. Jayswall - Choudhury ([7], 2016) đã thiết lập các định lí điểm yên ngựa cho bài toán tối ưu véc - tơ có ràng buộc bằng phương pháp hàm phạt minimax chính xác và xác định các điều kiện để bài toán tối ưu véc - tơ có ràng buộc tương đương với bài toán không có ràng buộc bằng phương pháp hàm phạt minimax chính xác. Đây là đề tài nhiều tác giả quan tâm nghiên cứu. Chính vì vậy, tôi chọn đề tài: "Phương pháp hàm phạt minimax chính xác cho bài toán tối ưu không trơn". Mục đích của luận văn trình bày phương pháp hàm phạt minimax chính xác và các định lí điểm yên ngựa cho bài toán tối ưu đơn mục tiêu của T. Antczak (đăng trong Tạp chí J. Optim. Theory Appl. 159 (2013), 437 - 453) và cho bài toán tối ưu véc - tơ của A. Jayswal - S. Choudhury (đăng trong Tạp chí J. Optim. Theory Appl. 169 (2016), 179 - 199) có ràng buộc đẳng thức và 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 của luận văn, phần kết luận và danh mục tài liệu tham khảo.
3 Chương 1: "Cận dưới của tham số phạt của phương pháp hàm phạt mini- max chính xác cho bài toán tối ưu đơn mục tiêu không khả vi" trình bày các kết quả của Antczak [2] về phương pháp hàm phạt minimax chính xác, và sự tương đương của bài toán tối ưu có ràng buộc và bài toán tối ưu không có ràng buộc phạt được chứng minh khi tham số phạt lớn hơn một giá trị cận dưới. Chương 2: "Phương pháp hàm phạt minimax chính xác và định lí điểm yên ngựa cho bài toán tối ưu véc - tơ lồi không trơn" trình bày các kết quả của Jayswal - Choudhury [7], phương pháp hàm phạt minimax chính xác và các định lí điểm yên ngựa cho bài toán tối ưu véc - tơ lồi không trơn với các hàm Lipschitz địa phương.
4 Chương 1 Cận dưới của tham số phạt của phương pháp hàm phạt minimax chính xác cho bài toán tối ưu đơn mục tiêu không khả vi Chương này trình bày phương pháp hàm phạt minimax chính xác và sự tương đương của bài toán tối ưu có ràng buộc và bài toán tối ưu phạt không có ràng buộc. Các kết quả trình bày trong chương này là của T. Antczak [2]. 1.1 Các khái niệm và kết quả liên quan Hàm f : X → R xác định trên tập lồi X ⊂ Rn được gọi là lồi nếu với ∀z, x ∈ R và λ ∈ [0, 1], ta có f (λz + (1 − λ)x) ≤ λf (z) + (1 − λ)f (x). Định nghĩa 1.1.1 Dưới vi phân của hàm lồi f : Rn → R tại x ∈ Rn được xác định 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 của hàm lõm f : Rn → R tại x ∈ Rn được xác định như sau: ∂f (x) := {ξ ∈ Rn : f (z) − f (x) ≤ ξ T (z − x), ∀z ∈ Rn }.
5 Nhận xét 1.1.3 Từ định nghĩa của hàm lồi f : Rn → R tại x, suy ra: f (z) − f (x) ≥ ξ T (z − x), ∀ξ ∈ ∂f (x), (1.1) đúng với ∀z ∈ Rn , trong đó ∂f (x) kí hiệu dưới vi phân của f tại x. Tương tự, với hàm lõm f : Rn → R tại x, ta có bất đẳng thức: f (z) − f (x) ≤ ξ T (z − x), ∀ξ ∈ ∂f (x), (1.2) đúng với ∀z ∈ Rn . Trước khi chứng minh kết quả chính cho bài toán (P ), ta cần bổ đề sau đây: Bổ đề 1.1.4 Giả sử ϕk , k = 1, ..., p, là hàm giá trị thực xác định trên X ⊂ Rn . Với x ∈ X, ta có p X max ϕk (x) = max αk ϕk (x), 1≤k≤p α∈Ω k=1 p X trong đó Ω := {α = (α1 , ..., αp ) ∈ Rp+ : αk = 1}. k=1 Bài toán cực trị đã xét ở đây là bài toán tối ưu phi tuyến tổng quát có ràng buộc đẳng thức và bất đẳng thức: (P ) min f (x), x ∈ D = {x ∈ X : gi (x) ≤ 0, i ∈ I, hj (x) = 0, j ∈ J}, trong đó I = {1, ..., m}, J = {1, ..., s}, f : X → R và gi : X → R, i ∈ I, hj : X → R, j ∈ J là các hàm Lipschitz địa phương trên tập khác rỗng X ∈ Rn và D là tập chấp nhận được của bài toán (P ). Để đơn giản ta sẽ đưa vào một số kí hiệu: g := (g1 , ..., gm ) : X → Rm và h := (h1 , ..., hs ) : X → Rs . Hơn nữa, ta kí hiệu tập các chỉ số ràng buộc bất đẳng thức tích cực tại x∈D I(¯ x) := {i ∈ I : gi (¯ x) = 0}.
6 Định lý 1.1.5 [9] Giả sử x¯ là nghiệm của bài toán (P ) và một điều kiện chính quy thích hợp thỏa mãn tại x¯. Khi đó tồn tại các nhận tử Lagrange ¯ ∈ Rm và µ λ ¯ ∈ Rs sao cho m X s X 0 ∈ ∂f (¯ x) + ¯ i ∂gi (¯ λ x) + µ ¯i ∂hj (¯ x), (1.3) i=1 j=1 ¯ i gi (¯ λ x) = 0, i ∈ I, (1.4) ¯ ≥ 0. λ (1.5) Định nghĩa 1.1.6 Điểm x¯ ∈ D được gọi là điểm Karush-Kuhn-Tucker trong ¯ ∈ Rm và µ bài toán (P ) nếu tồn tại nhân tử Lagrange λ ¯ ∈ Rs sao cho điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3) − (1.5) đúng. 1.2 Phương pháp hàm phạt minimax chính xác Năm 1978 Charalambous [4] đưa vào một lớp các hàm phạt chính xác không khả vi như sau: m s ! p1 X X + p Pp (x, α, β, c) := f (x) + c [αi gi (x)] + [βj |h+ j (x)|] p i=1 j=1 trong đó c là tham số phạt, p ≥ 1, αi > 0, i = 1, ..., m, βj > 0, j = 1, ..., s. Với một ràng buộc bất đẳng thức gi (x) ≤ 0, hàm gi+ (x) được định nghĩa bởi ( 0, gi (x) ≤ 0, gi+ (x) := (1.6) gi (x), gi (x) > 0. là bằng 0 với mọi x thỏa mãn ràng buộc và có giá trị dương khi ràng buộc này bị vi phạm. Hơn nữa, sự vi phạm lớn ở gi (x) ≤ 0 đạt giá trị gi+ (x). Như vậy hàm gi+ (x) có được điểm phạt liên quan với ràng buộc gi (x) ≤ 0. Với p = 1 và xét các tham số αi , i = 1, ..., m, βj , j = 1, ..., s bằng 1, ta nhận được hàm phạt chính xác không khả vi được gọi là hàm phạt chính xác l1 (ta cũng gọi là hàm phạt giá trị tuyệt đối). Phương pháp hàm phạt chính xác l1 đã được đưa vào bởi Pietrzykowski [8]. Đa số các tài liệu về phương pháp hàm phạt chính xác không khả vi nghiên cứu các điều kiện đảm bảo nghiệm tối ưu của bài toán có ràng buộc đã cho cũng là cực tiểu địa phương của bài toán với hàm phạt chính xác không có ràng buộc.
7 Với p = ∞, ta nhận được hàm phạt minimax chính xác được cho bởi: P∞ (x, c) := f (x) + c max {gi+ (x), |hj (x)|}. (1.7) 1≤i≤m 1≤j≤s Bây giờ, ta sử dụng hàm phạt minimax chính xác giải các bài toán cực trị (P ). Với bài toán cực trị (P ), ta xây dựng bài toán tối ưu phạt: (P∞ (c)) P∞ (x, c) := f (x) + c max {gi+ (x), |hj (x)|} → min . (1.8) 1≤i≤m 1≤j≤s Ta gọi bài toán tối ưu không ràng buộc xác định ở trên là bài toán tối ưu phạt minimax hay là bài toán tối ưu phạt với hàm phạt minimax chính xác. Ý tưởng của phương pháp hàm phạt minimax chính xác là giải bài toán tối ưu có ràng buộc phi tuyến (P ) qua bài toán tối ưu không có ràng buộc (P∞ (c)). Hàm phạt minimax chính xác của (P ) là P∞ (x, c) được cho bởi (1.7), trong đó c > 0 là tham số phạt, với tính chất là tồn tại một cận dưới c¯ ≥ 0 sao cho với c > c¯ nghiệm tối ưu bất kì của (P ) cũng là một cực tiểu của bài toán tối ưu phạt (P∞ (c)) với hàm phạt minimax chính xác. 1.3 Sự tương đương của bài toán tối ưu có ràng buộc và bài toán tối ưu phạt Trước hết, ta chỉ ra một điểm Karush-Kuhn-Tucker (KKT) trong bài toán tối ưu có ràng buộc (P ) sẽ cho ta một cực tiểu của hàm phạt minimax chính xác trong bài toán tối ưu phạt (P∞ (c)) với tham số phạt c trên một ngưỡng thích hợp nào đó. Định lý 1.3.1 Giả sử x¯ là điểm Karush-Kuhn-Tucker và điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3) − (1.5) thỏa mãn tại x¯ với các nhân tử Lagrange ¯ ∈ Rm và µ λ ¯ ∈ Rs . Kí hiệu J + (¯ x) := {j ∈ J : µ ¯j > 0} và J − (¯ x) := {j ∈ J : µ ¯j < 0}. Hơn nữa, ta giả sử hàm mục tiêu f và hàm ràng buộc gi , i ∈ I(¯ x) là lồi trên X, còn hàm ràng buộc hj , j ∈ J − (¯ x), hj , j ∈ J + (¯ x) Xm s X là lõm trên X. Nếu c đủ lớn (tức là c ≥ λ¯i + µj |, trong đó λ¯i , i = |¯ i=1 i=1 1, ..., m, µ ¯j , j = 1, ..., s là các nhân tử Lagrange ứng với gi và hj ), thì x¯ cũng là cực tiểu của bài toán tối ưu phạt (P∞ (c)) với hàm phạt minimax chính xác.
8 Chứng minh. Xét hai trường hợp: m X s X (i) ¯i + λ |¯ µj | > 0. i=1 i=1 Theo giả thiết, ta có hàm mục tiêu f và hàm ràng buộc gi , i ∈ I(¯ x), hj , j ∈ x) là lồi trên X. Hơn nữa, các hàm ràng buộc hj , j ∈ J − (¯ J + (¯ x) là lõm trên X. Khi đó, từ (1.1) và (1.2), ta có x) ≥ ξ T (x − x¯), f (x) − f (¯ (1.9) x) ≥ ηiT (x − x¯), i ∈ I(¯ gi (x) − gi (¯ x), (1.10) x) ≥ ζjT (x − x¯), j ∈ J + (¯ hj (x) − hj (¯ x), (1.11) x) ≤ ζjT (x − x¯), j ∈ J − (¯ hj (x) − hj (¯ x) (1.12) đúng với ∀x ∈ X và ∀ξ ∈ ∂f (¯ x), ηi ∈ ∂gi (¯ x), i ∈ I(¯ x), ζj ∈ ∂hj (¯ x), j ∈ + J (¯ − x) ∪ J (¯x), tương ứng. Vì λ ¯ i ≥ 0, i ∈ I, µ + ¯j > 0, j ∈ J (¯ x), và − ¯j < 0, j ∈ J (¯ µ x), cho nên (1.10) − (1.12) kéo theo, ∀x ∈ X, ¯ i gi (x) − λ λ ¯ i gi (¯ ¯ i η T (x − x¯), i ∈ I(¯ x) ≥ λ x), i ¯j hj (x) − µ µ x) ≥ µ ¯j hj (¯ x) ∪ J − (¯ ¯j ζjT (x − x¯), j ∈ J + (¯ x). Sử dụng các nhân tử Lagrange bằng 0, ta nhận được ¯ i gi (x) − λ λ ¯ i gi (¯ ¯ i η T (x − x¯), i ∈ I, x) ≥ λ (1.13) i ¯j hj (x) − µ µ ¯j hj (¯ ¯j ζjT (x − x¯), j ∈ J. x) ≥ µ (1.14) Lấy tổng hai vế của (1.13) và (1.14) theo i và j, ta được m X m X m X ¯ i gi (x) − λ ¯ i gi (¯ λ x) ≥ ¯ i η T (x − x¯), λ (1.15) i i=1 i=1 i=1 s X s X s X ¯j hj (x) − µ µ x) ≥ ¯j hj (¯ ¯j ζjT (x − x¯). µ (1.16) j=1 j=1 j=1
9 Bây giờ, ta cộng hai vế của (1.9), (1.15) và (1.16), ta nhận được m X m X s X s X f (x) − f (¯ x) + ¯ i gi (x) − λ ¯ i gi (¯ λ x) + ¯j hj (x) − µ µ ¯j hj (¯ x) i=1 i=1 j=1 j=1 " m s # X X ≥ ξT + ¯iηT + λ ¯j ζjT (x − x¯). µ i i=1 j=1 Do điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3), ta suy ra m X m X s X s X f (x) − f (¯ x) + ¯ i gi (x) − λ ¯ i gi (¯ λ x) + ¯j hj (x) − µ µ x) ≥ 0. ¯j hj (¯ i=1 i=1 j=1 j=1 Như vây, ta có m X s X f (x) + ¯ i gi (x) + λ µ ¯j hj (x) i=1 j=1 m X s X ≥ f (¯ x) + ¯ i gi (¯ λ x) + µ ¯j hj (¯ x). (1.17) i=1 j=1 Bây giờ, sử dụng điều kiện cần tối ưu Karush-Kuhn-Tucker (1.4) cùng với tính chất nhận được của x¯ trong bài toán (P ), ta có bất đẳng thức m X s X f (x) + ¯ i gi (x) + λ ¯j hj (x) ≥ f (¯ µ x) i=1 j=1 đúng với mọi x ∈ X. Như vậy, do (1.6), ta suy ra m X s X f (x) + ¯ i g + (x) λ + |¯ µj ||hj (x)| ≥ f (¯ x). i i=1 j=1 m X s X Chia hai vế của bất đẳng thức trên cho ¯i + λ |¯ µj | > 0. i=1 j=1
10 Khi đó, m 1 X λ¯i m s f (x) + m s gi+ (x) X X X X ¯i + λ |¯ µj | i=1 ¯i + λ |¯ µj | i=1 j=1 i=1 j=1 s X |¯ µj | 1 + m s |hj (x)| ≥ m s f (¯ x). (1.18) X X X X j=1 ¯i + λ |¯ µj | ¯i + λ |¯ µj | i=1 j=1 i=1 j=1 Ta kí hiệu ¯i λ α ¯k = m s , k = 1, ..., m. (1.19) X X ¯i + λ |¯ µj | i=1 j=1 |¯ µj | α ¯ m+k = m s , k = 1, ..., s. (1.20) X X ¯i + λ |¯ µj | i=1 j=1 ϕk (x) = gk+ (x), k = 1, ..., m. (1.21) ϕm+k (x) = |hj (x)|, k = 1, ..., s. (1.22) Chú ý rằng, theo (1.19) và (1.20), ta có m+s X ¯ k ≥ 0, k = 1, ..., m + s, α α ¯ k = 1. (1.23) k=1 Kết hợp (1.18) − (1.22), ta suy ra với mọi x ∈ X, m+s 1 X 1 m s f (x) + ¯ k ϕk (x) ≥ α m s f (¯ x). X X X X ¯i + λ |¯ µj | k=1 ¯i + λ |¯ µj | i=1 j=1 i=1 j=1 Như vậy, do (1.19) − (1.22), ta suy ra m+s 1 X 1 m s f (x) + max αk ϕk (x) ≥ m s f (¯ x), X X α∈Ω X X ¯i + λ |¯ µj | k=1 ¯i + λ |¯ µj | i=1 j=1 i=1 j=1
11 m+s X trong đó Ω := {α = (α1 , ..., αm+s ) ∈ Rm+s + : αk = 1}. Theo bổ đề k=1 1.1.4, suy ra 1 1 m s f (x) + max ϕk (x) ≥ m s f (¯ x). X X 1≤k≤m+s X X ¯i + λ |¯ µj | ¯i + λ |¯ µj | i=1 j=1 i=1 j=1 Vì vậy, (1.21) và (1.22) kéo theo 1 m s f (x) + max {gi+ (x), |hj (x)|} X X 1≤i≤m ¯i + λ |¯ µj | 1≤j≤s i=1 j=1 1 ≥ m s f (¯ x). (1.24) X X ¯i + λ |¯ µj | i=1 j=1 Theo giả thiết, x¯ là nghiệm tối ưu của bài toán (P ). Do đó, nó là điểm chấp nhận được của bài toán (P ). Vì vậy, do (1.6), ta có max {gi+ (¯ x), |hj (¯ x)|} = 0. (1.25) 1≤i≤m 1≤j≤s Kết hợp (1.24) và (1.25), ta thu được 1 m s f (x) + max {gi+ (x), |hj (x)|} X X 1≤i≤m ¯i + λ |¯ µj | 1≤j≤s i=1 j=1 1 ≥ m s x) + max {gi+ (¯ f (¯ x), |hj (¯ x)|}. X X 1≤i≤m ¯i + λ |¯ µj | 1≤j≤s i=1 j=1
12 m X s X Nhân bất đẳng thức trên với ¯i + λ |¯ µj | > 0, ta nhận được i=1 j=1 m s ! X X f (x) + ¯i + λ |¯ µj | max {gi+ (x), |hj (x)|} 1≤i≤m i=1 j=1 1≤j≤s m s ! X X ≥ f (¯ x) + ¯i + λ |¯ µj | max {gi+ (¯ x), |hj (¯ x)|}. 1≤i≤m i=1 j=1 1≤j≤s m X s X Theo giả thiết, c ≥ ¯i + λ |¯ µj |. Vì vậy, theo (1.25), bất đẳng thức i=1 j=1 sau x) + c max {gi+ (¯ f (x) + c max {gi+ (x), |hj (x)|} ≥ f (¯ x), |hj (¯ x)|} 1≤i≤m 1≤i≤m 1≤j≤s 1≤j≤s đúng với mọi x ∈ X. Theo định nghĩa của hàm phạt minimax chính xác P∞ (x, c), ta suy ra P∞ (x, c) ≥ P∞ (¯ x, c) (1.26) đúng với mọi x ∈ X. Điều này có nghĩa x¯ là nghiệm tối ưu của bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác. m X s X (ii) ¯i + λ |¯ µj | = 0. i=1 i=1 Khi đó, sử dụng (1.9) và điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3), ta có f (x) ≥ f (¯ x) m X s X đúng với mọi x ∈ X. Vì ¯i + λ |¯ µj | = 0, nên bất đẳng thức trên i=1 i=1 kéo theo m X s X ¯i + µj | max {gi+ (x), |hj (x)|} f (x) + λ |¯ 1≤i≤m i=1 j=1 1≤j≤s m X s X ¯i + µj | max {gi+ (¯ ≥ f (¯ x) + λ |¯ x), |hj (¯ x)|}. 1≤i≤m i=1 j=1 1≤j≤s
13 m X s X Theo giả thiết, c ≥ ¯i + λ |¯ µj | = 0. Do đó, kết hợp với bất đẳng i=1 i=1 thức trên và (1.25), ta có bất đẳng thức sau f (x) + c max {gi+ (x), |hj (x)|} ≥ f (¯ x) + c max {gi+ (¯ x), |hj (¯ x)|} 1≤i≤m 1≤i≤m 1≤j≤s 1≤j≤s đúng với mọi x ∈ X. Theo định nghĩa của hàm phạt minimax chính xác P∞ (x, c), ta suy ra bất đẳng thức sau P∞ (x, c) ≥ P∞ (¯ x, c) (1.27) đúng với mọi x ∈ X. Điều này có nghĩa là x¯ là nghiệm tối ưu của bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác. Vì vậy, từ (1.26) và (1.27), với mọi c ≥ m P ¯ Ps λ i=1 i + i=1 |¯ µj |, điểm Karush-Kuhn-Tucker x¯ của bài toán tối ưu có ràng buộc là một cực tiểu của bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác. Định lý được chứng minh. Hệ quả 1.3.2 Giả sử x¯ là một nghiệm tối ưu của bài toán (P ). Hơn nữa, giả sử rằng hàm mục tiêu f và hàm ràng buộc gi , i ∈ I(¯ x), hj , j ∈ J + (¯ x) − là lồi trên X, các hàm ràng buộc hj , j ∈ J (¯x) là lõm trên X. Nếu tồn tại Xm X s tham số phạt c là đủ lớn (sao cho c ≥ ¯i + λ |¯ µj |, trong đó λ ¯i, i = i=1 i=1 1, ..., m, µ ¯j , j = 1, ..., s là các nhân tử Lagrange ứng với gi và hj ), thì x¯ cũng là cực tiểu của bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác. Mệnh đề 1.3.3 Giả sử x¯ là cực tiểu của bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác. Khi đó, ta có bất đẳng thức f (x) ≥ f (¯ x) đúng với mọi x ∈ D. Chứng minh. Vì x¯ là nghiệm của bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác, bất đẳng thức P∞ (x, c) ≥ P∞ (¯ x, c) đúng với mọi x ∈ X. Theo định nghĩa của hàm phạt minimax chính xác
14 P∞ (x, c), ta suy ra bất đẳng thức sau f (x) + c max {gi+ (x), |hj (x)|} ≥ f (¯ x) + c max {gi+ (¯ x), |hj (¯ x)|} 1≤i≤m 1≤i≤m 1≤j≤s 1≤j≤s đúng với mọi x ∈ X. Như vậy, từ (1.6), mọi x ∈ D, ta có x) + c max {gi+ (¯ f (x) ≥ f (¯ x), |hj (¯ x)|} 1≤i≤m 1≤j≤s Lại sử dụng (1.6), ta có bất đẳng thức f (x) ≥ f (¯ x) đúng với mọi x ∈ D. Mệnh đề được chứng minh. Bây giờ, với giả thiết lồi thích hợp cho các hàm có trong bài toán (P ), ta chứng minh kết quả ngược lại. Như vậy, ta sẽ chỉ ra rằng tồn tại một ngưỡng c¯ sao cho mọi tham số phạt c vượt quá giá trị này, x¯, là một cực tiểu trong bài toán phạt (P∞ (c)) với hàm phạt minimax chính xác cũng là nghiệm tối ưu của bài toán cực trị (P ). Định lý 1.3.4 Giả sử x¯ là một cực tiểu của bài toán phạt (P∞ (c)) với hàm Xm phạt minimax chính xác và tham số phạt c đủ lớn (có nghĩa là c > ˜i + λ i=1 s |µ˜j |, trong đó x˜ là một điểm Karush-Kuhn-Tucker của (P ) với các nhân X j=1 tử Lagrange λ ˜ ∈ Rm và µ˜ ∈ Rs ). Hơn nữa, giả sử rằng hàm mục tiêu f và hàm ràng buộc gi , i ∈ I(˜ x), hj , j ∈ J + (˜ x) là lồi trên X, các hàm ràng buộc hj , j ∈ J − (˜ x) là lõm trên X. Nếu D là tập các nghiệm chấp nhận được của bài toán (P ) là tập compact thì x¯ cũng là nghiệm của bài toán cực trị (P ). Chứng minh. Để chứng minh x¯ là nghiệm tối ưu của (P ), trước hết chỉ ra x¯ là điểm chấp nhận được của (P ). Dùng phương pháp phản chứng, chúng ta giả sử x¯ là không chấp nhận được của (P ). Vì f liên tục, bị chặn dưới trên tập compact D, theo định lý Weierstrass, f đạt cực tiểu x˜ trên D. Vì vậy, bài toán cực trị (P ) có nghiệm tối ưu x˜. Do đó điều kiện cần tối ưu Karush-Kuhn-Tucker thỏa mãn tại x˜ với các nhân tử Lagrange λ ˜ ∈ Rm và µ ˜ ∈ Rs . Theo giả thiết, hàm mục tiêu f và hàm ràng buộc gi , i ∈ I(˜ x), hj , j ∈ J + (˜ x) là lồi trên X,
15 các hàm ràng buộc hj , j ∈ J − (˜ x) là lõm trên X. Vì vậy, theo (1.1) và (1.2), ta có các bất đẳng thức sau x) ≥ ξ T (x − x˜), f (x) − f (˜ x) ≥ ηiT (x − x˜), i ∈ I(˜ gi (x) − gi (˜ x), x) ≥ ζjT (x − x˜), j ∈ J + (˜ hj (x) − hj (˜ x), x) ≤ ζjT (x − x˜), j ∈ J − (˜ hj (x) − hj (˜ x) đúng với mọi x ∈ X và mọi ξ ∈ ∂f (˜ x), ηi ∈ ∂gi (˜ x), i ∈ I(˜ x), ζj ∈ ∂hj (˜ x), j ∈ x) ∪ J − (˜ J + (˜ x), tương ứng. Do đó, nó cũng thỏa mãn với x = x¯. Như vậy, f (¯ x) ≥ ξ T (¯ x) − f (˜ x − x˜), (1.28) gi (¯ x) ≥ ηiT (¯ x) − gi (˜ x − x˜), i ∈ I(˜ x), (1.29) hj (¯ x) ≥ ζjT (¯ x) − hj (˜ x − x˜), j ∈ J + (˜ x), (1.30) hj (¯ x − x˜), j ∈ J − (˜ x) ≤ ζjT (¯ x) − hj (˜ x). (1.31) Bởi vì các điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3) − (1.5) thỏa mãn tại x˜ với các nhân tử Lagrange λ ˜ ∈ Rm và µ ˜ i ≥ 0, i ∈ ˜ ∈ Rs , và hơn nữa, λ ˜j > 0, j ∈ J + (˜ I, µ ˜j < 0, j ∈ J − (˜ x), µ x), ta nhận được ˜ i gi (¯ ˜ i gi (˜ x) − λ ˜ i η T (¯ x) ≥ λ λ i x−x ˜), i ∈ I, (1.32) µ x) − µ ˜j hj (¯ ˜j hj (˜ ˜j ζjT (¯ x) ≥ µ x − x˜), j ∈ J. (1.33) Lấy tổng hai vế của (1.32) và (1.33) theo i và j, ta được m X m X m X ˜ i gi (¯ x) − ˜ i gi (˜ x) ≥ ˜ i η T (¯ λ λ λ i x−x ˜), (1.34) i=1 i=1 i=1 s X s X s X µ x) − ˜j hj (¯ µ x) ≥ ˜j hj (˜ ˜j ζjT (¯ µ x − x˜). (1.35) j=1 j=1 j=1 Bây giờ, ta cộng hai vế của (1.28), (1.34) và (1.35), ta nhận được m X m X s X s X x) − f (˜ f (¯ x) + ˜ i gi (¯ λ x) − ˜ i gi (˜ λ x) + µ x) − ˜j hj (¯ µ ˜j hj (˜ x) i=1 i=1 j=1 j=1
16 " m s # X X ≥ ξT + ˜iηT + λ ˜j ζjT (¯ µ x − x˜). i i=1 j=1 Do điều kiện cần tối ưu Karush-Kuhn-Tucker (1.3), ta suy ra m X m X s X s X x) − f (˜ f (¯ x) + ˜ i gi (¯ λ x) − ˜ i gi (˜ λ x) + µ x) − ˜j hj (¯ µ x) ≥ 0. ˜j hj (˜ i=1 i=1 j=1 j=1 Như vậy, ta có m X s X m X s X f (¯ x) + ˜ i gi (¯ λ x) + µ x) ≥ f (˜ ˜j hj (¯ x) + ˜ i gi (˜ λ x) + µ ˜j hj (˜ x). i=1 j=1 i=1 j=1 Từ tính chất nhận được của x˜ trong bài toán (P ) và điều kiện cần tối ưu Karush-Kuhn-Tucker (1.2), ta suy ra m X s X f (¯ x) + ˜ i gi (¯ λ x) + µ x) ≥ f (˜ ˜j hj (¯ x). i=1 j=1 Sử dụng (1.6), ta nhận được m X s X ˜ i g + (¯