Luận văn Về nguyên lý nhân tử Lagrange

ái Nguyên 16 Hình 3. với gradient ∇h. Như vậy, tại (x∗,y∗) thì hai gradient ∇ f và ∇h phải cộng tuyến với nhau. Đây chính là những gì mà phương trình (1.4) đã thể hiện. Cho c∗ là đường mức mà tại đó hàm f đạt cực tiểu địa phương tại (x∗,y∗), rõ ràng hai đường cong f (x,y) = c∗ và h(x,y) = 0 tiếp xúc nhau tại (x∗,y∗). Giả sử ta tìm được tập S các điểm thỏa mãn hệ phương trình{ h(x,y) = 0 ∇ f +λ ∇h = 0. (1.5) Khi đó, tập S chứa các điểm cực trị của hàm f đối với ràng buộc h(x,y) = 0. Hệ phương trình trên là hệ phi tuyến với các biến số x,y,λ và ta có thể giải quyết bằng nhiều phương pháp. Hàm Lagrange của bài toán (P2) có dạng L(x,y,λ ) = f (x,y)+λ h(x,y). ∇L=   ∂ f ∂x +λ ∂h ∂x∂ f ∂y +λ ∂h ∂y h(x,y)   T = (∇ f +λ ∇h, h). Suy ra ∇L= 0 do hệ phương trình phi tuyến (1.5). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 17 Giá trị λ gọi là nhân tử Lagrange. Phương pháp xây dựng hàm Lagrange và thiết lập để các gradient của nó bằng không, gọi là phương pháp nhân tử Lagrange. Ví Dụ 1.2. Tìm các giá trị cực trị của hàm f (x,y) = xy với ràng buộc h(x,y) = x 2 8 + y2 2 −1 = 0. Giải Đầu tiên, ta xây dựng hàm Lagrange và tìm gradient của nó. L(x,y,λ ) = xy+λ (x 2 8 + y2 2 −1). ∇L(x,y,λ ) =   y+ λx 4 x+λ y x2 8 + y2 2 −1  = 0. Từ đó dẫn đến ba phương trình y+ λ x 4 = 0. (1.6) x+λ y = 0. (1.7) x2+4y2 = 8. (1.8) Kết hợp (1.6) và (1.7) ta có λ 2 = 4 suy ra λ =± 2. Do đó x =± 2y. Thế phương trình này vào (1.8), ta được y =± 1 suy ra x =± 2. Vì vậy, có bốn điểm cực trị của hàm f thỏa mãn ràng buộc h là (2,1); (−2,1); (2,−1); (−2,−1). Giá trị cực đại đạt được tại hai điểm đầu tiên, trong khi giá trị cực tiểu đạt được ở hai điểm cuối. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 18 Hình 4. Về mặt đồ thị, ràng buộc h là hình elip. Đường mức của hàm f là hy- perbolas xy = c, với |c| tăng khi đường cong di chuyển ra xa gốc tọa độ. 1.2.2. Trường hợp hữu hạn chiều. Bây giờ, ta mở rộng bài toán (P2) tới trường hợp với nhiều ràng buộc. Cho h = (h1, . . . ,hm)T là một hàm số từ Rn vào Rm, trong đó m ≤ n. Xét bài toán tối ưu (P3) { min f (x) h(x) = 0. Mỗi ràng buộc h j(x) = 0, ( j = 1, . . . ,m) gọi là một siêu diện trong không gian Rn. Nếu h j(x) ∈C1 và chính quy thì siêu diện gọi là trơn. Chúng ta có một số khái niệm sau: • Giao của tất cả các siêu diện được gọi là mặt ràng buộc, kí hiệu là S. • Một đường cong trên S là tập các điểm x(t) ∈ S, với a ≤ t ≤ b. • Đường cong gọi là khả vi nếu tồn tại dxdt , kí hiệu x′ := dxdt . • Đường cong gọi là đi qua điểm x nếu x = x(t) với a ≤ t ≤ b. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 19 • Không gian tiếp xúc tại điểm x của siêu diện S là không gian con của Rn, tạo bởi tập các tiếp tuyến dxdt (t) của tất cả các đường cong x(t) trên S thỏa mãn x = x(t). Từ các khái niệm trên, ta có thể phát biểu khái niệm điểm chính quy như sau: “Một điểm x thỏa mãn h(x) = 0, gọi là điểm chính quy nếu các vectơ gradient ∇h1(x), . . . ,∇hm(x) là độc lập tuyến tính”. Định lý sau đây cho phép ta xác định không gian tiếp xúc của mặt ràng buộc. Định Lý 1.5. Tại một điểm chính quy x của mặt S được xác định bởi h(x) = 0, thì không gian tiếp xúc tại x là M = {y| ∇h(x)y = 0}. trong đó ma trận ∇h =   ∇h1... ∇hm   . Các hàng của ma trận ∇h(x) là các vectơ gradient ∇h j(x),( j = 1, . . . ,m). Chứng minh Cho T là không gian tiếp xúc tại x. Rõ ràng T ⊂ M với x là điểm chính quy. Nếu một đường cong bất kì x(t) đi qua điểm x tại t = t, và có đạo hàm x′(t) thỏa mãn ∇h(x)x′(t) 6= 0 thì đường cong đó không nằm trên S. Để chứng minh M ⊂ T , ta phải chứng tỏ rằng, nếu y ∈ M thì có một đường cong trên S qua x với đạo hàm tương ứng là y. Để xác định đường cong như vậy, ta xét hệ phương trình h(x+ ty+∇h(x)T u(t)) = 0. (1.9) trong đó t cố định, và u(t) ∈ Rm là ẩn. Đây là một hệ phi tuyến với m phương trình và m ẩn, được biểu diễn theo tham số t. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 20 Tại t = 0 có nghiệm u(0) = 0. Ma trận Jacobian của hệ đối với u tại t = 0 là ma trận cấp m×m ∇h(x)∇h(x)T . không suy biến. Do đó, theo định lý hàm ẩn thì có nghiệm u(t) khả vi liên tục trên −a ≤ t ≤ a. Đường cong x(t) = x+ ty+∇h(x)T u(t) theo cách xác định như vậy là một đường cong trên S. Lấy vi phân của (1.9) đối với t tại t = 0, ta có 0 = ddt h(x(t)) ∣∣∣ t=0 = ∇h(x)y+∇h(x)∇h(x)T u′(0). Theo định nghĩa của y, ta có ∇h(x)y= 0. Do đó, khi ∇h(x)∇h(x)T là không suy biến, ta suy ra u′(0) = 0. Như vậy x′(0) = y+∇h(x)T u′(0) = y.  Định lý sau nêu lên mối quan hệ giữa gradient của hàm mục tiêu với vectơ nằm trên không gian tiếp xúc. Định Lý 1.6. Cho x là cực trị của hàm f , và là điểm chính quy của ràng buộc h(x) = 0. Khi đó, với ∀y ∈ Rn thỏa mãn ∇h(x)y = 0, ta có ∇ f (x)y = 0. Chứng minh. Giả sử mặt ràng buộc h(x) = 0 xác định một siêu diện S. x(t) là một đường cong bất kì trên S, và đi qua điểm x. Gọi y là một vectơ bất kì trên không gian tiếp xúc tại x của S. Khi đó: x(0) = x, x′(0) = y, và h(x(t)) = 0 với ∀t ∈ [−a,a] , a > 0. Vì x là điểm chính quy nên không gian tiếp xúc là M = {y|∇h(x)y = 0}. Do đó, nếu x là cực trị địa phương thì d dt f (x(t)) ∣∣∣ t=0 = 0 hay ∇ f (x)y = 0.  Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 21 Định Lý 1.7. (Điều Kiện Cần Cấp Một) Cho x là cực trị địa phương của bài toán (P3). Giả sử rằng x là điểm chính quy của các ràng buộc h j(x) = 0, j = 1, . . . ,m. Khi đó, tồn tại λ ∈ Rm sao cho ∇ f (x)+λ T ∇h(x) = 0. Chứng minh. Từ định lý (1.6) ta suy ra rằng, giá trị của bài toán{ max ∇ f (x)y ∇h(x)y = 0. là bằng không. Theo định lý đối ngẫu của quy hoạch tuyến tính thì bài toán đối ngẫu là giải được. Từ đó, tồn tại λ ∈ Rm sao cho ∇ f (x)+λ T ∇h(x) = 0.  Nhận Xét 1.3. Điều kiện cần cấp một cùng với ràng buộc h(x) = 0, cho ta hệ gồm (m+n) phương trình với (m+n) ẩn x và λ . Do đó, ta có thể xác định được nghiệm duy nhất của hệ phương trình. Ví Dụ 1.3. Chúng ta xây dựng một khối hộp có thể tích lớn nhất từ bìa cứng, khi cho trước một diện tích bìa cố định. Giải Giả sử kích thước của khối hộp cần dựng là x,y,z. Bài toán có thể biểu thị như sau (P4) { max xyz xy+ yz+ zx = c2 . (1.10) trong đó c > 0 là diện tích cho trước của tấm bìa. Hàm Lagrange của bài toán L(x,y,z,λ ) = xyz+λ (xy+ yz+ zx− c 2 ). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 22 Từ điều kiện cần cấp một ta thấy rằng yz+λ (y+z)= 0. (1.11) xz+λ (x+z)= 0. (1.12) xy+λ (x+y)= 0. (1.13) Do đó (xy+ yz+ xz)+2λ (x+ y+ z) = 0. Từ ràng buộc (1.10) ta có c 2 +2λ (x+ y+ z) = 0. Suy ra λ 6= 0. Chú ý rằng x,y,z không thể nhận giá trị bằng không (vì nếu một trong ba số bằng không, thì do (1.11),(1.12),(1.13) ta được những số khác cũng bằng không). Để giải hệ gồm ba phương trình (1.11),(1.12),(1.13), ta nhân (1.11) với x và (1.12) với y, sau đó trừ hai phương trình cho nhau ta được λ (x− y)z = 0. Tương tự cho (1.12) và (1.13) ta được λ (y− z)x = 0. Do các biến không thể bằng không nên x = y = z = √ c 6 và λ = −1 2 . Như vậy, hàm Lagrange có điểm dừng tại x = y = z = √ c 6 và λ = −12 . Tuy nhiên, kết quả ta tìm được ở trong ví dụ (1.3) chỉ là điều kiện cần cấp một, có nghĩa rằng, ta chưa biết liệu tại điểm này khối hộp đã cho đạt thể tích lớn nhất hay nhỏ nhất. Muốn thế, ta cần xét tới điều kiện cấp hai sau. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 23 Định Lý 1.8. (Điều kiện cần cấp hai). Giả sử rằng x là cực tiểu địa phương của hàm f thỏa mãn h(x) = 0, và x là một điểm chính quy của các ràng buộc này. Khi đó, có một số λ ∈ Rm sao cho ∇ f (x)+λ T ∇h(x) = 0. Ma trận HL(x) = H f (x)+ m ∑ i=1 λiHhi(x). là nửa xác định dương trên không gian tiếp xúc M = {y|∇h(x)y = 0}, tức là yT HL(x)y ≥ 0, ∀y ∈ M. Chứng minh. Với mọi đường cong x(t) khả vi cấp hai trên mặt ràng buộc S, và đi qua x thỏa mãn x(0) = x, thì ta có d2 dt2 f (x(t)) ∣∣∣ t=0 ≥ 0. (1.14) Mặt khác d2 dt2 f (x(t)) ∣∣∣ t=0 = x′(0)T H f (x) x′(0)+∇ f (x)x′′(0). (1.15) Lấy vi phân cấp hai của phương trình λ T h(x(t)) = 0, ta có x′(0)T λ T Hh(x) x′(0)+λ T ∇h(x) x′′(0) = 0. (1.16) Cộng (1.16) vào (1.15) và từ (1.14) ta suy ra d2 dt2 f (x(t)) ∣∣∣ t=0 = x′(0)T HL(x) x′(0)≥ 0. Do x′(0) ∈ M nên ta suy ra điều cần chứng minh.  Chú ý rằng, khi sử dụng điều kiện cần ta chỉ xác định được điểm mà tại đó bài toán đạt cực trị. Do đó để xác định đó là cực đại hay cực tiểu ta cần tới điều kiện đủ cấp hai sau. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 24 Định Lý 1.9. (Điều kiện đủ cấp hai). Giả sử có điểm x thỏa mãn h(x) = 0 và số λ ∈ Rm sao cho ∇ f (x)+λ T ∇h(x) = 0. (1.17) Cũng giả sử rằng, ma trận HL(x) = H f (x)+ m ∑ i=1 λiHhi(x). là xác định dương trên không gian tiếp xúc M = {y| ∇h(x)y = 0}, (tức là: ∀y ∈ M, y 6= 0 thì yT HL(x) y > 0) . Khi đó, x là cực tiểu địa phương ngặt của hàm f thỏa mãn h(x) = 0. Chứng minh. Nếu x không phải là cực tiểu địa phương ngặt, thì tồn tại dãy các điểm chấp nhận được {yk} hội tụ tới x thỏa mãn f (yk)≤ f (x), ∀k. Biểu diễn yk dưới dạng yk = x+δksk. trong đó sk ∈ Rn, |sk|= 1 và δk > 0, ∀k. Rõ ràng δk −→ 0, và dãy {sk} bị chặn, nên phải có một dãy con hội tụ tới s. Để tiện cho việc kí hiệu, chúng ta giả sử rằng, dãy {sk} hội tụ tới s. Mặt khác h(yk)−h(x)= 0. (1.18) chia hai vế của phương trình (1.18) cho δk và cho k −→ ∞, ta được ∇h(x)s = 0. Theo định lý Taylor, với mỗi j ta có 0 = h j(yk) = h j(x)+δk∇h j(x)sk + δ 2k 2 sTk ∇2h j(η j)sk. (1.19) Và 0 ≥ f (yk)− f (x) = δk∇ f (x)sk + δ 2k 2 sTk ∇2 f (η0)sk. (1.20) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 25 trong đó η j là một điểm trên đoạn thẳng nối x và yk. Nhân (1.19) với λ j và cộng vào với (1.20), kết hợp với (1.17), ta được 0 ≥ δ 2 k 2 sTk { ∇2 f (η0)+ m ∑ i=1 λi∇2hi(ηi) } sk. Cho k −→ ∞ ta gặp mâu thuẫn.  Chú ý rằng, với các giả thiết như trong định lý thì: khi ma trận HL(x) là xác định âm ta có x là cực đại địa phương ngặt của hàm f thỏa mãn h(x) = 0. Ví Dụ 1.4. Giải bài toán sau max{x1x2 + x2x3+ x3x1 : x1 + x2+ x3 = 3} Giải Trước tiên, ta xây dựng hàm Lagrange cho bài toán L(x1,x2,x3,λ ) = x1x2+ x2x3 + x3x1+λ (x1+ x2+ x3−3) Từ điều kiện cần thứ nhất, ta có ∇L(x1,x2,x3,λ ) = ( ∂L ∂x1 , ∂L ∂x2 , ∂L ∂x3 ) = 0. Suy ra x2+ x3+λ = 0 x1+ x3+λ = 0 x1+ x2+λ = 0 Chúng ta giải ba phương trình này cùng với ràng buộc của bài toán, ta được x1 = x2 = x3 = 1 và λ =−2. Do đó x =   11 1   Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 26 Bây giờ, ta cần sử dụng đến điều kiện đủ cấp hai để xác định xem bài toán đạt cực đại hay cực tiểu tại x. Ta có: ∂ 2L ∂x21 = ∂ 2L ∂x22 = ∂ 2L ∂x23 = 0, ∂ 2L ∂x1x2 = ∂ 2L ∂x2x1 = 1, ∂ 2L ∂x1x3 = ∂ 2L ∂x3x1 = 1, ∂ 2L ∂x2x3 = ∂ 2L ∂x3x2 = 1. Như vậy, ta xác định được ma trận HL(x) = H f (x)+λ Hh(x) =   0 1 11 0 1 1 1 0   Mặt khác ∇h = ( ∂h ∂x1 , ∂h ∂x2 , ∂h ∂x3 ) = (1,1,1) Do đó, theo định lý (1.5) không gian tiếp xúc với mặt rằng buộc tại x là M= {y|y1 + y2+ y3 = 0}, với y = (y1,y2,y3). Tuy nhiên ta lưu ý là yT HLy = (y1,y2,y3)   0 1 11 0 1 1 1 0     y1y2 y3   =−(y21 + y22+ y23)< 0, ∀y 6= 0. Do đó, HL là xác định âm trên M và nghiệm ta tìm được là cực đại địa phương. Ví Dụ 1.5. Giải bài toán quy hoạch sau min{ax21+bx22 : x1+ x2−1 = 0} trong đó a > 0, b > 0. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 27 Giải Trước hết ta xây dựng hàm Lagrange L(x1,x2,λ ) = (ax21 +bx22)+λ (x1+ x2−1) Từ điều kiện cần thứ nhất, ta có ∂L ∂x1 = 2ax1+λ = 0 ∂L ∂x2 = 2bx2+λ = 0 Giải hai phương trình trên cùng với ràng buộc của bài toán, ta được x1 = b a+b, x2 = a a+b, λ =− 2a a+b Nhớ rằng nếu chỉ dựa vào điều kiện cần cấp một thì ta chưa thể biết được giá trị hàm mục tiêu tại điểm ( b a+b, a a+b) là lớn nhất hay nhỏ nhất khi có ràng buộc. Từ điều kiện đủ cấp hai, ta có ∂ 2L ∂x21 = 2a, ∂ 2L ∂x22 = 2b, ∂ 2L ∂x1∂x2 = ∂ 2L ∂x2∂x1 = 0. Do đó HL(x) = H f (x)+λ Hh(x) = ( 2a 0 0 2b ) Trên không gian tiếp xúc M = {y|y1+ y2 = 0} với y = (y1,y2), ta xét yT HLy = (y1,y2) ( 2a 0 0 2b )( y1 y2 ) = 2ay21+2by22 > 0, ∀y 6= 0. Như vậy, HL xác định dương trên M. Do đó, nghiệm ta tìm được là cực tiểu địa phương. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 28 1.2.3. Trường hợp tổng quát. Trở lại bài toán (P1), những kết quả sau là tổng quát từ những trường hợp cụ thể, và được thể hiện thông qua định lý (1.10) và hai hệ quả quan trọng sau. Định Lý 1.10. (Nguyên Lý Nhân Tử Lagrange) Cho hàm f và ánh xạ F khả vi Frechet tại x thỏa mãn F(x) = 0, với các đạo hàm Frechet tại f ′(x) và F ′(x). Ảnh của không gian X qua ánh xạ x −→ F ′(x)x là đóng. Khi đó, nếu x là cực tiểu địa phương của bài toán (P1) thì tồn tại các nhân tử Lagrange λ0 và y∗ không đồng thời bằng không sao cho L′x(x,λ0,y∗) = λ0 f ′(x)+F ′∗(x)y∗ = 0 (1.21) Hơn nữa, nếu F khả vi liên tục theo nghĩa Frechet tại x và F ′(x)X = Y (F là chính quy), thì λ0 6= 0 và có thể xem như λ0 = 1. Chứng Minh Theo giả thiết, F ′(x)X là không gian con đóng của không gian Y . Có thể xảy ra một trong hai trường hợp: F ′(x)X = Y hoặc F ′(x)X $ Y . a) Trường hợp F ′(x)X = Y . Theo định lý Ljusternik, không gian tiếp xúc với tập M = {x ∈ X : F(x) = 0} tại x trùng với Ker F ′(x). Do đó, nếu v ∈ Ker F ′(x), thì −v ∈ Ker F ′(x), và tồn tại số ε > 0, ánh xạ r : [−ε,ε] −→ X sao cho x(t,v) = x+ tv+ r(t) ∈ M (∀ t ∈ [−ε,ε]) trong đó ||r(t)||t −→ 0 khi t −→ 0. Suy ra F ( x (t,v) ) = 0 ∀ t ∈ [−ε,ε] Đặt ϕ(t) = f (x (t,v)). Khi đó, ϕ(t) đạt cực tiểu địa phương tại t = 0. Do đó ϕ ′(0) = 〈 f ′(x),v〉 (∀ v ∈ Ker F ′(x)). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 29 Vì thế f ′(x) ∈ (Ker F ′(x))⊥. Do F ′(x) là toán tử tuyến tính liên tục từ không gian Banach X lên không gian Banach Y , nên theo bổ đề (1.1) ta có (Ker F ′(x))⊥ = Im F ′∗(x) Vì vậy f ′(x) ∈ Im F ′∗(x), tức là, tồn tại y∗ ∈Y ∗ sao cho f ′(x) =−F ′∗(x)y∗. Điều này có nghĩa là f ′(x)+F ′∗(x)y∗ = 0. Vậy, ta có L′x(x,λ0,y∗) = λ0 f ′(x)+F ′∗(x)y∗ = 0 với λ0 = 1. b) Trường hợp F ′(x)X $ Y . Khi đó, tồn tại y0 ∈ Y\F ′(x)X . Do Y\F ′(x)X là tập mở, nên tồn tại lân cận mở V của y0 sao cho V ∩F ′(x)X = /0. Theo định lý Hahn-Banach và hệ quả (1.1) thì ∃y∗ ∈ Y ∗, y∗ 6= 0 sao cho 〈y∗,y〉> 0 (∀y ∈V ). 〈y∗,z〉= 0 (∀z ∈ F ′(x)X). Do đó, ta có 〈y∗,F ′(x)x〉= 〈F ′∗(x)y∗,x〉= 0 (∀x ∈ X). Suy ra F ′∗(x)y∗ = 0. Chọn λ0 = 1 thì L′x(x,0,y∗) = F ′∗(x)y∗ = 0.  Nhận Xét 1.4. • Trong trường hợp F ′(x)X =Y ta luôn có λ0 6= 0. Thật vậy, nếu λ0 = 0 thì ta có 〈y∗,F ′(x)x〉= 〈F ′∗(x)y∗,x〉= 0 (∀x ∈ X) Từ các điều kiện chính quy, suy ra y∗ = 0. Điều này mâu thuẫn với điều kiện của các nhân tử Lagrange là không đồng thời bằng không. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 30 • Phương trình (1.21) được gọi là phương trình Euler-Lagrange của bài toán (P1). Từ phương trình này ta thấy, x là điểm dừng của hàm Lagrange. Chúng ta có hai trường hợp đặc biệt của bài toán (P1) 1) Trường hợp 1: Cho X ,Y là các không gian hữu hạn chiều, khi đó bài toán có dạng (P5) { f0(x)−→ in f f1(x) = 0, . . . , fn(x) = 0 (1.22) trong đó, các nhân tử Lagrange là các số λ0, . . . ,λn sao cho hàm Lagrange có dạng L(x,λ0, . . . ,λn) = n ∑ i=0 λi fi(x). Hệ Quả 1.2. Cho các hàm số f0, . . . , fn thuộc lớp C1 tại x thỏa mãn điều kiện (1.22). Khi đó, nếu x là cực tiểu địa phương của bài toán (P5) thì tồn tại các số λ0, . . . ,λn không đồng thời bằng không sao cho λ0 f ′0(x)+ · · ·+λn f ′n(x) = 0. Hơn nữa, nếu các hàm f ′1(x), . . . , f ′n(x) là độc lập tuyến tính thì λ0 6= 0, và có thể coi λ0 = 1. Nhận Xét 1.5. Chứng minh của hệ quả (1.2) được suy ra trực tiếp từ định lý (1.10), và như đã nêu trong định lý (1.2) thì điều kiện chính quy của ánh xạ x −→ ( f1(x), . . . , fn(x)) có nghĩa đơn giản là các hàm f ′1, . . . , f ′n độc lập tuyến tính. 2) Trường hợp thứ hai phát sinh khi ánh xạ F trong bài toán (P1) có thể phân tích thành một ánh xạ chính quy vào một không gian Banach và một ánh xạ vào Rn. Khi đó, bài toán có dạng (P6)   f0(x)−→ in f F(x) = 0 (1.23) f1(x) = 0, . . . , fn(x) = 0 (1.24) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 31 Hệ Quả 1.3. Cho các hàm số f0, . . . , fn và ánh xạ F thuộc lớp C1 tại x thỏa mãn đẳng thức (1.23) và (1.24). Giả thiết rằng ánh xạ F là chính quy tại điểm x. Nếu x là cực tiểu địa phương của bài toán (P6) thì tồn tại các số λ0, . . . ,λn và một vectơ y∗ không đồng thời bằng không sao cho λ0 f ′0(x)+ . . .+λn f ′n(x)+F ′∗(x)y∗ = 0. Chứng minh của hệ quả (1.3) cũng được suy ra trực tiếp từ định lý (1.10). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 32 CHƯƠNG II: NGUYÊN LÝ NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU LỒI. Chương này dành để trình bày các kết quả về điều kiện cần đủ của bài toán tối ưu lồi, thông qua việc sử dụng các nhân tử Lagrange và khái niệm về dưới vi phân. Các kết quả của chương này là của A. D. Ioffe [1], Đỗ Văn Lưu và Phan Huy Khải [4]. 2.1. Một số kiến thức cơ bản của giải tích lồi Trong mục này chúng ta sẽ nhắc lại một số kiến thức cơ bản của giải tích lồi, đặc biệt là định lý Moreau-Rockafellar về phép tính dưới vi phân của tổng các hàm lồi. 2.1.1. Tập lồi. Định Nghĩa 2.1. Tập A ⊂ X được gọi là lồi nếu ∀x1,x2 ∈ A, ∀λ ∈ R : 0 ≤ λ ≤ 1 thì λ x1+(1−λ )x2 ∈ A. Định Nghĩa 2.2. Giả sử A ⊂ X , x1,x2 ∈ A. Đoạn thẳng nối hai điểm x1,x2 được định nghĩa như sau [x1,x2] = {x ∈ A : x = λ x1+(1−λ )x2, 0 ≤ λ ≤ 1}. Định Nghĩa 2.3. Cho A ⊂ X , x1,x2 ∈ A. Khi đó, đường thẳng đi qua x1,x2 là tập các điểm x = λ x1+(1−λ )x2, λ ∈ R. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 33 Ví Dụ 2.1. 1. Các nửa không gian trong R2 và R3 là các tập lồi. 2. Các tam giác, hình tròn trong mặt phẳng, hình cầu đơn vị trong không gian Banach là các tập lồi. Định Nghĩa 2.4. Tập K ⊂ X được gọi là nón có đỉnh tại 0 nếu: ∀x ∈ K, ∀λ > 0 thì λ x ∈ K. K được gọi là nón có đỉnh tại x0 nếu K − x0 là nón có đỉnh tại 0. Định Nghĩa 2.5. Nón K có đỉnh tại 0 được gọi là nón lồi, nếu K là một tập lồi. Điều này có nghĩa là ∀x,y ∈ K, ∀λ ,µ > 0 thì λ x+µy ∈ K. Một ví dụ quan trọng về nón lồi trong Rn là nón orthant dương Rn+ = {(x1,x2, . . . ,xn) : xi ≥ 0, i = 1,2, . . . ,n}. Định Nghĩa 2.6. Giả sử X là một không gian lồi địa phương, X∗ là không gian các phiếm hàm tuyến tính liên tục trên X . Vectơ x∗ ∈ X∗ được gọi là pháp tuyến của tập lồi A tại x nếu 〈x∗,x− x〉 ≤ 0, ∀x ∈ A. Tập tất cả các vectơ pháp tuyến của tập lồi A tại x ∈ A được gọi là nón pháp tuyến của A tại x. Kí hiệu là N(x | A). Như vậy N(x | A) = {x∗ ∈ X∗ : 〈x∗,x− x〉 ≤ 0, ∀x ∈ A}. 2.1.2. Hàm lồi. Giả sử X là không gian lồi địa phương, D ⊂ X và f : D −→ R= R∪{±∞}. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 34 Định nghĩa 2.7. Trên đồ thị của hàm f , kí hiệu là epi f , được định nghĩa như sau epi f = {(x,r) ∈ D×R : f (x)≤ r}. Định Nghĩa 2.8. Miền hữu hiệu của hàm f , kí hiệu là dom f , được định nghĩa bởi dom f = {x ∈ D : f (x)<+∞}. Định Nghĩa 2.9. Hàm f được gọi là chính thường, nếu dom f 6= /0 và f (x)>−∞ (∀x ∈ D). Hàm không chính thường được gọi là hàm phi chính. Định Nghĩa 2.10. Giả sử D ⊂ X là tập lồi. Khi đó, hàm f được gọi là • Hàm lồi nếu f (λ x1 +(1−λ )x2)≤ λ f (x1)+(1−λ ) f (x2) với ∀x1,x2 ∈ D và 0 ≤ λ ≤ 1. • Hàm Lõm nếu − f là hàm lồi. • Hàm affine nếu f vừa là hàm lõm vừa là hàm lồi. Ví Dụ 2.2. Một số ví dụ về hàm lồi. 1. Hàm affine f (x) = 〈x∗,x〉+α (x∗ ∈ X∗,α ∈ R) . là hàm lồi trên X , trong đó X∗ là không gian các phiếm hàm tuyến tính liên tục trên X . 2. Chuẩn Euclide là một hàm lồi trên Rn ||x||= 〈x,x〉12 = (x21 + . . .+ x2n) 1 2 . trong đó x = (x1, . . . ,xn) ∈ Rn. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 35 3. Hàm Chỉ δ (x|A) của tập lồi A ⊂ X là hàm lồi δ (x|A) = { 0 nếu x ∈ A +∞ nếu x /∈ A. 4. Hàm Tựa S(x|A) của tập lồi A ∈ X∗ là một hàm lồi. S(x|A) = sup x∗∈A 〈x∗,x〉. 2.1.3. Tập Affine. Định Nghĩa 2.11. Tập A ⊂ Rn được gọi là tập affine, nếu (1−λ )x+λ y ∈ A, (∀x,y ∈ A, ∀λ ∈ R). Nhận xét 2.1. Nếu A là tập affine, thì với a ∈ Rn A+a = {x+a : x ∈ A}. là tập affine. Mệnh Đề 2.1. Tập M ⊂ Rn là một không gian con khi và chỉ khi M là tập affine chứa không. Định Nghĩa 2.12. Tập affine A được gọi là song song với tập affine M nếu tồn tại a ∈ Rn sao cho A = M+a. Kí hiệu A//M. Mệnh Đề 2.2. Mỗi tập affine A 6= /0 song song với một không gian con duy nhất L được xác định bởi L = A−A = {x− y : x ∈ A,y ∈ A}. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 36 2.1.4. Các định lý tách. Giả sử X là không gian lồi địa phương, X∗ là không gian liên hợp của X , tức là không gian các phiếm hàm tuyến tính liên tục trên X . Định Nghĩa 2.13. Tập M ⊂ X thỏa mãn: bất cứ đường thẳng nào đi qua hai điểm của M cũng nằm trọn trong M được gọi là một đa tạp tuyến tính trong X . Nhận Xét 2.2. Khái niệm đa tạp tuyến tính chính là khái niệm tập affine trong không gian hữu hạn chiều. Lấy x∗ ∈ X∗, x∗ 6= 0, β ∈ R và kí hiệu H(x∗,β ) = {x ∈ X : 〈x∗,x〉= β}. H+(x∗,β ) = {x ∈ X : 〈x∗,x〉 ≤ β}. H−(x∗,β ) = {x ∈ X : 〈x∗,x〉 ≥ β}. Định Nghĩa 2.14. Với 0 6= x∗ ∈ X∗, β ∈ R thì • Tập H(x∗,β ) được gọi là một siêu phẳng trong X . • Tập H+(x∗,β ) và H−(x∗,β ) được gọi là các nửa không gian sinh bởi siêu phẳng H(x∗,β ). Định Nghĩa 2.15. Cho các tập hợp A,B ⊂ X . Ta nói phiếm hàm tuyến tính liên tục x∗ 6= 0 tách A và B, nếu tồn tại số α sao cho 〈x∗,y〉 ≤ α ≤ 〈x∗,x〉 (∀x ∈ A,∀y ∈ B). (2.1) Nếu (2.1) có dạng 〈x∗,y < α < 〈x∗,x〉 (∀x ∈ A,∀y ∈ B). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 37 thì ta nói x∗ tách ngặt A và B. Siêu phẳng đóng H(x∗,α) = {x ∈ X : 〈x∗,x〉= α}. được gọi là siêu phẳng tách A và B. Các tập A và B được gọi là tách được. Định Lý 2.1. (Định Lí Tách Thứ Nhất). Giả Sử A và B là hai tập lồi, khác rỗng trong không gian lồi địa phương X, A∩B = /0, int A 6= /0 (trong đó kí hiệu intA là phần trong của A). Khi đó, tồn tại x∗ ∈ X∗,x∗ 6= 0 tách A và B. Tức là, tồn tại x∗ ∈ X∗ sao cho 〈x∗,x〉 ≥ 〈x∗,y〉 với (∀x ∈ A,∀y ∈ B). Định Lý 2.2. (Định Lý Tách Thứ Hai). Giả sử A là tập con lồi đóng, khác rỗng trong không gian lồi địa phương X , x0 /∈ A. Khi đó, tồn tại x∗ 6= 0, x∗ ∈ X∗ tách ngặt A và x0. 2.1.5. Dưới vi phân của hàm lồi. Cho f là hàm lồi chính thường trên X . Định Nghĩa 2.16. Phiếm hàm x∗ ∈ X∗ được gọi là dưới gradient của hàm số f tại điểm x ∈ X nếu f (x)− f (x)≥ 〈x∗,x− x〉, (∀x ∈ X). Tập tất cả các dưới gradient của hàm số f tại x được gọi là dưới vi phân của hàm f tại điểm x, kí hiệu là ∂ f (x), tức là: ∂ f (x) = {x∗ ∈ X∗ : f (x)− f (x)≥ 〈x∗,x− x〉, ∀x ∈ X}. Nhận Xét 2.3. Trong giải tích lồi, dưới vi phân đóng vai trò giống với đạo hàm trong giải tích cổ điển. Nếu hàm f là khả vi Gateaux tại mọi điểm, thì ta có thể chứng minh được rằng: dưới vi phân của hàm f chỉ có một giá trị, và đó chính là đạo hàm Gateaux. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 38 Mệnh Đề 2.3. Nếu hàm f khả vi tại x thì: ∂ f (x) = ∇ f (x). Chứng minh Nếu p ∈ ∂x thì với mọi u ∈ X ,t > 0, ta có f (x+ tu)− f (x)≥ t〈p,u〉. Từ đó suy ra f (x+ tu)− f (x) t ≥ 〈p,u〉 (vì t > 0). Cho t −→ 0 ta được 〈5 f (x¯),u〉 ≥ 〈p,u〉. Điều đó có nghĩa là 〈5 f (x¯)− p,u〉 ≥ 0 ∀u ∈ X . Vậy: p =5 f (x).  Ví Dụ 2.3. Một số ví dụ về dưới vi phân. 1. Cho hàm affine f (x) := 〈x∗,x〉+α (x∗ ∈ X∗,α ∈ R) . thì ∂ f (x) = {x∗}, ∀x ∈ X . 2. Giả sử X là không gian Banach thì dưới vi phân của hàm: f (x) = ||x|| là ∂ f (x) = { x∗ ∈ X∗ : ||x∗|| ≤ 1 Khi x = 0 x∗ ∈ X∗ : ||x∗||= 1,〈x∗,x〉= ||x|| Khi x 6= 0. Nói riêng, nếu X = R, f (x) = |x| thì ∂ f (x) = { x |x| Khi x 6= 0 [−1,1] Khi x = 0. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 39 3. Dưới vi phân của hàm chỉ δ (x|A) của một tập lồi A là ∂δ (x|A) = {x∗ ∈ X∗ : 〈x∗,x− x¯〉 ≤ 0, ∀x ∈ A}= N(x|A). Thật vậy, với x ∈ A thì x∗ ∈ ∂δ (x|A)⇔ ∂δ (x|A)≥ ∂δ (x|A)+ 〈x∗,x− x〉, ∀x ∈ X ⇔ 〈x∗,x− x〉 ≤ 0, ∀x ∈ A. Điều này có nghĩa rằng, x∗ là vectơ pháp tuyến của A tại x. Như vậy, ∂δ (x|A) là nón pháp tuyến của A tại x. Do đó ∂δ (x|A) = N(x|A). Chú ý rằng • Với x /∈ A thì ∂δ (x|A) = /0 • Với ∀x ∈ A thì ∂δ (x|A) 6= /0, vì khi x ∈ A kéo theo 0 ∈ ∂δ (x|A). Nếu A = L là một không gian con thì ∂δ (x|L) = N(x|L) = L⊥ trong đó L⊥ = {x∗ ∈ X∗ : 〈x∗,x〉= 0, ∀x ∈ L}. 2.1.6. Định lý cơ bản về dưới vi phân của tổng các hàm lồi. Định Lý 2.3. (Moreau-Rockafellar). a) Cho các hàm f1 và f2 là những hàm lồi chính thường trên X. Khi đó ∂ ( f1 + f2)(x)⊃ ∂ f1(x)+∂ f2(x). b) Nếu một trong các hàm này mà liên tục tại một điểm thuộc miền hữu hiệu của hàm kia thì ta có ∂ ( f1 + f2)(x) = ∂ f1(x)+∂ f2(x). Chứng Minh a) Lấy x∗i ∈ ∂ fi(x), i = 1,2. Khi đó, với ∀z ∈ X ta có 〈x∗i ,z− x〉 ≤ fi(z)− fi(x), i = 1,2. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 40 Suy ra 〈x∗1 + x∗2, z− x〉 ≤ f1(z)+ f2(z)− ( f1(x)+ f2(x)). do đó x∗1 + x ∗ 2 ⊃ ∂ ( f1 + f2)(x). Như vậy ∂ ( f1 + f2)(x)⊃ ∂ f1(x)+∂ f2(x). b) Ta chứng m