Bài toán tối ưu với hàm thuần nhất dương

GS-TS Trần Vũ Thiệu Thái Nguyên - 2009 M l Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 Những kiến thứ về giải tí h lồi 5 1.1 Tập affin và tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Cá bài toán tối ưu 18 2.1 Cá khái niệm ơ bản . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Bài toán tối ưu không ràng buộ . . . . . . . . . . . . . . . . . . 23 2.3 Bài toán tối ưu ó ràng buộ . . . . . . . . . . . . . . . . . . . . 25 3 Bài toán tối ưu với hàm thuần nhất dương 32 3.1 Hàm thuần nhất . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Bài toán tối ưu với hàm thuần nhất dương . . . . . . . . . . . . . 38 3.3 Cá kết quả đối ngẫu hính . . . . . . . . . . . . . . . . . . . . 38 3.4 Tối ưu toàn  . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 1 Lời nói đầu Hàm thự thuần nhất dương ( òn gọi đơn giản là hàm thuần nhất) rất quen thuộ và hay gặp trong nhiều ứng dng, đặ biệt trong nghiên ứu kinh tế vi mô. Hàm tuyến tính, hàm bậ hai, hàm Cobb-Douglas, á hàm đa thứ thuần nhất ... là á ví d về hàm thuần nhất dương. Hàm thuần nhất biểu lộ hành vi rất đều đặn, khi mọi biến tăng theo ùng một tỉ lệ. Chẳng hạn, với hàm thuần nhất bậ 0, khi á biến thay đổi theo ùng một tỉ lệ thì giá trị ủa hàm không hề thay đổi; với hàm thuần nhất bậ 1, khi tăng gấp đôi (gấp ba) mọi biến thì giá trị ủa hàm ũng tăng gấp đôi (gấp ba). Một đặ trưng quan trọng ủa hàm thuần nhất là á đạo hàm riêng ủa một hàm thuần nhất ũng là một hàm thuần nhất và á hàm thuần nhất ó thể biểu diễn đượ qua á đạo hàm riêng ủa nó (Định lý Euler). Đề tài luận văn đề ập tới lớp bài toán tối ưu với á hàm thuần nhất dương, nghĩa là hàm m tiêu và á hàm ràng buộ ủa bài toán đều là á hàm thuần nhất (bậ ó thể khá nhau). Qui hoạ h tuyến tính và qui hoạ h bậ hai là những trường hợp riêng ủa lớp bài toán này. Việ tìm hiểu bài toán tối ưu với á hàm thuần nhất dương là hoàn toàn ần thiết và hữu í h, giúp ta hiểu sâu hơn về á bài toán, phương pháp tối ưu phi tuyến và mở rộng phạm vi ứng dng ủa húng. M tiêu ủa luận văn là tìm hiểu và trình bày một số kết quả ơ bản liên quan tới bài toán tối ưu với á hàm thuần nhất dương. Cá vấn đề đề ập trong luận văn đượ trình bày một á h hặt hẽ về mặt toán họ , một số khái niệm và sự kiện nêu trong luận văn ó kèm theo ví d và hình vẽ để minh hoạ. Nội dung luận văn đượ hia thành ba hương: Chương 1 “Những kiến thứ về giải tí h lồi” giới thiệu vắn tắt một số kiến thứ ơ bản, ần thiết về giải tí h lồi như á khái niệm về tập affine và bao affine, tập lồi và bao lồi, nón lồi và tập lồi đa diện, ùng với á khái niệm đỉnh, ạnh, diện ủa tập lồi đa diện và á khái niệm về hàm lồi, hàm lồi hặt ùng 2 một số tính hất ơ bản ủa húng. Nội dung trình bày trong hương này sẽ ần đến ở hương sau, khi nghiên ứu á bài toán tối ưu phi tuyến nói hung và bài toán tối ưu với hàm thuần nhất dương nói riêng. Chương 2 “Cá bài toán tối ưu” trình bày vắn tắt á khái niệm và kết quả về bài toán tối ưu phi tuyến, phân biệt tối ưu địa phương và tối ưu toàn  , tối ưu không ràng buộ và tối ưu ó ràng buộ , á điều kiện ần và điều kiện đủ ủa tối ưu, đặ biệt là điều kiện KKT ho tối ưu ó ràng buộ . Cá khái niệm nón tiếp xú , khái niệm hính quy, hàm Lagrange và nhân tử Lagrange ũng đượ giới thiệu. Nhiều ví d đã đượ đưa ra để minh hoạ ho á khái niệm và kết quả trình bày. Chương 3 “Bài toán tối ưu với hàm thuần nhất dương” đề ập tới lớp bài toán tối ưu phi tuyến với á hàm thuần nhất dương. Bài toán đượ xt ó thể diễn đạt như một bài toán “min-max” đơn giản, với “max” là bài toán tuyến tính thông thường ó một ràng buộ duy nhất. Từ đó nêu á h diễn đạt mới ho qui hoạ h tuyến tính và qui hoạ h toàn phương ràng buộ tuyến tính. Với những giả thiết nhất định, ó thể hỉ ra bài toán tối ưu không lồi bậ hai tương đương với bài toán tối ưu lồi. Do thời gian ó hạn nên luận văn này mới hỉ dừng lại ở việ tìm hiểu tài liệu, sắp xếp và trình bày á kết quả nghiên ứu đã ó theo hủ đề đặt ra. Trong quá trình viết luận văn ũng như trong xử lý văn bản hắ hắn không tránh khỏi ó những sai sót nhất định. Tá giả luận văn rất mong nhận đượ sự góp ý ủa á thầy ô và á bạn đồng nghiệp để luận văn đượ hoàn thiện hơn. Nhân dịp này, tá giả xin bày tỏ lòng biết ơn sâu sắ đến thầy hướng dẫn GS-TS Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tá giả xin hân thành ảm ơn á thầy, ô ở Viện Công nghệ thông tin, Viện Toán họ Hà Nội, Khoa Công nghệ thông tin, Khoa Toán và Phòng Đào tạo sau đại họ trường Đại họ Khoa họ - Đại họ Thái Nguyên đã tận tình giảng dạy và tạo mọi điều kiện thuận lợi ho tá giả trong quá trình họ tập tại trường. 3 Tá giả ũng xin hân thành ảm ơn Ban lãnh đạo Sở Giáo d và Đào tạo Quảng Ninh, Ban Giám hiệu và á thầy ô giáo Trường THPT Hoàng Quố Việt, nơi tá giả ông tá đã tạo những điều kiện thuận lợi nhất để tá giả hoàn thành nhiệm v họ tập. Tá giả ũng xin bày tỏ sự quý mến và lòng biết ơn sâu sắ tới Bố mẹ, gia đình và người thân đã luôn khuyến khí h, động viên tá giả trong suốt quá trình họ ao họ và viết luận văn này. Hà Nội, tháng 9/2009 Tá giả 4 Chương 1 Những kiến thứ về giải tí h lồi Chương này nhắ lại vắn tắt một số kiến thứ ơ bản, ần thiết về giải tí h lồi (tập lồi, hàm lồi và á tính hất) ph v ho tìm hiểu và nghiên ứu á bài toán tối ưu. Nội dung trình bày ở hương này hủ yếu dựa trên á tài liệu [1℄, [2℄. 1.1 Tập affin và tập lồi 1.1.1. Tập affine Cho x1, x2 là hai điểm trong Rn. Đường thẳng qua x1, x2 là tập á điểm x = λx1 + (1− λ)x2 = x2 + λ(x1 − x2) , λ ∈ R Tập M ⊆ Rn đượ gọi là tập affine nếu M hứa họn ả đường thẳng đi qua hai điểm bất kỳ thuộ M , tứ là ∀x1, x2 ∈ M , λ ∈ R ⇒ λx1 +(1−λ)x2 ∈ M . Nói á h khá , M là tập affine nếu nó hứa tổ hợp tuyến tính ủa hai điểm bất kỳ thuộ M với tổng á hệ số bằng 1. Ta gọi một điểm x ∈ R ó dạng x = k∑ i=1 λix i với λ1, λ2, ã ã ã , λk ∈ R và k∑ i=1 λi = 1 5 là tổ hợp affine ủa á điểm λ1, λ2, ã ã ã , λk ∈ Rn. Nếu M ⊆ Rn là một tập affine và x0 ∈ M thì tập L = M − x0 = {x− x0 | x ∈ M} là một không gian on, tứ là nếu a, b ∈ L thì mọi điểm c = λa + àb với λ, à ∈ R ũng thuộ L (L đóng với php ộng và php nhân vô hướng). Vì vậy, một tập affine ó thể biểu diễn bởi M = x0 + L = { x0 + v | v ∈ L}, trong đó x0 ∈ M và L là không gian on. Không gian on L tương ứng với tập affine M không ph thuộ vào á h họn x0, tứ x0 là điểm bất kỳ thuộ M . Hơn nữa, không gian on L này xá định duy nhất. Ta gọi L là không gian on song song với M . Thứ nguyên (dimension) hay òn gọi là số hiều ủa tập affine M là thứ nguyên ủa không gian on song song với nó. Bao affine (affine hull) ủa một tập E ⊆ Rn là giao ủa tất ả á tập affine hứa E. Đó là tập affine nhỏ nhất hứa E, kí hiệu là aff E. Ví d 1.1. Tập nghiệm M ủa hệ phương trình tuyến tính Ax = b, trong đó A là ma trận ấp m ì n và v tơ b ∈ Rm, là một tập affine. Thật vậy, với x1, x2 ∈ M , ∀λ ∈ R, ta ó A ( λx1 + (1− λ)x2) = λAx1 + (1− λ)Ax2 = λb + (1− λ)b = b ⇒ λx1 + (1− λ)x2 ∈ M Ví d 1.2. Bao affine ủa tập E = { x ∈ R3 | 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x3 = 0 } là mặt phẳng hứa hình vuông E,  thể aff E = { x ∈ R3 | x3 = 0 } . 1.1.2. Số hiều và điểm trong tương đối Số hiều (hay thứ nguyên) ủa một tập M ⊆ Rn là số hiều ủa bao affine ủa nó, ký hiệu là dimM . Cho tập M ⊆ Rn ó dimM < n. Một điểm a ∈ M đượ gọi là điểm trong tương đối (relative interior point) ủa M nếu tồn tại hình ầu mở B(a, ǫ) sao ho: ( B(a, ǫ) ∩ aff M) ⊂ M . Phần trong tương đối ủa tập M , ký hiệu là riM , là tập hứa tất ả á điểm trong tương đối ủa M . Một tập M ⊆ Rn đượ gọi là ó thứ nguyên đầy đủ nếu dimM = n. Dễ thấy rằng tập M ó phần trong khá rỗng (intM 6= ∅) khi và hỉ khi nó ó thứ nguyên đầy đủ. 6 Ví d 1.3. Cho E = { x ∈ R3 | 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x3 = 0 } , ta ó: intE = ∅, riE = {x ∈ R3 | 0 < x1 < 1, 0 < x2 < 1, x3 = 0}, và dimE = 2. 1.1.3. Tập lồi và điểm ự biên Cho hai điểm x1, x2 ∈ Rn. Tập tất ả á điểm ó dạng x = λx1 + (1− λ)x2 = x2 + λ(x1 − x2), 0 ≤ λ ≤ 1, đượ gọi là đoạn thẳng nối x1, x2, kí hiệu là [ x1, x2 ] . Tập M ⊆ Rn đượ gọi là tập lồi ( onvex set) nếu nó hứa họn đoạn thẳng nối hai điểm bất kỳ thuộ nó, tứ là ∀x1, x2 ∈ M , 0 ≤ λ ≤ 1 ta ó λx1 + (1− λ)x2 ∈ M . (b) ( ) (a) (d) Hình 1.1. (a), (b) - Tập lồi; ( ), (d) - Tập không lồi Từ định nghĩa dễ thấy rằng giao ủa một họ bất kỳ á tập lồi là tập lồi. Tuy nhiên hợp ủa á tập lồi hưa hắ là tập lồi. Ta gọi điểm x ∈ Rn ó dạng x = k∑ i=1 λix i với λ1, λ2, ã ã ã , λk ≥ 0 và k∑ i=1 λi = 1 là tổ hợp lồi ủa á điểm x1, x2, ã ã ã , xk ∈ Rn. Nếu λi ≥ 0 với ∀i = 1, 2, ã ã ã , k thì ta nói x là tổ hợp lồi hặt ủa x1, x2, ã ã ã , xk ∈ Rn. Mệnh đề 1.1. Một tập M ⊂ Rn là lồi khi và hỉ khi nó hứa tất ả á tổ hợp lồi ủa những phần tử thuộ nó. 7 Mệnh đề 1.2. a) NếuM ⊂ Rn là tập lồi và số thự α ∈ Rn thì αM = {y | y = αx, x ∈ M} ũng là tập lồi. b) Nếu M1,M2 ⊂ Rn là hai tập lồi thì M1 + M2 = { x | x = x1 + x2, x1 ∈ M1, x2 ∈ M2 } ũng là tập lồi. Bao lồi ( onvex hull) ủa tập E ⊂ Rn là giao ủa tất ả á tập lồi hứa E và đượ kí hiệu là convE. Đó là tập lồi nhỏ nhất hứa E. E convE convE Hình 1.2. Ví d về bao lồi Mệnh đề 1.3. Bao lồi ủa tập E ⊂ Rn hứa tất ả á tổ hợp lồi ủa á phần tử thuộ E. Cho tập lồi M ⊂ Rn. Một điểm x ∈ M đượ gọi là điểm ự biên (extreme point) ủa M nếu x không thể biểu diễn đượ dưới dạng tổ hợp lồi hặt ủa hai điểm phân biệt bất kỳ nào ủa M , tứ là 6 ∃y, z ∈ M, y 6= z sao ho x = λy + (1− λ)z, 0 < λ < 1. Theo định nghĩa, một điểm ự biên không thể là điểm trong ủa tập lồi. Vì vậy tất ả á điểm ự biên đều là á điểm biên. Nếu tập hợp không hứa biên thì nó không ó điểm ự biên. Mệnh đề 1.4. Một tập lồi đóng khá rỗng M ⊂ Rn ó điểm ự biên khi và hỉ khi nó không hứa họn một đường thẳng nào. 8 (a) (b) Hình 1.3. (a) - Hình vuông ó 4 điểm ự biên; (b) - Hình tròn ó vô số điểm ự biên Một đặ trưng rất quan trọng ủa tập lồi đóng và bị hặn là: Định lý 1.1. (Krein- Milman) Một tập lồi đóng, bị hặn trong R n là bao lồi ủa á điểm ự biên ủa nó. 1.1.4. Siêu phẳng, nửa không gian Cho a ∈ Rn \ {0} và α ∈ R. Tập H := {x ∈ Rn | = α} đượ gọi là một siêu phẳng (hyperplane). Đó là một tập affine ó số hiều bằng n− 1. Ta gọi v tơ a là v tơ pháp tuyến ủa siêu phẳng này. Cá tập x0 x a = α Hình 1.4. Siêu phẳng trong R 2 {x ∈ Rn | ≤ α} (hoặ {x ∈ Rn | ≥ α}) với a ∈ Rn \ {0} và α ∈ Rn là nửa không gian đóng và tập {x ∈ Rn | > α}) là nửa không gian mở xá định bởi siêu phẳng {x ∈ Rn | = α} Cho tập M ⊂ Rn, v tơ a ∈ Rn \ {0} và số thự α ∈ R. Ta gọi siêu phẳng H := {x ∈ Rn | = α} 9 là siêu phẳng tựa (supporting hyperplane) ủa M tại x0 ∈ M nếu x0 ∈ H và M nằm họn trong nửa không gian đóng xá định bởi H , tứ là = α và ≤ α, ∀x ∈ M . M a x0 Hình 1.5. Siêu phẳng tựa ủa M tại x0 Định lý 1.2. Qua mỗi điểm biên x0 ủa tập lồi M ⊂ Rn tồn tại ít nhất một siêu phẳng tựa ủa M tại x0. Định lý 1.3. Một tập lồi đóng khá rỗng M ⊂ Rn là giao ủa họ á nửa không gian tựa ủa nó. 1.1.5. Nón và nón lồi Tập M ⊂ Rn đượ gọi là nón ( one) nếu x ∈ M,λ ≥ 0 ⇒ λx ∈ M Một nón luôn hứa điểm gố 0 ∈ Rn. Tập M ⊂ Rn đượ gọi là nón lồi nếu M vừa là nón vừa là lồi, nghĩa là với bất kỳ x1, x2 ∈ M và λ1, λ2 ≥ 0 ta ó λ1x 1 + λ2x 2 ∈ M . 0 0 Hình 1.6. (a) - Nón lồi (b) - Nón không lồi Ví d 1.4. Cá tập sau đây là á nón lồi ó đỉnh tại gố 0 trong Rn: 10 • Rn+ := {x = (x1, x2, ã ã ã , xn) : xi ≥ 0, i = 1, 2, ã ã ã , n} (orthant không âm) • Rn++ := {x = (x1, x2, ã ã ã , xn) : xi > 0, i = 1, 2, ã ã ã , n} (orthant dương) Mệnh đề 1.5. Tập M ⊂ Rn là nón lồi khi và hỉ khi nó hứa tất ả á tổ hợp tuyến tính không âm ủa á phần tử ủa nó. Cho tập k v tơ v1, v2, ã ã ã , vk ∈ Rn. Tập cone { v1, v2, ã ã ã , vn} := {v ∈ Rn | v = k∑ i=1 λiv i, λi ≥ 0, i = 1, ã ã ã , k } ⊂ Rn đượ gọi là nón sinh bởi tập { v1, v2, ã ã ã , vk}. V tơ vh ∈ {v1, v2, ã ã ã , vk} gọi là không thiết yếu (non essential) nếu cone { v1, ã ã ã , vh−1, vh+1, ã ã ã , vk} = cone{v1, v2, ã ã ã , vk}. 0 0 v1 v2 v3 v1 v2 v3 (a) (b) Hình 1.7. (a) - V tơ v2 là không thiết yếu (b) - Hoặ v tơ v2 hoặ v tơ v3 là không thiết yếu 1.1.6. Phương lùi xa, phương ự biên Cho tập lồi khá rỗng D ⊆ Rn. V tơ d 6= 0 đượ gọi là phương lùi xa (re ession dire tion) ủa D nếu {x + λd | λ ≥ 0} ⊂ D với mỗi x ∈ D. Mọi nửa đường thẳng song song với một phương lùi xa d xuất phát từ một điểm bất kỳ ủa D đều nằm họn trong D. Rõ ràng rằng tập D không bị hặn khi và hỉ khi D ó một phương lùi xa. Tập tất ả á phương lùi xa ủa tập lồi D ⊆ Rn ùng v tơ 0 tạo thành một nón lồi. Nón lồi đó đượ gọi là nón lùi xa ủa tập D và kí hiệu là recD. 11 Ta nói hai phương d1 và d2 khá biệt (distin t) nếu d1 6= αd2 với α > 0. Phương lùi xa d ủa tập D đượ gọi là phương ự biên (extreme dire tion) ủa D nếu không tồn tại á phương lùi xa khá biệt d1 và d2 ủa D sao ho d = λ1d 1 + λ2d 2 với λ1, λ2 > 0. 1.1.7. Cá định lý tá h tập lồi Đây là những định lý ơ bản nhất ủa giải tí h lồi, là ông  hữu hiệu ủa lý thuyết tối ưu. Cho hai tập C,D ⊂ Rn và siêu phẳng H := {x ∈ Rn | = α} với a ∈ Rn \ {0} và α ∈ R Ta nói siêu phẳng H tá h hai tập C và D nếu ≤ α ≤ ∀x ∈ C, ∀y ∈ D và siêu phẳng H tá h hẳn (hay tá h hặt) hai tập C,D nếu ∀x ∈ C, ∀y ∈ D Định lý 1.4. (Định lý tá h I) Nếu hai tập lồi C,D ⊂ Rn không rỗng và rời nhau thì ó một siêu phẳng tá h húng. Định lý 1.5. (Định lý tá h II) Nếu hai tập lồi đóng C,D ⊂ Rn không rỗng, rời nhau và ít nhất một trong hai tập ấy là ompa thì ó một siêu phẳng tá h hẳn húng. Hệ quả 1.1. (Bổ đề Farkas) Cho v tơ a ∈ Rn và ma trận A ấp mì n. Khi đó, ≥ 0 với mọi x thoả mãn Ax ≥ 0 khi và hỉ khi ∃y ∈ Rn, y ≥ 0 sao ho a = ATy. Bổ đề Farkas ó rất nhiều ứng dng. Về mặt hình họ , bổ đề này hỉ ra rằng nón K = {x ∈ Rn | Ax ≥ 0} nằm hẳn trong nửa không gian {x ∈ Rn | ≥ 0} khi và hỉ khi v tơ pháp tuyến ủa siêu phẳng {x ∈ Rn | = 0} nằm trong nón sinh bởi á hàng ủa ma trận A. 1.1.8. Tập lồi đa diện Tập lồi đa diện P ⊆ Rn là giao ủa một số hữu hạn nửa không gian đóng. Nói á h khá , nó là tập nghiệm ủa một hệ hữu hạn á bất đẳng thứ tuyến 12 tính ≥ bi, i = 1, 2, ã ã ã , m. (1.1) Mỗi bất đẳng thứ trong (1.1) đượ gọi là một ràng buộ . Ràng buộ k ∈ {i = 1, 2, ã ã ã , m} là một ràng buộ thừa nếu{ x | ≥ bi, i = 1, 2, ã ã ã , m } = { x | ≥ bi, i ∈ {1, 2, ã ã ã , m} \ {k} } Ta kí hiệu A là ma trận ấp mìn với ai = (a1, a2, ã ã ã , an), i = 1, 2, ã ã ã , n, v tơ b = (b1, b2, ã ã ã , bm)T và x = (x1, x2, ã ã ã , xn)T thì hệ (1.1) đượ viết dưới dạng ma trận như sau Ax ≥ b Vì một phương trình tuyến tính ó thể biểu diễn tương đương bởi hai bất phương trình tuyến tính nên tập nghiệm ủa hệ phương trình và bất phương trình tuyến tính   < a i, x > = bi, i = 1, 2, ã ã ã , m1 ≥ bi, i = m1 + 1, ã ã ã , m ũng là một tập lồi đa diện. Dễ thấy rằng tập lồi đa diện là một tập lồi, đóng. Một tập lồi đa diện bị hặn đượ gọi là đa diện lồi hay gọi tắt là đa diện. a1 a2 a3 a4a 5 Hình 1.8. Đa diện này là giao ủa 5 nửa không gian Cho tập lồi đa diện D xá định bởi (1.1). Nếu điểm x0 ∈ D thoả mãn = bi, thì ta nói điểm x 0 thoả mãn hặt ràng buộ i. Tập 13 I(x0) := { i ∈ {1, 2, ã ã ã , m} = bi } là tập hợp á hỉ số á ràng buộ thoả mãn hặt tại x0 ∈ D. Mỗi điểm ự biên ủa tập lồi đa diện D đượ gọi là một đỉnh ủa D. Tập on lồi F 6= ∅ đượ gọi là một diện ủa D nếu F hứa một điểm trong tương đối ủa một đoạn thẳng nào đó thuộ D thì F hứa họn ả đoạn thẳng đó, nghĩa là y ∈ D, z ∈ D, x = λy + (1− λ)z ∈ F với 0 < λ < 1 ⇒ y ∈ F, z ∈ F 1.2 Hàm lồi 1.2.1. Định nghĩa hàm lồi và hàm lồi hặt Hàm f đượ gọi là hàm lồi ( onvex fun tion) xá định trên tập lồi D ⊆ Rn nếu với bất kỳ x1, x2 ∈ D và bất kỳ số thự λ ∈ [0, 1] ta ó f ( λx1 + (1− λ)x2) ≤ λf(x1) + (1− λ)f(x2). Ta gọi f là hàm lồi hặt (stri tly onvex fun tion) trên tập lồi D nếu f ( λx1 + (1− λ)x2) < λf(x1) + (1− λ)f(x2). với bất kỳ x1, x2 ∈ D, x1 6= x2 và bất kỳ số thự λ ∈ (0, 1). Miền xá định hữu hiệu ủa hàm f là dom f = {x ∈ D | f(x) < +∞} Epigraph (trên đồ thị) ủa hàm lồi f là tập hợp epi(f) := {(x, α) ∈ D ì R | x ∈ D, α ≥ f(x)}. Hàm lồi f : D −→ R∪{+∞} ó thể đượ mở rộng thành hàm lồi trên toàn không gian R n bằng á h đặt f(x) = +∞, ∀x /∈ dom f . Vì vậy để đơn giản, ta thường xt f là hàm lồi trên Rn. Mệnh đề 1.5. a) Hàm f xá định trên tập lồi khá rỗng D ⊆ Rn là hàm lồi khi và hỉ khi epi(f) là tập lồi. b) Hàm g xá định trên tập lồi khá rỗng D ⊆ Rn là hàm lõm khi và hỉ khi tập hypograph (dưới đồ thị) ủa nó là tập lồi, trong đó 14 hypo(g) := {(x, α) ∈ D ì R | x ∈ D, α ≤ g(x)}. (a) (b) Hình 1.9. (a) - Epigraph ủa một hàm lồi; (b) - Hypogrph ủa một hàm lõm 1.2.2. Cá php toán về hàm lồi Cho hàm lồi f1 xá định trên tập lồi D1 ⊆ Rn, hàm lồi f2 xá định trên tập lồi D2 ⊆ Rn và số thự λ > 0. Cá php toán λf1, f1 + f2, max{f1, f2} đượ định nghĩa như sau: (λf1)(x) := λf1(x), ∀x ∈ D1 (f1 + f2)(x) := f1(x) + f2(x), ∀x ∈ D1 ∩D2 max{f1, f2}(x) := max{f1(x), f2(x)}, ∀x ∈ D1 ∩D2 . Mệnh đề 1.6. Cho hàm f1 là lồi trên D1, f2 lồi trên D2 và hai số thự α > 0, β > 0. Khi đó, á hàm αf1 + βf2 và max{f1, f2} là lồi trên D1 ∩D2. 1.2.3. Tính liên t và đạo hàm theo hướng ủa hàm lồi Cho hàm lồi f xá định trên tập lồi mở D ⊆ Rn. Ta ó: Định lý 1.5. Nếu f là hàm lồi xá định trên tập lồi mở D ⊆ Rn thì f liên t trên D. Định lý 1.6. Nếu f : D −→ R là một hàm lồi xá định trên tập lồi D ⊆ Rn thì nó ó đạo hàm theo mọi hướng d ∈ R \ {0} tại mọi điểm x0 ∈ dom f và f ′(x0, d) ≤ f(x0 + d)− f(x0) Hệ quả 1.2. Nếu f là hàm lồi khả vi xá định trên tập lồi mở D thì f ó đạo hàm theo mọi hướng d ∈ R \ {0} tại mọi điểm x0 ∈ dom f và = f ′(x0, d) ≤ f(x0 + d)− f(x0) 15 1.2.4. Tiêu huẩn nhận biết hàm lồi khả vi Định lý 1.7. Cho f là hàm khả vi trên tập lồi mở D ⊆ Rn. Khi đó hàm f là hàm lồi trên D khi và hỉ khi f(y)− f(x) ≥ , ∀x, y ∈ D Ta đã biết với hàm một biến f xá định trên khoảng mở D = (a, b) ⊆ R thì f là hàm lồi trên D khi và hỉ khi f ′′(x) ≥ 0, ∀x ∈ D Định lý 1.8. Cho f là hàm khả vi hai lần trên tập lồi mở D ⊆ Rn. Khi đó f là hàm lồi trên D khi và hỉ khi ma trận Hesse ▽2f(x) là nửa xá định dương trên D, tứ với ∀x ∈ D thì yT ▽2 f(x)y ≥ 0, ∀y ∈ Rn Hàm f là hàm lồi hặt trên D nếu ▽2f(x) xá định dương trên D, tứ với mọi x ∈ D, thì yT ▽2 f(x)y > 0, ∀y ∈ Rn \ {0}. Hệ quả 1.3. Cho hàm toàn phương f(x) = 1 2 + + α, trong đó Q là ma trận vuông đối xứng ấp n, c ∈ Rn và α ∈ R. Khi đó, f là hàm lồi trên R n nếu Q là ma trận nửa xá định dương (f là hàm lồi hặt trên R n nếu Q là ma trận xá định dương). Ví d 1.5. Cho f(x1, x2) = 2x 2 1 + 3x1x2 + 4x 2 2. Ta ó: ▽f(x) =   4x1 3x2 3x1 8x2   ▽2f(x) =   4 3 3 8   Vì ma trận Hesses ▽2f(x) xá định dương nên hàm f đã ho là hàm lồi hặt trên R 2 . 16 Tóm lại, hương này đã nhắ lại á khái niệm về tập lồi (tập affine và bao affine, tập lồi và bao lồi, nón lồi và tập lồi đa diện, ùng với á khái niệm đỉnh, ạnh, diện ủa tập lồi đa diện) và á khái niệm về hàm lồi, hàm lồi hặt ùng một số tính hất ơ bản ủa húng. Nội dung trình bày trong hương sẽ ần đến ở á hương sau, khi nghiên ứu á bài toán phi tuyến nói hung và bài toán tối ưu với hàm thuần nhất dương nói riêng. 17 Chương 2 Cá bài toán tối ưu Chương này đề ập tới á bài toán tối ưu phi tuyến, bao gồm tối ưu địa phương và tối ưu toàn  , tối ưu không ràng buộ và tối ưu ó ràng buộ . Với mỗi loại bài toán ó xt đến á điều kiện ần và đủ ủa tối ưu. Nội dung ủa hương hủ yếu dựa trên á tài liệu [1℄, [2℄ và [3℄. 2.1 Cá khái niệm ơ bản Một bài toán tối ưu tổng quát đượ phát biểu như sau: min f(x) với x ∈ D (P1) hoặ max f(x) với x ∈ D (P2) trong đó D ⊆ Rn đượ gọi là tập nghiệm hấp nhận đượ hay tập ràng buộ và f : D −→ R là hàm m tiêu. Mỗi điểm x ∈ D đượ gọi là một nghiệm hấp nhận đượ hay một phương án hấp nhận đượ ( ó thể gọi tắt là một phương án). Điểm x∗ ∈ D mà −∞ < f(x∗) ≤ f(x), ∀x ∈ D đượ gọi là nghiệm tối ưu (nghiệm ự tiểu) hoặ nghiệm tối ưu toàn  (nghiệm ự tiểu toàn  - global minimizer), hoặ đơn giản hỉ là nghiệm 18 ủa bài toán (P1). Người ta òn gọi một nghiệm tối ưu là một phương án tối ưu hay lời giải ủa bài toán đã ho. Điểm x∗ ∈ D đượ gọi là nghiệm ự tiểu toàn  hặt (stri tly global minimizer) nếu f(x∗) < f(x), ∀x ∈ D và x 6= x∗ Không phải bài toán (P1) nào ũng ó nghiệm ự tiểu toàn  và nếu bài toán ó nghiệm ự tiểu toàn  thì hưa hắ ó nghiệm toàn  hặt. Nghiệm ự tiểu Nghiệm ự tiểu toàn  hặt toàn  không hặt Không ó nghiệm ự tiểu toàn  Hình 2.1. Giá trị tối ưu (hay giá trị ự tiểu) ủa bài toán (P1) đượ kí hiệu là minx∈D f(x) hoặ min{f(x) | x ∈ D} Nếu bài toán (P1) ó nghiệm tối ưu là x ∗ thì f(x∗) = min{f(x) | x ∈ D} Ta kí hiệu Agrmin{f(x) | x ∈ D} để hỉ tập nghiệm tối ưu ủa bài toán (P1). Nếu x ∗ là một nghiệm tối ưu ủa bài toán thì ó thể viết x∗ = agrmin{f(x) | x ∈ D} hay x∗ ∈ Agrmin{f(x) | x ∈ D}. Điểm x∗ ∈ D đượ gọi là nghiệm tối ưu địa phương hoặ nghiệm ự tiểu địa phương ủa bài toán (P1) nếu tồn tại một ǫ - lân ận B(x ∗, ǫ) ủa điểm x∗ ∈ D sao ho f(x∗) ≤ f(x), ∀x ∈ B(x∗, ǫ) ∩D Điểm x∗ ∈ D đượ gọi là nghiệm tối ưu địa phương hặt hoặ nghiệm ự tiểu địa phương hặt ủa bài toán (P1) nếu tồn tại một ǫ - lân ận B(x ∗, ǫ) ủa điểm x∗ ∈ D sao ho f(x∗) < f(x), ∀x ∈ B(x∗, ǫ) ∩D và x 6= x∗ 19 Hình 2.4. Nghiệm ự tiểu toàn  hặt Không ó nghiệm ự tiểu toàn  Nghiệm ự tiểu toàn  không hặt Người ta ũng thường phát biểu bài toán (P1) dưới dạng min{f(x) | x ∈ D} hoặ minx∈D f(x) hoặ f(x) −→ min với x ∈ D Tương tự, bài toán (P2) ũng thường phát biểu dưới dạng max{f(x) | x ∈ D} hoặ maxx∈D f(x) hoặ f(x) −→ max với x ∈ D Cá khái niệm tương tự ũng đượ định nghĩa ho bài toán (P2). C thể, nếu tồn tại một ǫ - lân ận B(x∗, ǫ) ủa điểm x∗ ∈ D sao ho f(x∗) ≥ f(x), ∀x ∈ B(x∗, ǫ) ∩D thì x∗ ∈ D đượ gọi là nghiệm tối ưu địa phương hoặ nghiệm ự đại địa phương ủa bài toán (P2). Nếu tồn tại một ǫ - lân ận B(x ∗, ǫ) ủa điểm x∗ ∈ D sao ho f(x∗) > f(x), ∀x ∈ B(x∗, ǫ) ∩D và x 6= x∗ thì x∗ đượ gọi là nghiệm tối ưu địa phương hặt hoặ nghiệm ự đại địa phương hặt ủa bài toán (P2). Điểm x∗ ∈ D thoả mãn f(x∗) ≥ f(x), ∀x ∈ D đượ gọi là nghiệm tối ưu hoặ nghiệm tối ưu toàn  hoặ nghiệm ự đại toàn  (global maximizer) hoặ hỉ đơn giản là nghiệm ủa bài toán (P2). Nếu x∗ ∈ D thoả mãn f(x∗) > f(x), ∀x ∈ D và x 6= x∗ thì ta gọi x∗ là nghiệm tối ưu toàn  hặt (stri tly global maximizer) ủa bài toán (P2). Giá trị tối ưu (hay giá trị ự đại) ủa bài toán (P2) đượ kí hiệu là 20 maxx∈D f(x) hoặ max{f(x) | x ∈ D} Tương tự như đối với bài toán (P1), ta kí hiệu Agrmax{f(x) | x ∈ D} là tập nghiệm tối ưu ủa bài toán P2. Nếu x ∗ là một nghiệm tối ưu ủa bài toán thì ó thể viết x∗ = agrmax{f(x) | x ∈ D} hoặ x∗ ∈ Agrmax{f(x) | x ∈ D}. Nhận xt 2.1. a) Bài toán (P1) tương đương với bài toán max −f(x) với x ∈ D theo nghĩa tập nghiệm tối ưu ủa hai bài toán này trùng nhau và giá trị tối ưu ủa húng thì ngượ dấu, tứ min{f(x) | x ∈ D} = −max{−f(x) | x ∈ D}. Vì vậy, không giảm tính tổng quát, ta hỉ ần xt bài toán (P1) hoặ bài toán (P2). b) Nếu D = Rn thì ta nói (P1) là bài toán tối ưu không ràng buộ . Ngượ lại, nếu D ⊂ Rn thì ta nói (P1) là bài toán tối ưu ó ràng buộ . Trong á bài toán tối ưu ó ràng buộ , tập D thường đượ xá định bởi D = {x ∈ Rn | gi(x) ≤ 0, i = 1, 2, ã ã ã , m}, (2.1) trong đó, gi(x), i = 1, 2, ã ã ã , m là á hàm thự xá định trên tập A ⊃ D (thông thường A = Rn). Ta gọi gi(x), i = 1, 2, ã ã ã , m là á hàm ràng buộ . Mỗi hệ thứ gi(x) ≤ 0, (i = 1, 2, ã ã ã , m) đượ gọi là một ràng buộ ủa bài toán. Vì ràng buộ gi(x) ≥ 0 ⇔ −gi(x) ≤ 0 và gi(x) =   gi(x) ≤ 0−gi(x) ≤ 0 nên rõ ràng biểu diễn (2.1) bao gồm hết á loại ràng buộ . Nhận xt 2.2. Nghiệm tối ưu toàn  ũng là nghiệm tối ưu địa phương nhưng điều ngượ lại hưa hắ đúng. Tuy nhiên, nếu D là tập lồi và f(x) là hàm lồi thì nghiệm tối ưu địa phương ủa bài toán (P1) ũng là nghiệm tối ưu toàn  21 ủa bài toán đó. C thể, ta ó Mệnh đề 2.1 Cho hàm lồi f : Rn → R và tập lồi khá rỗng D ⊂ Rn. Xt bài toán tối ưu min{f(x) | x ∈ D}. Khi đó: a) Nếu x∗ là nghiệm tối ưu địa phương ủa bài toán thì x∗ ũng là nghiệm tối ưu toàn  ; b) Nếu x∗ là nghiệm tối ưu địa phương hặt hoặ f là hàm lồi hặt thì x∗ ũng là nghiệm tối ưu toàn  duy nhất ủa bài toán. Nhận xt 2.3. Nếu bài toán (P1) không ó nghiệm tối ưu thì giá trị tối ưu ủa bài toán này, ký hiệu là inf f(D), là ận dưới lớn nhất (hay giá trị infimum) ủa hàm f trên D. Giả sử t0 = inf f(D) với t0 ∈ R ∪ {−∞}. Khi đó, f(x) ≥ t0, ∀x ∈ D và ∃{xk} ⊂ D sao ho lim k→∞ f(xk) = t0 Tương tự, nếu bài toán (P2) không ó nghiệm tối ưu thì giá trị tối ưu ủa bài toán này, ký hiệu là sup f(D), là ận trên nhỏ nhất (hay giá trị supremum) ủa hàm f trên D. Nếu t∗ = sup f(D) với t∗ ∈ R ∪ {+∞}. Khi đó, f(x) ≤ t∗, ∀x ∈ D và ∃{xk} ⊂ D sao ho lim k→∞ f(xk) = t∗ Ví d 2.1. Cho f(x) = cosx, x ∈ D = R. Khi đó, bài toán (P1) tương ứng ó vô số nghiệm tối ưu toàn  và Argmin{cos(x) | x ∈ D} = {x = (2k+1)π, k = 0,±1,±2, ã ã ã } và giá trị tối ưu là min{cos(x) | x ∈ R} = −1 Argmax{cos(x) | x ∈ D} = {x = 2kπ, k = 0,±1,±2, ã ã ã } và giá trị tối ưu là max{cos(x) | x ∈ R} = 1. Ví d 2.2. Cho f(x) = x1 và D = { x ∈ R2 | x12 + x22 ≤ 4, x12 ≥ 1 } . Hàm f ó nghiệm ự tiểu toàn  duy nhất trên D là x = (−2, 0)T và vô số nghiệm ự tiểu địa phương, đó là ả đoạn thẳng nối x = (1, √ 3)T và x = (1,−√3)T . Giá trị tối ưu ủa bài toán (P1) tương ứng là minx∈D f(x) = −2. Tương tự, x = (2, 0)T là nghiệm ự đại toàn  duy nhất ủa bài toán (P2) 22 tương ứng, tất ả những điểm nằm trong đoạn thẳng nối x = (−1,√3)T và x = (−1,−√3)T đều là nghiệm ự đại địa phương và giá trị tối ưu ủa bài toán (P2) tương ứng là maxx∈D f(x) = 2. −2 O 2 x1 x2 Hình 2.3 2.2 Bài toán tối ưu không ràng buộ Bài toán tối ưu phi tuyến không ràng buộ đượ phát biểu như sau: min f(x) với x ∈ Rn (P krb) trong đó f : Rn → R là một hàm phi tuyến. Định lý 2.1. (Điều kiện tối ưu bậ nhất) Cho hàm f xá định, khả vi liên t trên R n . Nếu x∗ ∈ Rn là nghiệm ự tiểu địa phương ủa bài toán (P krb) thì ▽f(x∗) = 0. Hệ quả 2.1. Giả sử f là hàm lồi khả vi trên Rn. Khi đó x∗ ∈ Rn là nghiệm ự tiểu toàn  ủa bài toán (P krb) khi và hỉ khi ▽f(x∗) = 0. Định lý 2.2. (Điều kiện tối ưu bậ hai) Giả sử hàm f hai lần khả vi liên t trên R n . Khi đó: a) Nếu x∗ ∈ Rn là điểm ự tiểu địa phương ủa f trên Rn thì ▽f(x∗) = 0 và ▽2f(x∗) nửa xá định dương; b) Ngượ lại, nếu 23 ▽f(x∗) = 0 và ▽2f(x∗) xá định dương thì x∗ là điểm ự tiểu địa phương hặt ủa f trên Rn. Ví d 2.3. Xt hàm số f(x1, x2) = e 3x2 − 3x1ex2 + x31. Ta ó ▽f(x) =   −3ex2 + 3x21 3e3x2 − 3x1ex2   và ▽2f(x) =   6x1 −3ex2 −3ex2 9e3x2 − 3x1ex2   tại x0 = (1, 0)T , ▽f(x0) =   0 0   và ▽2f(x0) =   6 −3 −3 6   Vì ▽f(x0) = 0 và ▽2f(x0) là ma trận xá định dương nên x0 = (1, 0)T là điểm ự tiểu địa phương hặt ủa f trên R2. Ta ó, f(1, 0) = −1 > f(−3, 0) = −17. Vậy x0 không phải là điểm ự tiểu toàn  ủa f trên R2. Ví d 2.4. Giải bài toán tối ưu không ràng buộ (P krb) với n = 2 và hàm m tiêu f(x1, x2) = x 2 1 + x1x2 + x 2 2 + 3(x1 + x2 − 2) Giải: Ta ó ▽f(x) =   2x1 + x2 + 3 x1 + 2x2 + 3   Giải hệ phương trình ▽f(x) = 0 ta nhận đượ điểm dừng ủa f trên R2 là x∗ = (−1,−1)T . Vì ▽2f(x∗) =   2 1 1 2   24 là ma trận đối xứng, xá định dương nên f(x) là hàm lồi hặt và điểm dừng x∗ = (−1,−1)T là nghiệm ự tiểu ủa bài toán đang xt. Hơn nữa, x∗ là nghiệm ự tiểu duy nhất ủa bài toán này. 2.3 Bài toán tối ưu ó ràng buộ Bài toán tối ưu phi tuyến ó ràng buộ đượ phát biểu như sau: min{f(x) | x ∈ D} (P rb) trong đó D ⊂ Rn và f : D → R là hàm số xá định trên D 2.3.1. Nón tiếp xú và điều kiện tối ưu Định nghĩa 2.1. Cho dãy {xk} ⊂ Rn hội t đến x0 ∈ Rn. Ta nói dãy {xk} hội t đến x0 theo hướng v ∈ Rn và viết {xk} v−→ x0 nếu tồn tại dãy số dương tk, lim k→∞ tk = 0 sao ho x k = x0 + tkv + 0(tk) Định nghĩa 2.2. Cho D ⊂ Rn, tập tất ả á hướng v ∈ Rn sao ho nó ó một dãy {xk} ⊂ D hội t đến x0 theo hướng v tạo thành một nón. Ta gọi đó là nón tiếp xú với D tại x0, kí hiệu là T (D, x0), nghĩa là T (D, x0) = { v ∈ Rn | ∃{xk} ⊂ D : {xk} v−→ x0} Nhận xt 2.3. a) Nếu x0 ∈ intX thì T (D, x0) = Rn b) Nếu D ⊂ Rn là tập lồi đóng thì T (D, x0) = cone{(x− x0) | x ∈ D} Bổ đề 2.1. Giả sử {xk} là một dãy thuộ D ⊂ Rn hội t đến x0 ∈ D theo hướng v và f là hàm khả vi liên t ấp một trên D. Khi đó = lim tk→0+ f(xk)− f(x0) tk Định lý 2.3. a) Giả sử f khả vi trên một tập mở hứa D. Nếu x0 ∈ D là nghiệm ự tiểu địa phương ủa bài toán (P rb) thì 25 ≥ 0, ∀v ∈ T (D, x0) b) Ngượ lại, nếu x0 ∈ D thoả mãn điều kiện > 0, ∀v ∈ T (D, x0) thì x0 là một nghiệm tối ưu địa phương hặt ủa bài toán (P rb). Một điểm x0 ∈ D thoả mãn ≥ 0, ∀v ∈ T (D, x0) đượ gọi là một điểm dừng hay điểm tới hạn ủa hàm f trên D. Ví d 2.5. Xt bài toán min { f(x1, x2) = x 2 1 − x22 |._.