Tài liệu Quy tắc nhân tử lagrange cho bài toán tối ưu vectơ khả vi

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ---------- LÊ THỊ THU HÀ QUY TẮC NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU VECTƠ KHẢ VI Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 Thái nguyên – 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ---------- LÊ THỊ THU HÀ QUY TẮC NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU VECTƠ KHẢ VI Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 Giáo viên hướng dẫn: PGS.TS Đỗ Văn Lưu Thái nguyên – 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ MỞ ĐẦU Lý thuyết các điều kiện tối ưu là một bộ phận quan trọng của lý thuyết tối ưu hóa và có nhiều ứng dụng trong kinh tế, kỹ thuật. Cho đến nay lý thuyết các điều kiện tối ưu đã thu được nhiều kết quả phong phú và đẹp đẽ. Để dẫn các điều kiện cần cho nghiệm hữu hiệu của bài toán tối ưu vectơ trước hết ta có thể sử dụng định lý Ljusternik của giải tích hàm để chứng minh các điều kiện cần dạng hệ bất đẳng thức không tương thích. Từ đó sử dụng định lý tách của giải tích lồi ta sẽ dẫn được các điều kiện cần Fritz John và Kuhn - Tucker. Điều kiện cần Kuhn - Tucker ấy sẽ trở thành điều kiện đủ tối ưu khi giả thiết thêm một điều kiện về tính lồi suy rộng của các hàm dữ liệu. Các điều kiện tối ưu là đề tài đã và đang được nhiều nhà toán học trong và ngoài nước quan tâm nghiên cứu. Chính vì vậy tôi đã chọn đề tài "Quy tắc nhân tử Lagrange cho bài toán tối ưu vectơ khả vi" Luận văn trình bày lý thuyết các điều kiện Fritz John và Kuhn - Tucker và các điều kiện đủ cho nghiệm hữu hiệu của bài toán tối ưu vectơ khả vi. Luận văn bao gồm phần mở đầu, ba chương, kết luận, và danh mục các tài liệu tham khảo. Chương 1: Nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu Trình bày các khái niệm cực tiểu, cực đại, cực tiểu yếu, cực đại yếu của một tập hợp và nghiệm hữu hiệu (hay cực tiểu), nghiệm hữu hiệu yếu (hay cực tiểu yếu) của bài toán cực tiểu vectơ cùng với một số kết quả bổ trợ để dẫn điều kiện tối ưu. Chương 2. Điều kiện cần cho nghiệm hữu hiệu yếu. Trình bày các điều kiện cần dạng hệ bất đẳng thức không tương thích, 1 điều kiện cần Fritz John và điều kiện cần Kuhn - Tucker cho nghiệm hữu hiệu yếu của bài toán tối ưu vectơ . Chương 3. Điều kiện đủ cho nghiệm hữu hiệu và nghiệm hữu hiệu yếu. Trình bày các tính chất của hàm tựa lồi và các điều kiện đủ cho nghiệm hữu hiệu yếu của bài toán tối ưu vectơ với giả thiết về tính lồi suy rộng của các hàm mục tiêu và ràng buộc. Nhân dịp này em xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Đỗ Văn Lưu, người đã tận tình hướng dẫn, giúp đỡ em hoàn thành bản luận văn này. Em xin chân thành cảm ơn Phòng đào tạo sau đại học, Ban Giám Hiệu Trường Đại học Khoa học - Đại học Thái Nguyên cùng các thầy cô giáo đã tham gia giảng dạy khóa học. Tôi xin chân thành cảm ơn gia đình, bạn bè, đồng nghiệp và các thành viên trong lớp cao học toán K6D đã luôn quan tâm, động viên, giúp đỡ tôi trong suốt thời gian học tập và quá trình làm luận văn. Thái Nguyên, tháng 04 năm 2014 Tác giả Lê Thị Thu Hà 2 Chương 1 NGHIỆM HỮU HIỆU CỦA BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU Chương 1 trình bày các khái niệm cực tiểu, cực đại, cực tiểu yếu, cực đại yếu của một tập trong không gian tuyến tính có thứ tự bộ phận và các khái niệm nghiệm hữu hiệu (hay cực tiểu), nghiệm hữu hiệu yếu (hay cực tiểu yếu) của bài toán cực tiểu vectơ cùng với một số kết quả bổ trợ để dẫn điều kiện tối ưu. Các kết quả trình bày trong chương này được tham khảo trong [2]. 1.1. Nghiệm hữu hiệu và nghiệm hữu hiệu yếu của một tập và bài toán tối ưu đa mục tiêu Trong phần này ta sẽ dẫn quy tắc nhân tử Lagrange cho bài toán tối ưu đa mục tiêu với các hàm khả vi Fréchet. Ta đưa vào các giả thiết sau:    Giả sử (X, k · kX ) và (Z2 , k · kZ2 ) là các không gian Banach thực;         (Y, k · kY ) và (Z1 , k · kZ1 ) là các không gian định chuẩn có thứ tự        bộ phận trong Y. Giả sử CY và CZ1 là các nón thứ tự bộ phận (1.1)    trong Y và trong Z1 có phần trong khác rỗng;        Ŝ là tập con lồi khác rỗng của X có phần trong khác rỗng;        Giả sử f : X 7−→ Y ; g : X 7−→ Z Xét tập ràng buộc sau đây: S := { x ∈ Ŝ | g(x) ∈ −CZ1 và h(x) = 0z2 } Giả sử tập S khác rỗng. Ta xét bài toán tối ưu trừu tượng sau: min f (x) x∈S 3 (1.2) Ánh xạ f được gọi là ánh xạ mục tiêu. Trước hết ta định nghĩa nghiệm của bài toán (1.2). Ta nhắc lại các khái niệm cực tiểu, cực đại, cực tiểu yếu và cực đại yếu của một tập. Định nghĩa 1.1.1 Giả sử S là tập con khác rỗng của không gian tuyến tính có thứ tự bộ phận X với nón thứ tự C. (i) Phần tử x̄ ∈ S được gọi là cực tiểu (minimal element) của tập S nếu:
{x̄} − C ∩S ⊂ {x̄} + C (1.3) (ii) Phần tử x̄ ∈ S được gọi là cực đại (maximal element) của tập S nếu:
{x̄} + C ∩S ⊂ {x̄} − C (1.4) Nếu nón thứ tự C nhọn thì các bao hàm thức (1.3) và (1.4)có thể thay bằng các đẳng thức sau:
{x̄} − C ∩S = {x̄} (hoặc x ≤C x̄, x ∈ S ⇒ x = x̄),
{x̄} + C ∩S = {x̄} (hoặc x̄ ≤C x, x ∈ S ⇒ x = x̄). và Nhắc lại: Phần trong đại số của của S 6= ∅ trong không gian tuyến tính thực X là tập  cor(S) = x̄ ∈ S | ∀x ∈ X, ∃λ̄ > 0 : x̄ + λx ∈ S, ∀λ ∈ [0, λ̄] Định nghĩa 1.1.2 Giả sử S là tập con khác rỗng của không gian tuyến tính có thứ tự bộ phận X với nón thứ tự C có phần trong đại số khác rỗng: (i) Phần tử x̄ ∈ S được gọi là cực tiểu yếu (weakly minimal element) của tập S nếu:
{x̄} − cor(C) ∩S = ∅; 4 (ii) Phần tử x̄ ∈ S được gọi là cực đại yếu (weakly maximal element) của tập S nếu:
{x̄} + cor(C) ∩S = ∅. Chú ý rằng các khái niệm cực tiểu và cực tiểu yếu liên quan chặt chẽ với nhau. Lấy một phần tử x̄ ∈ S là cực tiểu yếu của tập S tức là ta có:
{x̄} − cor(C) ∩S = ∅. Khi đó, X̄ cũng là cực tiểu yếu của tập S đối với thứ tự bộ phận sinh ra bởi Ĉ = cor(C) ∪ {0X }. Bổ đề 1.1.1[2] Giả sử S là tập con khác rỗng của không gian tuyến tính có bộ phận Xvới nón thứ tự C có phần trong đại số khác rỗng. (i) Mọi cực tiểu yếu x̄ ∈ S của tập S + C cũng là cực tiểu yếu của tập S. (ii) Mọi cực tiểu yếu x̄ ∈ S của tập S cũng là cực tiểu yếu của tập S + C. Mệnh đề 1.1.2 Giả sử S là tập con khác rỗng của không gian tuyến tính có thứ tự bộ phậnX Với nón thứ tự C mà C 6= X và cor(C) 6= ∅. Khi đó, mọi phần tử cực tiểu của tập S cũng là cực tiểu yếu của S. Chứng minh
Giả thiết C 6= X kéo theo −cor(C) ∩C = ∅. Do đó, với một phần tử cực tiểu x̄ của S, ta có
∅ = {x̄} − cor(C) ∩({x̄} + C)
= {x̄} − cor(C) ∩({x̄} − C) ∩ S
= {x̄} − cor(C) ∩S. Điều đó có nghĩa là x̄ cũng là cực tiểu của S. 2 Bây giờ ta định nghĩa khái niệm nghiệm hữu hiệu và nghiệm hữu hiệu yếu của bài toán tối ưu (1.2) Định nghĩa 1.1.3 5 Giả sử bài toán tối ưu (1.2) thỏa mãn các giả thiết (1.1). (i) Một phần tử x̄ ∈ S được gọi là cực tiểu (nghiệm hữu hiệu) của bài toán (1.2) nếu f (x̄) là cực tiểu của tập ảnh f (S). (ii) Một phần tử x̄ ∈ S được gọi là cực tiểu (nghiệm hữu hiệu yếu) của bài toán (1.2) nếu f (x̄) là cực tiểu yếu của tập ảnh f (S). 1.2. Một số kết quả bổ trợ để dẫn điều kiện tối ưu Để nhận được điều kiện cần cho cực tiểu yếu (nghiệm hữu hiệu yếu) của bài toán tối ưu (1.2) ta cần một kết quả về nón tiếp liên. Cho S là tập con của không gian định chuẩn X, nón tiếp liên của tập S tại điểm x̄ ∈ S được định nghĩa như sau: T (S; x̄) = {v ∈ X : ∃vn −→ v, ∃tn −→ 0+ sao cho x̄ + tn vn ∈ S, ∀n}. Để dẫn điều kiện cần cho nghiệm hữu hiệu yếu của bài toán (1.2) ta trình bày mệnh đề sau đề về nón tiếp liên. Mệnh đề 1.2.1 Giả sử (X, k · kX )là không gian định chuẩn thực và(Y, k · kY ) là không gian định chuẩn có thứ tự bộ phận với nón thứ tự CY có phần trong khác rỗng. Hơn nữa, giả sử S là tập con khác rỗng của X và ánh xạ r : X → Y. Nếu ánh xạ r là khả vi Fréchet tại x̄ ∈ S nào đó, với r(x̄) ∈ −CY thì  h ∈ T (S, x̄) | r(x̄) + r0 (x̄)(h) ∈ −int(CY )
⊂ T {x ∈ S | r(x) ∈ −int(CY )}, x̄ , trong đó T (., .) ký hiệu nón tiếp liên. Chứng minh: Chọn phần tử h ∈ T (S : x̄), với tính chất r(x̄) + r0 (x̄)(h) ∈ −int(CY ). Với h = 0X , khẳng định là tầm thường. Do đó, ta giả sử h 6= 0X . Khi đó, 6 tồn tại dãy (xn )n∈N các phần tử xn ∈ S và dãy (λn )n ∈ N gồm các số thực dương λn sao cho x̄ = lim xn x→0 và h = lim λn (xn − x̄). n→∞ Nếu ta đặt hn := λn (xn − x̄), ∀n ∈ N, thì ta nhận được 1 [λn (r(xn ) − r(x̄) − r0 (x̄)(xn − x̄)) + r0 (x̄)(hn − h) λn (1.5) 1 0 + r(x̄) + r (x̄)(h)] + (1 − )r(x̄), ∀n ∈ N, λn r(xn ) = và lim λn (r(xn ) − r(x̄) − r0 (x̄)(xn − x̄)) + r0 (x̄)(hn − h) = 0Y . n→∞ Theo giả thiết ta có r(x̄) + r0 (x̄)(h) ∈ −int(Cy ), và do đó từ (1.6) ta suy ra yn : = λn (r(xn ) − r(x̄) − r0 (x̄)(xn − x̄)) + r0 (x̄)(hn − h) + r(x̄) + r0 (x̄)(h) ∈ −int(CY ) với n ∈ N đủ lớn, và 1 λn yn ∈ −int(CY ) với n ∈ N đủ lớn. Bởi vì  1− 1 λn  r(x̄) ∈ −CY với n ∈ N đủ lớn, 7 (1.6) Từ (1.5) ta suy ra r(xn ) = 1 1 yn + (1 − )r(x̄) λn λn ∈ −int(CY ) − CY = −int(CY ) với n ∈ N đủ lớn, bởi vì với int(CY ) 6= 0 thì int(CY ) = cor(CY ). Nhưng điều này lại dẫn tới:
h ∈ T {x ∈ S | r(x) ∈ −int(CY )}, x̄ . 2 Mệnh đề 1.2.2[2] Giả sử CX là nón lồi trong không gian tuyến tính thực X. (a) Nếu X là không gian lồi địa phương và CX đóng thì CX = {x ∈ X | x∗ (x) ≥ 0 ∀x∗ ∈ CX ∗ }. (b) Nếu cor(CY ) 6= ∅ thì  cor(CX ) = x ∈ X | x0 (x) > 0 ∀x0 ∈ CX 0 \ {0X 0 } (c) Nếu X là không gian tôpô tuyến tính thực và int(CX ) 6= ∅ thì  int(CX ) = x ∈ X | x∗ (x) > 0 ∀x∗ ∈ CX ∗ \ {0X ∗ } , trong đó X ∗ là không gian ngẫu tôpô của X, X 0 là không gian ngẫu đại số của X. 8 Chương 2 ĐIỀU KIỆN CẦN CHO NGHIỆM HỮU HIỆU YẾU Chương 2 trình bày các điều kiện cần tối ưu dạng hệ bất đẳng thức không tương thích, điều kiện cần Fritz John cho nghiệm hữu hiệu yếu và điều kiện Kuhn - Tucker cho nghiệm hữu hiệu yếu của bài toán tối ưu vectơ. Các kết quả trong chương này được tham khảo từ các tài liệu [1], [2], [3], [5]. 2.1. Điều kiện cần dạng hệ bất đẳng thức không tương thích . Từ bổ đề trên và định lý Lyusternik ta trình bày điều kiện cần cho nghiệm hữu hiệu yếu của bài toán (1.2). Định lý 2.1.1 Giả sử bài toán tối ưu (1.2) thỏa mãn giả thiết (1.1) và x̄ ∈ S là nghiệm hứu hiệu yếu của bài toán (1.2). Hơn nữa, giả sử f và g khả vi Fréchet tại x̄ và h khả vi liên tục Fréchet tại x̄, trong đó h0 (x̄) là ánh xạ lên. Khi đó, không tồn tại x ∈ int(Ŝ) thỏa mãn: f 0 (x̄)(x − x̄) ∈ −int(CY ), g(x̄) + g 0 (x̄)(x − x̄) ∈ −int(Cz1 ) và h0 (x̄)(x − x̄) = 0z2 Chứng minh Giả sử rằng x ∈ int(Ŝ) thỏa mãn: f 0 (x̄)(x − x̄) ∈ −int(CY ), g(x̄) + g 0 (x̄)(x − x̄) ∈ −int(Cz1 ) và 9 h0 (x̄)(x − x̄) = 0z2 . Khi đó, theo định lý Lyusternik ta nhận được
x − x̄ ∈ T {s ∈ X | h(s) = 0z2 }, x̄ . Bởi vì Ŝ lồi và x ∈ int(Ŝ), ta nhận được x − x̄ ∈ T (S̃, x̄), trong đó S̃ = {s ∈ Ŝ | h(s) = 0z2 } Tiếp theo ta định nghĩa ánh xạ r : X → Y × Z1 như sau r(x) = f (x)−f (x̄) g(x) r(x̄) = 0Y g(x̄)
,với mọi x ∈ X. Rõ ràng ta có
∈ (−CY ) × (−CZ1 ). Do đó, theo mệnh đề (1.2.1) ta có: {h ∈ T (S̃, x̄) | f 0 (x̄)(h) ∈ −int(CY ), g(x̄) + g 0 (x̄)(h) ∈ −int(CZ1 )} ⊂ T ({s ∈ S̃ | f (s) − f (x̄) ∈ −int(CY ), g(s) ∈ −int(CZ1 )}, x̄). Bởi vì: x − x̄ ∈ T (S̃, x̄), f 0 (x̄)(x − x̄) ∈ −int(CY ) và g(x̄) + g 0 (x̄)(x − x̄) ∈ −int(CZ1 ), ta suy ra x − x̄ ∈ T ({s ∈ Ŝ | f (s) − f (x̄) ∈ −int(CY ), g(s) ∈ −int(CZ1 ), h(s) = 0Z1 }, x̄). Nhưng điều này kéo theo x̄ không là nghiệm hữu hạn yếu của bài toán (1.2). 10 2 Định lý được chứng minh. 2.2. Các điều kiện cần Fritz John và Kuhn - Tucker Bây giờ ta trình bày quy tắc nhân tử Lagrange. Điều kiện cần tối ưu này được chứng minh dựa trên định lý 2.1.1 và định lý tách. Định lý 2.2.1 Giả sử bài toán tối ưu (1.2) thỏa mãn giả thiết (1.1) và x̄ ∈ S là nghiệm hữu hiệu yếu của bài toán (1.2). Hơn nữa, f và g khả vi Fréchet tại x̄ , h khả vi liên tục Fréchet tại x̄ và tập ảnh h0 (x̄)(X) đóng. Khi đó, tồn tại các hàm tuyến tính liên tục t ∈ CY ∗ , u ∈ CZ1∗ và v ∈ Z2∗ với (t, u, v) 6= 0Y ∗ ×Z1∗ ×Z2∗ sao cho: (t ◦ f 0 (x̄) + u ◦ g 0 (x̄) + v ◦ h0 (x̄)) ≥ 0, ∀x ∈ Ŝ, (2.1) (u ◦ g)(x̄) = 0. (2.2) và Nếu tồn tại x̂ ∈ int(Ŝ), với g(x̄) + g 0 (x̄)(x̂ − x̄) ∈ −int(CZ1 ), và h0 (x̄)(x̂ − x̄) = 0Z2 và ánh xạ h0 (x̄) lên thì t 6= 0Y ∗ . Chứng minh: Trước hết ta giả sử rằng h0 (x̄) không là ánh xạ lên. Khi đó, áp dụng của định  lý tách 3.18 [2], tồn tại một phiếm hàm tuyến tính liên tục v ∈ Z2∗ \ 0Z2∗ với v ◦ h0 (x̄) = 0X . Nếu ta đặt t = 0∗Y và u = 0Z1∗ , thì ta nhận được ngay các điều kiện (2.1) và (2.2). Trong trường hợp này, phần đầu khẳng định 11 được chỉ ra. Sau đây ta giả sử rằng ánh xạ h0 (x̄) là lên. Trong trường hợp này ta xác định tập hợp sau: M : = {(f 0 (x̄)(x − x̄) + y, g(x̄) + g 0 (x̄)(x − x̄) + z1 , h0 (x̄)(x − x̄)) ∈ Y × Z1 × Z2 | x ∈ int(Ŝ), y ∈ int(CY ), z1 ∈ int(CZ1 )}. Tập này có thể viết dưới dạng: M = (f 0 (x̄), g 0 (x̄), h0 (x̄))(int(Ŝ) − {x̄}) + int(CY ) × ({g(x̄)} + int(CZ1 )) × {0Z2 }. Ánh xạ h0 (x̄)tuyến tính liên tục và lên. Do đó, theo định lý ánh xạ mở h0 (x̄) biến mọi tập con mở của X thành tập con mở của Z2 và tập M bằng phần trong của nó. Tập M là tập lồi bởi vì (f 0 (x̄), g 0 (x̄), h0 (x̄)) là tuyến tính và int(Ŝ) − {x̄} là một tập lồi. Bởi vì x̄ ∈ S là một nghiệm hữu hiệu yếu của bài toán(1.2), theo điều kiện cần đã cho trong định lý 2.1.1 thì phần tử 0Y ×Z1 ×Z2 không thuộc vào M , tức là ta có: M ∩ {0Y ×Z1 ×Z2 } = ∅. Tập M là lồi và mở. Do đó, theo định lý tách Eidelheit (định lý 3.16 [2]) thì phương trình tập trên kéo theo tồn tại một phiếm hàm tuyến tính liên tục t ∈ Y ∗ , u ∈ Z1∗ và v ∈ Z2∗ , với (t, u, v) 6= 0Y ∗ ×Z1∗ ×Z2∗ } và t(f 0 (x̄)(x − x̄) + y) + u(g(x̄) + g 0 (x̄)(x − x̄) + z1 ) + v(h0 ((x̄)(x − x̄)) > 0 ∀x ∈ int(Ŝ), y ∈ int(CY ), z ∈ int(CZ1 ) (2.3) Do tính liên tục của ánh xạ từ bắt đẳng thức (2.3) ta nhận được t(f 0 (x̄)(x − x̄) + y) + u(g(x̄) + g 0 (x̄)(x − x̄) + z1) + v(h0 ((x̄)(x − x̄)) ≥ 0 ∀x ∈ Ŝ, y ∈ CY , z1 ∈ CZ1 . 12 (2.4) Từ bất đẳng thức (2.4) trên ta suy ra với x = x̄, t(y) + u(g(x̄) + z1 ) ≥ 0, ∀y ∈ CY và z1 ∈ CZ1 (2.5) Với z1 = −g(x̄) ∈ CZ1 từ bất đẳng thức (2.5) ta suy ra t(y) ≥ 0, ∀y ∈ CY . Điều này kéo theo t ∈ CY ∗ . Với y = 0Y , từ bất đẳng thức (2.5) ta nhận được: u(g(x̄)) ≥ −u(z1 ) với mọi z1 ∈ Cz1 . (2.6) Từ bất đẳng thức (2.6) ta suy ra ngay u(z1 ) ≥ 0 với mọi z1 ∈ Cz1 . Cho nên u ∈ CZ∗ 1 . Nhưng bất đẳng thức (2.6) kéo theo u(g(x̄)) ≥ 0. Theo giả thiết, ta có g(x̄) ∈ −CZ1 , cho nên ta nhận được u(g(x̄)) ≤ 0. Do đó, bất đẳng thức (2.2) đúng. Để chứng minh bất đẳng thức (2.1) ta chú ý rằng với y = 0Y và z1 = −g(x̄), bất đẳng thức (2.4) dẫn đến: t(f 0 (x̄)(x − x̄)) + u(g 0 (x̄)(x − x̄) + v(h0 (x̄)(x − x̄)) ≥ 0, ∀x ∈ Ŝ, hoặc là (t ◦ f 0 (x̄) + u ◦ g 0 (x̄) + v ◦ h0 (x̄))(x − x̄) ≥ 0, ∀x ∈ Ŝ. Cuối cùng, ta xét trường hợp thêm vào giả thiết tồn tại x̂ ∈ int(Ŝ) với g(x̄) + g 0 (x̄)(x̂ − x̄) ∈ −int(CZ1 ) và h0 (x̄)(x̂ − x̄) = 0Z2 và ánh xạ h0 (x̄) là ánh xạ lên. Trong trường hợp này bất đẳng thức (2.3) kéo theo: t(f 0 (x̄)(x̂ − x̄) + y) > 0, ∀y ∈ int(CY ). 2 Từ đó suy ra t 6= 0Y ∗ . Điều kiện cần tối ưu trong định lý 2.2.1 tổng quát hóa quy tắc nhân tử Lagrange đã biết. Giả thiết thêm trong phần hai của định lý trên đảm bảo 13 t 6= 0Y ∗ được gọi là giả thiết chính quy. Nếu t 6= 0Y ∗ thì điều kiện cần tối ưu cũng được gọi là điều kiện Karush Kuhn - Tucker. Nếu tập Ŝ bằng toàn bộ không gian X thì bất đẳng thức (2.1) trở thành đẳng thức t ◦ f 0 (x̄) + u ◦ g 0 (x̄) + v ◦ h0 (x̄) = 0X ∗ . Quy tắc nhân tử trong định lý 2.2.1 được phát biểu qua hàm Lagrange giá trị thực t ◦ f + u ◦ g + v ◦ h. Định lý 2.2.2 Giả sử bài toán tối ưu (1.2) thỏa mãn giả thiết (1.1). Với x ∈ S) , giả sử f, g và h khả vi Fréschet tại x̄. Khi đó, hai phát biểu sau là tương đương:     Tồn tại các phiếm hàm tuyến tính liên tục        t ∈ CY∗ \{0Y ∗ }, u ∈ CZ∗ và v ∈ Z2∗ có tính chất (2.7)    (t ◦ f 0 (x̄) + u ◦ g 0 (x̄) + v ◦ h0 (x̄))(x − x̄) ≥ 0        với mọi x ∈ Ŝvà(u ◦ g)(x̄) = 0.    Tồn tại các ánh xạ tuyến tính liên tục         L1 : Z1 → Y với L1 (CZ1 ) ⊂ (int(CY ) ∪ {0Y })        và ánh xạ tuyến tính liên tục L2 : Z2 → Y (2.8)    có tính chất        (f 0 (x̄) + L1 ◦ g 0 (x̄) + L2 ◦ h0 (x̄))(x − x̄) ∈ / −int(CY )        với mọi x ∈ Ŝvà(L ◦ g)(x̄) = 0 . 1 Y Chứng minh Trước hết ta giả sử rằng (2.7) đúng. Theo mệnh đề 1.2.2, tồn tại ỹ ∈ int(CY ) với t(ỹ) = 1. 14 Khi đó, ta xác định ánh xạ L1 : Z1 → Y và L2 : Z2 → Y theo công thức: L1 (z1 ) = u(z1 )ỹ, với mọi z1 ∈ Z1 , (2.9) và L2 (z2 ) = v(z2 )ỹ, với mọi z2 ∈ Z2 . Rõ ràng L1 và L2 là ánh xạ tuyến tính liên tục và ta có: L1 (CZ1 ) ⊂ (int(CY ) ∪ {0Y }) Hơn nữa, ta nhận được t ◦ L1 = u và t ◦ L2 = v. Do đó, bất đẳng thức trong phát biểu (2.7) ta có thể viết như sau: (t ◦ (f 0 (x̄) + L1 ◦ g 0 (x̄) + L2 ◦ h0 (x̄)))(x − x̄) ≥ 0, với mọi x ∈ Ŝ. Khi đó, theo kết quả vô hướng hóa của hệ quả 5.29[1] ta có (f 0 (x̄) + L1 ◦ g 0 (x̄) + L2 ◦ h0 (x̄))(x − x̄) ∈ / −int(CY ), với mọi x ∈ Ŝ. Cuối cùng, từ đẳng thức (2.9) ta nhận được. (L1 ◦ g)(x̄) = (u ◦ g)(x̄)ỹ = 0Y . Vì vậy, phát biểu (2.8) đúng. Với phần hai của chứng minh này, ta giả sử phát biểu (2.8) đúng. Khi đó, ta có (f 0 (x̄) + L1 ◦ g 0 (x̄) + L2 ◦ h0 (x̄))(x − x̄) ∈ / −int(CY ) với mọi x ∈ Ŝ. Theo hệ quả 5.29[2] và bổ đề 3.15[2] tồn tại phiếm hàm tuyến tính liên tục t ∈ CY ∗ \ 0Y ∗ có tính chất 15 (t ◦ f 0 (x̄) + t ◦ L1 ◦ g 0 (x̄) + t ◦ L2 ◦ h0 (x̄))(x − x̄) ≥ 0, với mọi x ∈ Ŝ. Nếu ta đặt u := t ◦ L1 và v := t ◦ L2 , ta nhận được (t ◦ f 0 (x̄) + u ◦ g 0 (x̄) + v ◦ h0 (x̄))(x − x̄) ≥ 0, với mọi x ∈ Ŝ, và (u ◦ g)(x̄) = (t ◦ L1 ◦ g)(x̄) = 0. Hơn nữa, với mọi z1 ∈ CZ1 ta suy ra: u(z1 ) = (t ◦ L1 )(z1 ) ≥ 0 kéo theo u ∈ CZ1∗ . 2 Định lý được chứng minh. Rõ ràng từ chứng minh trên các tập ảnh của L1 và L2 là các không gian con một chiều của Y. Với bài toán tối ưu không có ràng buộc g, h quy tắc nhân tử cũng có thể sử dụng với g và h là ánh xạ không. Nhưng trong trường hợp này sẽ dẫn đến một kết quả tổng quát hơn. Định nghĩa 2.2.1 Giả sử X và Y là các không gian tuyến tính thực, S là tập con khác rỗng của X, T là tập con khác rỗng của Y. Giả sử f : S −→ Y và x̄ ∈ S. Ánh xạ f 0 (x̄) : S − {x̄} −→ Y được gọi là biến phân theo phương (directional variation) của f tại x̃ theo T nếu như hễ có một phần tử x ∈ S, x 6= x̄ và f 0 (x̄)(x − x̄) ∈ T thì ∃λ̄ > 0 với
x̄ + λ(x − x̄) ∈ S ∀λ ∈ (0, λ̄] và

1 f (x̃ + λ(x − x̄)) − f (x̃) ∈ T ∀λ ∈ (0, λ̄] . λn 16 Định lý 2.2.3 Giả sử S là tập con khác rỗng của không gian tuyến tính thực X và Y là không gian tuyến tính có thứ tự bộ phận với nón thứ tự CY 6= Y có phần trong đại số khác rỗng. Giả sử f : S → Y. Nếu x̄ ∈ S là cực tiểu yếu của bài toán tối ưu min f (x) x∈S (2.10) và nếu F có biến phân theo phương tại x theo −cor(CY ) thì f 0 (x̄)(x − x̄) ∈ / −cor(CY ), với mọi x ∈ S. (2.11) Chứng minh Nếu điều kiện (2.11) không đúng, tức là với x ∈ S nào đó, f 0 (x̄)(x − x̄) ∈ / −cor(CY ) Khi đó, theo định nghĩa (2.2.1) tồn tại λ̄ > 0 với x̂ := x̄ + λ̄(x − x̄) ∈ S, và 1 λ (f (x̂) − f (x̄)) ∈ −cor(CY ). Do đó, ta có f (x̂) ∈ ({f (x̄)} − cor(CY )) ∩ f (S). Điều này kéo theo x̄ không là cực tiểu yếu của bài toán tối ưu (2.10) 2 Bằng lý luận như trong định lý 2.2.2, điều kiện tối ưu (2.11) dạng véc tơ tương dương với một bất đẳng thức nếu biến phân theo phương của f tại x̄ là convexlike. Bổ đề 2.2.1 Giả sử S là tập con khác rỗng của không gian tuyến tính thực X và 17 Y là không gian tuyến tính có thứ tự bộ phận với nón thứ tự CY 6= Y có phần trong đại số khác rỗng. Giả sử f : S → Y là ánh xạ mà nó có biến phân theo phương tại điểm x̄ ∈ S nào đó theo -cor(CY ). Nếu tồn tại t ∈ CY 0 \ {0Y 0 } sao cho (t ◦ f 0 (x̄))(x − x̄) ≥ 0, ∀x ∈ S, (2.12) thì điều kiện (2.11) đúng. Nếu ánh xạ f 0 (x̄) là convexlike thì điều kiện (2.11) kéo theo sự tồn tại của phiếm hàm tuyến tính t ∈ CY 0 \ {0Y 0 } thỏa mãn (2.12) Chứng minh Nếu ta giả sử rằng tồn tại t ∈ CY 0 \ {0Y } thỏa mãn (2.12) thì theo định lý 5.28[2] ta có ngay điều kiện (2.11). Tiếp theo, ta giả sử (2.11) đúng theo bổ đề 4.13[2] ta nhận được:
(f 0 (x̄)(S − {x̄})) + CY ∩(−cor(CY )) = ∅. Bởi vì giả sử f 0 (x̄) là convexlike theo định lý 5.13[2] tồn tại phiếm hàm tuyến tính t ∈ CY0 \ {00Y } sao cho (2.12) thỏa mãn. 2 Bây giờ ta quay lại quy tắc nhân tử trong định lý 2.2.1 và chúng ta đặc biệt hóa kết quả này cho bài toán tối ưu đa mục tiêu (1.2). Định lý 2.2.4 Giả sử f : Rn → Rm , g : Rn → Rk và h : Rn → Rp là các hàm véc tơ và tập ràng buộc S được cho bởi S := {x ∈ Rn |gi (x) ≤ 0, với mọi i ∈ {1, ..., k}và hi (x) = 0, với mọi i ∈ {1, ..., p}}. Giả sử x̄ ∈ S là nghiệm hữu hiệu yếu của bài toán tối ưu đa mục tiêu min f (x), x∈S 18