Tài liệu Luận văn thạc sĩ khoa học giáo dục điều kiện tối ưu địa phương trong quy hoạch toàn phương

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 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 2 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: Toán giải tích Mã số: 8 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 được hoàn thành tại trường Đại học Sư phạm Hà Nội 2, dưới sự hướng dẫn của 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 và giúp đỡ em trong suốt quá trình nghiên cứu để em có thể hoàn thành luận văn này. Em cũng 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 2 đã giảng dạy và giúp đỡ em hoàn thành khóa học. Nhân dịp này em cũng 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 và bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện cho em về mọi mặt trong suốt quá trình học tập và thực hiện luận văn này. Hà Nội, ngày 28 tháng 07 năm 2018 Phạm Thị Lan Phương 1 LỜI CAM ĐOAN Tôi xin cam đoan, dưới sự hướng dẫn của PGS. TS. Nguyễn Năng Tâm, luận văn Chuyên ngành Toán giải tích với đề tài: Điều kiện tối ưu địa phương trong quy hoạch toàn phương do tôi tự làm. Trong quá trình nghiên cứu và thực hiện luận văn, tôi đã kế thừa những thành quả của các nhà khoa học với sự trân trọng và biết ơn. Các kết quả trích dẫn trong luận văn là trung thực và được chỉ rõ nguồn gốc. Hà Nội, ngày 28 tháng 07 năm 2018 Phạm Thị Lan Phương 2 Mục lục LỜI CẢM ƠN 1 LỜI CAM ĐOAN 2 LỜI MỞ ĐẦU 4 1 KIẾN THỨC CHUẨN BỊ 6 1.1 Một số nội dung cơ bản của giải tích lồi . . . . . . . . . . . 6 1.2 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 11 2 Đ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 nhất . . . . . . . . . . . . . . . . . . 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 trong quy hoạch toàn phương . . . . . 37 KẾT LUẬN 47 Tài liệu tham khảo 48 3 LỜI MỞ ĐẦU Các bài toán quy hoạch toàn phương lập thành một bộ phận của tối ưu phi tuyến, có nhiều ứng dụng trong lý thuyết cũng như trong thực tiễn. Nhiều kết quả nghiên cứu của tối ưu phi tuyến có thể áp dụng cho quy hoạch toàn phương. Tuy thế, do các bài toán quy hoạch toàn phương có cấu trúc đặc biệt nên các kết quả nghiên cứu về chúng thường sâu sắc hơn. Trong những năm gần đây, do vai trò của các bài toán quy hoạch toàn phương trong tối ưu hóa ngày một tăng, các tính chất định tính cũng như các thuật toán giải hữu hiệu các bài quy hoạch toàn phương trở thành một chủ đề được nhiều tác giả trong và ngoài nước quan tâm. Vì vậy, sau khi được học và nghiên cứu những kiến thức về Toán giải tích, với mong muốn tìm hiểu sâu hơn về những kiến thức đã học và ứng dụng của chúng, tôi đã chọn đề tài nghiên cứu “Điều kiện tối ưu địa phương trong quy hoạch toàn phương ”. Mục đích của luận văn này là tìm hiểu về các điều kiện cho nghiệm địa phương của lớp bài toán quy hoạch toàn phương với ràng buộc toàn phương trong không gian hữu hạn chiều. Qua đó, thấy được tầm quan trọng của những kiến thức đã học và những ứng dụng của chúng. Với nội dung nghiên cứu này, ngoài phần lời mở đầu, kết luận và tài liệu tham khảo, luận văn được chia thành hai chương. Kết quả chính tập trung trong Chương 2. Chương 1. Kiến thức chuẩn bị. Trong chương này, luận văn phần đầu trình bày những kiến thức cần thiết về giải tích lồi như tập lồi, hàm lồi, vv. . . Phần tiếp theo, luận văn trình bày về bài toán tối ưu ràng buộc 4 phi tuyến cùng với các khái niệm về điểm chấp nhận được, cực tiểu địa phương, cực tiểu toàn cục và cực tiểu địa phương cô lập nhằm phục vụ cho Chương 2. Chương 2. Điều kiện tối ưu địa phương trong quy hoạch toàn phương. Trong chương này, luận văn trình bày các điều kiện tối ưu bậc nhất và cá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 và đủ cho nghiệm địa phương và nghiệm địa phương cô lập của lớp bài toán quy hoạch toàn phương với ràng buộc toàn phương trong không gian hữu hạn chiều. 5 Chương 1 KIẾN THỨC CHUẨN BỊ Trong chương này, luận văn sẽ trình bày một số khái niệm, định nghĩa và các kết quả cần thiết về giải tích lồi cũng như về lý thuyết tối ưu nhằm phục vụ cho Chương 2. Tài liệu tham khảo chính cho chương này là [1], [2], [5] và [11]. 1.1 Một số nội dung cơ bản của giải tích lồi Trong phần này, ta ký hiệu Rn là không gian Euclide n-chiều trên trường số thực R. Mỗi véc tơ x ∈ Rn sẽ gồm n tọa độ là các số thực. Với hai véc tơ x = (x1 , . . . , xn )T và y = (y1 , . . . , yn )T thuộc Rn , ta nhắc lại rằng hx, yi := n X x j yj j=1 gọi là tích vô hướng của hai véc tơ x và y . Chuẩn Euclide của phần tử x được định nghĩa như sau: kxk := q hx, xi. Ký hiệu R := [−∞, +∞] = R ∪ {−∞} ∪ {+∞} là tập số thực mở rộng. Một đường thẳng nối hai điểm (hai véc tơ) u, v trong Rn là tập hợp tất cả các véc tơ x ∈ Rn có dạng {x ∈ Rn | x = λu + µv, λ, µ ∈ R, λ + µ = 1}. 6 Đoạn thẳng nối hai điểm u, v trong Rn là tập hợp tất cả các 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 được gọi là một tập lồi, nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Như vậy, tập C là lồi nếu và chỉ nếu với mọi x, y ∈ C , λ ∈ [0, 1] ta có λx + (1 − λ)y ∈ C. Ta gọi x là tổ hợp lồi của các điểm (véc tơ) x1 , x2 , . . . , xk nếu x= k X i λi x với λi > 0; ∀i = 1, . . . , k; i=1 Ví dụ 1.1.2 k X λi = 1. i=1 Một số ví dụ về tập lồi. (i) Theo định nghĩa, tập rỗng ∅ và Rn là các tập con lồi của Rn . (ii) Các tam giác và hình tròn trong mặt phẳng là các tập lồi. Hình cầu đơn vị trong không gian Rn là tập lồi. (iii) Tập Λ = {x ∈ Rn : kxk ≤ 1} là một tập lồi. (iv) Mặt cầu, đường cong nói chung không phải là tập lồi. Lớp các tập lồi là đóng với các phép giao, phép cộng đại số và phép nhân tích Descartes. Cụ thể, ta có định lý sau: Định lý 1.1.3 Cho A, B là các tập lồi trong Rn và C là tập lồi trong Rm . Khi đó, các tập sau là 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 hoá, lý thuyết trò chơi và nhiều chuyên ngành toán ứng dụng khác, khái niệm về nón có một vai trò quan trọng. Định nghĩa 1.1.4 ([1]) Cho C là một tập trong Rn . 7 (a) Tập C được gọi là nón nếu ∀λ > 0, ∀x ∈ C =⇒ λx ∈ C. (b) Một nón C được gọi là nón lồi nếu C đồng thời là một tập lồi. (c) Một nón lồi được gọi là nón nhọn nếu nó không chứa đường thẳng. Khi đó, ta nói O là đỉnh của nón. Nếu nón lồi này lại là một tập lồi đa diện thì ta nói nó là nón lồi đa diện. Ví dụ 1.1.5 Một ví dụ điển hình của nón lồi đa diện, thường được sử dụng, là tập hợp nghiệm của hệ bất phương trình tuyến tính có dạng {x : Ax ≥ 0}, với A là một ma trận thực cấp hữu hạn (số dòng và số cột là hữu hạn). Định lý 1.1.6 Một tập C là nón lồi nếu và chỉ nếu nó có các tính chất sau: (a) λC ⊆ C, (b) C + C ⊆ C. Chứng minh. với mọi λ > 0; Giả sử C là một nón lồi. Do C là một nón, nên ta có ngay (a). Từ C là một tập lồi, nên với mọi x, y ∈ C , ta có 1 (x + y) ∈ C. 2 Vậy theo (a) ta có x + y ∈ C . Ngược lại, giả sử ta có (a) và (b). Từ (a) suy ra ngay C là một nón. Giả sử x, y ∈ C và λ ∈ [0, 1]. Từ (a) suy ra λx ∈ C và (1 − λ)y ∈ C . Theo (b) ta có λx + (1 − λ)y ∈ C. Vậy C là một nón lồi. Định nghĩa 1.1.7 ([1]) Cho C ⊆ Rn là một tập lồi và x ∈ C . Khi đó, 8 (i) Tập n o NC (x) := w|hw, y − xi ≤ 0, ∀y ∈ C được gọi là nón pháp tuyến ngoài của C tại x. (ii) Tập n o −NC (x) := w|hw, y − xi ≥ 0, ∀y ∈ C được gọi là nón pháp tuyến trong của C tại x. Định nghĩa 1.1.8 Cho C ⊆ Rn , bao affine của C , ký hiệu là affC được xác định bởi n 1 m j affC = λ1 x + · · · + λm x | x ∈ C, m X o λj = 1 . j=1 Một điểm a ∈ C được gọi là điểm trong tương đối của C , nếu nó là điểm trong của C theo tô pô cảm sinh bởi affC và được ký hiệu là riC . Như vậy, ta có riC := {a ∈ C | ∃B : (a + B) ∩ affC ⊂ C}, ở đây B là một lân cận mở của gốc. Cho C ⊆ Rn là một tập lồi và f : C −→ R. Ta ký hiệu tập n o domf := x ∈ C | f (x) < +∞ là miền hữu dụng của f . Tập n o epif := (x, µ) ∈ C × R | f (x) ≤ µ được gọi là trên đồ thị của hàm f . Bằng cách cho f (x) = +∞ nếu x ∈ / C , ta có thể xem f được xác định trên toàn không gian, và ta có n o n domf = x ∈ R |f (x) < +∞ , n o epif = (x, µ) ∈ Rn × R|f (x) ≤ µ . 9 Định nghĩa 1.1.9 ([1]) Cho C ⊆ Rn là một tập lồi, khác rỗng và ánh xạ f : C −→ R. Ta nói f là hàm lồi trên C , nếu epif là một tập lồi trong Rn+1 . Trong trường hợp ta làm việc với hàm f : Rn −→ R ∪ {+∞}, thì định nghĩa trên tương đương với f là hàm lồi trên C nếu và chỉ nếu f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), với mọi x, y ∈ C , λ ∈ [0, 1]. Dưới đây là một điều kiện cần và đủ về hàm lồi, rất tiện ích trong nhiều trường hợp. Hàm f : C −→ R là lồi trên C nếu và chỉ nếu Mệnh đề 1.1.10 ∀x, y ∈ C , ∀λ ∈ [0, 1], ∀α ≥ f (x) và ∀β ≥ f (y), ta có f (λx + (1 − λ)y) ≤ λα + (1 − λ)β. Ví dụ 1.1.11 Các ví dụ về hàm lồi. (1) Hàm hằng f : X −→ R; f (x) = α với mọi x ∈ X , là một hàm lồi. (2) Cho C 6= ∅ là một tập lồi. Hàm chỉ ( 0 khi x ∈ C, δC (x) := +∞ khi x ∈ /C là một hàm lồi. (3) Hàm affine f : Rn −→ R; f (x) = hc, xi + α với mọi x ∈ Rn , là một hàm lồi. (4) Hàm khoảng cách đến tập lồi đóng C được định nghĩa bởi dC (x) := min kx − yk, y∈C là một hàm lồi. 10 (5) Hàm f : R −→ R xác định bởi f (x) = x3 là một hàm không lồi 1 trên R. Thật vậy, với x = −1, y = 0, λ = ta có 2 f (λx + (1 − λ)y) = − 1 8 1 và λf (x) + (1 − λ)f (y) = − , 2 điều này chứng tỏ f (λx + (1 − λ)y) > λf (x) + (1 − λ)f (y). Do đó, f (x) = x3 không lồi trên R. Dễ thấy hàm f (x) = x3 cũng không là hàm lõm trên R. Định nghĩa 1.1.12 Cho C ⊆ Rn là một tập lồi, khác rỗng. Khi đó, f : Rn −→ R ∪ {+∞} được gọi là hàm lồi ngặt trên C , nếu (1) f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1). f : Rn −→ R ∪ {+∞} được gọi là hàm lồi mạnh trên C với hệ (2) số k > 0, nếu 1 f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − kλ(1 − λ)kx − yk2 , 2 với mọi x, y ∈ C và với mọi λ ∈ (0, 1). f được gọi là hàm lõm trên C , nếu −f là hàm lồi trên C . (3) 1.2 Bài toán tối ưu Bài toán tối ưu ràng buộc phi tuyến ([11], trang 385) có dạng tổng quát như sau: min x∈Rn f (x) (1.1) sao cho ci (x) = 0, i = 1, . . . , me ; ci (x) ≥ 0, i = me + 1, . . . , m, 11 (1.2) (1.3) trong đó hàm mục tiêu f (x) và các hàm ràng buộc ci (x) (với i = 1, . . . , m) đều trơn, là các hàm thực trên Rn và ít nhất một trong số đó là hàm phi tuyến; me và m là các số nguyên không âm với 0 ≤ me ≤ m. Ta gọi E = {1, . . . , me } và I = {me + 1, . . . , m} lần lượt là tập chỉ số của các ràng buộc phương trình và các ràng buộc bất phương trình. • Nếu các điều kiện (1.2) và (1.3) không xảy ra, thì bài toán (1.1)-(1.3) là một bài toán tối ưu không ràng buộc; • Nếu me = m 6= 0 thì bài toán (1.1)-(1.3) được gọi là một bài toán tối ưu ràng buộc phương trình; • Nếu tất cả các hàm ci (x) (với i = 1, . . . , m) là tuyến tính, thì bài toán (1.1)-(1.3) được gọi là một bài toán tối ưu ràng buộc tuyến tính. Một bài toán tối ưu ràng buộc tuyến tính với hàm mục tiêu toàn phương f (x) được gọi là một bài toán quy hoạch toàn phương. Định nghĩa 1.2.1 Điểm x ∈ Rn được gọi là một điểm chấp nhận được (feasible point) ([11], trang 386) nếu và chỉ nếu (1.2)-(1.3) thỏa mãn. Tập tất cả các điểm chấp nhận được được gọi là một tập chấp nhận được. Trong bài toán (1.1)-(1.3), các điều kiện (1.2)-(1.3) được gọi là các điều kiện ràng buộc. Từ Định nghĩa 1.2.1, điểm chấp nhận được là điểm thỏa mãn tất cả các ràng buộc. Ta viết tập chấp nhận được X như sau:  ( )  c (x) = 0, i = 1, . . . , m ; e  i X = x ∈ Rn  (1.4)  ci (x) ≥ 0, i = me + 1, . . . , m hay X = {x ∈ Rn | ci (x) = 0, i ∈ E; ci (x) ≥ 0, i ∈ I}. (1.5) Do đó, bài toán (1.1)-(1.3) có thể được viết lại như sau min f (x). x∈X 12 (1.6) Điều này có nghĩa là việc tìm nghiệm của bài toán tối ưu ràng buộc (1.1)(1.3) quy về việc tìm một điểm x trên tập chấp nhận được X sao cho hàm mục tiêu f (x) đạt cực tiểu. Sau đây, ta sẽ định nghĩa về cực tiểu địa phương và cực tiểu toàn cục. Định nghĩa 1.2.2 ([11], trang 386) Nếu x∗ ∈ X và f (x) ≥ f (x∗ ), ∀x ∈ X, (1.7) thì x∗ được gọi là cực tiểu toàn cục (global minimizer ) của bài toán (1.1)(1.3). Nếu x∗ ∈ X và f (x) > f (x∗ ), ∀x ∈ X, x 6= x∗ , (1.8) thì x∗ được gọi là cực tiểu toàn cục ngặt (strict global minimizer ). Định nghĩa 1.2.3 ([11], trang 386) Nếu x∗ ∈ X và nếu tồn tại một lân cận B(x∗ , δ) của x∗ sao cho f (x) ≥ f (x∗ ), ∀x ∈ X ∩ B(x∗ , δ), (1.9) thì x∗ được gọi là cực tiểu địa phương (local minimizer ) của bài toán (1.1)-(1.3), trong đó B(x∗ , δ) = {x|kx − x∗ k2 ≤ δ} (1.10) và δ > 0. Nếu x∗ ∈ X và nếu tồn tại một lân cận B(x∗ , δ) của x∗ sao cho f (x) > f (x∗ ), ∀x ∈ X ∩ B(x∗ , δ), x 6= x∗ , (1.11) thì x∗ được gọi là cực tiểu địa phương ngặt (strict local minimizer ). Định nghĩa 1.2.4 Nếu x∗ ∈ X và nếu tồn tại một lân cận B(x∗ , δ) của x∗ sao cho x∗ chỉ là cực tiểu địa phương trên X ∩ B(x∗ , δ), thì x∗ được gọi là một cực tiểu địa phương cô lập. Giả sử rằng x∗ là một cực tiểu địa phương của bài toán (1.1)-(1.3). Nếu tồn tại một chỉ số i0 ∈ I = [me + 1, m] sao cho ci0 (x∗ ) > 0, 13 (1.12) khi đó, nếu ta xóa ràng buộc thứ i0 thì x∗ vẫn là cực tiểu địa phương của bài toán thu được bằng cách xóa ràng buộc thứ i0 . Do đó, ta nói rằng ràng buộc thứ i0 là không hoạt (inactive) tại x∗ . Bây giờ, ta sẽ đưa ra các định nghĩa về ràng buộc hoạt và ràng buộc không hoạt. Trước hết, ta đặt I(x) = {i | ci (x) = 0, i ∈ I}. (1.13) Định nghĩa 1.2.5 ([11], trang 387) Với mỗi x ∈ Rn , tập A(x) = E ∪ I(x) (1.14) là một tập chỉ số hoạt các ràng buộc (index set of active constraints) tại x, ci (x)(i ∈ A(x)) là một ràng buộc hoạt (active constraint) tại x, ci (x)(i ∈ / A) là một ràng buộc không hoạt (inactive constraint) tại x. Giả sử rằng A(x∗ ) là một tập chỉ số hoạt các ràng buộc của bài toán (1.1)-(1.3) tại x∗ , khi đó, dưới cách nhìn về các ràng buộc không hoạt, đủ để cho ta có thể giải bài toán tối ưu ràng buộc min f (x) sao cho ci (x) = 0, i ∈ A(x∗ ). (1.15) Việc giải bài toán ràng buộc phương trình (1.15), thường thì dễ hơn so với bài toán gốc (1.1)-(1.3). 14 Chương 2 ĐIỀU KIỆN TỐI ƯU ĐỊA PHƯƠNG TRONG QUY HOẠCH TOÀN PHƯƠNG Trong chương này, luận văn sẽ trình bày các điều kiện tối ưu bậc nhất và các điều kiện tối ưu bậc hai. Sau đó, luận văn trình bày về điều kiện cần, điều kiện đủ, điều kiện cần và đủ cho nghiệm địa phương và nghiệm địa phương cô lập của một số lớp bài toán quy hoạch toàn phương với ràng buộc toàn phương trong không gian hữu hạn chiều. Tài liệu tham khảo chính của chương này là [3], [6], [7] và [11]. 2.1 Điều kiện cực trị bậc nhất Trong mục này, ta sẽ trình bày các điều kiện tối ưu bậc nhất. Các định hướng chấp nhận được đóng một vai trò rất quan trọng trong việc rút ra các điều kiện tối ưu. Trước tiên, ta sẽ đưa ra các định nghĩa về hướng chấp nhận được. Định nghĩa 2.1.1 Giả sử x∗ ∈ X, 0 6= d ∈ Rn . Nếu tồn tại δ > 0 sao cho x∗ + td ∈ X, ∀t ∈ [0, δ], thì d được gọi là hướng chấp nhận được (feasible direction) (Trang 388 quyển [11]) của X tại x∗ . Ký hiệu F D(x∗ , X) là tập tất cả các hướng chấp nhận được của X tại 15 x∗ và ta có F D(x∗ , X) = {d | x∗ + td ∈ X, ∀t ∈ [0, δ]}. (2.1) Định nghĩa 2.1.2 Cho x∗ ∈ X và d ∈ Rn . Nếu dT ∇ci (x∗ ) = 0, i ∈ E, dT ∇ci (x∗ ) ≥ 0, i ∈ I(x∗ ), thì d được gọi là hướng chấp nhận được tuyến tính của X tại x∗ . Ký hiệu LF D(x∗ , X) là tập tất cả các hướng chấp nhận được tuyến tính của X tại x∗ và   T ∗ n  d ∇ci (x ) = 0, d∈R  T  d ∇ci (x∗ ) ≥ 0, ( LF D(x∗ , X) = i∈E ) i ∈ I(x∗ ) . (2.2) Định nghĩa 2.1.3 (Trang 388 quyển [11]) Cho x∗ ∈ X và d ∈ Rn . Nếu tồn tại các dãy dk (k = 1, 2, . . .) và δk > 0 (k = 1, 2, . . .) sao cho x∗ + δk dk ∈ X, ∀k và dk −→ d, δk −→ 0, thì hướng giới hạn d được gọi là hướng chấp nhận được theo dãy (sequential feasible direction) của X tại x∗ . Ký hiệu SF D(x∗ , X) là tập tất cả các hướng chấp nhận được theo dãy của X tại x∗ và  )  x∗ + δ d ∈ X, ∀k k k  d ∈ Rn  .  dk −→ d, δk −→ 0 ( SF D(x∗ , X) = (2.3) Chú ý 2.1.4 Từ định nghĩa trên ta thấy 1. Nếu ta đặt xk = x∗ + δk dk , thì {xk } là một dãy điểm chấp nhận được thỏa mãn: (i) xk 6= x∗ với mọi k ; 16 (ii) limk−→∞ xk = x∗ ; (iii) xk ∈ X với mọi k đủ lớn. 2. Nếu đặt δk = kxk − x∗ k, khi đó ta có xk − x∗ dk = −→ d, kxk − x∗ k điều này có nghĩa là xk = x∗ + δk dk là một dãy điểm chấp nhận được với hướng chấp nhận được d. 3. Nếu SF D(x∗ , X) bao gồm cả véc tơ không, thì nó đóng vai trò như là mặt nón tiếp tuyến của X tại x∗ , nghĩa là TX (x∗ ) = SF D(x∗ , X) ∪ {0}. Bổ đề sau đây cho phép chỉ ra mối liên hệ giữa các tập F D(x∗ , X), SF D(x∗ , X) và LF D(x∗ , X). Bổ đề 2.1.5 (Trang 389 quyển [11]) Cho x∗ ∈ X . Nếu tất cả các hàm ràng buộc là khả vi tại x∗ , thì F D(x∗ , X) ⊆ SF D(x∗ , X) ⊆ LF D(x∗ , X). (2.4) Chứng minh. Theo Định nghĩa 2.1.1, với mọi d ∈ F D(x∗ , X), tồn tại δ > 0 sao cho (2.1) thỏa mãn. Đặt dk = d và δk = δ , 2k thì (2.3) thỏa mãn và rõ ràng dk −→ d, δk −→ 0. Suy ra d ∈ SF D(x∗ , X). Do d là tùy ý, nên F D(x∗ , X) ⊆ SF D(x∗ , X). (2.5) Bây giờ, với mọi d ∈ SF D(x∗ , X), nếu d = 0 thì d ∈ LF D(x∗ , X). Giả sử d 6= 0. Khi đó, theo Định nghĩa 2.1.3, tồn tại các dãy dk (k = 1, 2, . . .) và δk > 0 (k = 1, 2, . . .) sao cho (2.3) thỏa mãn và dk −→ d 6= 0, δk −→ 0. 17 Bằng cách sử dụng (2.3), ta có x∗ + δk dk ∈ X , tức là 0 = ci (x∗ + δk dk ) = δk dTk ∇ci (x∗ ) + o(kδk dk k), i ∈ E; (2.6) 0 ≤ ci (x∗ + δk dk ) = δk dTk ∇ci (x∗ ) + o(kδk dk k), i ∈ I(x∗ ). (2.7) Chia hai phương trình trên cho δk > 0 và cho k −→ ∞, ta thu được  ( )  dT ∇c (x∗ ) = 0, i ∈ E i  LF D(x∗ , X) = d  T .  d ∇ci (x∗ ) ≥ 0, i ∈ I(x∗ ) Do đó, ta có SF D(x∗ , X) ⊆ LF D(x∗ , X). (2.8) Kết hợp với (2.5), ta suy ra F D(x∗ , X) ⊆ SF D(x∗ , X) ⊆ LF D(x∗ , X). Bổ đề được chứng minh hoàn toàn. Để mô tả một cách rõ ràng các điều kiện cần cho một nghiệm địa phương, ta đặt D(x0 ) = D0 = {d | dT ∇f (x0 ) < 0}. (2.9) Tập này gọi là tập định hướng giảm (set of descent direction) tại x0 . Bây giờ, ta sẽ mô tả điều kiện cần cơ bản nhất, đó là điều kiện tối ưu hình học. Định lý 2.1.6 (Trang 390 quyển [11]) (Điều kiện tối ưu hình học) Giả sử x∗ ∈ X là một cực tiểu địa phương của bài toán (1.1)-(1.3). Nếu f (x) và ci (x) (i = 1, 2, . . . , m) là khả vi tại x∗ , thì dT ∇f (x∗ ) ≥ 0, ∀d ∈ SF D(x∗ , X), (2.10) SF D(x∗ , X) ∩ D(x∗ ) = φ, (2.11) nghĩa là trong đó φ là một tập rỗng. 18