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

1ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM PHẠM PHÚC LONG VỀ NGUYÊN LÝ NHÂN TỬ LAGRANGE Chuyên ngành: Giải tích Mã số: 60 46 01 LUẬN VĂN THẠC SỸ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. TRƯƠNG XUÂN ĐỨC HÀ Thái Nguyên- Năm 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 2MỤC LỤC Mở đầu: ................................................................................................... 2 Chương I. NGUYÊN LÝ NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU TRƠN. 1.1 Một số kiến thức chuẩn bị .................................................................5 1.1.1 Khả vi Gateaux và khả vi Frechet .................................................5 1.1.2 Định lý Hahn-Banach, bổ đề về linh hóa tử ..................................9 1.1.3 Định lý Ljusternik, định lý hàm ẩn .............................................10 1.2 Điều kiện cần đủ cho bài toán tối ưu trơn ......................................12 1.2.1 Phát biểu bài toán ........................................................................12 1.2.2 Trường hợp hữu hạn chiều ..........................................................17 1.2.3 Trường hợp tổng quát .................................................................27 Chương II. NGUYÊN LÝ NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU LỒI. 2.1 Một số kiến thức cơ bản của giải tích lồi ........................................31 2.1.1 Tập lồi .........................................................................................31 2.1.2 Hàm lồi .......................................................................................32 2.1.3 Tập Affine ...................................................................................34 2.1.3 Các định lý tách ...........................................................................35 2.1.4 Dưới vi phân của hàm lồi ............................................................36 2.1.6 Định lý cơ bản về dưới vi phân của tổng các hàm lồi ...................38 2.2 Điều kiện cần đủ cho bài toán tối ưu lồi .........................................43 2.2.1 Bài toán không có ràng buộc .......................................................44 2.2.2 Bài toán với ràng buộc đẳng thức ................................................44 2.2.3 Bài toán với ràng buộc bất đẳng thức ..........................................47 KẾTLUẬN ..............................................................................................55 TÀI LIỆU THAMKHẢO ......................................................................56 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 3MỞ ĐẦU Trong cuộc sống, ai cũng mong muốn công việc hàng ngày của mình được hoàn thành một cách tốt nhất. Ai cũng tự đặt ra hai câu hỏi chính: Làm thế nào để công việc hoàn thành tốt nhất, và khi tốt nhất thì được cái gì? Như vậy, chẳng qua mọi người cũng phải giải các bài toán tối ưu của mình theo một nghĩa nào đó. Một vấn đề quan trọng nhất đặt ra cho mỗi bài toán tối ưu là: Với điều kiện nào, bài toán có nghiệm, và nếu có nghiệm điều gì sẽ xảy ra. Tất nhiên, điều kiện càng đơn giản thì việc tìm nghiệm càng dễ. Biết được điều gì xảy ra nếu có lời giải, thì việc tìm ra lời giải càng dễ dàng hơn. Ta biết trong bài toán tối ưu có hai đối tượng quan trọng: Tập chấp nhận được (hay tập ràng buộc) và Hàm mục tiêu xác định trên tập đó. Vậy thì khi xét đến điều kiện để tồn tại nghiệm tối ưu, ta phải quan tâm tới các điều kiện, tính chất của hai đối tượng ấy. Để nghiên cứu sự tồn tại nghiệm và tìm ra phương pháp giải nghiệm, người ta thường phân loại các bài toán theo cấu trúc của tập chấp nhận được và tính chất hàm mục tiêu của bài toán. Trong luận văn này, tác giả đề cập tới hai loại bài toán chính sau: 1. Bài toán tối ưu trơn với ràng buộc đẳng thức. Cụ thể: Cho X , Y là các không gian Banach, hàm f xác định trên X , ánh xạ F : X −→ Y . Bài toán: { f (x)−→ in f F(x) = 0. được gọi là bài toán tối ưu trơn với ràng buộc đẳng thức nếu hàm f và ánh xạ F thỏa mãn tính trơn. 2. Bài toán tối ưu lồi. Cụ thể: Cho X là không gian tôpô tuyến tính lồi địa phương, A ⊂ X là một tập lồi đóng không rỗng. f ,gi : X −→R= R∪{±∞} và h j : X −→R là những hàm affine. Bài toán quy hoạch lồi tổng quát cho dưới dạng Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 4sau:   min f(x) x ∈ A gi(x)≤ 0 (i = 1,2, . . . ,m) h j(x) = 0 ( j = 1,2, . . . , p). Trong giải tích cổ điển, ta đã biết định lý Weierstrass nổi tiếng: “ Một hàm số liên tục trên tập compact luôn đạt cực đại và cực tiểu”. Những mở rộng hay biến dạng khác nhau của định lý này chỉ ra nhiều điều kiện đủ cho sự tồn tại nghiệm của bài toán tối ưu. Khi hàm số khả vi, một điểm là nghiệm tối ưu của bài toán không có ràng buộc, thì đạo hàm của nó tại điểm này phải bằng không. Đó là điều kiện cần tối ưu. Khẳng định này vẫn còn đúng cho hàm lồi với đạo hàm được thay bằng dưới vi phân. Với ý tưởng như vậy, khi nghiên cứu một bài toán tối ưu có ràng buộc, người ta tìm cách đưa nó về một bài toán không có ràng buộc hoặc chỉ có những ràng buộc tương đối đơn giản. Có thể thấy điều đó trong các công trình nghiên cứu của Lagrange về tính biến phân từ cuối thế kỷ XVIII. Đó là: • Xây dựng hàm Lagrange cho bài toán tối ưu. • Tìm các điều kiện để hàm Lagrange đạt cực trị. Chính việc áp dụng rộng rãi nguyên lý nhân tử Lagrange trong các bài toán tối ưu đã khiến tác giả chọn đề tài nghiên cứu này. Luận văn trình bày hệ thống và chi tiết một số điều kiện tối ưu cho các bài toán tối ưu trơn, và bài toán tối ưu lồi được trình bày từ các tài liệu chuyên đề chính [1− 4], và có tham khảo thêm các tài liệu [5− 7]. Các điều kiện này được thể hiện thông qua các nhân tử Lagrange. Luận văn bao gồm: Phần mở đầu, hai chương và phần tài liệu tham khảo. Chương I: 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 trơn. Đầu tiên chúng ta nhắc lại một số kiến thức về khả vi Gateaux, khả vi Frechet, định lý Ljusternik, định lý hàm ẩn, sau đó trình bày điều kiện cần cấp một và điều kiện cần đủ cấp hai thông qua sự tồn tại của vi phân cấp hai và nhân tử Lagrange. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 5Chương II: 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. Tác giả trình bày một số kiến thức cơ bản về giải tích lồi, định lý Moreau-Rockafellar, và định lý cổ điển Kuhn-Tucker về điều kiện cần và đủ của bài toán tối ưu lồi thông qua sự tồn tại của nhân tử Lagrange tương ứng với dưới vi phân tại điểm đó. Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Trương Xuân Đức Hà, người đã trực tiếp giúp đỡ và chỉ bảo tận tình tác giả trong suốt quá trình học tập, nghiên cứu và viết bản luận văn này. Tác giả cũng bày tỏ tình cảm của mình trước sự giúp đỡ, động viên của gia đình, bạn bè, và tập thể học viên cao học Toán K16-ĐHSPTN. Trong quá trình viết luận văn cũng như trong việc xử lý văn bản chắc chắn không tránh khỏi những hạn chế và thiếu sót. Rất mong nhận được sự góp ý của thầy cô, các bạn đồng nghiệp để luận văn được hoàn thiện hơn. Thái Nguyên, tháng 8, năm 2010. Phạm Phúc Long Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 6CHƯƠNG I: NGUYÊN LÝ NHÂN TỬ LAGRANGE CHO BÀI TOÁN TỐI ƯU TRƠN 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 trơn thông qua sự tồn tại của các nhân tử Lagrange. Những kết quả này được tham khảo từ những tài liệu chuyên đề chính [1−4]. 1.1. Một số kiến thức chuẩn bị. Trong mục này, chúng ta nhắc lại một số khái niệm về khả vi Gateaux, khả vi Frechet, định lý Hahn-Banach, định lý Ljusternik và định lý hàm ẩn. 1.1.1. Khả vi Gateaux và khả vi Frechet. Định Nghĩa 1.1. Cho X , Y là các không gian tôpô tuyến tính, U là lân cận của x ∈ X , ánh xạ F : U −→Y . Ánh xạ F được gọi là khả vi Gateaux tại x nếu tồn tại toán tử tuyến tính liên tục F ′(x) : X −→ Y thỏa mãn: lim t→0 F(x+ th)−F(x)− tF ′(x)h t = 0. ∀h ∈ X . Định Nghĩa 1.2. Cho X , Y là các không gian Banach, U là lân cận của x ∈ X , ánh xạ F : U −→ Y . Ánh xạ F được gọi là khả vi Frechet tại x nếu tồn tại toán tử tuyến tính liên tục F ′(x) : X −→ Y thỏa mãn: lim h→0 F(x+h)−F(x)−F ′(x)h ||h|| = 0. Định Nghĩa 1.3. Cho U là tập con mở trong không gian X , ánh xạ F : X −→ Y với X ,Y là các không gian Banach. Nếu với mọi điểm của tập U , tồn tại đạo hàm F ′(x) và ánh xạ x −→ F ′(x) là liên tục trong không gian L(X ,Y ) trên U thì F gọi là khả vi liên tục trên U , hoặc ánh xạ thuộc lớp C1 trên U . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 7Định Nghĩa 1.4. Ta nói rằng, ánh xạ F : X −→ Y là chính quy tại điểm x nếu nó khả vi Frechet tại điểm đó, và ImF ′(x) = Y . Định Nghĩa 1.5. Cho hàm số f (x) xác định trên không gian tôpô tuyến tính X . Điểm x ∈ X thỏa mãn f ′(x) = 0 được gọi là điểm dừng. Định Nghĩa 1.6. Cho Ω là miền mở, giới nội trong Rn. Hàm số f : Ω −→ R với x ∈ Ω, x = (x1, . . . ,xn). Giả sử f có các đạo hàm riêng ∂ f∂xi (x), (i = 1, . . . ,n), thì vectơ ( ∂ f ∂x1 (x), . . . , ∂ f ∂xn (x) ) gọi là Gradient của f tại x. Kí hiệu: ∇ f (x) = ( ∂ f ∂x1 (x), . . . , ∂ f ∂xn (x) ) . Ma trận J = ( ∂ f ∂x1 (x), . . . , ∂ f ∂xn (x) ) gọi là Jacobian của f tại x. Nếu ∂ f∂xi (x) có các đạo hàm riêng thứ j với ( j = 1, . . . ,n), đạo hàm riêng này được gọi là đạo hàm riêng cấp hai theo các biến i, j của f tại x, và được kí hiệu là ∂ 2 f ∂xi∂x j (x), i, j = 1, . . . ,n. Ma trận H = ( ∂ 2 f ∂xi∂x j (x) ) , i, j = 1, . . . ,n. được gọi là Hessian của f tại x. Ví Dụ 1.1. Tính khả vi của một số hàm và ánh xạ. 1) Trong R2 hàm f (x1,x2) được cho bởi công thức.{ 1 nếu x1 = x22 0 Trong các trường hợp còn lại. là khả vi Gateaux tại gốc tọa độ. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 82) Ánh xạ affine. Một ánh xạ A : X −→ Y với X ,Y là các không gian tuyến tính được gọi là affine nếu: A(x) = λ x+a. trong đó a ∈ Y và λ : X −→ Y là ánh xạ tuyến tính. Nếu X ,Y là các không gian Banach, λ là ánh xạ tuyến tính liên tục, thì ánh xạ A là khả vi Frechet tại mọi điểm và A′(x) = λ . Đạo hàm cấp hai của A là: A′′(x) = 0. (điều này được suy ra trực tiếp từ định nghĩa). Nói riêng, đạo hàm Frechet của hàm affine a(x) = 〈x∗,x〉. là a′(x) = x∗ tại ∀x. 3) Hàm Bậc Hai. Cho X là không gian Banach, B(x1,x2) là hàm song tuyến tính liên tục trên X ×X , và Q(x) = B(x,x) là một dạng toàn phương. Về bản chất: Q(x+h) = B(x+h,x+h) = B(x,x)+B(x,h)+B(h,x)+B(h,h) = Q(x)+B(x,h)+B(h,x)+o(||h||), (khi h −→ 0). Do đó hàm Q(x) là khả vi Frechet và: Q′(x)h = B(x,h)+B(h,x). Nói riêng, nếu X là không gian Hilbert thì mọi dạng bậc hai có thể biểu diễn dưới dạng Q(x) = 1 2 〈λ x,x〉, với λ ∈ L(X ,Y ), λ ∗ = λ . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 9Và Q′(x) = λ x. Trong không gian hilbert, tổng của một dạng bậc hai với một hàm affine K(x) = 1 2 〈λ x,x〉+ 〈x,a〉+α. gọi là hàm bậc hai. Khi đó K′(x) = λ x+a. và K′′(x) = λ . các đạo hàm còn lại bằng không. Đặc biệt, nếu hàm e(x) = 1 2 ||x||2 = 1 2 〈x,x〉. thì e′(x) = x. e′′(x) = I. e′′′(x) = · · ·= 0. 4) Chuẩn trong không gian Hilbert. Hàm số f (x) = ||x|| là khả vi Frechet tại mọi điểm khác không và f ′(x) = x||x||. Tiếp theo chúng ta nhắc lại định lý Hahn-Banach, toán tử liên hợp, và một bổ đề quan trọng đó là, bổ đề về linh hóa tử (annihilator). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 10 1.1.2. Định lý Hahn-Banach, bổ đề về linh hóa tử. Định Lý 1.1. (Hahn-Banach). Cho X là không gian tôpô tuyến tính, A ⊂ X là tập lồi mở, L ⊂ X là một không gian con rời A. Khi đó, tồn tại một phiếm hàm tuyến tính liên tục x∗ trên X thỏa mãn • 〈x∗,x〉> 0 với ∀x ∈ A. • 〈x∗,x〉= 0 với ∀x ∈ L. Chúng ta chú ý rằng, tập L⊥ = {x∗ ∈ X∗ | 〈x∗,x〉= 0, ∀x ∈ L} được gọi là linh hóa tử của L. Hệ Quả 1.1. Cho L là một không gian con đóng của một không gian tôpô tuyến tính lồi địa phương, thì linh hóa tử của L chứa ít nhất một phần tử khác không. Định Nghĩa 1.7. (Toán tử liên hợp) Cho X ,Y là các không gian tuyến tính lồi địa phương, λ : X −→ Y là toán tử tuyến tính liên tục. Khi đó, toán tử liên hợp λ ∗ : Y ∗ −→ X∗ được xác định bởi 〈λ ∗y∗,x〉= 〈y∗,λ x〉 với ∀y∗ ∈ Y ∗, x ∈ X . Bổ Đề 1.1. (Bổ đề về linh hóa tử) Cho X ,Y là các không gian Banach, λ : X −→ Y là toán tử tuyến tính liên tục thỏa mãn Im λ = Y . Khi đó (Ker λ )⊥ = Im λ ∗. Định Lý 1.2. Cho ánh xạ F : X −→Rn và F(x) = ( f1(x), . . . , fn(x)) là khả vi Frechet tại x0. Ánh xạ F là chính quy tại x0 nếu và chỉ nếu các vectơ f ′1(x0), . . . , f ′n(x0) là độc lập tuyến tính. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 11 Để chứng minh điều kiện tối ưu của bài toán trơn với ràng buộc đẳng thức, ta cần tới các định lý quan trọng sau. 1.1.3. Định lý Ljusternik, Định lý hàm ẩn. Giả sử X là không gian Banach, tập M ⊂ X . Định Nghĩa 1.8. (Vectơ tiếp xúc) Một vectơ x ∈ X gọi là tiếp xúc với tập M tại điểm x0, nếu tồn tại số ε > 0 và ánh xạ r : [0,ε]−→ X t 7−→ r(t) thỏa mãn x0+ tx+ r(t) ∈ M, ∀t ∈ [0,ε] trong đó ||r(t)|| t −→ 0 khi t −→ 0. Nhận Xét 1.1. Tập tất cả các vectơ tiếp xúc với tập M tại x0 là một hình nón đóng, được gọi là nón tiếp tuyến của M tại x0 và được kí hiệu là TM(x0). Trong nhiều trường hợp, TM(x0) là một không gian con và được gọi là không gian tiếp xúc với tập M tại x0. Do 0 ∈ TM(x0) nên TM(x0) 6= /0 Định Lý 1.3. (Định Lý Ljusternik) Giả sử X ,Y là các không gian Banach,U là một lân cận của điểm x0 ∈X . Ánh xạ F : U −→ Y . Giả thiết rằng, F khả vi liên tục theo nghĩa Frechet tại x0 và Im F ′(x0) = Y Đặt M = {x ∈U : F(x) = F(x0)}. Khi đó, không gian tiếp xúc với tập M tại x0 trùng với Ker F ′(x0), tức là TM(x0) = Ker F ′(x0). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 12 Đồng thời, tồn tại lân cậnU ′ ⊂U của x0, số K > 0 và ánh xạ ξ −→ x(ξ ) từ U ′ vào X sao cho: với mọi ξ ∈U ′ F (ξ + x(ξ ))= F(x0), ||x(ξ )|| ≤ K ||F(ξ )−F(x0)|| . Nhận Xét 1.2. Thực ra, không cần các điều kiện của định lý (1.3) mà chỉ dựa vào định nghĩa của vectơ tiếp xúc với tập M tại x0, ta có thể chứng minh được: TM(x0)⊂ Ker F ′(x0). Ý nghĩa thực tế của định lý Ljusternik là chuyển công việc tìm không gian tiếp xúc của một tập (điều mà không dễ dàng tìm được theo định nghĩa) về việc tìm hạch của một toán tử. Giả sử ta có hệ gồm m phương trình với n biến số: hi(x) = 0, i = 1, . . . ,m và m ≤ n. Nếu cố định (n−m) ẩn, thì hệ phương trình được giải với m ẩn còn lại. Do đó, nếu ta chọn m biến đầu tiên là x1,x2, . . . ,xm và giả sử rằng các biến này có thể được biểu diễn thông qua các biến còn lại dưới dạng xi = φi(xm+1,xm+2, . . . ,xn), i = 1, . . . ,m. các hàm φi (nếu tồn tại) được gọi là các hàm ẩn. Định lý 1.4. (Định lý hàm ẩn). Cho x0 = (x01, . . . ,x 0 n) là một điểm trong R n thỏa mãn: 1. Các hàm số hi ∈Cp, i = 1, . . . ,m, p ≥ 1 trong lân cận của x0. 2. hi(x0) = 0, i = 1, . . . ,m. 3. Ma trận Jacobian cấp m×m J =   ∂h1(x0) ∂x1 · · · ∂h1(x0) ∂xm... ... ∂hm(x0) ∂x1 · · · ∂hm(x0) ∂xm   là không suy biến. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 13 Khi đó, có lân cận của xˆ0 = (x0m+1, . . . ,x 0 n) ∈ Rn−m thỏa mãn: với xˆ = (xm+1, . . . ,xn) trong lân cận này thì tồn tại các hàm φi(xˆ), i = 1, . . . ,m sao cho 1. φi ∈Cp. 2. x0i = φi(xˆ0), i = 1, . . . ,m. 3. hi(φi(xˆ),φ2(xˆ), . . . ,φm(xˆ), xˆ) = 0, i = 1, . . . ,m. Định lý hàm ẩn sẽ giúp ta chứng minh cách xác định không gian tiếp xúc của mặt ràng buộc sẽ được trình bày ở phần sau. 1.2. Điều kiện cần đủ cho bài toán tối ưu trơn . Trong mục này chúng ta trình bày điều kiện cần cấp một và điều kiện cần đủ cấp hai thông qua sự tồn tại của vi phân cấp hai và nhân tử La- grange. Đây chính là trường hợp ta hay gặp trong thực tiễn. 1.2.1. Phát biểu bài toán. Cho X , Y là các không gian Banach, hàm f xác định trên X , ánh xạ F : X −→ Y . Xét bài toán: (P1) { f (x)−→ in f (1.1) F(x) = 0 (1.2) bài toán (P1) được gọi là bài toán tối ưu trơn với ràng buộc đẳng thức nếu hàm f và ánh xạ F thỏa mãn tính trơn. Trong đó: • F(x) = 0 gọi là ràng buộc đẳng thức. • Ω = {x ∈ X : F(x) = 0} gọi là tập chấp nhận được. Hàm Lagrange của bài toán (P1) được thiết lập như sau L(x,λ0,y∗) = λ0 f (x)+ 〈y∗,F(x)〉 với λ0 ∈ R, y∗ ∈ Y ∗. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 14 trong đó λ0 và y∗ gọi là các nhân tử Lagrange. Để có một cái nhìn trực quan, chúng ta xét bài toán trong trường hợp cụ thể sau (P2) { min f (x,y) h(x,y) = 0 x,y ∈ R. trong đó các hàm số f ,h khả vi liên tục tới cấp 2, và f là chính quy. Chú ý rằng, nếu f và h là các hàm tuyến tính, thì bài toán trên chính là bài toán quy hoạch tuyến tính. Khi đó, ta có thể giải quyết bài toán bằng các thuật toán đơn hình. Vì vậy, chúng ta chỉ xét trường hợp các hàm này là phi tuyến. Ràng buộc h(x,y) = 0 xác định một đường cong như hình 1 Hình 1. Lấy vi phân của phương trình h(x,y) = 0 với ẩn x, ta có ∂h ∂x + ∂h ∂y . dy dx = 0. (1.3) Tiếp tuyến của đường cong là T (x,y) = ( 1, dy dx ) . và gradient của đường cong là ∇h = (∂h ∂x , ∂h ∂y ) . Vì vậy, phương trình (1.3) có nghĩa là: T.∇h = 0. Nói cách khác, tiếp tuyến của đường cong phải vuông góc với gradient tại mọi điểm. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 15 Giả sử ta đang ở một điểm trên đường cong, để điểm này nằm trên đường cong thì bất kì chuyển động nào cũng phải theo tiếp tuyến T . Để tăng hoặc giảm f (x,y) thì chuyển động dọc theo đường cong phải có một thành phần dọc theo gradient của f . Tức là ∇ f .T 6= 0. Hình 2. Tại điểm cực trị, chuyển động lúc này là đặc biệt. Khi đó, T trực giao với ∇ f , nói cách khác ∇ f .T = 0. Như vậy, T trực giao với cả gradient ∇ f và ∇h tại điểm cực trị, điều đó có nghĩa rằng ∇ f và ∇h phải song song với nhau. Do đó, tồn tại λ ∈ R sao cho ∇ f +λ ∇h = 0. (1.4) Hình (3)minh họa cho điều kiện (1.4) bằng cách chồng lên đường cong h(x,y) = 0 họ các đường mức của hàm f (x,y), đó là tập các đường cong f (x,y) = c, trong đó c là số thực bất kì trong khoảng biến thiên của f . Trong hình (3) ta có c5 > c4 > c3 > c∗ > c1. Nếu di chuyển dọc theo đường cong sẽ cho kết quả tăng hoặc giảm giá trị của f . Hãy tưởng tượng, một điểm di chuyển trên đường cong h(x,y) từ (x1,y1) đến (x2,y2). Ban đầu, chuyển động có một thành phần dọc theo hướng của −∇ f dẫn đến giảm giá trị của f . Giá trị này nhỏ dần, khi di chuyển tới (x∗,y∗), chuyển động là trực giao với gradient. Từ điểm này, chuyển động bắt đầu có một thành phần dọc theo hướng gradient ∇ f , như vậy giá trị của f tăng lên. Do đó, tại (x∗,y∗) hàm f đạt cực tiểu địa phương. Chuyển động này theo hướng tiếp tuyến của đường cong h(x,y) = 0, đó là trực giao Số hóa bởi Trung tâm Học liệu - Đại học Thá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 minh rằng, nếu f1 liên tục tại x ∈ dom f2 thì ∂ ( f1 + f2)(x) = ∂ f1(x)+∂ f2(x). Ta có, int(epi f1) 6= /0 Thật vậy, ε > 0, tồn tại lân cận U mở của x sao cho | f1(x)− f1(x)|< ε (∀x ∈U). Do đó tập A = {(x,α) ∈ X ×R : α > f1(x)+ ε, x ∈U} ⊂ epi f1. và A mở. Suy ra int(epi f1) 6= /0. Lấy x∗ ∈ ∂ ( f1 + f2)(x). Xét các tập sau C1 = {(z,α) ∈ X ×R : α ≥ f1(x+ z)− f1(x)}. C2 = {(z,α) ∈ X ×R : α < 〈x∗,z〉− f2(x+ z)+ f2(x)}. Khi đó C1 = epi f1 − (x, f1(x)). Vì vậy: C1 lồi và intC1 6= 0. Mặt khác, ta cũng có tập C2 là lồi. Thật vậy, lấy (zi,αi) ∈C2, (i = 1,2) và λ ∈ [0,1], ta có αi < 〈x∗,zi〉− f2(x+zi)+ f2(x), (i = 1,2). (2.2) Do f2 là hàm lồi nên f2 ( λ (x+ z1)+(1−λ )(x+ z2) )≤ λ f2(x+ z1)+(1−λ ) f2(x+ z2). (2.3) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 41 Từ (2.2) và (2.3) suy ra λ α1+(1−λ )α2 < 〈x∗,λ z1+(1−λ )z2〉− − f2 ( λ (x+ z1)+(1−λ )(x+ z2)+ f2(x) ) . Do đó λ (z1,α1)+(1−λ )(z2,α2) ∈C2. Vậy: C2 lồi. Ta lại có: C1∩C2 = /0. Thật vậy, nếu ∃ (z0,α0) ∈C1∩C2, thì 〈x∗,z0〉− f2(x+ z0)+ f2(x)> f1(x+ z0)− f1(x). Suy ra 〈x∗,z0〉> f1(x+ z0)+ f2(x+ z0)− ( f1(x)+ f2(x)). Điều này mâu thuẫn với giả thiết rằng: x∗ ∈ ∂ ( f1+ f2)(x) Vậy C1∩C2 = /0. Theo định lý tách thứ nhất ∃x∗1 ∈ X∗ và ∃β ∈ R với (x∗1,β ) 6= 0 sao cho sup (z,α)∈C1 {〈x∗1,z〉+β α} ≤ inf (z,α)∈C2 {〈x∗1,z〉+β α}. (2.4) Rõ ràng β ≤ 0, bởi vì nếu β > 0 thì, cận trên trong (2.4) là +∞, còn cận dưới là −∞. Hơn nữa, β 6= 0, vì nếu β = 0 thì bất đẳng (2.4) có dạng sup z∈dom f1−x 〈x∗1,z〉 ≤ inf z∈dom f2−x 〈x∗1,z〉. (2.5) Mặt khác, x∗1 6= 0 (do β = 0). Vì thế: 〈x∗1, x¯− x〉< sup z∈U−x 〈x∗1,z〉 ≤ sup z∈dom f1−x 〈x∗1,z〉. Do đó inf z∈dom f2−x 〈x∗1,z〉 ≤ 〈x∗1, x¯− x〉< sup z∈dom f1−x 〈x∗1,z〉. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 42 Điều này mâu thuẫn với (2.5). Vì vậy β 6= 0 và ta có β < 0. Không làm mất tính chất tổng quát, có thể xem β =−1. Như vậy C1 và C2 tách được bởi siêu phẳng H = {(z,α) ∈ X ×R : 〈x∗1,z〉−α = 0}. Do đó từ (2.4) suy ra sup z {〈x∗1,z〉− f1(x+ z)+ f1(x)} ≤ ≤ inf z {〈x∗1 − x∗,z〉+ f2(x+ z)− f2(x)}. (2.6) Các biểu thức trong ngoặc của cả hai vế trái và phải của (2.6) sẽ triệt tiêu với z = 0. Do đó, khi đặt x∗2 = x∗− x∗1, ta nhận được f1(x+ z)− f1(x)≥ 〈x∗1,z〉, (∀z ∈ X). f2(x+ z)− f2(x)≥ 〈x∗2,z〉, (∀z ∈ X). Suy ra x∗i ∈ ∂ fi(x), (i = 1,2). Vậy ∂ ( f1+ f2)(x) = ∂ f1(x)+∂ f2(x).  Bằng phương pháp quy nạp, định lý Moreau-Rockafellar có thể mở rộng với số lượng các hàm số bất kỳ. Hệ Quả 2.1. a) Giả sử f1, . . . , fn là những hàm lồi chính thường trên X. Khi đó ∂ ( f1+ · · ·+ fn)⊃ ∂ f1(x)+ · · ·+∂ fn(x), (∀x ∈ X). b) Hơn nữa nếu tại điểm x¯ ∈ ⋂ni=1 dom fi, tất cả các hàm số f1, . . . , fn đều liên tục (có thể trừ ra một hàm), thì với ∀x ∈ X ta có ∂ ( f1+ f2+ · · ·+ fn)(x) = ∂ f1(x)+∂ f2(x)+ · · ·+∂ fn(x). (2.7) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 43 Chứng Minh. Giả sử, x∗ ∈ ∂ f1(x)+∂ f2(x)+ · · ·+∂ fn(x) thì x∗ = x∗1 + · · ·+ x∗n với x∗i ∈ ∂ fi(x). Theo định nghĩa dưới vi phân ta có 〈x∗i ,z− x〉 ≤ fi(z)− fi(x), i = 1, . . . ,n. Do đó 〈x∗1 + · · ·+ x∗n,z− x〉 ≤ [ f1(z)+ · · ·+ fn(z)]− [ f1(x)+ · · ·+ fn(x)]. Suy ra x∗ = x∗1 + · · ·+ x∗n ∈ ∂ ( f1 + · · ·+ fn)(x). Vậy ∂ ( f1 + · · ·+ fn)(x)⊃ ∂ f1(x)+ · · ·+∂ fn(x). b) Ta chứng minh theo quy nạp. Trường hợp n = 2 chính là định lý Moreau-Rockafellar đã được chứng minh. Giả sử (2.7) đúng với n = k, tức là, nếu mọi hàm số f1, . . . , fk (có thể trừ ra một hàm) đều liên tục tại x ∈ n⋂ i=1 dom fi. thì ∂ ( f1+ · · ·+ fk)(x) = ∂ f1(x)+ · · ·+∂ fk(x). Ta cần chứng minh (2.7) đúng với n = k + 1, tức là nếu mọi hàm số f1, . . . , fk, fk+1 (có thể trừ ra một hàm) đều liên tục tại x ∈ k+1⋂ i=1 dom fi. thì ∂ ( f1 + · · ·+ fk+1)(x) = ∂ f1(x)+ · · ·+∂ fk+1(x) Thật vậy vì (2.7) đúng với n = 2 và n = k, ta có ∂ [( f1+ f2+ · · ·+ fk)+ fk+1](x) = ∂ ( f1 + f2+ · · ·+ fk)(x)+∂ fk+1(x) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 44 = ∂ f1(x)+∂ f2(x)+ · · ·+∂ fk(x)+∂ fk+1(x). Tức là, (2.7) đúng với n = k+1. Vậy (2.7) đúng với mọi số tự nhiên n.  2.2. Điều kiện cần đủ cho bài toán tối ưu lồi. Cho X là một không gian tôpô tuyến tính lồi địa phương, A ⊂ X là tập lồi đóng không rỗng. f ,gi : X −→ R là những hàm lồi và h j : X −→ R là những hàm afin. Xét bài toán quy hoạch lồi tổng quát cho dưới dạng sau  min f(x) x ∈ A gi(x)≤ 0 (i = 1,2, . . . ,m) h j(x) = 0 ( j = 1,2, . . . , p) trong đó: • x ∈ A gọi là ràng buộc hình học. • gi(x)≤ 0 gọi là ràng buộc bất đẳng thức. • h j(x) = 0 gọi là ràng buộc đẳng thức. • Ω = {x ∈ A : gi(x)≤ 0 (i = 1, . . . ,n),h j(x) = 0 ( j = 1, . . . , p)} gọi là tập chấp nhận được. Sử dụng định nghĩa, ta có thể chứng minh tập chấp nhận được là tập lồi. Định Nghĩa 2.17. Hàm Lagrange L : A×Rm+×Rp −→ R của bài toán (P) được xác định như sau L(x,λ ,µ) = λ0 f (x)+ m ∑ i=1 λigi(x)+ p ∑ j=1 µ jh j(x). trong đó x ∈ A, λ0 ∈ R+, λ = (λ1, . . . ,λm) ∈ Rm+, µ = (µ1, . . . ,µp) ∈ Rp. Khi đó, λi gọi là các nhân tử Lagrange ứng với rằng buộc gi(x) ≤ 0 và µ j gọi là các nhân tử Lagrange ứng với rằng buộc h j(x) = 0. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 45 2.2.1. Bài toán không có ràng buộc. Giả sử X là không gian lồi địa phương, f là hàm lồi trên X . Xét bài toán (P7) f (x)−→ in f . Định Lý 2.4. Để x ∈ X là nghiệm của (P7), điều kiện cần và đủ là 0 ∈ ∂ f (x) Chứng minh Ta có, x là nghiệm của (P2) khi và chỉ khi f (x)≤ f (x), (∀x ∈ X). Suy ra 0 = 〈0,x− x〉 ≤ f (x)− f (x), (∀x ∈ X). Vậy 0 ∈ ∂ f (x).  2.2.2. Bài toán với ràng buộc đẳng thức. Giả sử f là một hàm lồi trên X , C là đa tạp tuyến tính song song với không gian con M trong X . Xét bài toán (P8) { f (x) −→ in f x ∈C. Định Lý 2.5. a) Giả sử f liên tục tại một điểm của C, x là một nghiệm của bài toán (P8). Khi đó ∂ f (x)∩M⊥ 6= /0. (2.8) b) Giả sử (2.8) đúng tại ∀x ∈C. Khi đó x là nghiệm của bài toán (P8). Chứng minh Ta chú ý rằng M⊥ = {x∗ ∈ X∗ : 〈x∗,x〉= 0, ∀x ∈ M}. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 46 a) Xét hàm L(x) = f (x)+δ (x|C). trong đó: δ (x|M|) là hàm chỉ của tập C. Khi đó L(x) là hàm lồi trên X . Rõ ràng x là nghiệm của bài toán (P8) khi và chỉ khi hàm L(x) đạt cực tiểu tại x. Theo định lý (2.4) thì 0 ∈ ∂L(x). Do tính liên tục của f , nên ta có thể áp dụng định lýMoreau-Rockafellar, và nhận được 0 ∈ ∂L(x) = ∂ f (x)+∂δ (x|C). Từ ví dụ (2.3.3), ta lại có ∂δ (x|C) = N(x|C) = M⊥. Do đó ta có: ∂ f (x)∩M⊥ 6= /0. b) Giả sử ∂ f (x)∩M⊥ 6= /0 với x ∈C. Khi đó, ∃x∗ ∈ ∂ f (x)∩M⊥. Vì x− x ∈ M với x ∈C, cho nên 0 = 〈x∗,x− x〉 6= f (x)− f (x), (∀x ∈C). Do đó x là nghiệm của bài toán (P8).  Định Lý 2.6. Cho X là không gian Banach, x∗i ∈ X∗, αi ∈ R, (i = 1, . . . ,m) và C = {x ∈ X : 〈x∗i ,x〉= αi, (i = 1, . . . ,m)}. Giả sử f là hàm lồi trên X và liên tục tại một điểm của C. Khi đó, x đạt cực tiểu của hàm f trênC khi và chỉ khi tồn tại các số λi ∈R, (i= 1, . . . ,m) sao cho λ1x∗1+ · · ·+λmx∗m ∈ ∂ f (x). Để chứng minh định lý (2.6), ta cần bổ đề sau Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 47 Bổ Đề 2.1. Giả sử X là không gian Banach, x∗i ∈ X∗, (i = 1, . . . ,m). Đặt M = {x ∈ X : 〈x∗i ,x〉= 0, i = 1, . . . ,m}. Khi đó M⊥ = lin{x∗1, . . . ,x∗m}. trong đó lin là kí hiệu bao tuyến tính. Chứng minh Không mất tính tổng quát, ta có thể xem như x∗1, . . . ,x ∗ n là độc lập tuyến tính. Xét toán tử tuyến tính λ : X −→ Rm được xác định như sau x −→ λ x = (〈x∗1,x〉, . . . ,〈x∗m,x〉). Khi đó, Imλ = Rm. Theo bổ đề (1.1) ta có (Kerλ )⊥ = Imλ ∗. Ta lại có (Kerλ )⊥ = M⊥, Imλ ∗ = lin{x∗1, . . . ,x∗2}. Do đó M⊥ = lin{x∗1, . . . ,x∗m}. Chứng minh định lý 2.6. Đa tạp tuyến tính C song song với không gian con M : M = {x ∈ X : 〈x∗i ,x〉= 0, i = 1, . . . ,m}. Từ định lý (2.5) suy ra: x đạt cực tiểu hàm f trên C khi và chỉ khi ∃x∗ ∈ ∂ f (x)∩M⊥. Theo bổ đề (2.1), ta có x∗ ∈ M⊥ = lin{x∗1, . . . ,x∗2}. Do đó, tồn tại các số λ1, . . . ,λm sao cho λ1x∗1 + · · ·+λmx∗m ∈ ∂ f (x).  Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 48 2.2.3. Bài toán với ràng buộc bất đẳng thức. Giả sử X là không gian lồi địa phương, A ⊂ X là một tập lồi đóng không rỗng. f0, . . . , fn : X −→ R là các hàm lồi. Xét bài toán (P9)   min f0(x) x ∈ A (2.9) fi(x)≤ 0 (i = 1,2, . . . ,m). (2.10) Nhận Xét 2.4. Quan hệ (2.9) không có đặc trưng hàm, mặc dù nó có thể được viết dưới dạng hàm, ví dụ như trong dạng bất đẳng thức δ (x|A)≤ 0. Chúng ta xây dựng hàm Lagrange cho bài toán mà không bao gồm ràng buộc dạng (2.9), đó là L(x,λ0, . . . ,λn) = n ∑ i=0 λi fi(x). Tuy nhiên, chúng ta cũng có thể xét tới việc mở rộng hàm số Lagrange L(x,λ0, . . . ,λn) = n ∑ i=0 λi fi(x)+δ (x|A). Định lý Kuhn-Tucker dưới đây, sẽ đưa ra điều kiện cần và đủ cho điểm chấp nhận được là nghiệm của bài toán (P9). Định lý này có thể được phát biểu dưới hai dạng: dạng toàn cục (định lý 2.7) và dạng địa phương thông qua dưới vi phân (định lý 2.8). Định Lý 2.7. (Định Lý Kuhn-Tucker). Giả sử các hàm f0, . . . , fm và tập A là lồi. x là điểm chấp nhận được của bài toán (P9). Khi đó a) Nếu x là nghiệm của bài toán (P9), thì tồn tại λi ≥ 0, (i = 1, . . . ,m) không đồng thời bằng không sao cho L(x,λ0, . . . ,λm)=min x∈A L(x,λ0, . . . ,λm). (2.11) λi fi(x)= 0, (i= 1, . . . ,m). (2.12) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 49 Hơn nữa, nếu điều kiện Slater sau đây được thỏa mãn: ∃x0 ∈ A : fi(x0)< 0, (i = 1, . . . ,m). thì λ0 > 0 và có thể xem như λ0 = 1. b) Nếu (2.11) và (2.12) thỏa mãn với λ0 = 1, thì x là nghiệm của bài toán (P9). Chứng minh a) Giả sử x là nghiệm của (P9). Đặt C = {(µ0, . . . ,µm) ∈ Rm+1 : (∀x ∈ A) f0(x)− f0(x)< µ0, f1(x)≤ µ1, . . . , fm(x)≤ µm}. Ta có int Rm+1+ ⊂C. Thật vậy, lấy (µ0, . . . ,µm) ∈ int Rm+1+ . Khi đó, µi > 0, (i = 0, . . . ,m). Với x = x, ta có: µ0 > f0(x)− f0(x) = 0, µi > 0 ≥ fi(x), (i = 1, . . . ,m). Suy ra (µ0, . . . ,µm) ∈C, do đó int Rm+1+ ⊂C. Vậy int C 6= /0. Do f0, . . . , fm là hàm lồi, nên tập C là lồi. Hơn nữa, 0 /∈C. Thật vậy, nếu 0 ∈C thì ∃x ∈ A thỏa mãn f0(x)< f0(x), fi(x)≤ 0, (i = 1, . . . ,m). Do đó, x không phải là nghiệm của (P9). Điều này mâu thuẫn với giả thiết. Vì vậy 0 /∈C. Theo định lý tách thứ nhất, có thể tách các tập C và {0} bởi một phiếm hàm tuyến tính khác không, tức là tồn tại các số λ0, . . . ,λm không đồng thời bằng không, sao cho m ∑ i=0 λiµi ≥ 0, (∀(µ0, . . . ,µm) ∈C). (2.13) Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 50 Do int Rm+1+ ⊂C, ta suy ra λi ≥ 0, (i = 0, . . . ,m). Lấy x ∈ A sao cho µi = fi(x), (i = 1, . . . ,m). µ0 ↓ ( f0(x)− f0(x)). Từ (2.13) ta nhận được m ∑ i=0 λi fi(x)≥ λ0 f0(x), (∀x∈A). (2.14) Do x là điểm chấp nhận được, ta có fi(x)≤ 0, (i = 1, . . . ,m). Nếu ∃i ∈ {1, . . . ,m} : fi(x) =−α 0, 0 = f0(x)− f0(x)< ε, f j(x)≤ 0 < ε ( j = 1, . . . , i−1, i+1, . . . ,m). Do đó (ε, . . . ,ε,−α,ε, . . . ,ε) ∈C, (−α ở vị trí thứ i). Suy ra −λiα ≥ 0, (do (2.13) và cho ε → 0 ). Từ đó ta có λi ≤ 0, nên λi = 0, (do λi ≥ 0). Như vậy là, nếu fi(x)< 0 thì λi = 0. Do đó λi fi(x) = 0, (i = 1, . . . ,m). Vì vậy, từ (2.14) ta nhận được m ∑ i=0 λi fi(x)≥ m ∑ i=0 λi fi(x). Vậy ta có L(x,λ0, . . . ,λm) = min x∈A L(x,λ0, . . . ,λm). Bây giờ, giả sử điều kiện Slater đúng. Khi đó, nếu λ0 = 0, thì trong các số λ1, . . . ,λm phải có ít nhất một λi > 0. Do đó m ∑ i=0 λi fi(x)< 0 = m ∑ i=0 λi fi(x). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 51 Điều này mâu thuẫn với (2.11). Vậy λ0 6= 0, tức là λ0 > 0. Không mất tính tổng quát, ta có thể coi λ0 = 1. b) Giả sử x là điểm chấp nhận được, thỏa mãn (2.11) và (2.12) với λ0 = 1, λi ≥ 0, (i = 1, . . . ,m). Lấy x là điểm chấp nhận được, tức là x ∈ A, fi(x)≤ 0, (i = 1, . . . ,m). Khi đó f0(x) = f0(x)+ m ∑ i=1 λi fi(x). ≤ f0(x)+ m ∑ i=1 λi fi(x). ≤ f0(x). Điều này có nghĩa x là nghiệm của bài toán (P9).  Nhận Xét 2.5. Mối quan hệ (2.11) gọi là điều kiện Kuhn-Tucker, và đẳng thức (2.12) gọi là điều kiện bù. Điều kiện bù cho thấy, các nhân tử Lagrange λi tương ứng với ràng buộc tích cực tại điểm x0, (tức là fi(x0)< 0) thì bằng không. Định Lý 2.8. Giả sử các hàm số f0, . . . , fm và tập A là lồi, f0, . . . , fm liên tục tại một điểm của A. x là điểm chấp nhận được của bài toán (P9). Khi đó a) Nếu x là nghiệm của bài toán (P9), thì tồn tại các nhân tử Lagrange không đồng thời bằng không: λi ≥ 0, (i = 0, . . . ,m), sao cho 0∈ λ0∂ f0(x)+ · · ·+λm∂ fm(x)+N(x|A). (2.15) λi fi(x) = 0, (i = 1, . . . ,m). (2.16) trong đó N(x|A) là nón pháp tuyến của A tại x. Hơn nữa, nếu điều kiện Slater đúng, thì λ0 6= 0 và có thể xem như λ0 = 1. b) Nếu (2.15) và (2.16) thỏa mãn với λ0 = 1, thì x là nghiệm của bài toán (P9). Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 52 Chứng minh a) Xét hàm Lagrange của (P9) có dạng L1(x,λ0, . . . ,λm) = m ∑ i=0 λi fi(x)+δ (x|A). trong đó δ (x|A) là hàm chỉ của tập A. Do x là nghiệm của bài toán (P9), ta thu được điều kiện cần dạng (2.11) và (2.12) (định lý (2.7)). Vì thế, hàm L1(x,λ0, . . . ,λm) đạt cực tiểu tại x. Theo định lý (2.4) thì 0 ∈ ∂L1(x,λ0, . . . ,λm). Vì ∂δ (x|A) = N(x|A). Theo định lý Moreau-Rockafellar, ta có 0 ∈ λ0∂ f0(x)+ · · ·+λm∂ fm(x)+N(x|A). b) Giả sử (2.15) và (2.16) thỏa mãn với λ0 = 1. Khi đó, tồn tại x∗i ∈ ∂ fi(x), (i = 0, . . . ,m), và x∗m+1 ∈ N(x|A) sao cho x∗0 + m+1 ∑ i=1 λix∗i = 0. Suy ra 0 = 〈x∗0 + m+1 ∑ i=1 λix∗i ,x− x〉 ≤ ≤ f0(x)− f0(x)+ m ∑ i=1 λi ( fi(x)− fi(x)), (∀x ∈ A). Do đó f0(x)+ m ∑ i=1 λi fi(x)≥ f0(x)+ m ∑ i=1 λi fi(x), (∀x ∈ A). Theo định lý (2.7.b), ta suy ra x là nghiệm của (P9).  Nhận Xét 2.6. Quan hệ (2.15) goi là phương trình Euler-Lagrange. Nó có thể được coi là sự mở rộng tự nhiên của phương trình Euler-Lagrange (1.12) trong Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 53 trường hợp trơn. Trong trường hợp, tất cả các hàm f0, . . . , fm đều khả vi, X = Rn và điều kiện Slater được thỏa mãn, thì các phương trình (2.15) và (2.16) tạo thành một hệ gồm (m+ n) phương trình tuyến tính với (m+ n) ẩn. Đây chính là trường hợp định lý Kuhn-Tucker hay được áp dụng trong thực tiễn. Ví Dụ 2.4. Ví dụ về bài toán tối ưu lồi. Giải bài toán quy hoạch sau min{ n ∑ i=1 1 x2i : n ∑ i=1 xi ≤ 1, xi > 0}. Giải Đây là bài toán quy hoạch lồi vì x−2i là hàm lồi khi xi > 0. Đồng thời bài toán thỏa mãn điều kiện Slater. Hàm Lagrange của bài toán là L(x,λ ) = n ∑ i=1 1 x2i +λ ( n∑ i=1 xi−1 ) . Theo định lý Kuhn-Tucker, tồn tại λ ≥ 0 sao cho  ∇x L(x,λ ) = 0 λ ( n∑ i=1 xi−1 ) = 0. Suy ra   −2x−3i +λ = 0, (∀i = 1, . . . ,n) λ ( n∑ i=1 xi−1 ) = 0. Do đó λ > 0 và   xi = ( λ 2 ) 3, (∀i = 1, . . . ,n) n ∑ i=1 xi = n λ 3 8 = 1. Vậy   λ = 2 n−3 xi = 1 n . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 54 Mặt khác, xi = 1n > 0, ∀n. Suy ra, bài toán đạt cực tiểu tại xi = 12 với λ = 2 n−3 . Ví Dụ 2.5. Giải bài toán quy hoạch sau min {x+ y : x+ y ≤ 1, x2 + y2 ≤ 1}. Giải Đây là bài toán quy hoạch lồi, vì hàm mục tiêu và tập chấp nhận được là lồi. Đồng thời, bài toán thỏa mãn điều kiện Slater. Hàm Lagrange của bài toán là L(x,y,λ ,β ) = x+ y+λ (x+ y−1)+β (x2+ y2−1). Theo định lý Kuhn-Tucker, ta có  ∂Lx(x,y,λ ,β ) = 1+λ +2β x = 0 ∂Ly(x,y,λ ,β ) = 1+λ +2β y = 0 (2.17) λ (x+ y−1) = 0 β (x2 + y2−1) = 0. Do (λ ,β ) 6= 0, λ ≥ 0, β ≥ 0 nên • Nếu (λ = 0, β 6= 0) thì từ (2.17) ta được{ x = y = −12β = −1√ 2 β = 1√2 • Nếu (λ 6= 0, β = 0) thì từ (2.17) ta được{ λ =−1 (loại). x+ y−1 = 0. • Nếu (λ > 0, β > 0) thì từ (2.17) ta được  x = y = −λ−12β β = 0 (loại). λ =−1 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 55 Vậy theo định lý Kuhn-Tucker, bài toán đạt cực tiểu tại x = y = −1√2 với λ = 0, β = 1√2 . Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 56 KẾT LUẬN Trong các định lý về điều kiện cần và đủ cho một điểm là nghiệm tối ưu của bài toán tối ưu trơn và lồi, tác giả đã trình bày thành hai phần. Phần thứ nhất là về các nhân tử Lagrange tổng quát, phần thứ hai là: đối với một số các điều kiện chính quy, thì đảm bảo rằng, hệ số λ0 ứng với hàm mục tiêu là khác 0. Nhìn chung, ta không quan tâm nhiều tới trường hợp λ0 = 0 vì khi đó, các điều kiện cần không liên quan tới hàm mục tiêu mà chỉ liên quan tới các ràng buộc. Tuy vậy, việc sử dụng đẳng thức λ0 = 0, đôi khi khá tiện dụng khi xét các bài toán ở dạng chung. Thông thường, λ0 6= 0 dù điều kiện chính quy không thỏa mãn. Hơn nữa, việc xác định trực tiếp đẳng thức λ0 6= 0 trong nhiều trường hợp dễ dàng hơn so với việc kiểm tra các điều kiện chính quy tương ứng. Nói riêng, nếu hệ số λ0 = 0 phụ thuộc vào các ràng buộc được đưa vào trong hàm Lagrange, thì các ràng buộc đó được bỏ qua. Ví dụ như chúng ta không đưa ràng buộc x ∈ A vào trong hàm Lagrange của bài toán tối ưu lồi. Như đã nói, ràng buộc này có thể cho dưới dạng hàm như A = {x| fn+1(x) ≤ 0}. Tuy nhiên, có thể xảy ra rằng, không có điểm x nào thỏa mãn fi(x) < 0, (i = 1, . . . ,n+ 1). Nếu chúng ta đưa vào ràng buộc fn+1(x) ≤ 0 trong hàm Lagrange, thì điều kiện Slater sẽ bị vi phạm, và không thể đảm bảo rằng λ0 6= 0. Do đó, để nhân tử Lagrange λ0 6= 0, thì nên lựa chọn các ràng buộc đưa vào hàm Lagrange sao cho các điều kiện chính quy không bị vi phạm. Cuối cùng, chúng ta chú ý rằng, định lý Kuhn-Tucker cho ta một quy tắc đơn giản để xác định dấu của nhân tử Lagrange tương ứng với ràng buộc bất đẳng thức. Trong bài toán cực tiểu, dấu của các nhân tử phải được chọn sao cho hàm Lagrange là lồi. Tác giả đã cố gắng sắp xếp và trình bày vấn đề theo cách hiểu rõ ràng và trực quan, đưa ra các ví dụ và một số hình vẽ để minh họa cho nhiều khái niệm và sự kiện được đề cập tới trong luận văn. Hy vọng luận văn này sẽ là một tài liệu tham khảo bổ ích cho những người không chuyên sâu về toán muốn tìm hiểu và vận dụng công cụ giải tích, đặc biệt là các phương pháp tối ưu trong chuyên môn của mình. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên 57 TÀI LIỆU THAM KHẢO [1]A. D. Ioffe and V.M. Tikhomirov, Theory of extremal problems, NewYork 1979. [2]D. G. Luenberger. Linear and Nonlinear Programming. Addison-Wesley, 2nd edition, 1984. [3] Lagrange Multipliers, Com S 477/577. [4] Đỗ Văn Lưu và Phan Huy Khải, Giải tích lồi, Nhà xuất bản khoa học và kỹ thuật, 2000. [5] Nguyễn Xuân Tấn và Nguyễn Bá Minh, Lý thuyết tối ưu không trơn, Nhà xuất bản ĐHQGHN. [6] Hoàng Tụy, Lý thuyết tối ưu, Viện toán học Hà Nội, 2007. [7] Đỗ Phương Thảo, Nhân tử Lagrange cho bài toán quy hoạch lồi, Luận văn cao học, 2005. Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên