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

→ 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