Tài liệu điều kiện cực trị bậc 2 và độ nhạy nghiệm của bài toán tối ưu có ràng buộc

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ************* NGUYỄN THỊ HUẾ ĐIỀU KIỆN CỰC TRỊ BẬC HAI VÀ ĐỘ NHẠY NGHIỆM CỦA BÀI TOÁN TỐI ƯU CÓ RÀNG BUỘC KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Giải tích HÀ NỘI – 2018 TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN ************** NGUYỄN THỊ HUẾ ĐIỀU KIỆN CỰC TRỊ BẬC HAI VÀ ĐỘ NHẠY NGHIỆM CỦA BÀI TOÁN TỐI ƯU CÓ RÀNG BUỘC KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Giải tích NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Nguyễn Văn Tuyên Hà Nội – Năm 2018 LỜI CẢM ƠN Em xin được gửi lời cảm ơn tới các thầy cô giáo trường Đại học Sư phạm Hà Nội 2, các thầy cô giáo khoa Toán đã giúp đỡ em trong quá trình học tập tại trường và tạo điều kiện cho em hoàn thành đề tài khóa luận tốt nghiệp. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy Nguyễn Văn Tuyên đã tận tình giúp đỡ em trong suốt quá trình học tập, nghiên cứu và hoàn thành khóa luận này. Trong quá trình nghiên cứu, không tránh khỏi những thiếu sót và hạn chế. Kính mong nhận được sự đóng góp ý kiến của các thầy giáo, cô giáo và toàn thể bạn đọc để đề tài được hoàn thiện hơn. Em xin chân thành cảm ơn! Hà Nội, tháng 5 năm 2018 Sinh viên Nguyễn Thị Huế 2 LỜI CAM ĐOAN Em xin cam đoan dưới sự hướng dẫn của thầy Nguyễn Văn Tuyên khóa luận của em được hoàn thành không trùng với bất kì đề tài nào khác. Trong khi thực hiện đề tài em đã sử dụng và tham khảo các thành tựu của các nhà khoa học với lòng biết ơn trân trọng. Hà Nội, tháng 5 năm 2018 Sinh viên Nguyễn Thị Huế Mục lục Lời mở đầu 1 1 Một số kiến thức chuẩn bị 3 1.1 1.2 1.3 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Tập lồi và các tính chất của tập lồi . . . . . . . 3 1.1.2 Hàm lồi và một số tính chất của hàm lồi . . . . 4 Các tập tiếp xúc . . . . . . . . . . . . . . . . . . . . . 5 1.2.1 Nón tiếp tuyến . . . . . . . . . . . . . . . . . . 5 1.2.2 Tập tiếp xúc bậc hai . . . . . . . . . . . . . . . 8 Điều kiện cực trị bậc nhất . . . . . . . . . . . . . . . . 14 2 Điều kiện cực trị bậc hai và độ nhạy nghiệm 16 2.1 Điều kiện tối ưu. . . . . . . . . . . . . . . . . . . . . . 16 2.2 Độ nhạy nghiệm . . . . . . . . . . . . . . . . . . . . . . 26 Kết luận 32 Tài liệu tham khảo 32 i Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Lời mở đầu Lý thuyết tối ưu được hình thành với tư cách là một lý thuyết toán độc lập. Có thể nói lý thuyết tối ưu bắt đầu từ các bài toán quy hoạch tuyến tính, tiếp đó là các bài toán quy hoạch lồi. Đối tượng nghiên cứu của lý thuyết tối ưu được mở rộng và hình thành những hướng nghiên cứu khác nhau ngày càng có nhiều ứng dụng trong thực tế. Trong lý thuyết tối ưu, các điều kiện cực trị bậc nhất thường đóng vai trò như các điều kiện cần tối ưu. Các điều kiện cực trị bậc hai không những bổ sung cho các điều kiện cực trị bậc nhất mà còn đóng vai trò quan trọng trong các điều kiện đủ và trong việc nghiên cứu tính ổn định nghiệm tối ưu. Với mong muốn tìm hiểu sâu hơn các bài toán tối ưu, đặc biệt là các bài toán tối ưu có ràng buộc, tôi đã chọn nghiên cứu đề tài: “Điều kiện cực trị bậc hai và độ nhạy nghiệm của các bài toán tối ưu có ràng buộc”. Mục đích của khóa luận là trình bày một cách có hệ thống, các kiến thức cơ bản và quan trọng nhất về điều kiện cực trị bậc hai và độ nhạy nghiệm của các bài toán tối ưu có ràng buộc. Các kết quả chính trong khóa luận được trình bày dựa trên cuốn sách chuyên khảo [3] Nonlinear Optimization năm 2006. Khóa luận gồm hai chương: Chương 1 trình bày một số kiến thức chuẩn bị. Nội dung chính của chương này là trình bày một số kiến thức cơ bản của tập lồi và hàm lồi, tập tiếp xúc, điều kiện cực trị bậc nhất. Chương 2 trình bày về điều kiện cực trị bậc hai và độ nhạy nghiệm 1 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế của bài toán có ràng buộc. Mục 2.1 sẽ trình bày về điều kiện cực trị bậc hai. Mục 2.2 sẽ trình bày độ nhạy của nghiệm tối ưu. 2 Chương 1 Một số kiến thức chuẩn bị 1.1 1.1.1 Tập lồi và hàm lồi Tập lồi và các tính chất của tập lồi Định nghĩa 1.1. Một tập X của Rn được gọi là tập lồi nếu x, y ∈ X ta có λx + (1 − λ) y ∈ X, ∀λ ∈ [0, 1]. Nghĩa là nếu x, y ∈ X thì đoạn thẳng [x.y] ∈ X. Đặc biệt, nếu n = 1 thì tập lồi là một khoảng một đoạn hay nửa n P khoảng. Nếu α1 , . . . , αn là các số thực không âm, αi = 1 thì i=1 x= n X αi xi i=1 được gọi là một tổ hợp lồi của x1 , . . . , xn . Định lý 1.1. Một tập X ⊂ Rn là một tập lồi nếu và chỉ nếu mọi tổ hợp của các điểm X đều nằm trong X. 3 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Định lý 1.2. Nếu {Xi } , i ∈ J là một họ các tập lồi thì X = ∩i∈J Xi là một tập lồi. Định nghĩa 1.2. Cho X là một tập con của Rn . Khi đó bao lồi của X ký hiệu là convX, là giao của tất cả các tập lồi chứa X. Bao lồi của X là một tập lồi. Định lý 1.3. Cho X là một tập con của Rn . Khi đó bao lồi của X là tập tất cả các tổ hợp lồi của các phần tử của X. Định nghĩa 1.3. Một điểm x0 của tập lồi X được gọi là điểm cực biên nếu x0 không là điểm trong của bất cứ đoạn thẳng nào nằm trong X. Tức là không tồn tại hai điểm x1 , x2 ∈ X và λ ∈ (0; 1) để x0 = λx1 + (1 − λ) x2 . Định lý 1.4. Cho X ⊆ Rn là một tập lồi, compact. Khi đó X là bao lồi của tất cả các điểm cực biên của nó. 1.1.2 Hàm lồi và một số tính chất của hàm lồi Các hàm lồi được định nghĩa trên các tập lồi. Định nghĩa 1.4. Cho X là một tập lồi trong Rn và hàm f : X → R (i) f được gọi là hàm lồi nếu f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) với mọi x, y ∈ X và với mọi λ ∈ [0; 1]. (ii) f được gọi là hàm lồi chặt nếu (1.3) là bất đẳng thức ngặt với các điểm x, y phân biệt và λ ∈ (0; 1). 4 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế (iii) Nếu hàm −f là lồi (lồi chặt) thì ta nói f là hàm lõm (lõm chặt). (iv) Nếu f vừa là hàm lồi vừa là hàm lõm thì ta nói f là hàm affine. Thực ra, tại λ = 0 và λ = 1 thì (1.3) luôn đúng cho nên để cho tiện, đôi khi ta chỉ cần xét λ ∈ (0; 1). 1.2 Các tập tiếp xúc 1.2.1 Nón tiếp tuyến Định nghĩa 1.5. Hướng d được gọi là tiếp xúc của tập X ⊂ Rn tại điểm x ∈ X nếu tồn tại một dãy của điểm xk ∈ X và dãy số τk > 0, k = 1, . . . , sao cho τk ↓ 0 và xk − x . d = lim k→∞ τk Từ định nghĩa ta có xk → x, nếu ngược lại thì giới hạn trên không tồn tại. Bổ đề 1.1. Cho X ∈ Rn và x ∈ X. Tập TX (x) là tập tất cả các hướng tiếp xúc của X tại x là một tập nón đóng. Bổ đề 1.2. Cho X ∈ Rn là một tập lồi và x ∈ X. Khi đó TX (x) = KX (x), ở đó, KX (x) := {d ∈ Rn : d = β(y − x), y ∈ X, β ≥ 0}. Kí hiệu X là tập hợp được cho bởi hệ X = {x ∈ X0 : g(x) ∈ Y0 }, 5 (1.1) Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế ở đó g : Rn → R khả vi liên tục, Y0 và X0 lần lượt là các tập lồi đóng trong Rm , Rn . Định nghĩa 1.6. Hệ (1.1) được gọi là chính quy metric tại điểm x0 ∈ X nếu tồn tại ε > 0 và C sao cho tất cả x̃ và ũ thỏa mãn kx̃ − xk ≤ ε và kũk ≤ ε ta có thể tìm thấy xR ∈ X0 thỏa mãn g(xR ) − ũ ∈ Y0 , và sao cho kxR − x̃k ≤ C(dist(x̃, X0 ) + dist(g(x̃) − ũ), Y0 )). (1.2) Chính quy metric tương đương với điều kiện Robinson sau: {g 0 (x0 ) − υ : d ∈ KX0 (x0 ), υ ∈ KY0 (g(x0 ))} = Rm . (1.3) Trong đó x0 bị nhiễu theo hướng d, khi đó g 0 (x0 ) bị nhiễu theo hướng g 0 (x0 ). Ta thấy rằng tập hợp ở vế trái của (1.3) là một nón, do đó điều kiện Robinson có thể biểu diễn bởi 0 ∈ int {g 0 (x0 )(x − x0 ) − (y − g(x0 ) : x ∈ X0 , y ∈ Y0 )}. Định lý 1.5. Nếu hệ (1.1) là chính quy metric, thì TX (x0 ) = {d ∈ Rn : d ∈ TX0 (x0 ), g 0 (x0 )d ∈ TY0 (g(x0 ))}. (1.4) Nhận xét 1.1. Chúng ta có thể dễ dàng đưa ra dạng đại số của nón 6 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế tiếp tuyến của hệ gồm các phương trình và bất phương trình. Xét hệ có dạng gi (x) ≤ 0, i = 1, . . . , m, hi (x) = 0, i = 1, . . . , p, (1.5) x ∈ X0 , ở đó, g : Rn → Rm và h : Rn → Rp là các hàm khả vi liên tục và X0 là một tập lồi đóng. Với một điểm x0 thỏa mãn hệ (1.5), tập các ràng buộc bất đẳng thức hoạt của hệ này được định nghĩa bởi: I 0 (x0 ) = {1 ≤ i ≤ m : gi (x0 ) = 0}. Hệ (1.5) là một trường hợp đặc biệt của hệ (1.1) với Y0 = {(y, 0) ∈ Rm × Rp : yi ≤ 0, i ∈ I 0 (x0 )}. Điều kiện Robinson (1.3) có dạng:     g 0 (x )d − υ  0   : d ∈ TX0 (x0 ), υ ∈ Rm , υi ≤ 0, i ∈ I 0 (x0 ) = Rm × Rp .   h0 (x )d 0 (1.6) Một điều kiện đủ cho tính chính quy metric được phát biểu như sau. 7 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Bổ đề 1.3. Giả sử rằng tồn tại một điểm xM F ∈ intX0 sao cho hOgi (x0 ), xM F − x0 i < 0, i ∈ I 0 (x0 ) hOhi (x0 ), xM F − x0 i = 0, i = 1, . . . , p, (1.7) và hệ {∇hi (x0 ), i = 1, . . . , p} độc lập tuyến tính. Khi đó hệ (1.5) là chính quy metric. Các giả thiết của Bổ đề 1.3 với X0 = Rn được biết đến như là điều kiện chuẩn hóa ràng buộc Mangasarian - Fromovitz. Trong trường hợp này, điều kiện chuẩn hóa này tương đương với chính quy metric. Bổ đề 1.4. Hệ (1.5) với X0 = Rn thỏa mãn điều kiện chuẩn hóa ràng buộc Mangasarian - Fromovitz tại một điểm x0 khi và chỉ khi nó chính quy metric tại x0 . 1.2.2 Tập tiếp xúc bậc hai Để phát triển điều kiện tối ưu bậc 2, chúng ta xét quỹ đạo parabolic có dạng x(τ ) = x0 + τ s + τ2 w, 2 τ ≥ 0, (1.8) trong đó s là hướng tiếp xúc. Ý tưởng của chúng ta làm cho khoảng cách tới X nhỏ tùy ý so với τk 2 . Định nghĩa 1.7. Hướng w được gọi là tiếp xúc bậc 2 tới X ⊂ Rn tại điểm x0 ∈ X theo hướng s, nếu tồn tại một dãy điểm xk ∈ X, k = 1, 2, . . . , và một dãy τk > 0, k = 1, 2, . . ., sao cho τk ↓ 0 và xk − x0 − τk s w = lim . 2 1 k→∞ (τ ) k 2 8 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Ký hiệu ok là hiệu của vế trái và vế phải của phương trình cuối cùng, chúng ta có thể viết τk 2 τk 2 τk 2 x = x0 + τk s + w − ok = x(τk ) − ok . 2 2 2 k Theo định nghĩa các điểm trên quỹ đạo parapolic (1.8), ta có với τ = τk và k → ∞, rất gần với tập hợp X: dist(x(τk ), X) = o(τk 2 ). Từ Định nghĩa 1.7, ta thấy rằng s là hướng tiếp xúc (bậc nhất): s ∈ TX (x0 ). Thật vậy, nếu w là hướng tiếp xúc bậc 2, khi đó giới hạn của Định nghĩa 1.7 là tồn tại, điều đó suy ra rằng xk − x0 − τk s lim = 0, k→∞ τk và do đó (xk − xo )/τk → s. Với s ∈ / TX (x0 ) không tồn tại hướng tiếp xúc bậc 2. Tập hợp gồm tất cả hướng tiếp xúc bậc 2 tới X tại (x0 , s) gọi là tập tiếp xúc bậc 2 và kí hiệu bởi TX 2 (x0 , s). Mệnh đề 1.1. Cho X ∈ Rn , x0 ∈ X, s ∈ TX (x0 ). Tập hợp TX 2 (x0 , s) là đóng và Tk 2 (x0 , αs) = α2 TX 2 (x0 , s) với mọi α > 0.  Chứng minh. Cho w ∈ Tk 2 (x0 , s) và xk , {τk } là các dãy thoả mãn 9 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Định nghĩa 1.7. Với ∀α > 0 chúng ta thu được α2 (xk − x0 − τk s) α w = lim 2 1 k→∞ 2 (τk ) xk − x0 − ταk (αs) = lim .
2 2 1 τk 2 α k→∞ Do đó α2 w thỏa mãn Định nghĩa 1.7 với hướng αs, cùng với một dãy  điểm xk và sự tương ứng của vô hướng {τk /α} . Lập luận cho chiều ngược lại được tiến hành tương tự.  Để chứng tỏ rằng tập tiếp xúc bậc 2 là tập đóng. Ta xét 1 dãy wj hội tụ tới w trong đó mỗi wj ∈ TX 2 (x0 , s). Chúng ta cần chỉ ra rằng w thỏa mãn Định nghĩa 1.7 với (x0 , s). Chọn dãy bất kỳ εj ↓ 0, với mỗi wj Định nghĩa 1.7 thỏa mãn cùng với dãy của các điểm xj,k và các vô hướng τj,k , k = 1, 2 . . . . Chúng ta có thể tìm xj,k(j) và τj,k(j) sao cho xj,k(j) − x − τ 0 j,k(j) s j − w ≤ εj . 1 (τj,k(j) )2 2 Bởi vậy xj,k(j) − x − τ j 0 j,k(j) s , − w ≤ ε + w − w j 1 (τj,k(j) )2 2 và w thỏa mãn định nghĩa 1.7 cùng dãy xj,k(j) và τj,k(j) , j = 1, 2, . . . Tổng quát tập xúc bậc 2 không phải là một nón và nó có thể không lồi, kể cả với trường hợp X là lồi. Nhưng với trường hợp đa điện X, tập tiếp xúc bậc 2 có biểu diễn và trên thực tế là một nón lồi. 10 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Bổ đề 1.5. Nếu X là một tập lồi đa điện, thì TX2 (x0 , s) = TTX (x0 ) (s) . Chứng minh. Chúng ta nhắc lại rằng nếu X là một tập lồi đa điện, thì nón tiếp xúc TX (x0 ) là đồng nhất cùng với nón của hướng chấp nhận được KX (x0 ) và cả hai nón này là đa điện: chúng được xác định bởi hữu hạn các bất đẳng thức tuyến tính. Ký hiệu bởi ai , i = 1, 2, . . . , m, là các vector xác định các bất đẳng thức hoạt tại x0 , chúng ta có thể viết TX (x0 ) = {s ∈ Rn : hai , si ≤ 0, i = 1, ..., m} . Xét hướng s ∈ TX (x0 ) và dãy τk2 x (τk ) = x0 + τk s + w 2 cùng với τk ↓ 0. Vector w là phần tử của tập tiếp xúc bậc 2 khi và chỉ khi dist (x (τk ) − X) = o(τk2 ). Điều này tương đương với
hai , x (τk ) − x0 i ≤ o τk2 , i = 1, 2, . . . , m. (1.9) Với mỗi i = 1, . . . , m, có thể có 2 trường hợp. Nếu hai , si = 0 thì (1.9) có nghĩa đúng khi và chỉ khi hai , wi ≤ 0. Nếu hai , si < 0 thì (1.9) thỏa mãn với ∀w ∈ Rn . Cho nên w ∈ Tk2 (x0 ) khi và chỉ khi hai , wi ≤ 0 với mọi i sao cho hai , si = 0. Điều đó tương đương với sự bao gồm w ∈ TTX (x0 ) (s). 11 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Bây giờ xét tập X của các điểm x ∈ Rn thỏa mãn hệ thống các mối liên hệ gi (x) ≤ 0, i = 1, 2, . . . m, hi (x) = 0, i = 1, 2, . . . p, (1.10) x ∈ X0 . Cho x̂ ∈ X và mọi hàm số gi (·) và hi (·) khả vi liên tục đến cấp hai tại x̂. Hơn nữa, cho X0 là tập lồi. Điều kiện dưới Robinson (1.6), mặt nón TX (x̂) = {s ∈ TX0 (x̂) : h5gi (x̂), si ≤ 0, i ∈ I 0 (x̂), (1.11) h5hi (x̂), si = 0, i = 1, . . . , p} là tiếp xúc hình nón khả thi đến (x̂). Chúng ta sẽ suy ra sự mô tả đại số của tập tiếp xúc bậc 2. Bổ đề 1.6. Giả sử điều kiện Robinson thoả mãn tại điểm x̂ ∈ X. Khi đó với mọi s ∈ TX (x̂), TX2 (x̂, s) ={w ∈ TX2 0 (x̂, s) : h5gi (x̂), wi ≤ −hs, 52 gi (x̂)si, i ∈ I 00 (x̂, s), (1.12) h5hi (x̂), wi = −hs, 52 hi (x̂)si, i = 1, . . . , p}, với  I 00 (x̂, s) = i ∈ I 0 (x̂) : h∇gi (x̂) , si = 0 . Chứng minh. Cho s ∈ TX (x̂) và w là phần tử của tập vế phải (1.12). 12 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Xét quỹ đạo parabolic (1.8). Với mỗi i ∈ I 0 (x̂) chúng ta có thể khai triển gi (x (τ )) như sau: gi (x (τ )) = gi (x̂) + h∇gi (x̂) , x (τ ) − x̂i 
τ2 x (τ ) − x̂, ∇2 gi (x̂) (x (τ ) − x̂) + o τ 2 (1.13) + 2 
τ2 τ2 s, ∇2 gi (x̂) s + o τ 2 . =τ h∇gi (x̂) , si + h∇gi (x̂) , wi + 2 2 Thực tế chúng ta sử dụng gi (x̂) = 0 với i ∈ I 0 (x̂). Hai trường hợp có thể xảy ra. Nếu i ∈ / I 00 (x̂, s) thì h∇gi (x̂) , si < 0. Khi đó với mỗi w ∈ Rn chúng ta có gi (x (τ )) < 0 với mọi τ > 0 đủ nhỏ. Trong trường hợp thứ 2, khi i ∈ I 00 (x̂, s), số hạng thứ nhất biến mất. Nhưng nếu w là phần tử của định nghĩa (1.12), thì số hạng thứ 2 không dương. Tương tự như vậy áp dụng với các ràng buộc cho các đối số. Chúng ta kết luận rằng nếu w thỏa mãn điều kiện vế phải của (1.12), khi đó
gi (x (τ )) ≤ o τ 2 ,
|hi (x (τ ))| ≤ o τ 2 , i ∈ I 0 (x̂) , i = 1, . . . , p, (1.14)
dist (x (τ ) , X0 ) = o τ 2 . Mối quan hệ rút ra từ thực tế là s ∈ TX0 (x̂) và w ∈ TX2 0 (x̂, s). Từ 0 ∈ int{g 0 (x0 , u0 ) (x − x0 ) − (y − g (x0 )) : x ∈ X0 , y ∈ Y0 }, khi đó hệ g (x, u) ∈ Y0 , x ∈ X0 với g : Rn × Rs → Rm , g khả vi liên tục đến cấp hai. Từ điều kiện Robinson rằng hệ thống của sự giàng buộc chính quy tại x̂. Sử dụng Định nghĩa (1.6), suy ra rằng với mọi τ ∈ [0, τ0 ] tồn tại C ≥ 0 và τ0 > 0, chúng ta có thể tìm thấy điểm ϕ (τ ) ∈ X 13 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế thỏa mãn bất đẳng thức: kϕ(τ ) − x(τ )k ≤ C[dist(x(τ ), X0 ) X X + max(0, gi (x(τ ))) + |hi (x(τ ))|]. i=1 i∈I 0 (x̂) Bởi vì (1.14)
kϕ (τ ) − x (τ )k ≤ o τ 2 .
Bởi dist (x (τ ) , X) ≤ o τ 2 và thật vậy w ∈ TX2 (x̂, s) . Để chứng tỏ phần đảo, giả sử rằng w ∈ TX2 (x̂, s). Khi đó chúng ta có (1.14) cùng với dãy τk ↓ 0. Xét khai triển (1.13) chúng ta kết luận rằng w là một phần tử của vế phải (1.12). Từ 2 mệnh đề cho đa diện X0 và điều kiện dưới Robinson, tập tiếp xúc bậc 2 được xác định (1.10) là một hình nón lồi đóng. 1.3 Điều kiện cực trị bậc nhất Định lý 1.6. Giả sử x̂ là cực tiểu địa phương của bài toán min f (x) x∈X n n với f : R → R, X ⊂ R và f (·) khả vi tại x̂. Cho TX (x̂) là nón tiếp tuyến của tập X tại x̂. Khi đó −Of (x̂) ∈ [TX (x̂)]◦ . (1.15) Ngược lại, nếu hàm f (·) là lồi, tập X là lồi, và một điểm x̂ ∈ X thỏa mãn hệ thức (1.15), thì x̂ là cực tiểu toàn cục của bài toán min f (x). x∈X 14 Khóa luận tốt nghiệp Đại học Nguyễn Thị Huế Định lý 1.7. Cho x̂ là một cực tiểu địa phương của bài toán min f (x) với giả thiết gi (x) ≤ 0, i = 1, . . . , m, (1.16) hi (x) = 0, i = 1, . . . , p, x ∈ X0 . Giả sử rằng x̂ thỏa mãn điều kiện chuẩn hóa ràng buộc. Khi đó tồn tại các nhân tử λ̂i ≥ 0, i = 1, . . . , m, và µ̂i ∈ R, i = 1, . . . , p, sao cho 0 ∈ Of (x̂) + m X λ̂i Ogi (x̂) + i=1 p X µ̂i Ohi (x̂) + NX0 (x̂), (1.17) i=1 và λ̂i gi (x̂) = 0, i = 1, . . . , m. (1.18) Bổ đề 1.7. Cho x̂ là cực tiểu địa phương của bài toán (1.16) và cho p Λ̂(x̂) là tập hợp các nhân tử Lagrange λ̂ ∈ Rm + và µ̂ ∈ R thỏa mãn (1.17) - (1.18) . i) Tập hợp Λ̂(x̂) là lồi và đóng. ii) Nếu bài toán (1.16) thỏa mãn điều kiện Robinson tại x̂ thì tập Λ̂(x̂) cũng bị chặn. Định lý 1.8. Giả sử hàm f (·) và gi (·), i = 1, . . . , m, là lồi và hàm hi (·), i = 1, . . . , p, là affine. Nếu điểm x̂ ∈ X và các nhân tử λ̂i ≥ 0, i = 1, . . . , m, và µ̂i ∈ R, i = 1, . . . , p, thỏa mãn các điều kiện (1.17) - (1.18), thì x̂ là một cực tiểu toàn cục của bài toán (1.16). 15