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

đại học Thái Nguyên Tr•ờng đại học khoa học -------------  0  ------------- Nguyễn Xuân Huy Bài toán tối •u với hàm thuần nhất d•ơng Luận văn thạc sĩ toán học Thái Nguyên - 2009 Số húa bởi Trung tõm Học liệu – Đại học Thỏi Nguyờn đại học Thái Nguyên Tr•ờng đại học khoa học -------------  0  ------------- Nguyễn Xuân Huy Bài toán tối •u với hàm thuần nhất d•ơng Chuyên ngành: Toán ứng dụng Mã số: 60.46.36 Luận văn thạc sĩ toán học Ng•ời h•ớng dẫn khoa học 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 | x21 + x22 ≤ 1 } Tập hấp nhận đượ ủa bài toán là hình tròn đóng B(0, 1), tâm O, bán kính 1. Ta ó ▽f(x) = (2x1,−2x2)T và ▽f(x0) = 0 với x0 = (0, 0)T . Vì x0 ∈ intB(0, 1) nên T(B(0, 1), x0) = R2 và ≥ 0, ∀v ∈ T (B(0, 1), x0). Tuy nhiên, x0 = (0, 0)T không phải là nghiệm ự tiểu địa phương ủa bài toán đang xt vì f(0,±ǫ) = −ǫ2 0. Hệ quả 2.2. Giả sử x0 ∈ intX và x0 là điểm ự tiểu địa phương ủa bài toán (P rb). Khi đó, ▽f(x0) = 0. Định lý 2.4. Cho f là hàm lồi khả vi trên một tập mở hứa tập lồi D ⊂ Rn. Điều kiện ần và đủ để x∗ ∈ D là điểm ự tiểu toàn  ủa bài toán tối ưu lồi min{f(x) | x ∈ D} là ≥ 0, ∀v ∈ T (D, x∗) Ví d 2.6. Xt bài toán min { f(x1, x2) = x 2 1 + x 2 2 | x21 + x22 ≤ 1 } Tập hấp nhận đượ ủa bài toán là hình tròn đóng B(0, 1). Ta ó ▽f(x) = (2x1, 2x2) T và ▽f(x0) = 0 với x0 = (0, 0)T . Dễ thấy ma trận Hess ▽f(x)2 là xá định dương nên hàm m tiêu f(x) là hàm lồi hặt. Hệ quả 2.3. Cho f là hàm lồi khả vi trên một tập mở hứa tập lồi D ⊂ Rn. Điểm x∗ ∈ D là điểm ự tiểu toàn  ủa bài toán lồi min{f(x) | x ∈ D} khi và hỉ khi ≥ 0, ∀x ∈ D 26 2.3.2. Điều kiện tối ưu Karush - Kuhn - Tu ker (điều kiện KKT) Xt bài toán tối ưu phi tuyến min{f(x) | x ∈ D} (NLP) với D ⊂ Rn là tập nghiệm ủa hệ phương trình phi tuyến  gi(x) ≤ 0, i = 1, 2, ã ã ã , mhj(x) = 0, j = 1, 2, ã ã ã , p trong đó f, gi, hj : R n → R là những hàm số khả vi ho trướ . Cho x0 ∈ D là một nghiệm hấp nhận đượ ủa bài toán (NLP). Đặt I(x0) = { i ∈ {1, ã ã ã , m} | gi(x0) = 0 } là tập hỉ số ủa á ràng buộ gi(x 0) ≤ 0 (i = 1, ã ã ã , m) thoả mãn hặt tại x0. Kí hiệu S(x0) là tập hợp á v tơ v ∈ Rn thoả mãn hệ tuyến tính  < ▽gi(x 0), v > ≤ 0, i ∈ I(x0) = 0, j = 1, 2, ã ã ã , p. ó thể hứng minh rằng với ∀x0 ∈ D ta ó T (D, x0) ⊆ S(x0). Định nghĩa 2.3. Ta nói điều kiện hính quy (regular ondition) đượ thoả mãn tại x0 ∈ D nếu T (D, x0) = S(x0) Định lý 2.5. Điều kiện hính quy đượ thoả mãn tại x0 nếu ó một trong á điều kiện sau: a) Cá hàm gi, i = 1, ã ã ã , m và hj , j = 1, ã ã ã , p đều là á hàm affine; b) Cá hàm gi, i = 1, ã ã ã , m là lồi, hj, j = 1, ã ã ã , p là affine và điều kiện Slater sau đây đượ thoả mãn: ∃ x ∈ Rn : gi(x) < 0 (∀i) và hj(x) = 0 (∀j); 27 ) Cá v tơ ▽gi(x0), i ∈ I(x0) và ▽hj(x0), j = 1, ã ã ã , p là độ lập tuyến tính. Định lý 2.6. (Karush-Kuhn-Tu ker) Cho f, gi, i = 1, ã ã ã , m và hj , j = 1, ã ã ã , p là á hàm khả vi liên t trên một tập mở hứa D. Giả sử x∗ là điểm ự tiểu địa phương ủa bài toán (NLP) và điều kiện hính quy đượ thoả mãn tại x∗. Khi đó, điều kiện Karush-Kuhn-Tu ker (KKT) sau đượ thoả mãn: a) Tồn tại á số λ∗i ≥ 0, i = 1, ã ã ã , m và á số à∗j , j = 1, ã ã ã , p sao ho ▽f(x∗) + m∑ i=1 λ∗i ▽ gi(x∗) + p∑ j=1 à∗j ▽ hj(x∗) = 0 b) λ∗i gi(x ∗) = 0, ∀i = 1, ã ã ã , m (điều kiện bù) ) gi(x ∗) ≤ 0, i = 1, ã ã ã , m, hj(x∗) = 0, j = 1, ã ã ã , p (điều kiện hấp nhận đượ , nghĩa là x∗ ∈ D) Nhận xt 2.4. a) Điểm x∗ ∈ Rn thoả mãn điều kiện KKT đượ gọi là một điểm KKT ủa bài toán (NLP) tương ứng, b) Nếu x∗ là một nghiệm ự tiểu địa phương ủa bài toán (NLP) và tại đó thoả mãn điều kiện hính quy thì x∗ là điểm KKT, nhưng điều ngượ lại hưa hắ đúng. Ví d 2.7. Xt bài toán min −x21 − x22 với điều kiện x1 ≤ 1 Bài toán này thuộ lớp bài toán tối ưu phi tuyến (NLP) và hàm m tiêu min −x21 − x22 lõm hặt. Vì g(x) = x1 − 1 là hàm affine nên điều kiện hính quy thoả mãn tại mọi điểm hấp nhận đượ ủa bài toán. Ta ó: ▽f(x) =   −2x1 −2x2   và ▽g1(x) =   1 0   28 Điều kiện KKT tương ứng ủa bài toán này là  ▽f(x) + λ1 ▽ g1(x) = 0 λ1g1(x) = 0, λ1 ≥ 0 g1 = x1 − 1 ≤ 0 ⇔   −2x1 + 1λ1 = 0 −2x2 + 0λ1 = 0 λ1(x1 − 1) = 0, λ1 ≥ 0 x1 − 1 ≤ 0 Giải hệ này ta nhận đượ hai điểm KKT là x1 = (0, 0) T ứng với λ1 = 0 và x2 = (1, 0) T ứng với λ1 = 2. Dễ thấy x1 = (0, 0) T là nghiệm ự đại toàn  ủa bài toán đang xt, òn điểm x1 = (0, 0) T không phải là nghiệm ự tiểu địa phương ũng không phải là nghiệm ự đại địa phương (x2 là điểm yên ngựa). 2.3.3. Hàm Lagrange và điều kiện tối ưu KKT Hàm số L(x, λ, à) = f(x) = λTg(x) + àTh(x); trong đó λ = (λ1, ã ã ã , λm)T ≥ 0, à = (à1, ã ã ã , àp)T , g(x) = (g1(x), ã ã ã , gm(x)) T , h(x) = (h1(x), ã ã ã , hp(x))T gọi là hàm Lagrange tương ứng với bài toán (NLP). Cá số λ1 ≥ 0, λ2 ≥ 0, ã ã ã , λm ≥ 0, à1, à2, ã ã ã , àp đượ gọi là á nhân tử Lagrange. Kí hiệu ▽xL,▽λL,▽àL là gradient ủa hàm L theo x, λ, à tương ứng. Khi đó, định lý 2.6 đượ phát biểu theo ngôn ngữ hàm Lagrange như sau. Định lý 2.7. Cho f, gi (i = 1, ã ã ã , m), hj (j = 1, ã ã ã , p) là á hàm khả vi liên t trên R n . Giả sử x∗ là điểm ự tiểu địa phương ủa bài toán (NLP) và tại x∗ điều kiện hính quy đượ thoả mãn. Khi đó, ó á điều kiện: a) Tồn tại á số λ∗i ≥ 0, i = 1, ã ã ã , m và á số à∗j , j = 1, ã ã ã , p sao ho ▽xL(x∗, λ∗, à∗) = ▽f(x∗) + m∑ i=1 λ∗i ▽ gi(x∗) + p∑ j=1 à∗j ▽ hj(x∗) = 0 29 b) λ∗i gi(x ∗) = 0, ∀i = 1, ã ã ã , m (điều kiện bù) ) ▽λL(x∗, λ∗, à∗) = g(x∗) = (g1(x∗), ã ã ã , gm(x∗))T ≤ 0 ▽àL(x∗, λ∗, à∗) = h(x∗) = (h1(x∗), ã ã ã , hp(x∗))T = 0 (x∗ ∈ D) Nhận xt 2.5. Giả sử f, gi (i = 1, ã ã ã , m), hj (j = 1, ã ã ã , p) là á hàm hai lần khả vi liên t trong lân ận ủa điểm x∗ và x∗ là một điểm KKT ủa bài toán (NLP). Khi đó, với d ∈ Rn ó ‖ d ‖ đủ nhỏ, khai triển Taylor ủa hàm Lagrange tại (x∗, λ, à) là L(x∗ + d, λ, à) = L(x∗, λ, à) + dT (▽x(x∗, λ, à) + 12dT ▽2 L(ξ, λ, à)d = L(x∗, λ, à) + 12d T ▽2 L(ξ, λ, à)d, trong đó x∗ ≤ ξ ≤ x∗ + d, λ = (λ1, ã ã ã , λm)T , à = (à1, ã ã ã , àp)T . Như đã biết nếu ma trận ▽2L(x∗, λ, à) nửa xá định dương thì ▽2L(ξ, λ, à) ũng nửa xá định dương và x∗ là một nghiệm ự tiểu địa phương hặt ủa (NLP). 2.3.4. Bài toán tối ưu lồi Xt bài toán tối ưu lồi sau đây min{f(x) | x ∈ D} (CP) trong đó D = {x ∈ Rn | gi(x) ≤ 0, i = 1, 2, ã ã ã , m, hj(x) = 0, j = 1, 2, ã ã ã , p} với f, gi (i = 1, 2, ã ã ã , m) là á hàm lồi khả vi và hj , (j = 1, 2, ã ã ã , p) là hàm affine. Khi đó, ta ó điều kiện tối ưu ( ần và đủ) ho nghiệm ự tiểu ủa bài toán quy hoạ h lồi (CP) như sau. Định lý 2.8. Giả sử f và gi, (i = 1, 2, ã ã ã , m) là á hàm lồi, khả vi liên t trên một tập mở hứa D và điều kiện Slater đượ thoả mãn. Khi đó x∗ ∈ Rn là nghiệm ự tiểu ủa bài toán (CP) khi và hỉ khi thoả mãn á điều kiện: a) Tồn tại á số λ∗i ≥ 0, i = 1, ã ã ã , m, à∗j , j = 1, ã ã ã , p sao ho ▽xL(x∗, λ∗, à∗) = ▽f(x∗) + m∑ i=1 λ∗i ▽ gi(x∗) + p∑ j=1 à∗j ▽ hj(x∗) = 0 b) λ∗i gi(x ∗) = 0, ∀i = 1, ã ã ã , m (điều kiện bù) ) ▽λL(x∗, λ∗, à∗) = g(x∗) = (g1(x∗), ã ã ã , gm(x∗))T ≤ 0 ▽àL(x∗, λ∗, à∗) = h(x∗) = (h1(x∗), ã ã ã , hp(x∗))T = 0 (x∗ ∈ D) 30 Tóm lại, hương này đã trình bày vắn tắt á khái niệm và kết quả ơ bản ủa 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. 31 Chương 3 Bài toán tối ưu với hàm thuần nhất dương Hàm thự thuần nhất thường gặp trong nhiều ứng dng, đặ biệt trong nghiên ứu kinh tế vi mô. Chương này đề ập đến á hàm thuần nhất dương ( òn gọi đơn giản là hàm thuần nhất) và xt bài toán tối ưu với á hàm đặ biệt này. Tiếp đó giới thiệu những kết quả đáng hú ý ủa bài toán, dựa trên á phương pháp và ông  tối ưu đã đề ập ở hương trướ . Nội dung trình bày ở hương này hủ yếu dựa trên á tài liệu [3℄, [4℄ và [5℄. 3.1 Hàm thuần nhất Định nghĩa 3.1. Hàm thự f : Rn → R gọi là hàm thuần nhất bậ k nếu f(tx) = tkf(x), ∀t > 0. Hàm thuần nhất bậ k = 1 òn gọi là hàm thuần nhất tuyến tính f(tx) = tf(x), ∀t > 0. Hàm thuần nhất bậ k = 0 nếu f(tx) = f(x), ∀t > 0. Tính thuần nhất là một đặ trưng toàn  (đúng với mọi x ∈ Rn). 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, nếu hàm là thuần nhất bậ 1 thì khi tăng gấp đôi (gấp ba) mọi biến thì giá trị ủa hàm ũng tăng lên gấp đôi (gấp ba). 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. 32 Ví d 3.1. Hàm Cobb-Douglas ó dạng f(x1, x2) ≡ Axα1xβ2 , A > 0, α > 0, β > 0. Đây là hàm thuần nhất bậ α + β > 0. Thật vậy, f(tx1, tx2) ≡ A(tx1)α(tx2)β ≡ tαtβAxα1xβ2 ≡ tα+βf(x1, x2). Nếu α và β thoả mãn α + β = 1 thì đó là hàm thuần nhất bậ 1. Ví d 3.2. Có thể xt hàm thuần nhất trên một nón K ⊂ Rn a) Hàm f(x1, x2, x3) = √ x1 + 2x2 + 3x3 là thuần nhất bậ 1 2 trên K = R 3 + vì f(tx1, tx2, tx3) = √ tx1 + 2tx2 + 3tx3 = √ t. √ x1 + 2x2 + 3x3 = t 1 2f(x1, x2, x3). b) Hàm f(x1, x2) = x31 + 2x 2 1x2 − 3x32 x21 + x 2 2 là hàm thuần nhất bậ 1 trên K = R2+, vì f(tx1, tx2) = (tx1) 3 + 2(tx21)(tx2)− 3(tx2)3 (tx1)2 + (tx2)2 = t.f(x1, x2). ) Hàm f(x1, x2) = (x1 − x2). 3 √ x21 + x 2 2 là thuần nhất bậ 5 3 trên K = R 2 +, vì f(tx1, tx2) = (tx1 − tx2). 3 √ (tx1)2 + (tx2)2 = t. 3 √ t2(x1 − x2). 3 √ x21 + x 2 2 = t 5 3 .f(tx1, tx2). Từ định nghĩa hàm thuần nhất dễ dàng suy ra: 1. Nếu f(x1, x2, ã ã ã , xn) là hàm thuần nhất bậ k thì F (x1, x2, ã ã ã , xn) = [ f(x1, x2, ã ã ã , xn) ]q là hàm thuần nhất bậ kq. 2. Nếu f(x1, x2, ã ã ã , xn) là hàm thuần nhất bậ k và g(x1, x2, ã ã ã , xn) là hàm thuần nhất bậ r thì: 33 a. Tí h f(x1, x2, ã ã ã , xn) ì g(x1, x2, ã ã ã , xn) là một hàm thuần nhất bậ k + r. b. Thương f(x1, x2, ã ã ã , xn)/g(x1, x2, ã ã ã , xn) là một hàm thuần nhất bậ k − r. Ta hú ý một số lớp hàm thuần nhất quan trọng: • Dạng thứ tuyến tính f(x) = cTx với c ∈ Rn(K = Rn và k = 1) • Hàm tựa SC(x) = supy∈C xTy với C ⊆ Rn(K = Rn \ {0} và k = 1) • Dạng toàn phương f(x) = 1 2 xTQx với Q ∈ Rnìn(K = Rn và k = 2) • Đa thứ thuần nhất bậ d (K = Rn và k = d), v.v ... Định lý 3.1. Hàm thuần nhất tuyến tính f : Rn → (−∞,+∞] là lồi khi và hỉ khi f(x + y) ≤ f(x) + f(y) ∀x, y ∈ Rn. Chứng minh. a) Giả sử hàm thuần nhất tuyến tính f là lồi. Lấy bất kỳ x, y ∈ Rn. Khi đó f(x + y) = 2f ( 1 2 x + 1 2 y ) ≤ 2 [ 1 2 f(x) + 1 2 f(y) ] = f(x) + f(y). b) Ngượ lại, giả sử f(x + y) ≤ f(x) + f(y) ∀x, y ∈ Rn. Lấy bất kỳ (xi, ti) ∈ epi f (i = 1, 2) ta ó (x1 + x2, t1 + t2) ∈ epi f , bởi vì f(x1 + x2) ≤ f(x1) + f(x2) ≤ t1 + t2. Hơn nữa, f là hàm thuần nhất tuyến tính nên nếu (x, t) ∈ epi f thì f(x) ≤ t và λf(x) = f(λx) ≤ λt (0 < λ < ∞) ⇒ λ(x, t) ∈ epi f. Như vậy epi f đóng đối với php ộng và php nhân vô hướng, nghĩa là epi f là một nón lồi. Vậy f là hàm lồi. Hệ quả 3.1. Giả sử f là hàm lồi hính thường, thuần nhất tuyến tính. Khi đó, ∀xi ∈ Rn, ∀λi > 0, i = 1, ã ã ã , m (Chứng minh theo quy nạp): f(λ1x 1 + ã ã ã+ λmxm) ≤ λ1f(x1) + ã ã ã+ λmf(xm). 34 Hệ quả 3.2. Giả sử f là hàm lồi hính thường, thuần nhất tuyến tính. Khi đó, f(x) + f(−x) ≥ 0 (∀x ∈ Rn). Chứng minh. áp dng Định lý 2.2 với y = −x ta sẽ ó f(x) + f(−x) ≥ f(x− x) = f(0) = 0 với mọi x ∈ Rn. Một đặ 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. Định lý sau nói rõ điều này. Định lý 3.2. Đạo hàm riêng ủa hàm thuần nhất (Partial Derivatives of Homogeneous Fun tion) Nếu f(x) là hàm thuần nhất bậ k thì á đạo hàm riêng ủa nó là hàm thuần nhất bậ k − 1. Nói á h khá , ▽f : Rn → Rn là hàm thuần nhất bậ k − 1. Chứng minh. Giả sử f(x) là hàm thuần nhất bậ k. Khi đó: f(tx) ≡ tkf(x) ∀t > 0. (P.1) Lấy đạo hàm vế trái theo xj ta ó: ∂ ∂xj (f(tx)) = ∂f(tx) ∂xj = ∂f(tx) ∂xj ∂(tx) ∂xj = ∂f(tx) ∂xj t, (P.2) Lấy đạo hàm vế phải theo xj ta đượ : ∂ ∂xj (tkf(x)) = tk ∂f(x) ∂xj (P.3) Do (P.1) là một đồng nhất thứ nên (P.2) phải bằng (P.3) nghĩa là ∂f(tx) ∂xj t = tk ∂f(x) ∂xj Chia ả hai vế ho t ta nhận đượ ∂f(tx) ∂xj = tk−1 ∂f(x) ∂xj với  = 1, 2, ã ã ã , n và ∀t > 0. Định lý đượ hứng minh. 35 Nhiều ứng dng thường gặp khi hàm là thuần nhất bậ 1. Ta ghi lại kết quả này như một hệ quả trự tiếp. Hệ quả 3.3. Hàm thuần nhất tuyến tính (Linear Homogeneous Fun tion) Nếu f(x) là hàm thuần nhất bậ 1 thì ∂f(tx) ∂xj = ∂f(x) ∂xj với mỗi  = 1, 2, ã ã ã , n và ∀t > 0. Hệ quả nói rằng nếu hàm là thuần nhất tuyến tính thì khi tăng mọi biến theo ùng mọt tỉ lệ, tất ả n đạo hàm riêng ủa hàm sẽ không thay đổi. Ta hãy kiểm tra lại tính hất này đối với hàm Cobb-Douglas. Ví d 3.3. Giả sử f(x1, x2) = Ax α 1x β 2 và α + β = 1, vì thế hàm là thuần nhất tuyến tính ∂f(x1, x2) ∂x1 = αAxα−11 x β 2 Nhân x1, x2 với t và lấy đạo hàm riêng theo x1 tại (tx1, tx2) ta nhận đượ ∂f(tx1, tx2) ∂x1 = αA(tx1) α−1(tx2)β = tα+β−1αAxα−11 x β 2 = ∂f(x1, x2) ∂x1 do α+β = 1 nên tα+β−1 = t0 = 1. Đạo hàm riêng theo biến x2 ũng tương tự. Tính hất uối ùng ủa hàm thuần nhất đượ nêu hi tiết trong định lý Euler, đôi khi gọi là định lý ộng (Adding-up Theorem): Hàm thuần nhất ó thể biểu diễn đượ theo á đạo hàm riêng ủa nó. Ta ũng nhận đượ kết quả quan trọng đối với hàm tuyến tính thuần nhất. Định lý 3.3. Định lý Euler (Euler's Theorem) 1. Nếu f(x) là hàm thuần nhất bậ k thì kf(x) = n∑ j=1 ∂f(x) ∂xj xj = , ∀x ∈ Rn. 2. Nói riêng, nếu f(x) là hàm thuần nhất bậ 1 thì f(x) = n∑ j=1 ∂f(x) ∂xj xj = , ∀x ∈ Rn. 36 Chứng minh. Giả thiết f(x) là hàm thuần nhất bậ k. Theo định nghĩa tkf(x) = f(tx) ∀t > 0 Cá h hứng minh là xem đồng nhất thứ này như một hàm ủa t, rồi lấy vi phân hai vế ủa nó theo t. Trướ hết lấy vi phân vế trái ta đượ : ktk−1f(x). (P.1) Khi lấy vi phân vế phải đối với t ta ần nhớ rằng f ph thuộ n biến và t tá động vào tất ả n biến này. Ta ần xem hàm f ó dạng f(g1(t), ã ã ã , gn(t)) với gj(t) ≡ txj, áp dng quy tắ lấy đạo hàm ủa hàm hợp ta đượ n∑ j=1 ∂f(tx1, ã ã ã , txn) ∂xj ∂(txj) ∂t . Nhưng ∂(txj) ∂t = xj, vì thế biểu thứ này trở thành n∑ j=1 ∂f(tx) ∂xj xj. (P.2) Php lấy vi phân bảo toàn đẳng thứ , vì thế (P.1) và (P.2) bằng nhau: ktk−1f(x) = n∑ j=1 ∂f(tx) ∂xj xj. Đẳng thứ này đúng với mọi t > 0. Đặt t = 1 ta đượ kf(x) = n∑ j=1 ∂f(x) ∂xj xj. Đó là điều ần hứng minh. Phần hai là trường hợp riêng khi k = 1. 37 3.2 Bài toán tối ưu với hàm thuần nhất dương Xt bài toán quy hoạ h phi tuyến (NLP) ó dạng: min{f(x) : x ∈ K, gi(x) ≤ bi, i = 1, 2, ã ã ã , m} với f, gi : K → Rn là hàm thuần nhất dương bậ p, qi trên nón mở K ⊆ Rn. Một số trường hợp riêng quan trọng ủa bài toán (P): • Quy hoạ h tuyến tính: f(x) = → min gi(x) =< a i, x > ≤ bi, i = 1, ã ã ã , m ( bậ p = 1, qi = 1) với ai, c ∈ Rn và b ∈ Rm ho trướ . • Quy hoạ h bậ hai với ràng buộ tuyến tính: f(x) = 1 2 → min gi(x) = 1 2 ≤ bi, i = 1, ã ã ã , m ( bậ p = 2, qi = 1) với ai ∈ Rn, b ∈ Rm và Q0 ∈ Rnìn ho trướ . • Quy hoạ h bậ hai với ràng buộ bậ hai (dùng trong kỹ thuật): f(x) = 1 2 → min gi(x) = 1 2 ≤ bi, i = 1, ã ã ã , m ( bậ p = 2, qi = 2) với ai ∈ Rn, b ∈ Rm và Q0, Qi ∈ Rnìn ho trướ . 3.3 Cá kết quả đối ngẫu hính 3.3.1. Điều kiện tối ưu KKT Bài toán (P ) đối với biến x ∈ Rn sẽ đượ lồng trong bài toán mới (P̂ ) đối với á biến (x, u) ∈ Rn+1 như sau (giả thiết p 6= 0): (P̂ ) min { u.f(x) : x ∈ K, [gi(x)−bi(1−q p ) ] u ≤ q p bi, i = 1, 2, ã ã ã , m, u ≥ 0 } 38 Định lý 3.4. Giả sử f và gi, i = 1, 2, ã ã ã , m, khả vi trên K . Khi đó: a) Nếu x∗ ∈ K là điểm KKT ủa (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ thì (x∗, 1) là điểm KKT ủa (P̂ ) tương ứng với nhân tử Lagrange (λ∗, 0) ∈ Rm+1+ . b) Nếu (x, u) là điểm KKT ủa (P̂ ) tương ứng với nhân tử Lagrange (λ, à) ∈ R m+1 + và nếu u > 0 thì u = 1 và x ∗ := x là điểm KKT ủa (P ) tương ứng với nhân tử Lagrange λ∗ := λ ∈ Rm+ . Chứng minh. Hàm Lagrange ủa hàm bài toán (P̂ ) là L(x, u, λ, à) = uf(x)+ m∑ i=1 λi {[ gi(x)−bi(1−p q ) ] u−p q bi } −àu, à ≥ 0, λi ≥ 0. Điểm (x, u) ∈ Rn ì R là điểm KKT ủa (P̂ ) nếu u ≥ 0 và [gi(x)− bi(1− q p ) ] u ≤ q p bi, ∀i = 1, 2, ã ã ã , m, (3.1) và ó tồn tại nhân tử Lagrange (λ, à) ∈ Rm+1+ sao ho [▽ f(x) + m∑ i=1 (λi ▽ gi(x) ] u = 0 (3.2) f(x) + m∑ i=1 λi [ gi(x)− bi(1− q p ) ] = à (3.3) λi {[ gi(x)− bi(1− q p ) ] u− q p )bi } = 0, ∀i = 1, 2, ã ã ã , m, (3.4) u.à = 0. (3.5) a) Giả sử x∗ ∈ K là điểm KKT ủa (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ , nghĩa là gi(x ∗) ≤ bi, ∀i = 1, 2, ã ã ã , m , (3.6) 39 ▽f(x∗) + m∑ i=1 λ∗i ▽ gi(x∗) = 0, (3.7) λ∗i [gi(x ∗)− bi] = 0, ∀i = 1, 2, ã ã ã , m, (3.8) áp dng đồng nhất thứ Euler kf(x) = (Định lý 3.3) vào (3.7) ta nhận đượ pf(x∗) + q m∑ i=1 λ∗i gi(x ∗) = 0 ⇒ f(x∗) + q p m∑ i=1 λ∗i gi(x ∗) = 0, (3.9) hay theo (3.8) f(x∗) + q p m∑ i=1 λ∗i bi + q p m∑ i=1 λ∗i [gi(x ∗)− bi] = f(x∗) + q p m∑ i=1 λ∗i bi = 0. Từ đây theo (3.8) ta lại ó f(x∗) + q p m∑ i=1 λ∗i bi + m∑ i=1 λ∗i [gi(x ∗)− bi] = 0 hay f(x∗) + m∑ i=1 λ∗i [gi(x ∗)− bi(1− q p )] = 0, (3.10) Bằng á h đặt x = x∗, λ = λ∗, u = 1, à = 0, ta khẳng định rằng (x, u) là điểm KKT ủa (P̂ ) tương ứng với nhân tử Lagrange (λ, à). Thật vậy, • u ≥ 0 và [gi(x)− bi(1− qp)]u = gi(x)− bi(1− qp) ≤ qpbi, ∀i = 1, ã ã ã , m, vì thế (x, u) thoả mãn (3.1) • (3.2) đượ suy trự tiếp từ (3.7). • Do à = 0 nên (3.3) hính là (3.10). • Do à = 1 nên (3.4) đượ suy ra từ (3.8). • (3.5) hiển nhiên đượ thoả mãn. b) Ngượ lại, giả sử (x, u) ∈ K ì R+ là điểm KKT ủa (P̂ ) tương ứng với nhân tử Lagrange (λ, à) ∈ Rm+1+ . Do giả thiết u > 0 nên ta phải ó à = 0. Đặt x∗ = x, λ∗ = λ. Ta khẳng định rằng x∗ là điểm KKT ủa (P ) tương ứng với nhân tử Lagrange λ∗. Thật vậy, 40 • Từ (3.2) và u 6= 0 ta nhận đượ (3.7) và (3.9) nhận đượ nhờ áp dng đồng nhất thứ Euler vào (3.7). • Hơn nữa sử dng (3.9) trong (3.3) ho ta (p− q) m∑ i=1 λ∗i [gi(x ∗)− bi] = 0. (3.11) Sử dng đẳng thứ này vào (3.4) òn ho ta (1− u)q p m∑ i=1 λ∗i bi = 0, điều này ko theo u = 1, vì từ (3.9) và (3.11) ho thấy q p m∑ i=1 λ∗i bi = −f(x∗) 6= 0. • Do u = 1 nên từ (3.1) suy ra gi(x∗) ≤ bi, ∀i = 1, 2, ã ã ã , m và từ (3.4) suy ra λ∗i [gi(x ∗)− bi], ∀i = 1, 2, ã ã ã , m và định lý đượ hứng minh xong. Nhận xt 3.1. Trường hợp u = 0 rất đặ biệt, ó thể khắ ph nhờ đưa vào giả thiết (H) như sau:  bi < 0 với ít nhất một i ∈ {1, 2, ã ã ã , m} hoặ bi ≥ 0, ∀i = 1, 2, ã ã ã , m và inf P < 0. Nhận xt 3.2. Nếu x hấp nhận đượ đối với (P ) thì (x, 1) hấp nhận đượ đối với (P̂ ). Vì thế inf P ≥ inf P̂ . (3.12) Trường hợp p = q > 0, bài toán (P̂ ) ó ấu trú đơn giản: min { u.f(x) : x ∈ K; gi(x).u ≤ bi, i = 1, 2, ã ã ã , m; u ≥ 0 } . Kết quả sau đây bổ sung ho định lý 3.4. Định lý 3.5. Giả sử p = q. Khi đó x∗ ∈ K là nghiệm ự tiểu toàn  ủa (P ) khi và hỉ khi (x∗, 1) là nghiệm ự tiểu toàn  ủa (P̂ ). 41 Chứng minh. Giả sử (y∗, u) ∈ K ì R+ là nghiệm ự tiểu toàn  ủa (P̂ ). Do f, gi, i = 1, 2, ã ã ã , m, là á hàm thuần nhất bậ q và K là một nón nên x∗ = u 1 py∗ ∈ K là nghiệm hấp nhận đượ ủa (P ). Hơn nữa, inf P ≤ f(x∗) = uf(y∗) = inf P̂ , vì thế từ (3.12) suy ra inf P = f(x∗) = inf P̂ . Ngượ lại, giả sử x∗ là nghiệm tối ưu toàn  ủa (P ). Nếu như inf P̂ < inf P = f(x∗) thì tìm đượ dãy nghiệm ự tiểu {(yn, un)} ⊂ K ìR+ sao ho unf(y n) ↓ inf P̂ . Vì thế, với n đủ lớn, hẳng hạn với n ≥ n0 thì unf(yn) ≤ f(x∗). Nhưng khi đó xn = (un) 1 pyn ∈ K là nghiệm hấp nhận đượ ủa (P ) và lại ó f(xn) < f(x∗), đó là điều vô lý. Như vậy, phải ó inf P̂ = f(x∗), nghĩa là (x∗, 1) là nghiệm ự tiểu toàn  ủa (P̂ ). 3.3.2. Dạng tương đương ủa bài toán (P̂ ) (P̂ ) ó thể tá h thành hai bài toán tối ưu liên tiếp (theo x ∈ Rn và u ∈ R+): minx∈K min { u.f(x) : [ gi(x)− bi(1− q p ) ] u ≤ q p bi, i = 1, 2, ã ã ã , m; u ≥ 0 } . Với x ∈ K ố định, bài toán bên trong là bài toán quy hoạ h tuyến tính theo một biến u ≥ 0, ký hiệu là (LP )x. Đối ngẫu ủa (LP )x là bài toán (D)x max { − q p m∑ i=1 λibi : f(x)+ m∑ i=1 λi [ gi(x)−bi(1− q p ) ] ≥ 0}. Đây là bài toán quy hoạ h tuyến tính với ràng buộ hính đối với biến λ ≥ 0. Như vậy, bài toán "min-max" tương ứng với bài toán (P ) là (D) minx∈K maxλ≥0 { −q p m∑ i=1 λibi : f(x)+ m∑ i=1 λi [ gi(x)−bi(1−q p ) ] ≥ 0}. với ùng giá trị tối ưu như (P̂ ). Vì thế, việ tìm điểm KKT x∗ ủa (P ) quy về tìm điểm KKT x∗ ủa (D). Trường hợp riêng. Đôi khi ó thể đơn giản hoá bài toán (D) nêu trên. Chẳng hạn, khi p = q và nếu bi ≥ 0 với mọi i = 1, 2, ã ã ã , m thì inf P < 0, bởi vì f(0) = 0 và 0 ∈ S với S là tập nghiệm hấp nhận đượ ủa (P ). 42 Vì thế, ta hỉ ần quan tâm đến những x ∈ K thoả mãn f(x) < 0 và với những x như thế thì biểu thứ maxλ≥0 { − q p m∑ i=1 λibi : f(x) + m∑ i=1 λigi(x) ≥ 0 } trở thành (với ký hiệu [a]+ = max{0, a}) max{i:gi(x)>0}−bi [−f(x) gi(x) ]+ = max{i:gi(x)>0} f(x) bi gi(x) . Do đó, (D) đơn giản hỉ là bài toán (D) min{x∈K,f(x)0} f(x) bi gi(x) . Thật vậy, nếu ó x ∈ K sao ho f(x) < 0 và gi(x) < 0 với mọi i = 1, 2, ã ã ã , m, thì do tính thuần nhất nên inf P = −∞. Ví d 3.4. Xt một số bài toán tối ưu ó bài toán đối ngẫu (D) dạng hiển: • Quy hoạ h tuyến tính (p = q = 1) min{ : Ax ≥ b, x ≥ 0} với K = Rn+. Bài toán "min-max" (D) ó dạng (D) minx∈K maxλ≥0{ : ≥ 0}, trùng với bài toán đối ngẫu thông thường max{ : ATλ ≤ c, λ ≥ 0}, • Tuyến tính-toàn phương (hàm m tiêu bậ hai, ràng buộ tuyến tính) minx∈K {1 2 : Ax ≤ b } với K = Rn Bài toán "min-max" (D) tương ứng ó dạng (D) minx∈K maxλ≥0 { − 1 2 m∑ i=1 λibi : 1 2 + < λ,Ax− b 2 >≥ 0 } . • Quy hoạ h bậ hai minx∈K { : ≤ bi, i = 1, 2, ã ã ã , m } với K = Rn. 43 Bài toán "min-max" (D) tương ứng ó dạng (D) minx∈K maxλ≥0 { − m∑ i=1 λibi : < x, ( Q0 + m∑ i=1 λiQi ) x > ≥ 0 } . 3.4 Tối ưu toàn  3.4.1. Trường hợp tổng quát • Xt bài toán (P ), trong đó f (gi, i = 1, 2, ã ã ã , m) là hàm thuần nhất bậ p (bậ q). Trướ hết ta sẽ nêu đặ trưng ủa điểm KKT là nghiệm tối ưu toàn  ủa (P ) trong trường hợp p = q, nhờ dùng bài toán (D). Để đơn giản á h trình bày, ta giả thiết bi ≥ 0 với mọi i = 1, 2, ã ã ã , m. Bổ đề 3.1. Giả sử p = q và x∗ là điểm KKT ủa (P ) ứng với nhân tử Lagrange λ∗ ∈ Rm+ . Khi đó, x∗ là điểm ự tiểu toàn  ủa (P ) khi và hỉ khi m∑ i=1 λ∗i bi ≥ min{i:gi(y)>0} −bi gi(y) f(y), (3.13) đối với mọi y ∈ K mà f(y) < 0. Chứng minh. Điều kiện ần. Do x∗ là điểm KKT ủa (P ) ứng với nhân tử Lagrange λ∗ ∈ Rm+ và do f, gi là á hàm thuần nhất bậ p nên ta ó inf P = f(x∗) = − m∑ i=1 λ∗i bi. Từ inf P = inf P̂ (Định lý 3.5) và sự tương đương giữa (D) và (P̂ ) suy ra với mỗi y ∈ K ta ó f(x∗) ≤ maxλ≥0 { − m∑ i=1 λibi : f(y) + m∑ i=1 λigi(y) ≥ 0 } . Nghiệm tối ưu ủa quy hoạ h tuyến tính ở vế phải đẳng thứ trên bằng • −∞ nếu f(y) < 0 và gi(y) < 0 với mọi i = 1, 2, ã ã ã , m. • 0 nếu f(y) ≥ 0 và gi(y) < 0 với mọi i = 1, 2, ã ã ã , m. 44 •maxi:gi(y)>0 − [−f(y) gi(y) ]+ bi nếu trái lại (ký hiệu [a] + = max{0, a}) Do inf P = inf P̂ nên trường hợp đầu không xảy ra và kết luận ủa bổ đề ó đượ là do ta quan tâm tới những y ∈ K mà f(y) < 0. Điều kiện đủ đượ hứng minh bằng phản hứng. Giả sử x∗ thoả mãn (3.13) nhưng không phải là nghiệm ự tiểu toàn  ủa (P ), vì thế (x∗, 1) không là nghiệm ự tiểu toàn  ủa (P̂ ). Do đó tìm đượ y ∈ K sao ho inf P ≤ f(y) < f(x∗) = − m∑ i=1 λ∗i bi. Sự tương đương giữa (D) và (P̂ ) ho thấy maxλ≥0 { − m∑ i=1 λibi : f(y) + m∑ i=1 λigi(y) ≥ 0 } < f(x∗). Quy hoạ h tuyến tính này ó nghiệm tối ưu vì nó bị hặn trên và luôn ó nghiệm hấp nhận đượ . Hơn nữa, ó y ∈ K với f(y) < 0. Vì thế, f(x∗) = − m∑ i=1 λibi > max{i:gi(y)>0}− [−f(y) gi(y) ]+ bi = max{i:gi(y)>0} bi gi(y) f(y) Bổ đề đượ hứng minh. Có thể dùng bổ đề trên để hứng tỏ x∗ không là nghiệm ự tiểu toàn  ủa (P ), vì khi đó hỉ ần hỉ rõ ó y ∈ K với f(y) < 0 không thoả mãn (3.13). Ký hiệu S = {x | gi(x) ≤ bi} là tập nghiệm hấp nhận đượ ủa (P ). Hàm (đối ngẫu) Lagrange tương ứng với (P ) là L(x, λ) = f(x) + m∑ i=1 λi[gi(x)− bi]. Ta sẽ hứng tỏ rằng việ tìm nghiệm tối ưu toàn  ủa (P ) quy về giải một bài toán quy hoạ h lồi với hàm m tiêu tuyến tính, khi điểm KKT x∗ là 45 nghiệm ự tiểu toàn  ủa hàm Lagrange trên K . Trường hợp mọi hàm tham gia trong bài toán đều là bậ hai, bài toán (P ) là bài toán lồi LMI (bất đẳng thứ ma trận tuyến tính), một bài toán ó thể giải không quá khó. Định lý 3.6. Giả sử x∗ ∈ K là điểm KKT ủa bài toán (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ . Giả sử x∗ ũng là nghiệm ự tiểu toàn  ủa hàm L(ã, λ∗) trên K . Khi đó: a) f(x) + m∑ i=1 λ∗i [ gi(x)− bi(1− q p ) ] ≥ 0 trên K. b) (P ) tương đương với bài toán quy hoạ h lồi minλ≥0 {q p m∑ i=1 λibi : f(x) + λi [ gi(x)− bi(1− q p ) ] ≥ 0 ∀x ∈ K}. (3.14) Chứng minh. a) Giả sử x∗ ∈ K là điểm KKT ủa bài toán (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ . Nói riêng, (x∗, λ∗) thoả mãn (3.7), (3.8). Do đó áp dng đồng nhất thứ Euler vào (3.7) và dùng (3.8) ta nhận đượ f(x∗) + m∑ i=1 λ∗i gi(x ∗) = p− q p m∑ i=1 λ∗i bi, vì thế f(x∗) = f(x∗) + m∑ i=1 λ∗i [gi(x ∗ − bi]) = −q p m∑ i=1 λ∗i bi, (3.15) Do x∗ là nghiệm ự tiểu toàn  ủa hàm Lagrange L(ã, λ∗) trên K nên f(x) + m∑ i=1 λ∗i [gi(x)− bi] ≥ f(x∗) = − q p m∑ i=1 λ∗i bi, ∀xεK, (3.16) nghĩa là ó a). b) Từ (3.15), (3.16) suy ra f(x∗) ≤ maxλ≥0 {q p m∑ i=1 λibi : f(x) + m∑ i=1 λi [ gi(x)− bi(1− q p ) ] ≥ 0, x ∈ K}. (3.17) 46 Hơn nữa, với x ∈ K ho trướ thì tập Sx = { λ ∈ Rm+ : f(x) + m∑ i=1 λi [ gi(x)− bi(1− q p ) ] ≥ 0} hứa tập ⋂ x∈K = { λ ∈ Rm+ : f(x) + m∑ i=1 λi [ gi(x)− bi(1− q p ) ] ≥ 0, ∀x ∈ K} Do đó với mọi x ∈ K thì max { − q p m∑ i=1 λibi : λ ∈ ⋂ x∈K Sx } ≤ max { − q p m∑ i=1 λibi : λ ∈ Sx } . Vì thế, từ (3.17) suy ra f(x∗) ≤ minx∈K max { − q p m∑ i=1 λibi : λ ∈ Sx } = inf P̂ . Kết hợp với (3.12) ta nhận đượ f(x∗) = inf P̂ . Cuối ùng, rõ ràng ⋂ x∈K Sx là tập lồi nên điều này ho thấy ó b). Nhận xt 3.3. a) Khi p = q tập hấp nhận đượ S ủa (P ) ó phần trong khá rỗng và 0 ∈ intS thì trong Định lý 3.6 hỉ ần giả thiết điểm KKT x∗ là nghiệm ự tiểu toàn  ủa L(ã, λ∗) trên S ∩K . b) Một điều kiện đủ để x∗ là một nghiệm ự tiểu toàn  ủa L(ã, λ∗) trên S ∩K là f và á hàm gi lồi. ) Để ý rằng khi K = Rn và (P ) là bài toán quy hoạ h bậ hai, nghĩa là khi f(x) = và gi(x) =, i = 1, 2, ã ã ã , m, thì bài toán quy hoạ h lồi (3.14) trong định lý 3.6 là bài toán tối ưu LMI (bất đẳng thứ ma trận tuyến tính): maxλ≥0 { − m∑ i=1 λibi : (Q0 + m∑ i=1 λiQi  0 (ma trận nửa xá định dương) } , bài toán này ó thể giải một á h không quá khó. Ví d 3.5. Xt bài toán tối ưu không lồi trong R 2(p = 1, q = 2): (P ) minx=(x1,x2)∈K{x1 : x21 − x22 ≤ 1; x1 : x21 + x22 ≤ 7}, 47 với K = R2. Xt điểm KKT x∗ = (−2,±√3) tương ứng với nhân tử Lagrange λ∗ = (1 8 , 1 8 ). Ta ở tình huống x∗ ũng là nghiệm ự tiểu toàn  ủa hàm Lagrange L(x, λ∗) = x1 + x21 4 − 1 trên K . Vì thế, giá trị tối ưu ủa (P ) nhận đượ bằng á h tìm ự tiểu ủa λ1 + 7λ2 trên tập lồi A ⊂ R2 xá định bởi x21 + λ1(x 2 1 − x22) + λ2(x21 + x22) ≥ 0, ∀(x1, x2) ∈ R2; λ1, λ2 ≥ 0. 3.4.2. Trường hợp bậ hai Trường hợp p = q = 2 ó tầm quan trọng đặ biệt, ả về lý thuyết lẫn ứng dng. Với hai ma trận thự vuông, đối xứng bất kỳ X, Y ký hiệu X  Y nghĩa là X − Y nửa xá định dương. Mọi việ đượ đơn giản khi f và á hàm gi(x) là hàm bậ hai. Trong m này ta xt bài toán (P ) với á hạn hế K là nón lồi, f là dạng toàn phương và gi(x) là á hàm toàn phương nửa xá định dương. C thể là với mọi x: f(x) = và gi(x) =, i = 1, 2, ã ã ã , m, với Qi là á ma trận thự đối xứng, i = 0, 1, ã ã ã , m và Qi  0, i = 1, 2, ã ã ã , m. Trong trường hợp này ta sẽ hỉ ra rằng nếu điểm KKT x∗ ∈ K ủa (P ) ũng là nghiệm ự tiểu địa phương ủa hàm Lagrange trên S ∩K thì Định lý 3.6 đúng, vì thế việ tìm nghiệm tối ưu toàn  ủa (P ) quy về bài toán quy hoạ h lồi dễ giải. Bổ đề 3.2. Giả sử x∗ ∈ K là điểm KKT ủa bài toán (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ và giả sử rằng a) S ó phần trong khá rỗng, 0 ∈ intS và b) x∗ là nghiệm ự tiểu địa phương ủa L(ã, λ∗) trên S ∩K . Khi đó, x∗ là ự tiểu toàn  ủa (P ) và (P ) ⇔ với bài toán lồi: maxλ≥0 { − m∑ i=1 λibi : < ( Q0 + m∑ i=1 λiQi ) x, x > ≥ 0, ∀x ∈ K } (3.18) và khi K = Rn thì (P ) tương đương với bài toán lồi LMI maxλ≥0 { − m∑ i=1 λibi : ( Q0 + m∑ i=1 λiQi )  0 (nửa xá định dương)}. (3.19) 48 Chứng minh. Theo Định lý 3.6 hỉ ần hứng tỏ x∗ ũng là nghệm ự tiểu toàn  ủa L(ã, λ∗) trên K hay nghiệm ự tiểu toàn  trên K ủa L1(ã, λ∗) = f(x) + m∑ i=1 λ∗i gi(x) = L(ã, λ∗) + m∑ i=1 λ∗i bi. Trướ hết ta ần hứng minh x∗ là nghiệm ự tiểu toàn  ủa L(ã, λ∗) trên S ∩K . Xt điểm bất kỳ y ∈ S ∩K . Do Qi nửa xá định dương với mọi i = 1, 2, ã ã ã , m, S và K lồi nên u = y − x∗ là hướng hấp nhận đượ . Vì x∗ là nghiệm ự tiểu địa phương ủa L(ã, λ∗) (do đó ủa L1(ã, λ∗)) trên S ∩K và L1(x ∗, λ∗) = 0 ũng như ▽xL1(x∗, λ∗) = 0 nên ta ó ≥ 0. Từ đó, ta suy ra L1(x ∗, λ∗) ≥ 0 = L1(x∗, λ∗) bởi vì = 2 < ( Q0 + m∑ i=1 λ∗iQi ) y, y > = 2L1(y, λ ∗). Vì thế, x∗ là nghiệm ự tiểu toàn  ủa L1(x∗, λ∗) (do đó ủa L(ã, λ∗)) trên S ∩K . Do 0 ∈ intS và K là một nón nên do tính thuần nhất ta ó 0 = L1(x ∗, λ∗) ≤ L1(y, λ∗) với mọi y ∈ K, hứng tỏ < ( Q0 + m∑ i=1 λ∗iQi ) x, x > ≥ 0 trên K. Phần òn lại là hệ quả ủa Định lý 3.6. Bây giờ ta nêu ra điều kiện đủ để ho điểm KKT x∗ ủa (P ) là nghiệm ự tiểu toàn  ủa (P ) mà không ần giả thiết á gi lồi. Hệ quả 3.4. Cho f và gi, i = 1, 2, ã ã ã , m, là á dạng toàn phương và giả sử x∗ là điểm KKT ủa bài toán (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ . Giả sử bi > 0 với mọi i = 1, 2, ã ã ã , m và (với I(x∗) = {i : gi(x∗) = bi}) ≥ 0 mỗi khi ≤ 0, i ∈ I(x∗). (3.20) 49 Khi đó, x∗ là nghiệm ự tiểu toàn  ủa (P ) và giá trị tối ưu ủa (P ) là giá trị tối ưu ủa bài toán lồi LMI maxλ≥0 { − m∑ i=1 λibi : ( Q0 + m∑ i=1 λiQi )  0 (nửa xá định dương)}. Chứng minh. Ký hiệu L1(x, λ ∗) = f(x) + m∑ i=1 λ∗i gi(x). Trướ hết ta hứng minh rằng x∗ là nghiệm ự tiểu toàn  ủa L1(ã, λ∗) trên tập K∗ hứa x∗. Sau đó, nhờ tính thuần nhất sẽ suy ra rằng x∗ là nghiệm ự tiểu toàn  ủa L1(ã, λ∗) (do đó ủa L(ã, λ∗) trên K). Từ đó theo Định lý 3.6 x∗ là nghiệm ự tiểu toàn  ủa (P ). Xt tập K∗ = {y ∈ K : ≤ 2bi, i ∈ I(x∗)}. Rõ ràng là 0 ∈ K∗ (do bi > 0 ∀y) và x∗ ∈ K∗ (do đồng nhất thứ Euler). = 2gi(x∗) = 2bi với i ∈ I(x∗). Xt điểm bất kỳ y ∈ K∗. Ta ó = −2bi ≤ 0, i ∈ I(x∗). vì thế từ (3.20) ta ó ≥ 0. Vì x∗ là điểm KKT ủa (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ , nên L1(y, λ ∗) = L1(x∗ + (y − x∗), λ∗) = L1(x ∗, λ∗) + 1 2 ≥ L1(x∗, λ∗) = 0, 50 vì thế L1(y, λ ∗) ≥ L1(x∗, λ∗) = 0 với mọi y ∈ K∗. Bây giờ ta xt một điểm bất kỳ y ∈ K . Do K là một nón nên tìm đượ số thự α nào đó với 0 0 với mọi i = 1, 2, ã ã ã , m, x ∈ K∗ và vì thế L1(x, λ∗) ≥ 0. Nhưng khi đó, theo tính thuần nhất, L1(y, λ ∗) = α−2L1(x, λ∗) ≥ L1(x∗, λ∗) = 0. Do vậy, x∗ là nghiệm ự tiểu toàn  ủa L(ã, λ∗) trên K . Kết luận nêu trong Hệ quả đượ suy ra từ Định lý 3.6. Chúng ta kết thú m này với kết quả đặ biệt sau đây, ó lợi khi tìm ự tiểu ủa hàm lõm bậ hai với một số hữu hạn ràng buộ lồi bậ hai, nghĩa là xt trường hợp f(x) = và gi(x) = với Q0  0 và Qi  0 với mọi i = 1, 2, ã ã ã , m (Q0 nửa xá định âm, Qi nửa xá định dương với mọi i). Định lý 3.7. Giả sử x∗ 6= 0 là điểm KKT ủa (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ . Giả sử Q0 ó một giá trị riêng âm đơn và Ker(Q0) ∩Ker ( m∑ i=1 λ∗iQi ) = {0}. Khi đó, x∗ là nghiệm ự tiểu toàn  ủa (P ) và (P ) tương đương với bài toán lồi LMI Chứng minh. Chỉ ần hỉ ra rằng Q0 + m∑ i=1 λ∗iQi là ma trận nửa xá định dương, từ đó L(ã, λ∗) là lồi và x∗ là nghiệm ự tiểu toàn  ủa L(ã, λ∗) và Định lý 3.6 sẽ ho ta kết quả mong muốn. Với bất kỳ ma trận thự vuông đối xứng ấp n ì n, ký hiệu σj(A), j = 1, 2, ã ã ã , n là á giá trị riêng ủa ma trận xếp theo thứ tự tăng dần. Chú ý là Qi nửa xá định dương với mọi i = 1, 2, ã ã ã , m, ta ó σj ( Q0 + m∑ i=1 λ∗iQi ) ≥ σj(Q0), j = 1, 2, ã ã ã , n. 51 Đặt H = m∑ i=1 λ∗iQi. Rõ ràng là Q0 + H  Q0 + αH với mọi 0 ≤ α ≤ 1. Bây giờ ta sẽ hứng tỏ rằng σj(Q0 + H) > 0 với mọi j = 2, 3, ã ã ã , m. Xt 0-nhóm ủa r giá trị riêng ủa Q0. Có tồn tại á h sắp xếp á giá trị riêng σ2(Q0), ã ã ã , σr+1(Q0) sao ho á đạo hàm theo hướng ủa húng σ′k(Q0;H), k = 2, ã ã ã , r, theo hướng H là á giá trị riêng ủa ma trận P THP ấp r ì r, trong đó á ột pi, i = 1, 2, ã ã ã , r ủa P là á v tơ riêng bội 0 ủa Q0. Do á giá trị riêng đó không âm nên hỉ ần hỉ ra rằng tất ả húng đều dương. Giả sử rằng P THpu = 0 với v tơ u 6= 0 nào đó ∈ Rr, nghĩa là pTi H ( r∑ j=1 ujpj ) = 0, i = 1, 2, ã ã ã , r. Nhân với ui và ộng lại ta nhận đượ ( r∑ j=1 uip T i ) H ( r∑ j=1 ujpj ) = 0, từ đó H ( r∑ j=1 ujpj ) = 0. Từ giả thiết Ker(Q0) ∩Ker ( m∑ i=1 λ∗iQi ) = {0} suy ra rằng r∑ j=1 uipi = 0 và u = 0 suy ra từ sự độ lập tuyến tính ủa á v tơ pi. Ta đã vừa hứng minh đượ rằng σj ( Q0 + m∑ i=1 λ∗iQi ) > 0, ∀j = 2, 3, ã ã ã , n. 52 Vì thế, do x∗ là điểm KKT ủa (P ) tương ứng với nhân tử Lagrange λ∗ ∈ Rm+ nên từ ( Q0 + m∑ i=1 λ∗iQi ) x∗ = 0 suy ra σ1 ( Q0 + m∑ i=1 λ∗iQi ) = 0. Điều này ko theo ( Q0 + m∑ i=1 λ∗iQi ) nửa xá định dương, đó là điều ần hứng minh. Tóm lại, hương này nghiên ứu 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 quy hoạ h thông thường o một ràng buộ duy nhất. Từ đó nêu á h diễn đạt mới ho quy hoạ h tuyễn tính và quy 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. 53 Kết luận Hàm thuần nhất dương là sự mở rộng ủa á hàm tuyến tính và hàm bậ hai. Có nhiều hàm thuần nhất phi tuyến như: hàm Cobb-Douglas (trong kinh tế), hàm lồi thuần nhất (hàm huẩn, hàm tựa), hàm đa thứ thuần nhất. Hàm thuần nhất ó nhiều tính hất đẹp và đáng đượ hú ý. Luận văn này hủ yếu tập trung vào tìm hiểu bài toán tối ưu với hàm m tiêu và á hàm ràng buộ đều là hàm thuần nhất, đă biệt lưu ý đến điều kiện ần KKT đặ trưng ho điểm tối ưu toàn  ủa bài toán. Chương 1 giới thiệu tóm tắt một số kiến thứ ơ bản về giải tí h lồi, ần thiết ho nghiên ứu á bài toán tối ưu. Đó là á khái niệm về tập lồi, nón lồi và tập lồi đa diện (đỉ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 tập lồi và hàm lồi. Chương 2 đề ập tới á 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à đủ ho tối ưu không ràng buộ và điều kiện ần KKT ho tối ưu ó ràng buộ . Chương 3 trình bày một số kết quả nghiên ứu về bài toán tối ưu với á hàm thuần nhất dương. Đáng hú ý là điều kiện ần KKT ho bài toán đượ xt và tính hất đặ trưng ủa điểm KKT mà nó là điểm tối ưu toàn  ủa bài toán, trong trường hợp hàm m tiêu và á hàm ràng buộ là á hàm thuần nhất ùng bậ . Tá giả đã ố gắng sắp xếp và trình bày vấn đề theo á h hiểu rõ ràng và trự quan nhất ó thể, đưa ra á ví d và hình vẽ để minh hoạ ho một số khái niệm và sự kiện đượ đề ập tới trong luận văn. Hy vọng tá giả luận văn sẽ ó dịp làm quen với những lớp bài toán tối ưu khá và nhiều ứng dng phong phú ủa húng trong lý thuyết và thự tế. 54 Tài liệu tham khảo Tiếng Việt [1℄ N. T. B. Kim (2008), Giáo trình á phương pháp tối ưu (Lý thuyết và thuật toán), Nxb Bá h khoa - Hà Nội. [2℄ T. V. Thiệu (2004), Giáo trình tối ưu tuyến tính, Nxb Đại họ Quố gia Hà Nội. Tiếng Anh [3℄ E. D. Andersen (1998), Linear Optimization: Theory, Methods and Ex- tensions, Dept. of Management, Odense University, Denmark. [4℄ J. B. Lasserre and J. B. Hiriart - Urruty (2004), Some Mathemati al Prop- erties of Optimization Problems Defined by Positively Homogeneous Fun - tions, Preprint, LAAS – CNRS, Toulouse, Fran e. [5℄ D. G. Luenberger and Y. Ye (2008), Linear and Nonlinear Programming, 3rd Edition, Springer. 55