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

 - global minimizer), hoặ đơn giản hỉ là nghiệm 18 www.VNMATH.com ủ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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com ủ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 www.VNMATH.com 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 www.VNMATH.com ▽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 www.VNMATH.com 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 www.VNMATH.com ≥ 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 www.VNMATH.com 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 www.VNMATH.com ) 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 www.VNMATH.com Đ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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com 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 www.VNMATH.com Đị