BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI PHẠM THỊ LAN PHƯƠNG ĐIỀU KIỆN TỐI ƯU ĐỊA PHƯƠNG TRONG QUY HOẠCH TOÀN PHƯƠNG LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội - 2018 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI PHẠM THỊ LAN PHƯƠNG ĐIỀU KIỆN TỐI ƯU ĐỊA PHƯƠNG TRONG QUY HOẠCH TOÀN PHƯƠNG Chuyên ngành: Tốn giải tích Mã số: 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 - 2018 LỜI CẢM ƠN Luận văn hoàn thành trường Đại học Sư phạm Hà Nội 2, hướng dẫn PGS TS Nguyễn Năng Tâm Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy, người tận tình hướng dẫn giúp đỡ em suốt trình nghiên cứu để em hồn thành luận văn Em bày tỏ lòng biết ơn chân thành tới quý thầy, cô giáo trường Đại học Sư phạm Hà Nội giảng dạy giúp đỡ em hồn thành khóa học Nhân dịp em xin chân thành cảm ơn Ban giám hiệu, đồng nghiệp trường THPT Quang Minh huyện Mê Linh - Hà Nội, gia đình bạn bè ln động viên, giúp đỡ tạo điều kiện cho em mặt suốt trình học tập thực luận văn Hà Nội, ngày 28 tháng 07 năm 2018 Phạm Thị Lan Phương LỜI CAM ĐOAN Tôi xin cam đoan, hướng dẫn PGS TS Nguyễn Năng Tâm, luận văn Chun ngành Tốn giải tích với đề tài: Điều kiện tối ưu địa phương quy hoạch tồn phương tơi tự làm Trong q trình nghiên cứu thực luận văn, kế thừa thành nhà khoa học với trân trọng biết ơn Các kết trích dẫn luận văn trung thực rõ nguồn gốc Hà Nội, ngày 28 tháng 07 năm 2018 Phạm Thị Lan Phương Mục lục LỜI CẢM ƠN LỜI CAM ĐOAN LỜI MỞ ĐẦU KIẾN THỨC CHUẨN BỊ 1.1 Một số nội dung giải tích lồi 1.2 Bài toán tối ưu 11 ĐIỀU KIỆN TỐI ƯU ĐỊA PHƯƠNG TRONG QUY HOẠCH TOÀN PHƯƠNG 15 2.1 Điều kiện cực trị bậc 15 2.2 Điều kiện cực trị bậc hai 31 2.3 Các điều kiện tối ưu quy hoạch toàn phương 37 KẾT LUẬN 47 Tài liệu tham khảo 48 LỜI MỞ ĐẦU Các tốn quy hoạch tồn phương lập thành phận tối ưu phi tuyến, có nhiều ứng dụng lý thuyết thực tiễn Nhiều kết nghiên cứu tối ưu phi tuyến áp dụng cho quy hoạch tồn phương Tuy thế, tốn quy hoạch tồn phương có cấu trúc đặc biệt nên kết nghiên cứu chúng thường sâu sắc Trong năm gần đây, vai trò tốn quy hoạch tồn phương tối ưu hóa ngày tăng, tính chất định tính thuật tốn giải hữu hiệu quy hoạch tồn phương trở thành chủ đề nhiều tác giả ngồi nước quan tâm Vì vậy, sau học nghiên cứu 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 ứng dụng chúng, chọn đề tài nghiên cứu “Điều kiện tối ưu địa phương quy hoạch toàn phương ” Mục đích luận văn tìm hiểu điều kiện cho nghiệm địa phương lớp toán quy hoạch toàn phương với ràng buộc toàn phương khơng gian hữu hạn chiều Qua đó, thấy tầm quan trọng kiến thức học ứng dụng chúng Với nội dung nghiên cứu này, phần lời mở đầu, kết luận tài liệu tham khảo, luận văn chia thành hai chương Kết tập trung Chương Chương Kiến thức chuẩn bị Trong chương này, luận văn phần đầu trình bày kiến thức cần thiết giải tích lồi tập lồi, hàm lồi, vv Phần tiếp theo, luận văn trình bày tốn tối ưu ràng buộc phi tuyến với khái niệm điểm chấp nhận được, cực tiểu địa phương, cực tiểu tồn cục cực tiểu địa phương lập nhằm phục vụ cho Chương Chương Điều kiện tối ưu địa phương quy hoạch toàn phương Trong chương này, luận văn trình bày điều kiện tối ưu bậc điều kiện tối ưu bậc hai Tiếp đó, luận văn trình bày điều kiện cần, điều kiện đủ, điều kiện cần đủ cho nghiệm địa phương nghiệm địa phương cô lập lớp tốn quy hoạch tồn phương với ràng buộc tồn phương khơng gian hữu hạn chiều Chương KIẾN THỨC CHUẨN BỊ Trong chương này, luận văn trình bày số khái niệm, định nghĩa kết cần thiết giải tích lồi lý thuyết tối ưu nhằm phục vụ cho Chương Tài liệu tham khảo cho chương [1], [2], [5] [11] 1.1 Một số nội dung giải tích lồi Trong phần này, ta ký hiệu Rn không gian Euclide n-chiều trường số thực R Mỗi véc tơ x ∈ Rn gồm n tọa độ số thực Với hai véc tơ x = (x1 , , xn )T y = (y1 , , yn )T thuộc Rn , ta nhắc lại n x, y := x j yj j=1 gọi tích vơ hướng hai véc tơ x y Chuẩn Euclide phần tử x định nghĩa sau: x, x x := Ký hiệu R := [−∞, +∞] = R ∪ {−∞} ∪ {+∞} tập số thực mở rộng Một đường thẳng nối hai điểm (hai véc tơ) u, v Rn tập hợp tất véc tơ x ∈ Rn có dạng {x ∈ Rn | x = λu + µv, λ, µ ∈ R, λ + µ = 1} Đoạn thẳng nối hai điểm u, v Rn tập hợp tất véc tơ x ∈ Rn có dạng {x ∈ Rn | x = λu + µv, λ ≥ 0, µ ≥ 0, λ + µ = 1} Định nghĩa 1.1.1 ([1]) Một tập C ⊆ Rn gọi tập lồi, C chứa đoạn thẳng qua hai điểm Như vậy, tập C lồi với x, y ∈ C , λ ∈ [0, 1] ta có λx + (1 − λ)y ∈ C Ta gọi x tổ hợp lồi điểm (véc tơ) x1 , x2 , , xk k k i x= λi x với λi > 0; ∀i = 1, , k; i=1 Ví dụ 1.1.2 λi = i=1 Một số ví dụ tập lồi (i) Theo định nghĩa, tập rỗng ∅ Rn tập lồi Rn (ii) Các tam giác hình tròn mặt phẳng tập lồi Hình cầu đơn vị không gian Rn tập lồi (iii) Tập Λ = {x ∈ Rn : (iv) Mặt cầu, đường cong nói chung khơng phải tập lồi x ≤ 1} tập lồi Lớp tập lồi đóng với phép giao, phép cộng đại số phép nhân tích Descartes Cụ thể, ta có định lý sau: Định lý 1.1.3 Cho A, B tập lồi Rn C tập lồi Rm Khi đó, tập sau lồi: A ∩ B := {x | x ∈ A, x ∈ B}; λA + µB := {x | x = λa + µb, a ∈ A, b ∈ B; λ, µ ∈ R}; A × C := {x ∈ Rn+m | x = (a, c) : a ∈ A, c ∈ C} Trong tối ưu hố, lý thuyết trò chơi nhiều chuyên ngành toán ứng dụng khác, khái niệm nón có vai trò quan trọng Định nghĩa 1.1.4 ([1]) Cho C tập Rn (a) Tập C gọi nón ∀λ > 0, ∀x ∈ C =⇒ λx ∈ C (b) Một nón C gọi nón lồi C đồng thời tập lồi (c) Một nón lồi gọi nón nhọn khơng chứa đường thẳng Khi đó, ta nói O đỉnh nón Nếu nón lồi lại tập lồi đa diện ta nói nón lồi đa diện Ví dụ 1.1.5 Một ví dụ điển hình nón lồi đa diện, thường sử dụng, tập hợp nghiệm hệ bất phương trình tuyến tính có dạng {x : Ax ≥ 0}, với A ma trận thực cấp hữu hạn (số dòng số cột hữu hạn) Định lý 1.1.6 Một tập C nón lồi có tính chất sau: (a) λC ⊆ C, (b) C + C ⊆ C Chứng minh với λ > 0; Giả sử C nón lồi Do C nón, nên ta có (a) Từ C tập lồi, nên với x, y ∈ C , ta có (x + y) ∈ C Vậy theo (a) ta có x + y ∈ C Ngược lại, giả sử ta có (a) (b) Từ (a) suy C nón Giả sử x, y ∈ C λ ∈ [0, 1] Từ (a) suy λx ∈ C (1 − λ)y ∈ C Theo (b) ta có λx + (1 − λ)y ∈ C Vậy C nón lồi Định nghĩa 1.1.7 ([1]) Cho C ⊆ Rn tập lồi x ∈ C Khi đó, ta có f (x∗ + δk dk ) = L(x∗ + δk dk , λ∗ ) = L(x∗ , λ∗ ) + δk2 dTk ∇2xx L(x∗ , λ∗ )dk + o(δk2 ) = f (x∗ ) + δk2 dTk ∇2xx L(x∗ , λ∗ )dk + o(δk2 ) (2.84) Với k đủ lớn, x∗ cực tiểu địa phương, ta có f (x∗ + δk dk ) ≥ f (x∗ ) (2.85) Từ (2.84), (2.85) cho qua giới hạn, ta thu dT ∇2xx L(x∗ , λ∗ )d ≥ Nhưng d ∈ S(x∗ , λ∗ ) tùy ý, nên ta suy dT ∇2xx L(x∗ , λ∗ )d ≥ 0, ∀d ∈ S(x∗ , λ∗ ) Cuối cùng, kết hợp (2.81) (2.82) ta có (2.83) Định lý chứng minh hoàn toàn Định lý 2.2.4 (Theorem 8.3.4 [11]) (Các điều kiện đủ bậc hai) Cho x∗ điểm KKT toán (1.1)-(1.3) Nếu dT ∇2xx L(x∗ , λ∗ )d > 0, ∀d ∈ G(x∗ , λ∗ ), (2.86) x∗ cực tiểu địa phương ngặt Chứng minh Ta chứng minh phản chứng Giả sử x∗ không cực tiểu địa phương ngặt Khi đó, tồn dãy {xk } ⊂ X cho f (xk ) ≤ f (x∗ ), (2.87) với xk −→ x∗ xk = x∗ (k = 1, 2, ) Khơng tính tổng qt, ta giả sử xk − x∗ xk − x∗ 35 −→ d Lập luận tương tự (2.45)-(2.47), ta có dT ∇f (x∗ ) ≤ (2.88) d ∈ SF D(x∗ , X) ⊆ LF D(x∗ , X) (2.89) Từ điều kiện KKT (2.4), suy m ∗ T λi dT ∇ci (x∗ ) ≥ d ∇f (x ) = (2.90) i=1 Kết hợp (2.88) (2.90), ta nhận dT ∇f (x∗ ) = (2.91) Do đó, từ (2.90) Định nghĩa 2.1.2, ta có λi dT ∇ci (x∗ ) = 0, ∀i ∈ I(x∗ ) (2.92) Theo (2.89), (2.92) Định nghĩa 2.2.2, ta suy d ∈ G(x∗ , λ∗ ) (2.93) Từ (2.87), ta có L(x∗ , λ∗ ) ≥ L(xk , λ∗ ) = L(x∗ , λ∗ ) + δk2 dTk ∇2xx L(x∗ , λ∗ )dk + o(δk2 ) (2.94) Chia cho δk2 , sau cho qua giới hạn, ta thu dT ∇2xx L(x∗ , λ∗ )d ≤ 0, (2.95) điều mâu thuẫn với (2.86) Vậy x∗ cực tiểu địa phương ngặt Định lý chứng minh Một điều kiện đủ cho (2.86) dT ∇2xx L(x∗ , λ∗ )d > 0, 36 với d = cho dT ∇ci (x∗ ) = 0, i ∈ A+ (x∗ , λ∗ ), A+ (x∗ , λ∗ ) = E ∪ {i | i ∈ I(x∗ ), λ∗i > 0} (2.96) Vì thế, ta có hệ sau đây, hệ điều kiện đủ bậc hai thuận lợi thực hành Hệ 2.2.5 Cho x∗ điểm KKT toán (1.1)-(1.3) Nếu dT ∇2xx L(x∗ , λ∗ )d > (2.97) dT ∇ci (x∗ ) = 0, ∀i ∈ A+ (x∗ , λ∗ ), (2.98) với d thỏa mãn x∗ cực tiểu địa phương ngặt Chứng minh Ta cần chứng minh (2.97) (2.98) điều kiện đủ (2.86) Thật vậy, x∗ điểm KKT, với d ∈ SF D(x∗ , X) ⊆ LF D(x∗ , X), ta có dT ∇ci (x∗ ) = 0, ∀i ∈ E, dT ∇ci (x∗ ) ≥ 0, ∀i ∈ I(x∗ ) (2.99) (2.100) Vì thế, ta có λ∗i dT ∇ci (x∗ ) = 0, ∀i ∈ I(x∗ ) thỏa mãn Từ Định nghĩa 2.2.2, suy d ∈ G(x∗ , λ∗ ) Do đó, theo Định lý 2.2.4 điều kiện (2.97) (2.98) suy (2.86) Hệ chứng minh 2.3 Các điều kiện tối ưu quy hoạch tồn phương Xét tốn quy hoạch tồn phương với ràng buộc tồn phương khơng gian hữu hạn chiều:  min f (x) x ∈ C = {y ∈ Rn | c (y) ≤ 0, i = 1, 2, , m}, i 37 (2.101) f (x) := Qx, x + q, x ; Qi x, x + qi , x + pi ; Q, Qi ma trận đối xứng; q, qi ∈ Rn , pi ∈ R, i = 1, 2, , m Với ci (x) := x = (x1 , x2 , , xn ), y = (y1 , y2 , , yn ) ∈ Rn xT ma trận chuyển vị x, tích vô hướng không gian Rn định nghĩa sau: n xi yi = xT y x, y = i=1 Bài toán (2.101) gọi thỏa mãn điều kiện chuẩn hóa MangasarianFromovitz x ∃v ∈ Rn : ∇ci (x), v < 0, ∀i ∈ I(x), I(x) = {i ∈ {1, 2, , m} | ci (x) = 0} tập số hoạt C x, với x ∈ C Định nghĩa 2.3.1 Cho toán quy hoạch tồn phương với ràng buộc tồn phương khơng gian hữu hạn chiều (2.101) (1) Nếu f (x) = +∞ tồn lân cận U x cho f (x) ≥ f (x), với x ∈ C ∩ U , x gọi nghiệm địa phương toán (2.101) (2) Nếu f (x) = +∞ tồn lân cận U x cho f (x) > f (x), với x ∈ (C ∩ U ) \ {x}, x gọi nghiệm địa phương lập tốn (2.101) Ta bắt đầu với điều kiện đủ cho nghiệm địa phương lớp toán (2.101) Định lý 2.3.2 Cho toán (2.101) Giả sử x ∈ C hàm ci , i ∈ I(x) tựa lồi tập lồi C chứa C Nếu hai điều kiện thỏa mãn: 38 Qx + q, v ≥ ∀v ∈ T1 (x) = {v ∈ Rn | Qi x + qi , v ≤ 0, i ∈ (a) I(x)}; (b) Qv, v ≥ ∀v ∈ T2 (x) = T1 (x) ∩ Qx + q ⊥ , x nghiệm địa phương (2.101) Để chứng minh Định lý 2.3.2 Trước hết luận văn trình bày khái niệm hàm tựa lồi tính chất chúng Định nghĩa 2.2.3 Cho C ⊆ Rn tập lồi f : C −→ R Với α ∈ R, ta định nghĩa tập mức hàm f (với mức α): L(f ; α) := x ∈ C | f (x) ≤ α = x ∈ C | (x, α) ∈ epif Bổ đề 2.3.4 ([2], Bổ đề 4.2) Nếu f hàm lồi tập mức L(f ; α) tập lồi với α ∈ R Chứng minh Trước hết, với x, y ∈ L(f ; α) ta có (x, α), (y, α) ∈ epif Bây giờ, λ ∈ (0, 1) (λx + (1 − λ)y, α) = λ(x, α) + (1 − λ)(y, α) ∈ epif Suy λx + (1 − λ)y ∈ L(f ; α) Từ đó, ta có L(f ; α) lồi với α ∈ R Định nghĩa 2.3.5 ([2]) Giả sử C ⊆ Rn tập lồi cho f : C −→ R hàm số Khi đó, f gọi hàm tựa lồi (quasiconvex function) tập mức L(f ; α) tập lồi với α ∈ R (1) f hàm tựa lồi nếu, với x, y ∈ Rn Nhận xét 2.3.6 t ∈ (0, 1), ta có f (tx + (1 − t)y) ≤ max{f (x), f (y)} (2) Mọi hàm lồi hàm tựa lồi Tuy nhiên, điều ngược lại không (chẳng hạn, ta thấy hàm đơn điệu R hàm tựa lồi) Ví dụ 2.3.7 Các ví dụ hàm tựa lồi 39 (1) Cho f : R −→ R hàm tăng tùy ý Khi đó, f hàm tựa lồi Thật vậy, với x, y ∈ R, λ ∈ (0, 1) Khơng tính tổng qt, ta giả sử x > y Khi đó, ta có x > λx + (1 − λ)y > y Do f hàm tăng, f (x) ≥ f (λx + (1 − λ)y) ≥ f (y) Từ f (x) = max{f (x), f (y)} bất đẳng thức đầu cho ta f (λx + (1 − λ)y) ≤ max{f (x), f (y)} Điều chứng tỏ f hàm tựa lồi |x| hàm tựa lồi R (2) Hàm f (x) = (3) Hàm f : (0, +∞) −→ R xác định f (x) = lnx hàm tựa lồi (tuy nhiên f không hàm lồi) Tiếp theo, ta đến với đặc trưng hàm tựa lồi ứng với dạng toàn phương f (x) = xT Ax Định lý 2.3.8 ([5], Hệ 3.3) Cho dạng toàn phương f (x) = xT Ax A ma trận đối xứng thực cấp n Khi đó, tính chất sau dạng tồn phương f (x) = xT Ax tương đương: (i) f hàm lồi; (ii) f hàm tựa lồi; (iii) A ma trận nửa xác định dương Cho f hàm tồn phương có dạng f (x) = xT Ax + bx, 40 A ma trận đối xứng thực cấp n b n-véc tơ thực Ta viết f (x) dạng tắc sau: f (x) = − k r x2i i=1 x2 + γxr+1 + c, + i=k+1 i (*) ≤ k ≤ r ≤ n, γ nhận giá trị 1, c số x = (x1 , , xn ) Để chứng minh Định lý 2.3.2, ta cần đến bổ đề sau Bổ đề 2.3.9 (Bổ đề Hoffmann) ([3]) Cho ∈ Rn , i = 1, , p ∆ = {x ∈ Rn : , x ≤ bi , i = 1, , p} Khi đó, tồn số α > phụ thuộc vào ∈ Rn , i = 1, , p cho với x ∈ X , ta có p [ , x − bi ]+ , dist(x, ∆) ≤ α i=1 với a + = max{0; a}, a ∈ R Chứng minh Định lý 2.3.2 Giả sử x không nghiệm địa phương (2.101) Khi đó, tồn dãy {xk } ⊂ C cho xk −→ x f (xk ) − f (x) < với k ≥ Bây giờ, ta đặt tk = xk − x v k = xk − x xk − x Ta có > f (xk ) − f (x) = Q(xk − x), xk − x + Qx + q, xk − x ⇐⇒ > t2k Qv k , v k + tk Qx + q, v k ⇐⇒ Qx + q, v k < − tk Qv k , v k Với i ∈ I(x), ci hàm tựa lồi C ⊃ C c(xk ) − c(x) ≤ nên ta có Qi x + qi , xk − x ≤ 41 Do đó, với i ∈ I(x), ta có Qi x + qi , v k ≤ Thành thử, ta có v k ∈ T1 (x) Theo điều kiện (a), ta có Qx + q, v k ≥ Suy ≤ Qx + q, v k < − tk Qv k , v k −→ 0, k −→ ∞ Hay là, Qx + q, v k −→ k −→ ∞ Tiếp tục trình chứng minh, ta đặt T2 (x) = {v ∈ Rn : Qx + q, v = 0, Qi x + qi , v ≤ 0, i ∈ I(x)} = {v ∈ Rn : Qx + q, v ≤ 0, −Qx − q, v ≤ 0, Qi x + qi , v ≤ 0, i ∈ I(x)} Theo Bổ đề 2.3.3, tồn α1 > cho dist(v k , T2 (x)) ≤ α1 Qx+q, v k ++ −Qx−q, v k ++ [ Qi x+qi , v k ]+ i∈I(x) Nhưng Qi x + qi , v k ≤ Qx + q, v k ≥ 0, với i ∈ I(x), ta thu dist(v k , T2 (x)) ≤ α1 Qx + q, v k Tiếp theo, T2 (x) tập đóng, nên tồn wk ∈ T2 (x) cho v k − wk ≤ α1 Qx + q, v k Ta có Qwk , wk − Qv k , v k = Q(wk − v k ), wk + v k = α2 w k − v k w k + v k , 42 với α2 > Từ v k − wk ≤ α1 Qx + q, v k −→ k −→ ∞, ta suy wk + v k ≤ wk − v k + 2v k −→ k −→ ∞ Cho nên, với k đủ lớn, wk + v k bị chặn Vì thế, tồn α3 > cho Qwk , wk − Qv k , v k ≤ α3 wk − v k Từ đó, ta có Qwk , wk − Qv k , v k ≤ α4 Qx + q, v k , α4 = α3 α1 Hay là, Qv k , v k ≥ Qwk , wk − α4 Qx + q, v k Ta có đánh giá f (xk ) − f (x) = t2k Qv k , v k + tk Qx + q, v k ≥ t2k ( Qwk , wk − α4 Qx + q, v k ) + tk Qx + q, v k 2 ≥ tk (−α4 Qx + q, v k ) + tk Qx + q, v k (Do wk ∈ T2 (x), từ điều kiện (b) ta có Qwk , wk ≥ 0) ≥ tk [(2 − α4 tk ) Qx + q, v k ] ≥ 0, với k đủ lớn (do tk −→ 0+ k −→ ∞ Qx + q, v k ≥ với k ) Nhưng điều lại mâu thuẫn với giả thiết f (xk ) − f (x) < với k ≥ Định lý chứng minh hoàn toàn Tiếp theo điều kiện cần cho nghiệm địa phương lớp toán (2.101) Định lý 2.3.10 Giả sử toán (2.101) thỏa mãn điều kiện chuẩn hóa Mangasarian-Fromovitz x ∈ C Với i ∈ I(x), giả sử hệ   Qx + q, v =    (H) Qi x + q i , v =     Q v, v > i 43 vô nghiệm Khi đó, x nghiệm địa phương tốn (2.101), khẳng định sau đúng: (a) Qx + q, v ≥ ∀v ∈ T1 (x) = {v ∈ Rn | Qi x + qi , v ≤ 0, i ∈ I(x)}; (b) Qv, v ≥ ∀v ∈ T2 (x) = T1 (x) ∩ Qx + q ⊥ Chứng minh Khẳng định (a) suy trực tiếp từ trường hợp tổng quát (xem [11], Chương 8) Bây giờ, ta chứng minh khẳng định (b) Giả sử tồn v ∈ T2 (x) cho Qv, v < Ta đặt xt = x + tv, t > Với i ∈ / I(x), ci (x) < Khi đó, tồn δ1 > thỏa mãn ci (xt ) ≤ 0, với t ∈ (0, δ1 ) Với i ∈ I(x), ta có ci (xt ) = ci (x) + t2 Qi v, v + t Qi x + qi , v = t(t Qi v, v + Qi x + qi , v ) Đến đây, ta xét ba trường hợp: Trường hợp Nếu   Qi x + qi , v <  Q v, v ≤ i ci (xt ) ≤ 0, với t ≥ Trường hợp Nếu   Qi x + qi , v <  Q v, v > i ci (xt ) ≤ 0, với t ∈ 0, δ2i := − 44 Qi x + qi , v Qi v, v Trường hợp Nếu Qi x + qi , v = 0, từ giả thiết hệ phương trình (H) vơ nghiệm, ta suy v (nếu tồn tại) phải thỏa mãn Qi v, v ≤ Điều kéo theo ci (xt ) ≤ 0, với t ≥ Như vậy, tồn δ = min{δ1 , δ2i , i ∈ I(x)} cho ci (xt ) ≤ 0, với t ∈ (0, δ) Hay là, với t ∈ (0, δ), ta có xt ∈ C Thành thử, ta có f (xt ) = f (x) + t2 Qv, v + t Qx + q, v < f (x) Điều mâu thuẫn với giả thiết x nghiệm địa phương toán (2.101) Định lý chứng minh Dưới điều kiện cần đủ cho nghiệm địa phương lớp tốn (2.101) Nó suy trực tiếp từ Định lý 2.3.2 Định lý 2.3.4 Hệ 2.3.11 Giả sử tốn (2.101) thỏa mãn điều kiện chuẩn hóa Mangasarian–Fromovitz x ∈ C Giả sử hàm ci , i ∈ I(x), tựa lồi tập lồi C chứa C hệ:   Qx + q, v =    Qi x + q i , v =     Q v, v > i vô nghiệm Khi đó, (a) (b) Định lý 2.3.2 điều kiện cần đủ để x nghiệm địa phương (2.101) Lập luận tương tự chứng minh Định lý 2.3.2 Định lý 2.3.4, ta suy kết cho điều kiện cực trị nghiệm địa phương lập tốn (2.101) Định lý 2.3.12 Xét toán (2.101) x ∈ C Giả sử hàm ci , i ∈ I(x), tựa lồi tập lồi C chứa C Nếu hai điều kiện thỏa mãn: (i) Qx + q, v ≥ ∀v ∈ T1 (x) = {v ∈ Rn : Qi x + qi , v ≤ 0, i ∈ I(x)}; 45 (ii) Qv, v > ∀v ∈ T2 (x) = T1 (x) ∩ Qx + q ⊥ , x nghiệm địa phương lập tốn (2.101) Định lý 2.3.13 Giả sử toán (2.101) thỏa mãn điều kiện chuẩn hóa Mangasarian–Fromovitz x ∈ C Giả sử với i ∈ I(x) hệ:   Qx + q, v =    Qi x + q i , v =     Q v, v > i vô nghiệm Khi đó, x nghiệm địa phương lập tốn (2.101), khẳng định sau đúng: (i) Qx + q, v ≥ ∀v ∈ T1 (x) = {v ∈ Rn : Qi x + qi , v ≤ 0, i ∈ I(x)}; (ii) Qv, v > ∀v ∈ T2 (x) = T1 (x) ∩ Qx + q ⊥ Hệ sau suy trực tiếp từ Định lý 2.3.6 Định lý 2.3.7 Hệ 2.3.14 Giả sử toán (2.101) thỏa mãn điều kiện chuẩn hóa Mangasarian–Fromovitz x ∈ C Giả sử hàm ci , i ∈ I(x), tựa lồi tập lồi C chứa C hệ:   Qx + q, v =    Qi x + q i , v =     Q v, v > i vơ nghiệm Khi đó, (i) (ii) Định lý 2.3.6 điều kiện cần đủ để x nghiệm địa phương cô lập toán (2.101) 46 KẾT LUẬN Luận văn “Điều kiện tối ưu địa phương quy hoạch toàn phương ” trình bày số vấn đề sau: Hệ thống lại kiến thức giải tích lồi lý thuyết tối ưu tập lồi, hàm lồi, điểm chấp nhận được, cực tiểu địa phương, cực tiểu địa phương lập Trình bày điều kiện tối ưu bậc điều kiện tối ưu bậc hai Luận văn trình bày điều kiện cần, điều kiện đủ, điều kiện cần đủ cho nghiệm địa phương nghiệm địa phương cô lập lớp tốn quy hoạch tồn phương với ràng buộc tồn phương khơng gian hữu hạn chiều 47 Tài liệu tham khảo [A] Tiếng Việt [1] Nguyễn Văn Hiền, Lê Dũng Mưu, Nguyễn Hữu Điển (2015), Nhập môn Giải tích lồi ứng dụng, NXB Đại học Quốc Gia Hà Nội [2] Huỳnh Thế Phùng (2012), Cơ sở Giải tích lồi, NXB Giáo dục Việt Nam [3] Trần Văn Nghị (2015),“Về nghiệm địa phương toán quy hoạch tồn phương với ràng buộc tồn phương”, Tạp chí khoa học trường Đại học Sư phạm Hà Nội [B] Tiếng Anh [4] Boyd S., Vandenbergen L (2006), Convex Optimization, Cambridge Univ Press [5] Dinh The Luc (1993), “Characterisations of quasiconvex functions”, Bull Austral Math Soc., 48, pp 393-406 [6] Karush W (1939), Minima of functions of several variables with inequalities as side conditions, Master’s thesis, University of Chicago, Chicago, Illinois [7] Kuhn H W and Tucker A W (1951), “Nonlinear programming, in: J Neyman, ed., Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability” (University of California Press, Berkeley, California), pp 481-492 48 [8] Lee G M., Tam N N., Yen N D (2005), “Quadratic Programming and Afine Variational Inequalities: Aqualitative Study, Series: Nonconvex Optimization and its Applications”, 78, Spinger, New York [9] Majthay A (1971), “Optimality conditions for quadratic programming, Mathematical Programming 1”, pp 359-365 [10] Shi Ziye, Jin Qingwei, (2014), “Second order optimality conditions and reformulations for nonconvex quadratically constraied quadratic programming problems”, Journal of Industrial and Management Optimization, 10 (3) [11] Sun W., Yuan Y (2006), Optimization Theory and Methods: Nonlinear Programming, Springer, New York 49 ... kiện tối ưu địa phương quy hoạch toàn phương Trong chương này, luận văn trình bày điều kiện tối ưu bậc điều kiện tối ưu bậc hai Tiếp đó, luận văn trình bày điều kiện cần, điều kiện đủ, điều kiện. .. HOẠCH TỒN PHƯƠNG Trong chương này, luận văn trình bày điều kiện tối ưu bậc điều kiện tối ưu bậc hai Sau đó, luận văn trình bày điều kiện cần, điều kiện đủ, điều kiện cần đủ cho nghiệm địa phương. .. tài nghiên cứu Điều kiện tối ưu địa phương quy hoạch toàn phương ” Mục đích luận văn tìm hiểu điều kiện cho nghiệm địa phương lớp tốn quy hoạch tồn phương với ràng buộc tồn phương khơng gian