Download miễn phí Luận văn Bài toán tối ưu với hàm thuần nhất dương
Mục lục
Lờinóiđầu.2
1Nhữngkiếnthứ vềgiảitíhlồi 5
1.1Tậpaffinvàtậplồi.5
1.2Hàmlồi.14
2Cábàitoántốiưu 18
2.1Cákháiniệmơbản.18
2.2Bàitoántốiưukhôngràngbuộc.23
2.3Bàitoántốiưuóràngbuộc.25
3Bàitoántốiưuvớihàmthuầnnhấtdương 32
3.1Hàmthuầnnhất.32
3.2Bàitoántốiưuvớihàmthuầnnhấtdương.38
3.3Cákếtquảđốingẫuhính.38
3.4Tốiưutoàn.44
Kếtluận.53
Tàiliệuthamkhảo.54
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
- 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 x t 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 x t 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 x t 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. X t 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 x t 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. X t hàm số f(x1, x2) = e
3x2 − 3x1ex2 + x31. Ta
ó
▽f(x) =
−3ex2 + 3x21
3e3x2 − 3x1ex2