Luận văn Thạc sĩ Toán học: Điều kiện tối ưu và tính đối ngẫu cho bài toán tối ưu đa mục tiêu không trơn

Chia sẻ: Tri Lễ | Ngày: | Loại File: PDF | Số trang:54

Thêm vào BST

Báo xấu

22
lượt xem 1
download

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

Đề tài có cấu trúc gồm 2 chương trình bày điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu chính thường và cô lập của bài toán tối ưu đa mục tiêu không trơn; điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu và nghiệm hữu hiệu yếu của bài toán tối ưu đa mục tiêu không trơn.

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: Điều kiện tối ưu và tính đối ngẫu cho bài toán tối ưu đa mục tiêu không trơn

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- TRẦN THỊ LAN HƯƠNG ĐIỀU KIỆN TỐI ƯU VÀ TÍNH ĐỐI NGẪU CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊ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 ------------------------------- TRẦN THỊ LAN HƯƠNG ĐIỀU KIỆN TỐI ƯU VÀ TÍNH ĐỐI NGẪU CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU KHÔNG TRƠN LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số : 60 46 01 12 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 Mở đầu 1 1 Điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu chính thường và cô lập của bài toán tối ưu đa mục tiêu không trơn 4 1.1. Các định nghĩa và kết quả bổ trợ . . . . . . . . . . . . . . 4 1.2. Điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu chính thường và cô lập . . . . . . . . . . . . . . . . . . . . . . . 7 1.3. Đối ngẫu cho nghiệm hữu hiệu chính thường . . . . . . . . 18 2 Điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu và nghiệm hữu hiệu yếu của bài toán tối ưu đa mục tiêu không trơn 24 2.1. Các kết quả bổ trợ . . . . . . . . . . . . . . . . . . . . . . 24 2.2. Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . 28 2.3. Các định lý đối ngẫu . . . . . . . . . . . . . . . . . . . . . 38 2.3.1. Đối ngẫu kiểu Wolfe . . . . . . . . . . . . . . . . . 38 2.3.2. Đối ngẫu kiểu Mond - Weir . . . . . . . . . . . . . 44 Kết luận 48 Tài liệu tham khảo 50
1 Mở đầu 1. Lí do chọn đề tài Điều kiện tối ưu và đối ngẫu là các hướng nghiên cứu quan trọng của lý thuyết tối ưu đa mục tiêu. Với một bài toán tối ưu không trơn, người ta thường dùng các khái niệm dưới vi phân để thiết lập các điều kiện tối ưu và các định lý đối ngẫu như các dưới vi phân lồi, Clarke, Michel - Penot, Mordukhovich, dưới vi phân suy rộng. T.D. Chuong [2], 2013 đã sử dụng giải tích biến phân, dạng không trơn của quy tắc Fermat và dưới vi phân Mordukhovich để thiết lập các điều kiện tối ưu và các định lý đối ngẫu kiểu Wolfe cho nghiệm hữu hiệu chính thường và nghiệm hữu hiệu cô lập của bài toán tối ưu đa mục tiêu có ràng buộc đẳng thức và bất đẳng thức. T.D. Chuong - D.S. Kim [3], 2014 đã thiết lập các điều kiện tối ưu và các định lý đối ngẫu kiểu Wolfe và Mond - Weir cho nghiệm hữu hiệu và nghiệm hữu hiệu yếu của bài toán đó. Đây là đề tài được nhiều tác giả quan tâm nghiên cứu. Chính vì thế tôi chọn đề tài: "Điều kiện tối ưu và đối ngẫu cho bài toán tối ưu đa mục tiêu không trơn". 2. Mục đích của đề tài Luận văn trình bày các kết quả về điều kiện tối ưu và đối ngẫu của T.D. Chuong đăng trong tạp chí Nonlinear Analysis 76 (2013), 93 - 104 cho nghiệm hữu hiệu chính thường và nghiệm hữu hiệu cô lập của bài toán tối ưu đa mục tiêu có ràng buộc đẳng thức và bất đẳng thức, và của T.D. Chuong - D.S. Kim đăng trong tạp chí Annals of Operations Research 217 (2014), 117 - 136 cho nghiệm hữu hiệu và nghiệm hữu hiệu
2 yếu của bài toán đó. 3. Nội dung của luận văn Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục tài liệu tham khảo Chương 1. "Điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu chính thường và cô lập của bài toán tối ưu đa mục tiêu không trơn" Trình bày các điều kiện cần cho các nghiệm hữu hiệu chính thường địa phương và cô lập địa phương của bài toán tối ưu đa mục tiêu có ràng buộc đẳng thức và bất đẳng thức bằng cách sử dụng công cụ giải tích biến phân và vi phân suy rộng như: Quy tắc Fermat không trơn, dưới vi phân Mordukhovich (hay còn gọi là dưới vi phân giới hạn) của hàm max, quy tắc tổng cho các dưới vi phân Fréchet và giới hạn. Các điều kiện đủ tối ưu được trình bày với các giả thiết về tính lồi suy rộng dưới ngôn ngữ dưới vi phân giới hạn của hàm Lipschitz địa phương. Các định lý đối ngẫu yếu, mạnh cũng được trình bày trong chương này. Các kết quả trình bày trong chương này được tham khảo trong [2], [1], [7], [8]. Chương 2. "Điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu và hữu hiệu yếu của bài toán tối ưu đa mục tiêu không trơn" Trình bày các điều kiện cần cho nghiệm hữu hiệu và nghiệm hữu hiệu yếu của bài toán tối ưu đa mục tiêu với ràng buộc đẳng thức và bất đẳng thức bằng công cụ giải tích biến phân như: Nguyên lý cực trị xấp xỉ, quy tắc tổng mờ cho vi phân Fréchet, quy tắc tổng cho vi phân giới hạn và công thức vô hướng hóa đối đạo hàm. Các điều kiện đủ cho nghiệm hữu hiệu yếu và nghiệm hữu hiệu được trình bày với các giả thiết về tính lồi suy rộng dưới ngôn ngữ dưới vi phân giới hạn. Các định lý đối ngẫu Wolfe và Mond - Weir cũng được trình bày trong chương này. Các kết quả được trình bày trong chương này được tham khảo trong [3], [7], [1]. Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của PGS.TS. Đỗ Văn
3 Lưu. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn tận tình và đầy trách nhiệm để tác giả hoàn thành luận văn này. Tác giả đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Nhân dịp này tác giả xin gửi lời cảm ơn sâu sắc tới các Thầy giáo, Cô giáo đã tham gia giảng dạy lớp Cao học Toán K9Y; Nhà trường và các phòng chức năng của Trường; Khoa Toán - Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Cuối cùng tác giả xin cảm ơn gia đình, bạn bè và đồng nghiệp đã động viên, ủng hộ và tạo mọi điều kiện cho tác giả trong suốt thời gian nghiên cứu và học tập. Thái Nguyên, ngày 05 tháng 9 năm 2017 Tác giả luận văn Trần Thị Lan Hương
4 Chương 1 Điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu chính thường và cô lập của bài toán tối ưu đa mục tiêu không trơn Chương 1 trình bày các điều kiện cần cho các nghiệm hữu hiệu chính thường địa phương và cô lập địa phương của T.D. Chuong [2], 2013 cho bài toán tối ưu đa mục tiêu có ràng buộc đẳng thức và bất đẳng thức bằng cách sử dụng công cụ giải tích biến phân và vi phân suy rộng. Các điều kiện đủ tối ưu được trình bày với các giả thiết về tính lồi suy rộng dưới ngôn ngữ dưới vi phân giới hạn của hàm Lipschitz địa phương. Các định lý đối ngẫu Wolfe cũng được trình bày trong chương này. 1.1. Các định nghĩa và kết quả bổ trợ Nón cực của Ω ⊂ Rn là tập Ωo := {v ∈ Rn | hv, xi 6 0, ∀ x ∈ Ω}. (1.1)
5 Cho ánh xạ đa trị F : Rn ⇒ Rn , ta kí hiệu: Lim sup F (x) := {v ∈ Rn : ∃xn → x và vn → v với vn ∈ F (xn ), ∀n ∈ N} x→x là giới hạn trên (ngoài) Painlevé - Kuratowski dãy của F khi x → x. Một tập Ω ⊂ Rn được gọi là đóng xung quanh x ∈ Ω nếu có một lân cận U của x sao cho Ω ∩ clU là tập đóng. Ta nói Ω là đóng địa phương nếu Ω đóng xung quanh x với mọi x ∈ Ω. Cho Ω ⊂ Rn là tập đóng xung quanh x ∈ Ω. Nón pháp tuyến Fréchet của Ω tại x ∈ Ω được định nghĩa bởi ( ) ∗ hx , x − xi N b (x, Ω) := x∗ ∈ Rn | Lim sup ≤0 , (1.2) Ω x−→x kx − xk Ω trong đó x −→ x nghĩa là x → x với x ∈ Ω. Nếu x ∈/ Ω ta đặt N b (x, Ω) = ∅. b (x, Ω) của Ω tại x ∈ Ω nhận được Nón pháp tuyến Mordukhovich N từ các nón pháp tuyến Fréchet bằng việc lấy giới hạn trên Painlevé - Kuratowski dãy như sau N (x, Ω) := Lim sup N b (x, Ω). (1.3) Ω x−→x Nếu x ∈ / Ω ta đặt N (x, Ω) := ∅. Đặc biệt, nếu Ω là tập lồi địa phương xung quanh x, nghĩa là có một lân cận U ⊂ Rn của x sao cho Ω ∩ U là tập lồi thì ta có N (x, Ω) := {x∗ ∈ Rn | hx∗ , x − xi ≤ 0, ∀x ∈ Ω ∩ U }. (1.4) Với một hàm giá trị thực mở rộng ϕ : Rn → R := Rn ∪ {∞}, ta đặt domϕ := {x ∈ Rn | ϕ(x) < ∞} epiϕ := {(x, µ) ∈ Rn × R | µ ≥ ϕ(x)}. Dưới vi phân Modukhovich và dưới vi phân Fréchet của ϕ tại x ∈ domϕ được định nghĩa tương ứng bởi ∂ϕ(x) := {x∗ ∈ Rn | (x∗ , −1) ∈ N ((x, ϕ(x); epiϕ)}. (1.5)
6 và ∂ϕ(x) b := {x∗ ∈ Rn | (x∗ , −1) ∈ N b ((x, ϕ(x); epiϕ)}. (1.6) Nếu x ∈ / domϕ, ta đặt ∂ϕ(x) = ∂ϕ(x)b := ∅. Từ (1.3), (1.5) và (1.6), ta có ∀ x ∈ Rn , ∂ϕ(x) b ⊂ ∂ϕ(x). Đặc biệt, nếu ϕ là hàm lồi thì dưới vi phân được định nghĩa trong (1.5) và (1.6) trùng với vi phân dưới trong giải tích lồi cổ điển. Xét hàm chỉ δ(., Ω) được định nghĩa bởi δ(x, Ω) = 0 với x ∈ Ω và δ(x, Ω) := ∞ nếu x ∈ / Ω. Ta có một mối quan hệ giữa nón pháp tuyến Mordukhovich và dưới vi phân Mordukhovich của hàm chỉ như sau (xem [7]): N (x, Ω) := ∂δ(x, Ω), ∀ x ∈ Ω. (1.7) Dạng không trơn của quy tắc Fermat (xem [7]) rất quan trọng cho nhiều ứng dụng có thể phát biểu như sau: Nếu x là cực tiểu địa phương của ϕ thì 0 ∈ ∂ϕ(x) b ⊂ ∂ϕ(x). (1.8) Trong chương này ta cũng xét dưới vi phân trên Fréchet của ϕ tại x với |ϕ(x)| < ∞, được định nghĩa bởi ∂b+ ϕ(x) := −∂(−ϕ)(x). b (1.9) Quy tắc tổng cho dưới vi phân Fréchet như sau: Bổ đề 1.1 [8] Cho ϕi : Rn → R hữu hạn tại x ∈ Rn với i := 1, 2. Nếu ∂b+ ϕ2 (x) 6= ∅ thì \ h i b 1 + ϕ2 )(x) ⊂ ∂(ϕ b 1 (x) + x∗ . ∂ϕ x∗ ∈∂b+ ϕ2 (x) Bổ đề 1.2 [7] Cho ϕi : Rn → R, i = 1, 2, ..., n, n ≥ 2 là nửa liên tục dưới quanh x ∈ Rn và tất cả những hàm này, có thể ngoại trừ một hàm là liên
7 tục Lipschitz quanh x. Khi đó, ∂(ϕ1 + ϕ2 + ... + ϕn )(x) ⊂ ∂ϕ1 (x) + ∂ϕ2 (x) + ... + ∂ϕn (x). (1.10) 1.2. Điều kiện tối ưu và đối ngẫu cho các nghiệm hữu hiệu chính thường và cô lập Cho Ω là tập con đóng địa phương 6= ∅ của Rn và cho K := {1, 2, ..., m}, I := {1, 2, ..., p} ∪ ∅, J := {1, 2, ..., q} ∪ ∅ là tập chỉ số. Giả sử rằng f := (fk ), k ∈ K, g := (gi ), i ∈ I, h := (hj ), j ∈ J là các hàm vectơ với các thành phần Lipschitz địa phương xác định trong Rn . Xét bài toán tối ưu đa mục tiêu có ràng buộc sau: min m {f (x)|x ∈ C}. (1.11) R+ Tập chấp nhận được C được định nghĩa bởi C := {x ∈ Ω| gi (x) ≤ 0, i ∈ I, hj (x) = 0, j ∈ J}. (1.12) Định nghĩa 1.1 (i) Ta nói x ∈ C là nghiệm hữu hiệu địa phương của bài toán (1.11) nếu tồn tại một lân cận U của x sao cho / −Rm ∀x ∈ U ∩ C, f (x) − f (x) ∈ + {0}. (ii) [4] Điểm x ∈ C được gọi là nghiệm hữu hiệu cô lập địa phương của bài toán (1.11) nếu tồn tại một lân cận U của x và một hằng số ν > 0 sao cho ∀x ∈ U ∩ C, max {fk (x) − fk (x)} ≥ νkx − xk. 1≤k≤m (iii) Điểm x ∈ C được gọi là nghiệm hữu hiệu chính thường địa phương của bài toán (1.11) nếu tồn tại một lân cận U của x và λ ∈ intRm + sao cho ∀x ∈ U ∩ C, hλ, f (x)i ≥ hλ, f (x)i.
8 Ta kí hiệu các tập nghiệm hữu hiệu địa phương, nghiệm hữu hiệu cô lập địa phương, nghiệm hữu hiệu chính thường địa phương của bài toán (1.11) tương ứng là locS(P ), locS iv (P ), locS p (P ). Khi U := Rn ta kí hiệu các tập nghiệm trên tương ứng S(P ), S iv (P ), S p (P ). Ta biết rằng (xem [4]), locS iv (P ) ⊂ locS(P ) và locS p (P ) ⊂ locS(P ). Nhưng bao hàm thức ngược lại không đúng. Chú ý rằng các tập locS iv (P ) và locS p (P ) có thể khác nhau. Xét hai ví dụ sau: Ví dụ 1.1 Cho f : R → R2 xác định bởi f (x) := (f1 (x), f2 (x)) với ( x, nếu x ≥ 0, f1 (x) := 3x, nếu x < 0, ( −3x, nếu x ≥ 0, f2 (x) := −x, nếu x < 0, và cho g, h : R → R được xác định bởi g(x) := −|x| và h(x) := 0 với x ∈ R. Ta xét bài toán (1.11) với m = 2, Ω = R. Chọn x = 0 ∈ C = R và ν = 1 ta có max{f1 (x) − f1 (x), f2 (x) − f2 (x)} = |x| ≥ ν|x| = ν|x − x|, ∀x ∈ C. Như vậy x ∈ locS iv (P ). Trong khi x ∈ / locS p (P ). Thật vậy, giả sử ngược lại rằng tồn tại một lân cận U của x và điểm (λ1 , λ2 ) ∈ intR2+ sao cho λ1 f1 (x) + λ2 f2 (x) ≥ 0 = λ1 f1 (x) + λ2 f2 (x), ∀x ∈ U ∩ C. Điều này tương đương với ( λ1 x − 3λ2 x ≥ 0, nếu x ∈ U ∩ (0, +∞), 3λ1 x − λ2 x ≥ 0, nếu x ∈ U ∩ (−∞, 0). Điều này cho ta λ2 ≥ 9λ2 (mâu thuẫn). Ví dụ 1.2 Cho f : R → R2 được xác định bởi f (x) := (f1 (x), f2 (x)) trong đó
9 f1 (x) := −x4 , f2 (x) := x4 , và cho g, h : R → R xác định bởi g(x) := x−1, h(x) := 0 với x ∈ R. Ta xét bài toán (1.11) với m = 2, Ω = R. Chọn 1 1 x = 0 ∈ C = (−∞, 1] và λ := , ∈ intR2+ , ta có 2 2 1 1 1 1 f1 (x) + f2 (x) = 0 ≥ 0 = f1 (x) + f2 (x), ∀x ∈ C. 2 2 2 2 Điều này cho thấy x ∈ locS p (P ), trong khi đó x ∈ / locS iv (P ) với ν > 0. Thật vậy, với v > 0 cố định bất kì, bất đẳng thức max{f1 (x) − f1 (x), f2 (x) − f2 (x)} = x4 ≥ ν|x| = ν|x − x|. / locS iv (P ). (không thỏa mãn ∀x ∈ C gần x). Do đó, x ∈ Với x ∈ Ω, ta đặt I(x) = {i ∈ I| gi (x) = 0} và J(x) = {j ∈ J| hj (x) = 0}. Định nghĩa 1.2 Ta nói điều kiện chính quy (CQ) được thỏa mãn tại x ∈ Ω nếu không tồn tại µi ≥ 0, i ∈ I(x) và γj ≥ 0 ∈ J(x) sao cho P P µi + 6 0 và γj = i∈I(x) j∈J(x) X X 0∈ µi ∂gi (x) + γj (∂hj (x) ∪ ∂(−hj )(x)) + N (x, Ω). i∈I(x) j∈J(x) Khi xét x ∈ C xác định trong (1.12) với Ω = Rn điều kiện (CQ) đã nêu trên đúng nếu điều kiện chính quy Mangasarian - Fromovitz đúng trong trường hợp trơn. Định lý sau đưa ra một điều kiện cần cho nghiệm hữu hiệu cô lập của bài toán (1.11) dưới định nghĩa trên (CQ). Định lý 1.1 Cho (CQ) xác định trong Định nghĩa 1.2 thỏa mãn tại x ∈ Ω. Nếu x ∈ locS iv (P ) với ν > 0 nào đó thì X X νBRn ⊂ λk ∂fk (x) + µi ∂gi (x) k∈K i∈I X X + γj (∂hj (x) ∪ ∂(−hj )(x)) |λk ≥ 0, k ∈ K, λk = 1, (1.13) j∈J k∈K µi ≥ 0, µi gi (x) = 0, i ∈ I, γj ≥ 0, j ∈ J + N (x, Ω).
10 Chứng minh Lấy x ∈ locS iv (P ). Đặt ϕ(x) = max {fk (x) − fk (x)} − νkx − xk. 1≤k≤m Xét bài toán tối ưu sau: min ϕ(x). x∈C Do x ∈ locS iv (P ), tồn tại một lân cận U của x sao cho ϕ(x) ≥ 0 = ϕ(x), ∀x ∈ U ∩ C. (1.14) Điều này có nghĩa là x là cực tiểu địa phương của (1.14). Do đó, x là một cực tiểu địa phương của bài toán tối ưu hóa vô hướng không có ràng buộc min ϕ(x) + δ(x, C). (1.15) x∈Rn Áp dụng dạng không trơn của quy tắc Fermat (1.8) cho bài toán (1.15) ta có 0 ∈ ∂(ϕ b + δ(., C))(x). (1.16) Đặt ϕ1 (x) := max {fk (x) − fk (x)} + δ(x, C) và ϕ2 (x) := −kkx − xk. Khi 1≤k≤m đó, ϕ + δ(., C) = ϕ1 + ϕ2 . Do (1.16) nên ta có 0 ∈ ∂(ϕ b 1 + ϕ2 )(x). (1.17) Dễ thấy −ϕ2 là hàm lồi nên ∂b+ ϕ2 (x) = −∂(−ϕ b 2 )(x) = ∂(νk., −xk)(x) = νBRn 6= ∅. Sử dụng Bổ đề 1.1 và (1.17) ta có \ h i ∗ 0∈ ∂ϕ1 (x) + x . b x∗ ∈νBRn Điều này dẫn dến νBRn ⊂ ∂ϕ b 1 (x). Như vậy, νBRn ⊂ ∂ϕ1 (x) = ∂ max {fk (.) − fk (x)} + δ(., C) (x). (1.18) 1≤k≤m
11 Vì max {fk (.) − fk (x)} là hàm Lipschitz liên tục quanh x và hàm δ(., C) 1≤k≤m là nửa liên tục dưới quanh điểm này, từ quy tắc tổng (1.10) áp dụng vào (1.18), và từ mối quan hệ trong (1.7) ta suy ra νBRn ⊂ ∂ max {fk (.) − fk (x)} (x) + N (x, C). (1.19) 1≤k≤m e := {x ∈ Rn | gi (x) ≤ 0, i ∈ I, hi = 0, j ∈ J}. Ta có C = Ω Đặt Ω e ∩ Ω. Điều kiện (CQ) thỏa mãn tại x kéo theo không tồn tại µi ≥ 0, i ∈ I(x) P P và γj ≥ 0, j ∈ J(x) = J sao cho µi + γj 6= 0 và i∈I(x) j∈J(x) X X 0∈ µi ∂gj (x) + γj (∂hj (x) ∪ ∂(−hj )(x)). i∈I(x) j∈J(x) Do đó, từ Mordukhovich [7, Hệ quả 4.36] ta có X X N x, Ω ⊂ e µi ∂gj (x)+ γj (∂hj (x) ∪ ∂(−hj )(x)) | µi ≥ 0, i∈I(x) j∈J(x) i ∈ I(x), γj ≥ 0, j ∈ J(x) . Vì điều kiện (CQ) được thỏa mãn tại x, từ [7, Hệ quả 3.37] ta có e ∩ Ω) ⊂ N (x, Ω) N (x, C) = N (x, Ω e + N (x, Ω). Do đó, X X N (x, C) ⊂ µi ∂gj (x)+ γj (∂hj (x) ∪ ∂(−hj )(x)) | µi ≥ 0, i∈I(x) j∈J(x) (1.20) i ∈ I(x), γj ≥ 0, j ∈ J(x) + N (x, Ω). Bên cạnh đó, sử dụng công thức cho dưới vi phân cơ bản của hàm max (xem [7], Định lý 3.46(ii)) và quy tắc tổng (1.10) ta thu được ∂ max {fk (.) − fk (x)} (x) ⊂ 1≤k≤m (1.21) ( ) X X λk ∂fk (x)|λk ≥ 0, k ∈ K, λk = 1 . k∈K k∈K
12 Đặt µi = 0 với i ∈ / I(x), (1.13) được suy ra từ (1.20) - (1.21). Định lý được chứng minh. Đinh lí 1.1 có thể sai nếu điều kiện (CQ) không thỏa mãn tại điểm đang xét như trong ví dụ sau: Ví dụ 1.3 Cho f : R → R2 được xác định bởi f (x) := (f1 (x), f2 (x)) với f1 (x) = f2 (x) = x và cho g, h : R → R được xác định bởi g(x) := x2 , h(x) := 0, ∀x ∈ R. Xét bài toán (1.11) với m = 2 và Ω = R. Chú ý rằng C = {0} và x := 0 ∈ S iv (P ) với ν > 0 bất kì. Dễ thấy rằng điều kiện (CQ) không thỏa mãn tại x. Khi đó (1.13) không thỏa mãn. Để xây dựng điều kiện đủ cho cực tiểu cô lập địa phương của bài toán (1.11), trong định lý tiếp theo ta nhắc lại một hàm ϕ : Ω ⊂ Rn → R là hàm lồi địa phương (affine địa phương) tại x ∈ Ω nếu tồn tại một lân cận U của x sao cho Ω ∩ U là tập lồi và ϕ là hàm lồi (affine) trên Ω ∩ U . Định lý 1.2 Cho x ∈ C. Giả sử fk , k ∈ K; gi , i ∈ I là hàm lồi địa phương tại x và hj , j ∈ J là hàm affine địa phương tại x. Nếu x thỏa mãn (1.13) thì x ∈locS iv (P ). Chứng minh Từ giả thiết của định lý, tồn tại một lân cận U của x sao cho U ∩ Ω là một tập lồi và fk , k ∈ K; gi , i ∈ I là hàm lồi trên U ∩ Ω và hj , j ∈ J là hàm affine trên U ∩ Ω. Chú ý rằng với ∀ z ∈ Rn , kzk = max (z ∗ , z). Do z∈BRn ∗ ∗ đó, tồn tại z ∈ BRn sao cho kzk = hz , zi. Lấy bất kì x ∈ U ∩ C, tồn tại z ∗ ∈ BRn sao cho kx − xk = hx∗ , x − xi. (1.22) λk = 1, zk∗ ∈ P Vì x ∈ C thỏa mãn (1.13) nên tồn tại λk ≥ 0, k ∈ K với k∈K ∂fk (x), k ∈ K, µi ≥ 0, x∗i ∈ ∂gi (x) với µi gi (x) = 0, i ∈ I, γj ≥ 0, yi∗ ∈
13 ∂hj (x) ∪ ∂(−hj )(x), j ∈ J sao cho ! X X X vx∗ − λk zk∗ + µi x∗i + γj yj∗ ∈ N (x, Ω). k∈K i∈I i∈J Từ (1.4) suy ra X X ∗ νhx , x − xi − λk hzk∗ , x − xi + µi hx∗i , x − xi k∈K i∈I X (1.23) γj hyj∗ , x − xi ≤ 0. + i∈J Từ tính chất lồi địa phương của fk , gi và tính chất affine địa phương của hj ta có X X X λk hzk∗ , x − xi + µi hx∗i , x − xi + γj hyj∗ , x − xi k∈K i∈I i∈J X X ≤ λk [fk (x) − fk (x)] + µi [gi (x) − gi (x)] (1.24) k∈K i∈I X 1 X + γj [hj (x) − hj (x)] ≤ λk [fk (x) − fk (x)], ωj j∈J k∈K trong đó ωj ∈ {−1, 1} và bất đẳng thức sau đúng vì µi gi (x) = 0, µi gi (x) ≤ 0, i ∈ I và hj (x) = 0, hj (x) = 0, j ∈ J. Kết hợp (1.22) với (1.23) và (1.24) ta nhận được X νkx − xk ≤ λk [fk (x) − fk (x)]. k∈K Hơn nữa, X X λk [fk (x)−fk (x)] ≤ λk max {fk (x)−fk (x)} = max {fk (x)−fk (x)}. 1≤k≤m 1≤k≤m k∈K k∈K Nên νkx − xk ≤ max {fk (x) − fk (x)}. 1≤k≤m Suy ra x ∈ locS iv (P ) vì x bất kì trong U ∩ C. Ví dụ tiếp theo chỉ ra rằng tính lồi địa phương của hàm mục tiêu f tại điểm x trong Định lý 1.2 là rất quan trọng. Cụ thể là, một điểm khả thi
14 x thỏa mãn (1.13) không cần thiết là cực tiểu cô lập của bài toán (1.11) nếu không có tính lồi địa phương của f tại x. Ví dụ 1.4 Cho f : R → R2 được xác định bởi f (x) := (f1 (x), f2 (x)) với  x2 sin 1 ,  nếu x 6= 0, f1 (x) = f2 (x) := x  0, nếu x = 0, và gọi g, h : R → R được xác định bởi g(x) := x − 1 và h(x) := 0 với x ∈ R. Xét bài toán (1.11) với m = 2, Ω = R thì C = (−∞, 1]. Chú ý rằng f1 , f2 là Lipschitz địa phương tại x = 0 ∈ C và ∂f1 (x) = ∂f2 (x) = [−1, 1]. / locS iv (P ), do f1 , f2 Ta thấy x thỏa mãn (1.13) ∀ ν ∈ (0, 1]. Tuy nhiên, x ∈ không lồi địa phương tại x. Định lý sau đây trình bày điều kiện cần cho nghiệm hữu hiệu chính thường địa phương của bài toán (1.11) với điều kiện (CQ) như trong Định nghĩa 1.2. Định lý 1.3 Giả sử điều kiện (CQ) thỏa mãn tại x ∈ Ω. Nếu x ∈ loc S p (P ) thì tồn tại λk > 0, k ∈ K, µi ≥ 0, i ∈ I và γj ≥ 0, j ∈ J sao cho X X 0∈ λk ∂fk (x) + µi ∂gi (x) k∈K i∈I X + γj (∂hj (x) ∪ ∂(−hj )(x)) + N (x, Ω), (1.25) j∈J µi gi (x) = 0, i ∈ I. Chứng minh Giả sử x ∈ locS p (P ). Khi đó tồn tại một lân cận U của x và λ := (λ1 , ...λm ) ∈ int Rm + sao cho X λk [fk (x) − fk (x)] ≥ 0, ∀x ∈ U ∩ C. k∈K Điều đó có nghĩa là x là một cực tiểu địa phương của bài toán tối ưu
15 không có ràng buộc sau: min θ(x), x∈C trong đó X θ(x) = λk fk (x). (1.26) k∈K Như vậy, x là cực tiểu địa phương của bài toán tối ưu không ràng buộc sau min θ(x) + δ(x, C). (1.27) x∈Rn Áp dụng dạng không trơn của quy tắc Fermat (1.8) cho bài toán (1.27) ta có 0 ∈ ∂(θ + δ(., C))(x). (1.28) Vì θ là Lipschitz địa phương tại x và δ(., C)) là nửa liên tục dưới quanh x, từ (1.10) và (1.7), ta có 0 ∈ ∂θ(x) + ∂δ(x, C)) = ∂θ(x) + N (x, C). (1.29) Tương tự chứng minh của Định lý 1.3 ta nhận được X X N (x, C) ⊂ µi ∂gi (x)+ γj (∂hj (x) ∪ ∂(−hj )(x))| µi ≥ 0, i∈I(x) j∈J(x) (1.30) i ∈ I(x), γi ≥ 0, j ∈ J(x) + N (x, Ω). Áp dụng quy tắc tổng (1.10), từ (1.30) ta nhận được X X X 0∈ λk ∂fk (x) + µi ∂gi (x) + γj (∂hj (x) ∪ ∂(−hj (x)) k∈K i∈I j∈J (1.31) + N (x, Ω), µi ≥ 0, i ∈ I(x), γi ≥ 0, j ∈ J(x). Lấy µi = 0, i ∈ I(x) trong (1.31) ta nhận được (1.25). Định lý được chứng minh.
16 Nhận xét 1.1 Như đã chỉ ra trong Ví dụ 1.3, kết quả của Định lý 1.3 có thể không đúng nếu điều kiện (CQ) không thỏa mãn. Để trình bày điều kiện đủ cho nghiệm hữu hiệu chính thường toàn cục của bài toán (1.11) trong định lý tiếp theo ta cần khái niệm lồi bất biến vô hạn (suy rộng) cho hàm Lipschitz địa phương. Định nghĩa 1.3 Ta nói (f, g, h) là L - lồi bất biến trên Ω tại x ∈ Ω nếu ∀x ∈ Ω, zk∗ ∈ ∂fk (x), k ∈ K, x∗i ∈ ∂gi (x), i ∈ I và yj∗ ∈ (∂hj (x) ∪ ∂(−hj )(x)), j ∈ J thì tồn tại v ∈ N (x, Ω)o sao cho fk (x) − fk (x) ≥ hzk∗ , vi, k ∈ K, gi (x) − gi (x) ≥ hx∗i , vi, i ∈ I, hj (x) − hj (x) = ωj hyj∗ , vi, j ∈ J. trong đó ωj = 1 (tương ứng ωj = −1) với yj∗ ∈ ∂hj (x) (tương ứng yj∗ ∈ ∂(−hj )(x).) Chú ý rằng nếu Ω lồi, fk , k ∈ K, gi , i ∈ I lồi và hj , j ∈ J là affine thì (f, g, h) là L - lồi bất biến trên Ω tại ∀x ∈ Ω với v = x − x, x ∈ Ω. Định lý 1.4 Cho x ∈ C và giả sử (f, g, h) là L - lồi bất biến trên Ω tại x. Nếu x thỏa mãn (1.25) thì x ∈ S p (P ). Chứng minh Giả sử tồn tại λk > 0, k ∈ K, µi ≥ 0, i ∈ I và γj ≥ 0, j ∈ Ω thỏa mãn (1.25). Khi đó, tồn tại zk∗ ∈ ∂fk (x), k ∈ K, x∗i ∈ ∂gi (x) với µi gi (x) = 0, i ∈ I và yj∗ ∈ (∂hj (x) ∪ ∂(−hj )(x)), j ∈ J sao cho   X X X − λk zk∗ + µi x∗i + γj yj∗  ∈ N (x, Ω). (1.32) k∈K i∈I j∈J Do tính chất L - lồi bất biến của (f, g, h) trên Ω tại x, với mỗi x ∈ Ω ta có v ∈ N (x, Ω)o sao cho
17 λk hzk∗ , vi + µi hx∗i , vi + γj hyj∗ , vi P P P k∈K i∈I j∈J X X X 1 ≤ λk [fk (x) − fk (x)] + µi [gi (x) − gi (x)] + γj [hj (x) − hj (x)], ωj k∈K i∈I j∈J trong đó ωj ∈ {−1, 1}. Từ định nghĩa của nón cực (1.1), từ (1.32) và v ∈ N (x, Ω)o ta suy ra X X X 0≤ λk hzk∗ , vi + µi hx∗i , vi + γj hyj∗ , vi k∈K i∈I j∈J Vì vậy, X X X X X X λk fk (x)+ µi gi (x)+ σj hj (x) ≤ λk fk (x)+ µi gi (x)+ σj hj (x), k∈K i∈I j∈J k∈K i∈I j∈J γj trong đó σj = ∈ R, j ∈ J. Chú ý rằng µi gi (x) = 0, i ∈ I và hj (x) = ωj 0, j ∈ J. Do đó, khi x ∈ C, X X X X λk fk (x) = λk fk (x) + µi gi (x) + σj hj (x) k∈K k∈K i∈I j∈J P P P ≤ λk fk (x) + µi gi (x) + σj hj (x) k∈K i∈I j∈J P ≤ λk fk (x). k∈K Từ đó suy ra x ∈ S p (P ). Định lý được chứng minh. Một điểm thỏa mãn (1.25) không nhất thiết là nghiệm hữu hiệu chính thường của bài toán (1.11) thậm chí cả trong trường hợp trơn nếu tính chất L - lồi bất biến trên Ω tại điểm x của (f, g, h) không đúng. Điều đó được minh họa bởi ví dụ sau. Ví dụ 1.5 Cho f : R → R2 được xác định bởi f (x) := (f1 (x), f2 (x)) với f1 (x) = f2 (x) := x3 và cho g, h : R → R được xác định bởi g(x) := −x4 , h(x) := 0, ∀x ∈ R. Xét bài toán (1.11) với m := 2 và Ω := R. Khi đó, C = R, và do đó x = 0 ∈ C. Ta thấy rằng x thỏa mãn (1.25). Tuy / S p (P ). nhiên, x ∈