ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC  - NGUYỄN THỊ XUÂN SINH ĐIỀU KIỆN TỐI ƯU CẤP CHO BÀI TOÁN TỐI ƯU VECTƠ VỚI CÁC HÀM LỚP C1 LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2021 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC  - NGUYỄN THỊ XUÂN SINH ĐIỀU KIỆN TỐI ƯU CẤP CHO BÀI TOÁN TỐI ƯU VECTƠ VỚI CÁC HÀM LỚP C1 Chuyên ngành: Toán ứng dụng Mã số : 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS Đỗ Văn Lưu THÁI NGUYÊN - 2021 i Mục lục Mở đầu 1 Kiến thức chuẩn bị 1.1 Phát biểu toán 1.2 Một số khái niệm định nghĩa 1.3 Điều kiện quy cấp Điều kiện cần đủ tối ưu cấp 16 2.1 Điều kiện cần tối ưu cấp dạng nguyên thủy 16 2.2 Điều kiện cần tối ưu cấp dạng đối ngẫu 19 2.3 Điều kiện đủ tối ưu cấp 22 Kết luận 27 Tài liệu tham khảo 28 Mở đầu Các điều kiện tối ưu Karush-Kuhn-Tucker (KKT) đóng vai trị quan trọng lý thuyết tối ưu phi tuyến Các điều kiện KKT cấp cho phép ta tìm nghiệm tối ưu tập điểm dừng Các điều kiện tối ưu Karush-Kuhn-Tucker cấp nghiên cứu nhiều tác giả nước quốc tế Gần đây, M Feng S Li [2] thiết lập điều kiện tối ưu cấp dạng nguyên thủy dạng đối ngẫu cho toán tối ưu vectơ với hàm khả vi Fréchet Với điều kiện quy kiểu Abadie, M Feng S Li [2] thiết lập điều kiện cần tối ưu Karush-Kuhn-Tucker cấp cho toán tối ưu vectơ Hơn nữa, điều kiện đủ cấp cho nghiệm Pareto địa phương chặt toán tối ưu vectơ nghiên cứu [2] 1.2 Mục đích đề tài luận văn Luận văn trình bày kết Feng Li [2] đăng tạp chí Optimization năm 2018 điều kiện cần đủ tối ưu dạng nguyên thủy dạng đối ngẫu cho tốn tối ưu vectơ có ràng buộc đẳng thức bất đẳng thức với hàm khả vi liên tục Fréchet Nội dung đề tài luận văn vấn đề cần giải Luận văn bao gồm phần mở đầu, hai chương, kết luận danh mục tài liệu tham khảo Chương với tiêu đề "Kiến thức chuẩn bị"trình bày khái niệm tập tiếp tuyến cấp 2, loại đạo hàm theo phương cấp điều kiện quy cấp Chương với tiêu đề "Điều kiện cần đủ tối ưu cấp 2" trình bày điều kiện cần đủ tối ưu cấp dạng nguyên thủy dạng đối ngẫu Sử dụng định lý luân phiên Motzkin, từ điều kiện cần tối ưu dạng nguyên thủy để chứng minh điều kiện cần tối ưu dạng đối ngẫu Luận văn “Điều kiện tối ưu cấp cho toán tối ưu vectơ với hàm lớp C ” hoàn thành Trường Đại học Khoa học - Đại học Thái Nguyên hoàn thành hướng dẫn GS.TS Đỗ Văn Lưu Tác giả xin bày tỏ lòng biết ơn chân thành sâu sắc tới Thầy, người dành nhiều thời gian, tận tình hướng dẫn giúp đỡ tác giả suốt trình nghiên cứu hoàn thiện luận văn Tác giả xin bày tỏ lòng biết ơn chân thành tới thầy giáo, giáo khoa Tốn - Tin trường Đại học Khoa học, Đại học Thái Nguyên giảng dạy giúp đỡ cho tác giả suốt thời gian học tập Trường Đồng thời, xin gửi lời cảm ơn tới gia đình, bạn bè đồng nghiệp động viên, khích lệ tạo điều kiện thuận lợi cho thời gian học tập q trình hồn thành luận văn Thái Ngun, ngày 25 tháng 10 năm 2020 Tác giả luận văn Nguyễn Thị Xuân Sinh Chương Kiến thức chuẩn bị Chương trình bày số khái niệm cần thiết cho chương sau bao gồm: khái niệm tập tiếp tuyến cấp 2, loại đạo hàm theo phương cấp điều kiện quy cấp Các kiến thức trình bày Chương tham khảo [2] 1.1 Phát biểu toán Ký hiệu orthant không âm (dương) Rn ký hiệu Rn+ (t.ư., dương: Rn++ ), t.ư viết tắt từ tương ứng Như với x, y ∈ Rn , x ≤ y có nghĩa y − x ∈ Rn+ ; viết x < y có nghĩa y − x ∈ Rn++ Trong luận văn này, ta xét toán tối ưu véctơ VOP sau: f (x) =(f1 (x), f2 (x), , fl (x))T với ràng buộc gi (x) ≤ 0, i = 1, , m, hj (x) = 0, j = 1, , r, fk : Ω → R, k ∈ K = {1, , l}, gi : Ω → R, i ∈ I = {1, , m}, hj : Ω → R, j ∈ J = {1, , r} giả thiết khả vi liên tục Fréchet tập mở Ω Ω ⊆ Rp Đặt g(x) = (g1 (x), , gm (x))T h(x) = (h1 (x), , hr (x))T , T ký hiệu phép chuyển vị Ta ký hiệu tập chấp nhận cho X := {x ∈ Ω : gi (x) ≤ 0, i ∈ I, hj (x) = 0, j ∈ J} Tập số tích cực x ∈ X ràng buộc bất đẳng thức ký hiệu A(x) := {i ∈ I : gi (x) = 0} 1.2 Một số khái niệm định nghĩa Định nghĩa 1.1 Véctơ x∗ ∈ X nghiệm tối ưu Pareto địa phương (t ư., nghiệm Pareto địa phương yếu VOP) tồn δ > cho không tồn x thuộc X∩B(x∗ , δ) thỏa mãn f (x) ≤ f (x∗ ) f (x) = f (x∗ ) (tương ứng f (x) < f (x∗ )), B(x∗ , δ) ký hiệu hình cầu tâm x∗ , bán kính δ Giả sử A ⊆ Rp tập khác rỗng Biên, bao đóng, phần bao nón A ký hiệu bdA, clA, intA coneA Chúng nhắc lại vài khái niệm nón tiếp tuyến, tập tiếp tuyến bậc hai đạo hàm theo phương Định nghĩa 1.2 Nón tiếp tuyến S ⊆ Rp x0 ∈ cl S ký hiệu T (S, x0 ) := {u ∈ Rp : ∃tn → 0+ , ∃un → u cho x0 + tn un ∈ S, ∀n ∈ N} Định nghĩa 1.3 Giả sử S ⊆ Rp , x0 ∈ cl S v ∈ Rp (a) Tập tiếp tuyến bậc hai S x0 theo phương v T (S, x0 , v) :={w ∈ Rp : ∃tn → 0+ , ∃wn → w cho x0 + tn v + t2n wn ∈ S, ∀n ∈ N} (b) Nón tiếp tuyến cấp hai tiệm cận S x0 theo phương v T (S, x0 , v) :={w ∈ Rp : ∃tn → 0+ , ∃sn → 0+ , ∃wn → w cho tn /sn → 0, x0 + tn v + s−1 n tn wn ∈ S, ∀n ∈ N} (c) Nón tiếp tuyến cấp hai chiếu S x0 theo phương v T (S, x0 , v) :={(w, s) ∈ Rp × R+ : ∃tn → 0+ , ∃sn → s, ∃wn → w cho tn /sn → 0+ , x0 + tn v + s−1 n tn wn ∈ S, ∀n ∈ N} Tập T (S, x0 , v) biết Nón T (S, x0 , v) lần đưa vào Cambini cộng [7] sử dụng rộng rãi tối ưu Nón T (S, x0 , v) sử dụng Jiménez Novo [8] để phát biểu điều kiện tối ưu cho toán tối ưu khả vi Nếu S lồi T (S, x0 , v) T (S, x0 , v) lồi, T (S, x0 , v) khơng lồi Để ý T (S, x0 , v) trùng với tập sau T (S, x0 , v) := cone+ (T (S, x0 , v) × {1}) ∪ (T (S, x0 , v) × {0}), cone+ (A) := t>0 tA (1.1) cho tập A Rp+1 Mệnh đề 1.1 Giả sử S tập Rp , x0 ∈ cl S v ∈ Rp (i) T (S, x0 , 0) = T (S, x0 , 0) = T (S, x0 ) T (S, x0 , 0) = T (S, x0 )×R+ (ii) Nếu v ∈ / T (S, x0 ) T (S, x0 , v) = T (S, x0 , v) = ∅ T (S, x0 , v) = ∅ (iii) Hơn S lồi v ∈ T (S, x0 ) T (S, x0 , v) + (T (T (S, x0 ), v) × {0}) ⊆ T (S, x0 , v) Định nghĩa 1.4 ([5]) Giả sử f : Rn → Rl khả vi Fréchet x0 ∈ Rp Đạo hàm theo phương radial cấp f x0 theo phương v xác định f (x0 , v) := lim 2t−2 f (x0 + tv) − f (x0 ) − t∇f (x0 )T v t→0+ Định nghĩa 1.5 Giả sử f : Rp → Rl khả vi Fréchet x0 giả sử v, w ∈ Rp (a) Đạo hàm theo phương conic Hadamard cấp f x0 theo phương v xác định công thức d2c f (x0 , v) := lim (t,u)→(0+ ,v) 2t−2 f (x0 + tu) − f (x0 ) − t∇f (x0 )T u (b) Đạo hàm theo phương cấp parabolic Hadamard f (x0 , v) theo phương w xác định công thức d2p f (x0 , v, w) := 2t−2 lim (t,u)→(0+ ,w) × f (x0 + tv + t2 u) − f (x0 ) − t∇f (x0 )T v (c) Đạo hàm theo phương cấp tiệm cận Hadamard f (x0 , v) theo phương w xác định công thức d f (x0 , v, w) := lim 2st−2 (t,s)→(0+ ,0+ ),t/s→0,u→w × f (x0 + tv + s−1 t2 u) − f (x0 ) − t∇f (x0 )T v Định nghĩa 1.6 Ta nói f : Rp → Rl ổn định x0 ∈ Rp tồn lân cận U x0 số k > cho f (x) − f (x0 ) ≤ k x − x0 ∀x ∈ U Ta nói f Lipschitz tập mở U ⊆ Rp f (x) − f (x ) ≤ L x−x với x, x ∈ U với L > Rõ ràng f Lipschitz U kéo theo f ổn định điểm x ∈ U Như f C lân cận U x0 đạo hàm ∇f Lipschitz U (nghĩa f C 1,1 U ), ∇f ổn định x0 Trong kết chính, ta sử dụng bổ đề sau Bổ đề 1.1 Giả sử f : Rp → Rl có đạo hàm Fréchet ∇f liên tục x0 ∈ Rp f (x0 , v) tồn theo phương v ∈ Rp Giả sử xn → x0 với xn ∈ Rp tn → 0+ , sn → s với sn > Nếu wn := (xn − x0 − tn v)/(1/2)s−1 n tn → w f (xn ) − f (x0 ) − tn ∇f (x0 )T v = ∇f (x0 )T w + sf (x0 , v) −1 n→∞ s t n n lim Chứng minh Định lý giá trị trung bình khẳng định với a, b gần x0 ta có f (b) − f (a) − ∇f (x0 )T (b − a) ≤ b − a sup ∇f (x) − ∇f (x0 ) x∈[a,b] (1.2) Sử dụng bất đẳng thức cho a := x0 + tn v b := xn = x0 + tn v + −1 s t wn , ta có n n T f (xn ) − f (x0 + tn v) − s−1 n tn ∇f (x0 ) wn −1 ≤ sn tn wn sup ∇f (x) − ∇f (x0 ) x∈[x0 +tn v,xn ] Chia hai vế bất đẳng thức cho s−1 n tn đặt f (xn ) − f (x0 + tn v) yn := , −1 s t n n ta có yn − ∇f (x0 )T wn ≤ wn sup x∈[x0 +tn v,xn ] ∇f (x) − ∇f (x0 ) (1.3) 15 −1 rn tn ta thấy < sn < rn Vì sn → 2 n → ∞ Từ (1.12) ta suy w ∈ T (X, x¯, v) Vậy, C (X, x¯, v) ⊆ Nếu ta đặt sn := T (X, x¯, v) C (X, x¯, v) ⊆ T (X, x¯, v) Như vậy, C (X, x¯, v) ⊆ T (X, x¯, v) Mệnh đề phát biểu SOACQ đảm bảo SOZCQ ACQ đồng thời Nhưng trường hợp ngược lại, ACQ SOZCQ không suy SOACQ, tương ứng Ví dụ 2.2 2.3 16 Chương Điều kiện cần đủ tối ưu cấp Chương trình bày điều kiện cần đủ tối ưu cấp dạng nguyên thủy dạng đối ngẫu Khi sử dụng định lý luân phiên Motzkin, từ điều kiện cần tối ưu dạng nguyên thủy chứng minh điều kiện cần tối ưu dạng đối ngẫu Các kiến thức trình bày Chương tham khảo [2] 2.1 Điều kiện cần tối ưu cấp dạng nguyên thủy Trong phần này, ta trình bày điều kiện cần KKT cấp cho toán VOP với SOACQ Giả sử x ∈ X Nón phương giảm x xác định C(f, x) := {v ∈ Rp : ∇fk (x)T v ≤ 0, k ∈ K}, nón tới hạn C(x) xác định C(x) := {C(X, x) ∩ C(f, x)} Nón tới hạn CT (x) := T (X, x) ∩ C(x) Chú ý CT (x) ⊆ C(x) Ta cần tập C0 (f, x) := {v ∈ Rp : ∇fk (x)T v < 0, k ∈ K} Cho v ∈ C(f, x), tập số K(x, v) ký hiệu K(x, v) := {k ∈ K : ∇fk (x)T v = 0} 17 Ta định nghĩa tập C02 (f, x, v) := {(w, s) ∈ Rp ×R+ : ∇fk (x)T w+sfk (x, v) < ∀k ∈ K(x, v)} Cho x¯ ∈ X v ∈ C(¯ x) Trong phần ta sử dụng giả thiết (C): (C) nói cho toán VOP (¯ x, v), đạo hàm theo x, v), k ∈ K, gi (¯ x, v), i ∈ A(¯ x) hj (¯ x, v), j ∈ J tồn phương cấp fk (¯ x¯ theo phương v Bổ đề 2.1 Xét toán VOP Giả sử x∗ nghiệm tối ưu Pareto yếu địa phương v ∈ CT (x∗ ) \ C0 (f, x∗ ) phương tới hạn Giả sử f (¯ x, v) tồn Khi đó, ta có T (X, x∗ , v) ∩ C02 (f, x∗ , v) = ∅ Chứng minh Bởi ∇f liên tục x∗ f (x∗ , v) tồn Từ Mệnh đề 1.2 (ii) ta suy ∀w ∈ Rp , d2p f (x∗ , v, w) = ∇f (x∗ )T w + f (x∗ , v) d f (x∗ , v, w) = ∇f (x∗ )T w Do v ∈ CT (x∗ ) \ C0 (f, x∗ ), ta nhận v ∈ T (X, x∗ ) ∇f (x∗ )T v ∈ bd(−Rl+ ) Khi đó, theo Định lý 5.2 (ii) [11], ta có (a) ∇f (x∗ )T w + f (x∗ , v) ∈ / −intcone(Rl+ + ∇f (x∗ )T v) ∀w ∈ T (X, x∗ , v), (b) ∇f (x∗ )T w ∈ / −intcone(Rl+ + ∇f (x∗ )T v) ∀w ∈ T (X, x∗ , v) Xét (w, s) ∈ T (X, x∗ , v) Khi đó, từ (1.1) suy s−1 w ∈ T (X, x∗ , v) với s = w ∈ T (X, x∗ , v) với s = Vậy, từ (a)-(b) ta có ∇f (x∗ )T w + sf (x∗ , v) ∈ / −int cone(Rl+ + ∇f (x∗ )T v) (2.1) Ta khẳng định (w, s) ∈ / C02 (f, x∗ , v) Giả sử ngược lại (w, s) ∈ C02 (f, x∗ , v) Khi ∇fk (x∗ )T w + sfk (x∗ , v) < ∀k ∈ K(x∗ , v) (2.2) Ở ta giả sử K\K(x∗ , v) = ∅, K(x∗ , v) = K thì∇fk (x∗ )T v = với k ∈ K (2.2) mâu thuẫn với (2.1) Do ∇fk (x∗ )T v < 18 với k ∈ K \ K(x∗ , v), tồn số nguyên dương n0 đủ lớn cho ∇fk (x∗ )T w + sfk (x∗ , v) ∈ [∇fk (x∗ )T v, |∇fk (x∗ )T v|] ∀k ∈ K \ K(x∗ , v) n0 (2.3) Đặt ηk := − ∇fk (x∗ )T w + sfk (x∗ , v) − ∇fk (x∗ )T v với k ∈ K, n0 + từ (2.2) (2.3) ta thấy η = (η1 , , ηl )T ∈ intRl+ η + ∇f (x∗ )T v ∈ int(Rl+ + ∇f (x∗ )T )v Như ∇f (x∗ )T w + sf (x∗ , v) = −(n0 + 1)(η + ∇f (x∗ )T v) ∈ −int cone(Rl+ + ∇f (x∗ )T v) Điều mâu thuẫn với (2.1) Vì vậy, (w, s) ∈ / C02 (f, x∗ , v) Bây ta phát biểu điều kiện cần tối ưu cấp KKT cho toán VOP Định lý 2.1 (Điều kiện cần nguyên thủy) Xét toán VOP Giả sử x∗ nghiệm tối ưu Pareto yếu địa phương v ∈ CT (x∗ )\C0 (f, x∗ ) phương tới hạn Giả sử (C) (x∗ , v) Giả sử SOACQ (x∗ , v) Khi đó, hệ sau theo (w, s) ∈ Rp × R+ khơng tương thích: ∇fk (x∗ )T w + sfk (x∗ , v) < 0, k ∈ K(x∗ , v), ∇gi (x∗ )T w + sgi (x∗ , v) ≤ 0, i ∈ I(x∗ , v), ∇hj (x∗ )T w + shj (x∗ , v) = 0, j ∈ J (2.4) Chứng minh Bởi x∗ nghiệm tối ưu Pareto yếu địa phương, theo Bổ đề 2.1 sử dụng C (X, x∗ , v) = T (X, x∗ , v), ta có C (X, x∗ , v) ∩ C02 (f, x∗ , v) = ∅ Như vậy, theo định nghĩa C (X, x∗ , v) C02 (f, x∗ , v) điều cần chứng minh suy 19 Định lý 2.1 tổng quát hóa bổ sung Định lý 2.1 [5], hệ bất đẳng thức trường hợp đặc biệt với s = h không xét Cho x∗ ∈ X, ký hiệu M (x∗ ) tập tất nhân tử (θ, λ, µ) ∈ r Rl+ × Rm + × R , với (θ, λ, µ) = cho θk ∇fk (x∗ ) + λi ∇gi (x∗ ) + i∈A(x∗ ) k∈K µj ∇hj (x∗ ) = 0, (2.5) j∈J λi gi (x∗ ) = 0, i ∈ I (2.6) Chú ý v ∈ C(x∗ ) (θ, λ, µ) ∈ M (x∗ ) (2.5) (2.6) kéo theo θk ∇fk (x∗ )T v = 0, i∈A(x∗ ) k∈K θk = 0, λi ∇gi (x∗ )T v = 0, k ∈ K \ K(x∗ , v) (2.7) Cho v ∈ C(X, x∗ ), ký hiệu M (x∗ , v) tập tất nhân tử (θ, λ, µ) ∈ r Rl+ × Rm + × R , với (θ, λ, µ) = 0, phụ thuộc vào phương v 2.2 Điều kiện cần tối ưu cấp dạng đối ngẫu Định lý 2.2 (Điều kiện cần đối ngẫu) Xét toán VOP Giả sử x∗ nghiệm tối ưu Pareto yếu địa phương v ∈ CT (x∗ ) \ C0 (f, x∗ ) phương tới hạn khác không Giả sử (C) (x∗ , v) Giả sử SOACQ (x∗ , v) Khi đó, tồn (θ, λ, µ) ∈ M (x∗ , v), với θk > với k thuộc K(x∗ , v) cho (2.5)-(2.6) đúng, θk fk (x∗ , v) + k∈K λi gi (x∗ , v) + i∈A(x∗ ) µj hj (x∗ , v) ≥ j∈J (2.8) 20 Chứng minh Giả sử x∗ nghiệm tối ưu Pareto yếu địa phương Đặt K ∗ = K(x∗ , v), I ∗ = I(x∗ , v) ma trận A= fk (x∗ , v)  D= z = w s T ∇fk (x∗ ) , k∈K ∗ gi (x∗ , v) , i∈I ∗ T ∇hj (x∗ )  ∗ hj (x , v) C= T ∇gi (x∗ ) j∈J , sử dụng Định lý 2.1 ta suy hệ bất đẳng thức Az < 0, Cz ≤ 0, (0, , 0, −1)z ≤ 0, Dz = khơng tương thích theo z ∈ Rp+1 Áp dụng định lý Motzkin’s (xem [1], trang 38-39), tồn θk ≥ 0, k ∈ K(x∗ , v), λi ≥ 0, i ∈ {0} ∪ I(x∗ , v) µj ∈ R, j ∈ J cho θk ∇fk (x∗ ) + k∈K(x∗ ,v) λi ∇gi (x∗ ) + i∈I(x∗ ,v) θk fk (x∗ , v) + k∈K(x∗ ,v) µj ∇hj (x∗ ) = 0, j∈J λi gi (x∗ , v) + i∈I(x∗ ,v) µj hj (x∗ , v) = λ0 , j∈J θk > k∈K(x∗ ,v) Đặt θk = 0, k ∈ K \ K(x∗ , v) λi = 0, i ∈ I \ I(x∗ , v), ta suy điều phải chứng minh Rõ ràng, Mệnh đề 1.5, định lý bổ sung mở rộng Định lý 4.2 [5] xét toán véctơ với ràng buộc bất đẳng thức Nó bao gồm Định lý 5.2 [4] Định lý 4.4 [3], hàm fk , gi hj khả vi Fréchet hai lần Chú ý Định lý 2.2 tập trung vào trường hợp v = Thật vậy, chọn v = điều kiện Định lý 2.2 trở lại điều kiện cần tối ưu KKT cấp với điều kiện ACQ 21 Ví dụ 2.1 Xét toán VOP với liệu sau: f (x1 , x2 ) = (−x1 + bx22 , x2 )T , g(x1 , x2 ) = x1 − x22 ,  −x1 + x2 , x2 ≤ 0; h(x1 , x2 ) = −x + x3/2 , x > 0, 2 b > tham số, X = {x ∈ R2 : g(x) ≤ 0, h(x) = 0} x∗ = (0, 0)T Điểm x∗ nghiệm tối ưu Pareto yếu kiểm chứng Chú ý ∇f1 (x∗ )T = (−1, 0), ∇f2 (x∗ )T = (0, 1), ∇g(x∗ )T = (1, 0), ∇h(x∗ )T = (−1, 0), C(x∗ ) = {(0, v2 ) : v2 ≤ 0} C0 (f, x∗ ) = {(v1 , v2 ) : v1 > 0, v2 < 0} Lấy v = (0, −1)T ∈ C(x∗ ) \ C0 (f, x∗ ) Khi M (x∗ , v) = {(, , à) R2 ì R ì R : θ = α(1, 0), λ − µ = α > 0, λ ≥ 0}, g (x∗ , v) = −2, h (x∗ , v) = 2, f1 (x∗ , v) = 2b f2 (x∗ , v) = Ta dễ dàng tính T (X, x∗ , v) = C (X, x∗ , v) = {(w, s) ∈ R2 × R : w1 = 2s, s ≥ 0} Vậy, SOACQ (x∗ , v) Vì theo Định lý 2.2 tồn (θ, λ, µ) ∈ M (x∗ , v), với θ = thỏa mãn (2.8) Thật vậy, chọn (θ, λ, µ) = (1, 0, 2, 1) ∈ M (x∗ , v) θ1 f1 (x∗ , v) + θ2 f2 (x∗ , v) + λg (x∗ , v) + µh (x∗ , v) = 2(b − 1) > Ví dụ đồng thời minh họa SOACQ không kéo theo ACQ SOZCQ Ví dụ 2.2 (SOACQ khơng kéo theo ACQ) Xét Ví dụ 2.1 Rõ ràng SOCAQ (x∗ , v) với v ∈ C(x∗ ) \ C0 (f, x∗ ) với v = (0, 0)T ACQ không Thật vậy, T (X, x∗ ) = {(0, v2 ) : v2 ≤ 0}, C(X, x∗ ) = {(0, v2 ) : v2 ∈ R} Ví dụ 2.3 (SOACQ khơng kéo theo SOZCQ) Xét Ví dụ 2.1 thay ràng buộc đẳng thức h(x) = ràng buộc bất đẳng thức h(x) ≤ 22 −h(x) ≤ Khi tồn (x∗ , v), SOACQ Ví dụ 2.1 Cịn SOZCQ khơng Thật vậy, cl(Z(x∗ , v)) = {(2, 0)}, W (x∗ , v) = {(2, w2 ) : w2 ∈ R} Bởi x∗ nghiệm tối ưu Pareto yếu địa phương tốn nghiên cứu Ví dụ 2.1 nên SOACQ (x∗ , v) ACQ SOZCQ không đúng, Định lý 2.2 áp dụng được, Định lý 4.2 [5] không áp dụng 2.3 Điều kiện đủ tối ưu cấp Phần trước dẫn điều kiện cần cho nghiệm tối ưu Pareto yếu địa phương Phần trình bày điều kiện đủ cho nghiệm tối ưu Pareto Định nghĩa 2.1 Véctơ x∗ ∈ X gọi nghiệm Pareto địa phương chặt cấp 2, ký hiệu x∗ ∈ Strl(2, f, X) tồn δ > số ρ > cho (f (x) + Rl+ ) ∩ B(f (x∗ ), ρ x − x∗ ) = ∅ ∀x ∈ X ∩ B(x∗ , δ) \ {x∗ } Rõ ràng điều kiện Pareto chặt cấp phải nghiệm Pareto địa phương (cô lập) Sau sử dựng giả thiết (C0 ): (C0 ) gọi thỏa mãn cho toán VOP x¯, giả thiết (C) x¯ với v ∈ CT (¯ x) đạo hàm ∇fk , ∇gi , i ∈ A(¯ x) ∇hj ổn định x¯ Định lý 2.3 (Điều kiện đủ đối ngẫu) Xét toán VOP điểm chấp nhận x∗ ∈ X Giả sử (C0 ) x∗ Khi đó, x ∈ Strl(2, f, X) ∀v ∈ CT (x∗ ) \ {0} tồn (θ, λ, µ) ∈ M (x∗ , v) cho (2.5)-(2.6) đúng, 23 θk fk (x∗ , v) + λi gi (x∗ , v) + i∈A(x∗ ) k∈K µj hj (x∗ , v) > (2.9) j∈J Chứng minh Giả sử ngược lại x∗ ∈ / Strl(2, f, X) Khi đó, từ Định nghĩa 2.1 suy tồn dãy xn ∈ B(x∗ , ) ∩ X \ {x∗ } dn ∈ Rl+ cho n bn := f (xn ) − f (x∗ ) + dn ∈ B 0, t2n , (2.10) n tn := xn − x∗ Khi đó, xn → x∗ tn → 0+ n → ∞ Với dãy {xn }, ta giả sử tồn dãy ký hiệu {xn } cho xn − x∗ → v ∈ T (X, x∗ ) với v = := tn Rõ ràng, ta suy công thức f (xn ) − f (x∗ ) lim = ∇f (x∗ )T v n→∞ tn Chia (2.10) cho tn lấy giới hạn, ý bn /tn dần tới ta có f (xn ) − f (x∗ ) + dn dn lim = ∇f (x∗ )T v + lim = n→∞ n→∞ tn tn Như vậy, ∇f (x∗ )T v = limn→∞ (−dn /tn ) ∈ −Rl+ , dn ∈ Rl+ Do đó, v ∈ CT (x∗ ) \ {0} Theo giả thiết tồn (θ, λ, µ) ∈ M (x∗ , v) cho (2.5)-(2.6) (2.9) Ta định nghĩa hàm ψ : Ω → R ψ(x) := θk fk (x) + k∈K λi gi (x) + i∈A(x∗ ) µj hj (x), x ∈ Ω j∈J Từ (2.10) suy θ θ tn ≤ t , n n n tính bất đẳng thức thứ hai suy từ θT dn ≥ Liên θT f (xn ) − θT f (x∗ ) ≤ −θT dn + hệ điều với (2.5) (2.6) cho ta ψ(xn ) − ψ(x∗ ) − tn ∇ψ(x∗ )T ≤ θ t n n (2.11) 24 Bởi (C0 ) x∗ , từ Mệnh đề 1.2 (iii) suy đạo hàm theo phương d2c ψ(x∗ , v) tồn d2c ψ(x∗ , v) = lim 2t−2 ψ(xn ) − ψ(x∗ ) − tn ∇ψ(x∗ )T = ψ (x∗ , v) n n→∞ Như vậy, (2.11) chia cho t2n lấy giới hạn ta có ψ (x∗ , v) = θk fk (x∗ , v) + λi gi (x∗ , v) + i∈A(x∗ ) k∈K µj hj (x∗ , v) ≤ j∈J Điều mâu thuẫn với (2.9) Định lý 2.4 (Điều kiện đủ nguyên thủy) Xét toán VOP điểm chấp nhận x∗ ∈ X Giả sử (C0 ) x∗ Khi đó, x∗ ∈ Strl(2, f, X) ∀v ∈ CT (x∗ ) \ {0} hệ sau theo w ∈ Rp không tương thích: ∇fk (x∗ )T w + fk (x∗ , v) ≤ 0, k ∈ K, ∇gi (x∗ )T w + gi (x∗ , v) ≤ 0, i ∈ A(x∗ ), ∇hj (x∗ )T w + hj (x∗ , v) = 0, j ∈ J (2.12) Chứng minh Giả sử v ∈ CT (x∗ ) \ {0} Do tính khơng tương thích hệ (2.12), xét ma trận  ∇fk (x∗ ) ∇gi (x∗ ) C= fk (x∗ , v) gi (x∗ , v) k∈K w z = s T   ,D =  i∈A(x∗ ) T ∗ ∇hj (x ) hj (x∗ , v)  j∈J , ta suy hệ bất đẳng thức (0, , 0, −1)z < 0, Cz ≤ 0, Dz = khơng có nghiệm z ∈ Rp+1 Theo định lý Motzkin [1], tồn θ0 > 0, θk ≥ 0, k ∈ K, λi ≥ 0, i ∈ A(x∗ ) µj ∈ R, i ∈ J cho θk ∇fk (x∗ ) + k∈K λi ∇gi (x∗ ) + i∈A(x∗ ) θk fk (x∗ , v) + k∈K (2.13) µj hj (x∗ , v) = θ0 (2.14) j∈J λi gi (x∗ , v) + i∈A(x∗ ) µj ∇hj (x∗ ) = 0, j∈J 25 Bằng cách đặt λi = 0, i ∈ I \ A(x∗ ), liên hệ với (2.13), ta suy (2.5)-(2.6) Từ (2.14) ta đến (2.9) Do đó, theo Định lý 2.3, ta suy điều phải chứng minh Để kết thúc phần này, ta cho ví dụ minh họa kết Định lý 2.3, kết ([6], Mục 4) khơng Ví dụ 2.4 Xét toán VOP với liệu sau đây: f (x1 , x2 , x3 ) = (x1 + bx22 + cx23 , −x2 , x3 )T ,  −x1 + x2 , x1 ≥ 0; g(x1 , x2 , x3 ) = −x − x2 , x < 0, b, c ∈ R tham số x∗ = (0, 0, 0)T Tính tối ưu x∗ xét Chú ý f C g C 1,1 , X = {x ∈ R2 : g(x) ≤ 0}, ∇f1 (x∗ )T = (1, 0, 0), ∇f2 (x∗ )T = (0, −1, 0), ∇f3 (x∗ )T = (0, 0, 1), ∇g(x∗ )T = (−1, 0, 0), M (x∗ , v) = {(θ, λ) ∈ R3 × R : θ = α(1, 0, 0), λ = α > 0} C(x∗ ) = {(0, v2 , v3 ) : v2 ≥ 0, v3 ≤ 0} Khi đó, rõ ràng f2 (x∗ , v) = f3 (x∗ , v) = với v ∈ C(x∗ ) = {(0, v2 , v3 ) : v2 ≥ 0, v3 ≤ 0} Nếu ta xét v = (0, 0, v2 )T ∈ C(x∗ ) với v3 = Khi f1 (x∗ , v) = 2cv32 g (x∗ , v) = Cho (θ, λ) = (1, 0, 0, 1) ∈ M (x∗ , v), ta có θ1 f1 (x∗ , v) + θ2 f2 (x∗ , v) + θ3 f3 (x∗ , v) + λg (x∗ , v) = 2cv32 Nếu ta xét v = (0, v2 , 0)T ∈ C(x∗ ) với v2 = Khi f1 (x∗ , v) = 2bv22 g (x∗ , v) = 2v22 Cho (θ, λ) = (1, 0, 0, 1) ∈ M (x∗ , v), ta có θ1 f1 (x∗ , v) + θ2 f2 (x∗ , v) + θ3 f3 (x∗ , v) + λg (x∗ , v) = 2(b + 1)v22 Ta phải xét (0, v2 , v3 )T ∈ C(x∗ ) với v2 v3 < Khi f1 (x∗ , v) = 2bv22 + 2cv32 g (x∗ , v) = 2v22 Cho (θ, λ) = (1, 0, 0, 1) ∈ M (x∗ , v), ta có θ1 f1 (x∗ , v) + θ2 f2 (x∗ , v) + θ3 f3 (x∗ , v) + λg (x∗ , v) = 2(b + 1)v22 + 2cv32 26 Do đẳng thức (2.9) thỏa mãn với ∀v ∈ C(x∗ ) \ {(0, 0, 0)} b > −1 c > Do đó, theo Định lý 2.3, b > −1 c > điểm x∗ nghiệm tối ưu Pareto chặt cấp Tuy nhiên ví dụ sử dụng để phát triển định lý [6], giả thiết (chính xác (H) ([6], Mục 4) không Thật vậy, ta lấy phương tới hạn v = (0, 0, −1)T chọn w = (0, 1, 0)T ∈ v ⊥ \ {(0, 0, 0)} ∇g(x∗ )T w = λ, ∇g(x∗ )T w ≮ với (θ, λ) ∈ M (x∗ , v) 27 Kết luận Luận văn trình bày kết M Feng S Li đăng tạp chí Optimization (2018) điều kiện cần đủ tối ưu dạng nguyên thủy đối ngẫu cho toán tối ưu vectơ có ràng buộc đẳng thức bất đẳng thức với hàm khả vi liên tục Fréchet Nội dung luận văn bao gồm: - Các khái niệm đạo hàm theo phương cấp 2, tập tiếp tuyến cấp 2, điều kiện quy Abadie cấp 2; - Các điều kiện cần tối ưu cấp dạng nguyên thủy dạng đối ngẫu; - Các điều kiện đủ tối ưu cấp dạng nguyên thủy dạng đối ngẫu; - Các ví dụ minh họa điều kiện tối ưu trình bày Điều kiện cần đủ tối ưu dạng nguyên thủy đối ngẫu cho tốn tối ưu vectơ trơn khơng trơn đề tài nhiều tác giả quan tâm nghiên cứu 28 Tài liệu tham khảo Tiếng Anh [1] Mangasarian O.L (1994), Nonlinear programming Philadelphia: SIAM [2] Feng M., Li S (2018), “On second-order optimality conditions for continuously Fréchet differentiable vector optimization problems”, Optimization, 67(12), pp 2117-2137 [3] Hachimi M, Aghezzaf B (2007), “New results on second-order optimality conditions in vector optimization problems”, J Optim Theory Appl, 135, pp 117-133 [4] Bigi G, Castellani M (2000), “Second order optimality conditions for differentiable multiobjective problems”, RAIRO Oper Res, 34, pp 411-426 [5] Ivanov V.I (2015), “Second-order optimality conditions for vector problems with continuously Fréchet differentiable data and secondorder constraint qualifications”, J Optim Theory Appl, 166, pp 777–790 [6] Gutiérrez C, Jiménez B, Novo V (2010), “On second-order Fritz John type optimality conditions in nonsmooth multiobjective programming”, Math Program, 123(1), pp 199-223 29 [7] Cambini A, Martein L, Vlach M (1999), “Second-order tangent sets and optimality conditions”, Math Japon, 49, pp 451-461 [8] Jiménez B, Novo V (2004), “Optimality conditions in differentiable vector optimization via second-order tangent sets”, Appl Math Optim, 49(2), pp 123–144 [9] Jiménez B, Novo V (2003), “Optimality conditions in directionally differentiable Pareto problems with a set constrained via tangent cones”, Numer Funct Anal Optim, 24, pp 557–574 [10] Penot J.P (1999), “Second-order conditions for optimization problems with constraints”, SIAM J Control Optim, 37, pp 303-318 [11] Gutiérrez C, Jiménez B, Novo V (2009), “New second-order directional derivative and optimality conditions in scalar and vector optimization”, J Optim Theory Appl, 142, pp 85-106 [12] Jiménez B, Novo V (2004), “First and second order sufficient conditions for strict minimality in nonsmooth vector optimization”, J Math Anal Appl, 284(2), pp 496-510 [13] Minchenko L, Stakhovski S (2011), “On relaxed constant rank regularity condition in mathematical programming”, Optimization, 60, pp 429-440 [14] Jiménez B (2002), “Strict efficiency in vector optimization”, J Math Anal Appl, 265(2), pp 264-284 ... đủ tối ưu cấp 16 2. 1 Điều kiện cần tối ưu cấp dạng nguyên thủy 16 2. 2 Điều kiện cần tối ưu cấp dạng đối ngẫu 19 2. 3 Điều kiện đủ tối ưu cấp 22 Kết luận 27 Tài... XUÂN SINH ĐIỀU KIỆN TỐI ƯU CẤP CHO BÀI TOÁN TỐI ƯU VECTƠ VỚI CÁC HÀM LỚP C1 Chuyên ngành: Toán ứng dụng Mã số : 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS Đỗ Văn Lưu THÁI... Fréchet Với điều kiện quy kiểu Abadie, M Feng S Li [2] thiết lập điều kiện cần tối ưu Karush-Kuhn-Tucker cấp cho toán tối ưu vectơ Hơn nữa, điều kiện đủ cấp cho nghiệm Pareto địa phương chặt toán tối