BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI NGUYỄN VĂN PHÚ BÀI TOÁN TỐI ƯU TOÀN PHƯƠNG LỒI VỚI RÀNG BUỘC TUYẾN TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI Nguyễn Văn Phú BÀI TOÁN TỐI ƯU TOÀN PHƯƠNG LỒI VỚI RÀNG BUỘC TUYẾN TÍNH Chuyên ngành: Toán giải tích Mã số: 60 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS TS Nguyễn Năng Tâm Hà Nội - 2015 ii LỜI CẢM ƠN Luận văn hoàn thành trường Đại học Sư phạm Hà Nội hướng dẫn thầy giáo PGS TS Nguyễn Năng Tâm Sự giúp đỡ hướng dẫn tận tình song nghiêm túc thầy suốt trình thực luận văn giúp tác giả trưởng thành nhiều cách tiếp cận vấn đề Tác giả xin bày tỏ lòng biết ơn, lòng kính trọng sâu sắc thầy Tác giả xin trân trọng cảm ơn Ban giám hiệu trường Đại học Sư phạm Hà Nội 2, phòng Sau đại học, thầy cô giáo nhà trường thầy cô giáo dạy cao học chuyên ngành Toán giải tích giúp đỡ, tạo điều kiện thuận lợi cho tác giả suốt trình học tập Tác giả xin chân thành cảm ơn Hà Nội, ngày 10 tháng 08 năm 2015 Tác giả Nguyễn Văn Phú LỜI CAM ĐOAN Luận văn hoàn thành trường Đại Học Sư phạm Hà Nội hướng dẫn PGS TS Nguyễn Năng Tâm Tôi xin cam đoan luận văn công trình nghiên cứu riêng Trong trình nghiên cứu hoàn thành luận văn kế thừa thành khoa học nhà khoa học đồng nghiệp với trân trọng biết ơn Tôi xin cam đoan thông tin trích dẫn luận văn rõ nguồn gốc Hà Nội, ngày 10 tháng 08 năm 2015 Tác giả Nguyễn Văn Phú Mục lục Lời cảm ơn iii Lời cam đoan iv Bảng ký hiệu vii Mở đầu 1 Kiến thức chuẩn bị 1.1 Tập lồi hàm lồi 1.1.1 Tập lồi 1.1.2 Nón lùi xa tập lồi 1.1.3 Hàm lồi 1.2 Hệ bất phương trình tuyến tính tập lồi đa diện 11 1.2.1 Hệ bất phương trình tuyến tính 11 1.2.2 Tập lồi đa diện 13 1.3 Hàm toàn phương lồi 13 1.4 Bài toán tối ưu lồi 15 Bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính 20 2.1 Phát biểu toán v 20 2.2 Sự tồn nghiệm 22 2.3 Điều kiện cực trị 27 2.4 Tính ổn định tập nghiệm 41 2.4.1 Tính nửa liên tục ánh xạ nghiệm 42 2.4.2 Tính nửa liên tục ánh xạ nghiệm 46 2.5 Hàm giá trị tối ưu toán có tham số 52 Kết luận 58 Tài liệu tham khảo 59 vi BẢNG KÝ HIỆU N Tập số tự nhiên R Tập số thực R+ Tập số thực dương ∅ Tập hợp rỗng Rn Không gian Euclide n chiều trường số thực x, y = xT y = x = n j=1 xj n j=1 xj yj Tích vô hướng hai vectơ x y Chuẩn Euclide vectơ x B (x, δ) ¯ (x, δ) B Hình cầu mở tâm x, bán kính δ [x, y] Đoạn thẳng đóng nối x y 0+ (C) f¯ Nón lùi xa tập lồi C domf Tập hữu dụng hàm f epi(f ) Trên đồ thị hàm f ∂f (x) Dưới vi phân f x ∇f (x) Vectơ gradient f x Sol (P ) Tập nghiệm toán (P ) Sol (D, A, c, b) Tập nghiệm toán tối ưu toàn phương (QP ) Bài toán tối ưu toàn phương Rm×n Không gian ma trận m × n Rn×n S Không gian ma trận đối xứng n × n AT Ma trận chuyển vị A T∆ (¯ x) Nón tiếp ∆ x¯ Hình cầu đóng tâm x, bán kính δ Hàm bao đóng f Kết thúc chứng minh MỞ ĐẦU Lý chọn đề tài Quy hoạch toàn phương lồi phận quy hoạch toàn phương nghiên cứu nhiều gần mang tính hoàn thiện cách chuẩn mực Tuy vậy, việc tìm hiểu khía cạnh khác quy hoạch toàn phương lồi cách thấu đáo việc làm có nhiều ý nghĩa (xem [2], [4] tài liệu tham khảo đó) Sau học kiến thức Toán giải tích, với mong muốn tìm hiểu sâu kiến thức học, mối quan hệ ứng dụng chúng, chọn đề tài nghiên cứu: “ Bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính ” Mục đích nghiên cứu Nghiên cứu chi tiết toàn diện tính chất định tính toán tối ưu toàn phương lồi với ràng buộc tuyến tính Nhiệm vụ nghiên cứu Nghiên cứu toán tối ưu toàn phương lồi với ràng buộc tuyến tính dựa tài liệu có Phân tích toán sau nghiên cứu khía cạnh toán Đối tượng phạm vi nghiên cứu Hàm tối ưu toàn phương lồi Hệ bất phương trình tuyến tính Bài toán tối ưu lồi Điều kiện cực trị Sự tồn nghiệm tính ổn định tập nghiệm toán tối ưu toàn phương lồi với ràng buộc tuyến tính Phương pháp nghiên cứu Thu thập thông tin toán tối ưu toàn phương lồi với ràng buộc tuyến tính Sưu tầm, nghiên cứu tài liệu liên quan Suy luận logic, phân tích, tổng hợp xếp trình bày kiến thức thu thập theo phương pháp Giải tích Đóng góp luận văn Luận văn trình bày tổng quan có hệ thống với phân tích sâu sắc, chi tiết số tính chất toán tối ưu toàn phương lồi với ràng buộc tuyến tính Chương Kiến thức chuẩn bị 1.1 Tập lồi hàm lồi Trong phần trình bày số khái niệm liên quan đến tập lồi hàm lồi Đây kiến thức làm tảng cho việc nghiên cứu toán tối ưu toàn phương lồi với ràng buộc tuyến tính Nội dung chương tham khảo dựa tài liệu [1] - [3] 1.1.1 Tập lồi Định nghĩa 1.1.1 [1] Tập C Rn gọi tập lồi αx + (1 − α)y ∈ C, ∀x, y ∈ C, ∀α ∈ [0, 1] Chú ý rằng, ta quy ước tập rỗng tập lồi Mệnh đề 1.1.1 [1] (a) Giao ∩i∈I Ci họ tập lồi {Ci |i ∈ I} tập lồi (b) Tổng C1 + C2 hai tập lồi C1 C2 tập lồi (c) Nếu tập C lồi tập λC lồi với λ Hơn nữa, C tập 45 x0 ∈ Rn Ta có x0 ∈ ∆ (A, b) Cố định x ∈ ∆ (A, b) Giả sử (b2 ) hệ (2.29) quy Khi tồn dãy ξ k , ξ k ∈ ∆ Ak , bk , ∀k ∈ N, cho lim xk = x Từ f xk ≤ f ξ k , lấy k → ∞ ta thu k→∞ ≤ f (x) Như x0 ∈ Sol (D, A, c, b) ⊂ Ω Điều mâu thuẫn f x với thực tế xk ∈ / Ω, ∀k Giả sử xk không bị chặn Bằng cách lấy dãy cần, ta giả sử xk → ∞ Từ xk ∈ Sol Dk , Ak , ck , bk với k có tồn λk ∈ Rm cho Dk xk − Ak T λk + ck ≤ 0, Ak xk − bk ≤ 0, λk ≥ 0, xk Từ xk , λk T Dk xk − Ak xk , λk T (2.32) λk + ck + λk T Ak xk − bk = (2.33) → ∞, không tính tổng quát ta giả sử = 0, ∀k, dãy vectơ xk , λk = (xk , λk ) λk xk , (xk , λk ) (xk , λk ) ¯ ∈ Rn × Rm với hội tụ đến số x¯, λ (2.31) (2.32) cho xk , λk (2.31) xk , λk ¯ x¯, λ = Chia hai vế , chia hai vế (2.33) cho , lấy giới hạn k → ∞, ta thu ¯ ≤ 0, A¯ D¯ x − AT λ x ≤ 0, (2.34) ¯ ≥ 0, λ (2.35) ¯ +λ ¯ T A¯ x¯T D¯ x − AT λ x = (2.36) Hệ (2.34) - (2.36) chứng minh x¯ ∈ S (D, A, 0, 0) Theo (b1 ), x¯ = Vì ¯ ≤ 0, λ ¯ ≥ −AT λ ¯ = 0, Kết hợp (2.37) (b2 ) ta có λ ¯ x¯, λ (2.37) = 0, mâu thuẫn 46 2.4.2 Tính nửa liên tục ánh xạ nghiệm Theo định nghĩa, hàm đa trị Sol (.) liên tục (D, A, c, b) đồng thời nửa liên tục nửa liên tục điểm Định lý 2.4.3 [4] Ánh xạ nghiệm Sol (.) (P ) nửa liên tục (D, A, c, b) ba điều kiện sau thỏa mãn: (a) hệ Ax ≤ b quy, (b) Sol (D, A, 0, 0) = {0} , (c) |Sol (D, A, c, b)| = Để chứng minh Định lý ta cần số Bổ đề Bổ đề 2.4.3 [7] Nếu Sol (.) nửa liên tục (D, A, c, b), hệ Ax ≤ b quy Chứng minh Nếu hệ Ax ≤ b không quy, theo [7, lemma 3], tồn dãy Ak , bk ∈ Rm×n ×Rm tiến tới (A, b) cho ∆ Ak , bk = ∅ cho k Vì thế, Sol D, Ak , c, bk = ∅ cho k, trái với giả thiết nửa liên tục tập nghiệm Bổ đề 2.4.4 [4] Nếu hàm đa trị Sol (.) nửa liên tục (D, A, c, b), Sol (D, A, 0, 0) = {0} Chứng minh Ngược lại, giả sử Sol (D, A, 0, 0) = ∅ Sau có vectơ khác không x¯ ∈ Rn cho A¯ x ≤ 0, x¯T D¯ x ≤ (2.38) Từ ∆ (A, b) = ∅, từ (2.38) ta có ∆ (A, b) không xác định Cho ε > 0, ta nhận từ (2.38) x¯T (D − εE) x¯ < Vì thế, cho x ∈ ∆ (A, b), f (x + t¯ x) = (x + t¯ x)T (D − εE) (x + t¯ x) + cT (x + t¯ x) → −∞ 47 t → ∞ Như thế, Sol (D − εE, A, c, b) = ∅ Điều mâu thuẫn với giả sử Sol (.) nửa liên tục (D, A, c, b) Bổ đề 2.4.5 [4] (i) Nếu Sol (D, A, 0, 0) = {0} đó, cho (c, b) ∈ Rn × Rm , Sol (D, A, c, b) tập compact (ii) Nếu Sol (D, A, 0, 0) = {0} ∆ (A, b) không rỗng, Sol (D, A, c, b) không rỗng với c ∈ Rn Chứng minh (i) Giả sử Sol (D, A, 0, 0) = {0}, Sol (D, A, c, b) bất định với vài (c, b) Khi có dãy xk ⊂ Sol (D, A, c, b) cho xk → ∞ k → ∞ Cố định x ∈ ∆ (A, b), ta có 1 k T x Dxk + cT xk ≤ xT Dx + cT x, (2.39) 2 Axk ≤ b (2.40) Ta giả sử dãy xk −1 k x hội tụ tới x¯ với x¯ = Sử dụng (2.39) (2.40) dễ dàng cho thấy x¯T D¯ x ≤ 0, A¯ x ≤ Điều mâu thuẫn với Sol (D, A, 0, 0) = {0} Ta chứng minh Sol (D, A, c, b) tập bị chặn Khi Sol (D, A, 0, 0) = {0} bị đóng, tập compact (ii) Lấy Sol (D, A, 0, 0) = {0} , ∆ (A, b) = ∅ lấy c ∈ Rn cách tùy ý Nếu dạng toàn phương f (x) = xT Dx + cT x bị chặn khối đa diện ∆ (A, b), tập hợp nghiệm Sol (D, A, c, b) không rỗng với k, xk k T T x Dxk + ck xk ≤ (2.41) −1 k → ∞, xk x hội tụ tới x¯ k → ∞ Nó đơn giản cho thấy x¯ ∈ ∆ (A, 0) Chia vế (2.41) cho xk lấy k → ∞ ta có x¯T D¯ x ≤ Cũng x¯ = 1, Sol (D, A, 0, 0) = {0}, 48 Bổ đề 2.4.6 [4] Nếu hàm đa trị Sol (.) nửa liên tục (D, A, c, b), tập Sol (D, A, c, b) hữu hạn Bổ đề 2.4.7 [4] Cho tập G := {(D, A) : Sol (D, A, 0, 0) = {0}} mở RSn×n × Rm×n Chứng minh Ngược lại, giả sử có dãy Dk , Ak hội tụ tới (D, A) ∈ G cho Sol Dk , Ak , 0, = {0} , ∀k Khi với k tồn vectơ xk cho xk = Ak xk ≤ 0, xk T Dk xk ≤ (2.42) Không tính tổng quát, ta giả sử xk hội tụ tới x0 với x0 = Lấy giới hạn (2.42) k → ∞, ta thu Ax0 ≤ 0, x0 T Dx0 ≤ Điều mâu thuẫn với giả sử Sol (D, A, 0, 0) = {0} Bổ đề 2.4.8 [4] Nếu ánh xạ nghiệm Sol (D, A, c, b) hữu hạn với α ⊂ {1, , m} β ⊂ {1, , n}, ta có |Sol (D, A, c, b) ∩ F (α, β)| ≤ Bổ đề 2.4.9 [4] Nếu hàm đa trị Sol (.) nửa liên tục (D, A, c, b) |Sol (D, A, c, b)| = Chứng minh Ngược lại, giả sử Sol (D, A, c, b) ta tìm thấy hai vectơ khác x¯, y¯ Lấy J (¯ x) = {j : x¯j = 0}, J (¯ y ) = {j : y¯j = 0} Nếu J (¯ x) = J (¯ y ), tồn j0 cho x¯j0 = 0, y¯j0 > tồn j1 cho x¯j1 > 0, y¯j1 = Do đối xứng, nên ta xét trường hợp Cho y¯ ∈ Sol (D, A, c, b) yj0 , có tập mở U y¯ 49 cho f (y) ≥ f (¯ y ) yj0 > với y ∈ U Cố định ε > đặt c (ε) = (ci (ε)) sau ci (ε) = ci i = j0 ci + ε i = j0 Lấy fε (x) = f (x) + εxj0 , mà trước f (x) = T x Dx + cT x Xét toán toàn phương M in fε (x) với x ∈ ∆ (A, b) , có tập nghiệm Sol (D, A, c (ε) , b) Cho y ∈ U ta có fε (y) = f (y) + εyj0 > f (y) ≥ f (¯ y) = f (¯ x) = fε (¯ x) Vì y ∈ / Sol (D, A, c (ε) , b) Tuy nhiên Sol (D, A, c (ε) , b) ∩ U = ∅ (2.43) Từ ε > nhỏ tùy ý, (2.43) mâu thuẫn với giả thiết Sol (.) nửa liên tục (D, A, c, b) Ta giả sử J (¯ x) = J (¯ y ) Lấy α, α tập số cho x¯ ∈ F (α, β) , y¯ ∈ F (α , β) , β bù J (¯ x) = J (¯ y ) {1, , n} Từ Bổ đề 2.4.6, Sol (D, A, c, b) tập hữu hạn Khi đó, từ Bổ đề 2.4.8, α = α Vì tập α\α , α \α không rỗng Bởi tính đối xứng, ta xét trường hợp Lấy i0 ∈ α\α Khi đó, ta có (A¯ x)i0 < bi0 , (A¯ y )i0 = bi0 (2.44) Với Sol (D, A, c, b) hữu hạn, tìm thấy miền W y¯ cho Sol (D, A, c, b) ∩ W = {¯ y} (2.45) 50 Cố định ε > đặt b (ε) = (bi (ε)), bi (ε) = bi i = i0 bi + ε i = i0 Theo (2.44), tồn δ > cho x¯ ∈ ∆ (A, b (ε)) với ε ∈ (0, δ) Từ ∆ (A, b (ε)) ⊂ ∆ (A, b), ta có inf x∈∆(A,b(ε)) f (x) ≥ inf f (x) = f (¯ x) x∈∆(A,b) Do đó, với ε ∈ (0, δ), x¯ ∈ Sol (D, A, c, b (ε)) Ngoài ra, Sol (D, A, c, b (ε)) ⊂ Sol (D, A, c, b) Rõ ràng y¯ ∈ / ∆ (A, b (ε)) Khi Sol (D, A, c, b (ε)) ⊂ Sol (D, A, c, b) \ {¯ y } Vì thế, theo (2.45), Sol (D, A, c, b (ε)) ∩ W = ∅ với ε ∈ (0, δ) Điều mâu thuẫn với nửa liên tục Sol (.) (D, A, c, b) Sau chứng minh Định lý 2.4.3 Chứng minh Nếu Sol (.) nửa liên tục (D, A, c, b) từ Bổ đề 2.4.3, 2.4.4 2.4.9, ta (a), (b) (c) Ngược lại, giả sử điều kiện (a), (b) (c) thỏa mãn Lấy Ω tập mở chứa nghiệm x¯ ∈ Sol (D, A, c, b) Theo (a), tồn δ1 > cho ∆ (A , b ) = ∅ với cặp (A , b ) thỏa mãn max { A − A , b − b } < δ1 Theo (b) Bổ đề 2.4.7, tồn δ2 > cho Sol (D , A , 0, 0) = {0} với cặp (D , A ) thỏa mãn max { D − D , A − A } ≤ δ2 Cho δ := {δ1 , δ2 }, theo khẳng định thứ Bổ đề 2.4.5 ta có Sol (D , A , c , b ) = {∅} với (D , A , c , b ) thỏa mãn max { D − D , A − A , c − c , b − b } < δ (2.46) Theo (a) (b), tiếp Định lý 2.4.1 Sol (.) nửa liên tục (D, A, c, b) Vì Sol (D , A , c , b ) ⊂ Ω với (D , A , c , b ) thỏa mãn (2.46) Thấy Sol (.) nửa liên tục (D, A, c, b) 51 Hệ 2.4.2 [4] Nếu hàm đa trị Sol (.) nửa liên tục (D, A, c, b) nửa liên tục (D, A, c, b), cố định điểm Hệ 2.4.3 [4] Nếu D ma trận nửa xác định âm, hàm đa trị Sol (.) cố định (D, A, c, b) điều kiện sau thỏa mãn (i) hệ Ax ≤ b quy, (ii) ∆ (A, b) tập compact, (iii) |Sol (D, A, c, b)| = Chứng minh Giả sử Sol (.) nửa liên tục (D, A, c, b) Theo Định lý 2.4.3, điều kiện (i) (ii) thỏa mãn Ngoài ra, Sol (D, A, 0, 0) = {0} (2.47) Ta khẳng định ∆ (A, 0) = {0} Thật vậy, theo giả thiết, xT Dx ≤ với x ∈ ∆ (A, 0) Nếu không tồn x¯ ∈ ∆ (A, 0) với tính chất x¯T D¯ x < Sol (D, A, 0, 0) = ∆ (A, 0), (2.47) suy ∆ (A, 0) = {0} Nếu x¯T D¯ x < với x¯ ∈ ∆ (A, 0) rõ ràng Sol (D, A, 0, 0) = ∅, Tính chất (ii) suy trực tiếp từ đẳng thức ∆ (A, 0) = {0} Ngược lại, giả sử (i), (ii) (iii) thỏa mãn Như ∆ (A, b) = ∅ theo (i), giả sử (ii) cho ∆ (A, 0) = {0} Vì thế, Sol (D, A, 0, 0) = {0} Từ điều kiện (a), (b) (c) Định lý 2.4.3 thỏa mãn, Sol (.) nửa liên tục (D, A, c, b) Hệ 2.4.4 [4] Nếu D ma trận xác định dương, hàm đa trị Sol (.) cố định (D, A, c, b) hệ Ax ≤ b quy 52 2.5 Hàm giá trị tối ưu toán có tham số Xét vấn đề tổng quát toán toàn phương với ràng buộc tuyến tính,   M in f (x, c, D) := xT Dx + cT x  x ∈ ∆ (A, b) := {x ∈ Rn : Ax ≤ b} (2.48) tùy thuộc vào tham số ω = (D, A, c, b) ∈ Ω, Ω := Rn×n × Rm×n × Rn × Rm S ¯ Tập nghiệm (2.48) kí hiệu Sol (D, A, c, b) Hàm ϕ : Ω → R định nghĩa ϕ (ω) = inf {f (x, c, D) : x ∈ ∆ (A, b)} gọi hàm giá trị tối ưu toán có tham số (2.48) Nếu v T Dv ≥ hay v T Dv ≤ , ∀v ∈ Rn f (., c, D) hàm lồi (hay lõm) (2.48) toán (QP ) lồi (hay lõm) Nếu điều kiện không xác định (2.48) toán không xác định Trước thu tính chất mong muốn, ta nêu số bổ đề Bổ đề 2.5.1 [2] Nếu ∆ (A, b) khác rỗng Sol (D, A, 0, 0) = {0}, với c ∈ Rn , Sol (D, A, c, b) tập compact khác rỗng Chứng minh Lấy ∆ (A, b) khác rỗng Sol (D, A, 0, 0) = {0} Giả sử Sol (D, A, c, b) = ∅ với c ∈ Rn Theo Định lý Frank-Wolfe, có tồn dãy xk cho Axk ≤ b với k f xk , c, D = k x T Dxk + cT xk → −∞ k → ∞ Rõ ràng xk → +∞ k → ∞ Bằng cách lấy dãy cần, ta giả sử xk −1 k x → x¯ ∈ Rn f xk , c, D = k x T Dxk + cT xk < (2.49) 53 Ta có xk b A k ≤ k x x Lấy k → ∞, ta thu x¯ ∈ ∆ (A, 0) Chia hai vế (2.49) cho xk lấy k → ∞, ta x¯T D¯ x ≤ Từ x¯ = ta có Sol (D, A, 0, 0) = {0} Điều mâu thuẫn với giả thiết Sol (D, A, 0, 0) = {0} Như Sol (D, A, c, b) rỗng với c ∈ Rn Giả sử, trái với khẳng định ta, Sol (D, A, c, b) không xác định với c ∈ Rn Khi có tồn dãy xk ⊂ Sol (D, A, c, b) cho xk → ∞ k → ∞ xk −1 k x hội tụ đến số x¯ ∈ Rn Lấy x ∈ ∆ (A, b), ta có k x T Dxk + cT xk ≤ xT Dx + cT x, Axk ≤ b (2.50) (2.51) Chia hai vế (2.50) cho xk , hai vế (2.51) cho xk , lấy k → ∞, ta thu x¯T D¯ x ≤ 0, A¯ x ≤ Như Sol (D, A, 0, 0) = {0} mâu thuẫn Ta chứng minh với c ∈ Rn , tập nghiệm Sol (D, A, c, b) bị chặn Cố định x¯ ∈ Sol (D, A, c, b) ta có Sol (D, A, c, b) = {x ∈ ∆ (A, b) : f (x, c, D) = f (¯ x, c, D)} Do Sol (D, A, c, b) tập đóng Sol (D, A, c, b) tập compact Tiếp theo Định lý tính liên tục hàm giá trị tối ưu ϕ Định lý nêu hàng loạt điều kiện cần đủ cho liên tục ϕ điểm ω = (D, A, c, b), ϕ có giá trị hữu hạn Định lý 2.5.1 [4] Lấy (D, A, c, b) ∈ ω Giả sử ϕ (D, A, c, b) = ±∞ Khi đó, hàm giá trị tối ưu ϕ (.) liên tục (D, A, c, b) hai điều kiện sau thỏa mãn: 54 (a) hệ Ax ≤ b quy, (b) Sol (D, A, 0, 0) = {0} Chứng minh Điều kiện cần: Đầu tiên, giả sử ϕ (.) liên tục ω := (D, A, c, b) ϕ (ω) = ±∞ Nếu (a) vi phạm đó, từ nhận xét 2.1, có tồn dãy Ak , bk Rm×n × Rm hội tụ tới (A, b) cho, với k, hệ Ak x ≤ bk vô nghiệm Xét dãy D, Ak , c, bk Từ ∆ Ak , bk = ∅,ϕ D, Ak , c, bk = +∞ với k Hàm ϕ (.) liên tục D, Ak , c, bk ω hội tụ tới ω, ta có lim ϕ D, Ak , c, bk = ϕ (D, A, c, b) = ±∞ k→∞ Dẫn đến mâu thuẫn Do (a) thỏa mãn Bây giờ, giả sử (b) sai Khi đó, có vectơ khác không x¯ ∈ Rn cho A¯ x ≤ 0, x¯T D¯ x ≤ (2.52) Xét dãy Dk , A, c, b , mà Dk := D − E, E ma trận đơn vị k Rn×n Từ giả thiết ϕ (ω) = ±∞ dẫn đến ∆ (A, b) khác rỗng Khi từ (2.52) ta suy ∆ (A, b) không xác định Với k, từ (2.52) ta có x¯T Dk x¯ = x¯T D − E x¯ < k Vì thế, với x thuộc ∆ (A, b) t > 0, ta có x + t¯ x ∈ ∆ (A, b) x)T Dk (x + t¯ x) + cT (x + t¯ x) → −∞ f x + t¯ x, c, Dk = (x + t¯ t → ∞ Điều ngụ ý rằng, với k, Sol Dk , A, c, b = ∅ ϕ Dk , A, c, b = −∞ Dẫn đến mâu thuẫn, ϕ (.) liên tục ω ϕ (ω) = ±∞ Do (b) Điều kiện đủ: Giả sử (a), (b) thỏa mãn Dk , Ak , ck , bk ⊂Ω 55 dãy hội tụ tới ω Từ Bổ đề 2.4.2, điều kiện (a) suy tồn số nguyên dương k0 cho ∆ Ak , bk = ∅ với k ≥ k0 Điều kiện (b) suy tập G := (D, A) ∈ Rn×n × Rm×n : Sol (D, A, 0, 0) = {0} S mở Vì tồn số nguyên dương k1 ≥ k0 cho Sol Dk , Ak , 0, = {0} với k ≥ k1 Theo Bổ đề 2.5.1, Sol Dk , Ak , ck , bk = ∅ với k ≥ k1 Do đó, với k ≥ k1 tồn xk ∈ Rn thỏa mãn k x ϕ Dk , Ak , ck , bk = T Dxk + ck T k x , Ak xk ≤ bk (2.53) (2.54) Từ ϕ (ω) = ±∞, Định lý Frank-Wolfe cho thấy Sol (D, A, c, b) = ∅ Lấy x0 ∈ Sol (D, A, c, b), ta có x ϕ (D, A, c, b) = T Dx0 + cT x0 , (2.55) Ax0 ≤ b (2.56) Theo Bổ đề 2.4.2, có tồn dãy y k ⊂ Rn hội tụ đến x0 Ak y k ≤ bk , ∀k ≥ k1 (2.57) Từ (2.57) suy y k ∈ ∆ Ak , bk với k ≥ k1 Như ϕ Dk , Ak , ck , bk ≤ k y T D k y k + ck T k y (2.58) Từ (2.58) suy lim sup ϕ Dk , Ak , ck , bk k→∞ ≤ lim sup k→∞ = lim k→∞ k y k y T T D k y k + ck Dk y k + ck T k y T k y Vì thế, từ (2.55) (2.56), ta có lim sup ϕ Dk , Ak , ck , bk ≤ ϕ (D, A, c, b) k→∞ (2.59) 56 Giờ ta khẳng định dãy xk , k ≥ k1 , bị chặn Thật vậy, không xác định, cách lấy dãy cần, ta giả sử xk → ∞ k → ∞ xk = 0, ∀k ≥ k1 Khi dãy xk −1 k x , k ≥ k1 , dãy hội tụ Không tính tổng quát ta giả sử xk −1 k x → xˆ, xˆ = Từ (2.54) ta có A xk bk ≤ k xk x k Lấy k → ∞, ta thu Aˆ x ≤ (2.60) Từ (2.53) (2.58), k x T Dk xk + ck T k x ≤ Chia hai vế (2.61) cho xk k y 2 T D k y k + ck T k y (2.61) lấy giới hạn k → ∞, ta xˆT Dˆ x ≤ (2.62) Từ (2.60) (2.62), ta có Sol (D, A, 0, 0) = {0} Điều mâu thuẫn (b) Như ta thấy dãy xk , k ≥ k1 , bị chặn; dãy hội tụ Không tính tổng quát giả sử xk → x˜ ∈ Rn lim ϕ Dk , Ak , ck , bk = x˜T D˜ x + cT x˜ = f (˜ x, c, D) , k→∞ A˜ x ≤ b (2.63) (2.64) Từ (2.64) cho thấy x˜ ∈ ∆ (A, b) Vì f (˜ x, c, D) ≥ ϕ (D, A, c, b) Do đó, từ (2.63), lim ϕ Dk , Ak , ck , bk ≥ ϕ (D, A, c, b) k→∞ Kết hợp (2.59) với (2.65) dẫn tới lim ϕ Dk , Ak , ck , bk = ϕ (D, A, c, b) k→∞ Điều cho thấy ϕ liên tục (D, A, c, b) (2.65) 57 Kết luận chương Trong chương trình bày số vấn đề liên quan đến toán tối ưu toàn phương lồi với ràng buộc tuyến tính, bao gồm: tồn nghiệm, điều kiện tối ưu, tính liên tục ánh xạ nghiệm tính liên tục hàm giá trị tối ưu Nội dung chương tham khảo dựa tài liệu [2] - [7] 58 KẾT LUẬN Luận văn tập trung nghiên cứu "Bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính" Cụ thể luận văn trình bày kiến thức chuẩn bị chương 1, gồm tập lồi hàm lồi, hệ bất phương trình tuyến tính, hàm toàn phương lồi, toán tối ưu lồi Chương trình bày toán, tồn nghiệm, điều kiện cực trị, tính ổn định tập nghiệm hàm giá trị tối ưu toán có tham số Luận văn tổng quan khoa học toán tối ưu toàn phương lồi với ràng buộc tuyến tính Với khả thời gian có hạn, chắn luận văn không tránh khỏi thiếu sót Kính mong quý thầy cô bạn góp ý để luận văn hoàn thiện Tôi xin chân thành cảm ơn ! Tài liệu tham khảo [A] Tài liệu tiếng Việt [1] Huỳnh Thế Phùng (2012), Cơ sở giải tích lồi, NXB Giáo dục [B] Tài liệu tiếng Anh [2] D P Bertsekas (2003), Convex Analysis and Optimization, Springer [3] Z Dostál (2009) , On Solvability of Convex Noncoercive Quadratic Programming Problems, J Optim Theory Appl 143, 413-416 [4] G M Lee, N N Tam, N D Yen (2007),Quadratic Programming and Affine Variational Inequalities: A Qualitative Study, Springer [5] Z Q Luo, S Zhang (1999),On extensions of the Frank-Wolfe theorems, Computational Optim and Applications 13, 87-108 [6] R T Rockafellar (1970), Convex Analysis, Princeton Univ Rress [7] S M Robinson (1977), A characterization of stability in linear programming, Operations Research, 25, 435-477 59 [...]... 2 Bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính Trong chương này, chúng tôi trình bày về bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính, sự tồn tại nghiệm của bài toán, điều kiện cực trị và tính ổn định của tập nghiệm Nội dung của chương này được tham khảo dựa trên các tài liệu [2] -[7] 2.1 Phát biểu bài toán Định nghĩa 2.1.1 [4] Ta nói rằng f : Rn → R là một hàm toàn phương tuyến. .. hàm tuyến tính là đối xứng Các không gian của ma trận đối xứng cỡ n × n sẽ được ký hiệu là RS n×n Cho D ∈ Rsn×n , A ∈ Rm×n , c ∈ Rn , b ∈ Rm Xét bài toán tối ưu toàn phương   M in f (x) := 1 xT Dx + cT x 2 (QP )  x ∈ Rn , Ax ≤ b Định nghĩa 2.1.2 [4] Bài toán (QP ) được gọi là bài toán tối ưu toàn phương lồi với ràng buộc tuyến tính (hoặc bài toán quy hoạch toàn phương) nếu f là một hàm toàn phương. .. đó ∆ là lồi Hơn nữa, vì tính lồi ngặt của f nên giá trị của f có thể nhỏ hơn tại trung điểm của x và y Từ đó x và y là cực tiểu toàn cục Dẫn tới mâu thuẫn Kết luận chương 1 Chương này nhằm trình bày những khái niệm cơ bản nhất và những tính chất đặc trưng về tập lồi, hàm lồi, nón lùi xa của một tập lùi, tập lồi đa diện, hệ bất phương trình tuyến tính, hàm toàn phương lồi và bài toán tối ưu lồi, sẽ... hoạch toàn phương) nếu f là một hàm toàn phương lồi, tuyến tính và ∆ là một tập lồi đa diện Trong (2.1), nếu D là ma trận không, thì f là một hàm affine Do đó các bài toán quy hoạch tuyến tính là một lớp con của lớp bài toán tối ưu toàn phương Ví dụ 2.1.1 Giải bài toán 1 1 min f (x) = x21 + x22 : −x1 + x2 ≤ 1, x1 + 2x2 ≥ 2, x1 ≤ 3 2 2 Ở đây f là một hàm lồi, ta có miền chấp nhận được D = x ∈ R2 | −... toán tối ưu toàn phương lồi với ràng buộc tuyến tính 2.2 Sự tồn tại nghiệm Trong mục này chúng tôi trình bày Định lý về sự tồn tại nghiệm của bài toán (QP ) Xét bài toán quy hoạch toàn phương 1 min f(x) := xT Dx + cT x 2 với x ∈ Rn thỏa mãn   g1 (x) := A1 x + b1 ≤ 0,      g (x) := A x + b ≤ 0, 2 2 2       g (x) := A x + b ≤ 0; m m m Với Ai T ∈ Rn , bi ∈ R, i = 1, , m Bài toán trên được... mâu thuẫn với Ai u = 0, ∀i = 1, 2, , l + 1 Sử dụng Định lý trên, ta sẽ chứng minh Định lý về sự tồn tại nghiệm của bài toán quy hoạch toàn phương lồi dưới đây Định lý 2.2.2 [4] Bài toán (2.2) có nghiệm nếu hàm mục tiêu bị chặn dưới trên miền ràng buộc Chứng minh Giả sử a > −∞ là infimum của hàm mục tiêu f (x) trên miền ràng buộc của bài toán (2.2) Khi đó, tồn tại một dãy (xk ) thuộc miền ràng buộc thỏa... ) ≤ g (α2 ) , với bất đẳng thức ngặt nếu f là lồi ngặt Vì thế g là dãy đơn điệu tăng với α, và ngặt nếu f là lồi ngặt Một hệ quả đơn giản của Mệnh đề 1.1.5(a): nếu f : Rn → R là một hàm lồi và ∇f (x∗ ) = 0, sau khi x∗ cực tiểu f trên Rn Đây là lớp điều kiện đủ bài toán tối ưu không ràng buộc, được đề xuất bởi Fermat năm 1637 Đối với hàm lồi khả vi cấp 2, ta có đặc trưng khác của tính lồi trong mệnh... một nghiệm x Khi đó, x là một nghiệm của bài toán (2.2) Năm 1956, Frank - Wolfe đã chỉ ra sự tồn tại nghiệm của bài toán (QP ) trong trường hợp f là hàm toàn phương không lồi Định lý 2.2.3 [4] (Định lý Frank - Wolfe) Nếu một hàm toàn phương f bị chặn dưới trên một tập lồi đa diện khác rỗng thì f đạt giá trị nhỏ nhất trên tập đó 27 Ví dụ 2.2.1 Xét bài toán tối ưu hai biến min f (x) = x21 + 2x22 − x1... 1 (x1 − x2 )2 + x21 + 3x22 ≥ 0 2 với mọi x ∈ R2 và ∆ = x ∈ R2 : −x1 + x2 = 1, x1 ≥ 0, x2 ≥ 0 là tập Trong bài này f (x) = x21 + 2x22 − x1 x2 = lồi đa diện không bị chặn Do f (x) bị chặn dưới trên ∆ nên theo Định lý Frank - Wolfe, bài toán đã cho có nghiệm Có thể thấy nghiệm cực tiểu của bài toán là x∗ = (0, 1)T với fmin = f (x∗ ) = 2 Ví dụ 2.2.2 Xét bài toán tối ưu sau min f (x) = 1 4x21 − x22 + 2x1... bài toán trên có nghiệm Có thể thấy 1 nghiệm cực tiểu của bài toán là x∗ = (1, 1)T và fmin = f (x∗ ) = (4 − 1)+ 2 7 2= 2 2.3 Điều kiện cực trị Trong phần này chúng tôi trình bày chi tiết về điều kiện cần và đủ cực trị địa phương của bài toán (QP ) Các kết quả chính theo hướng này đã được Majthay (1971) và Contesse (1980) chứng minh Cho D ∈ RS n×n , A ∈ Rm×n , c ∈ Rn , b ∈ Rm Xét bài toán tối ưu toàn