www.VNMATH.com
®¹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
www.VNMATH.com
®¹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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.Lrc-tnu.edu.vn
www.VNMATH.com
M
l
1
2
Lêi nãi ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
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
C¸
bµi to¸n tèi u
18
2.1 C¸
kh¸i niÖm
¬ b¶n
3
. . . . . . . . . . . . . . . . . . . . . . .
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
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
. . . . . . . . . . . . . . . . . . . . . . . . . . .
1
54
www.VNMATH.com
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 ®Æ
trng 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
www.VNMATH.com
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
www.VNMATH.com
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
www.VNMATH.com
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é
Nãi
¸
h kh¸
,
kú thué
M , tø
lµ ∀x1, x2 ∈ M , λ ∈ R ⇒ λx1 + (1 − λ)x2 ∈ M .
M lµ tËp affine nÕu nã
høa tæ hîp tuyÕn tÝnh
ña hai ®iÓm bÊt
M víi tæng
¸
hÖ sè b»ng 1. Ta gäi mét ®iÓm x ∈ R
ã d¹ng
x=
k
X
λi xi
i=1
víi
λ1 , λ2, · · · , λk ∈ R vµ
k
X
λi = 1
i=1
5
www.VNMATH.com
λ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
lµ
tæ hîp affine
on, tø
lµ nÕu
ña
¸
®iÓm
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
trong ®ã
M = x0 + L = x0 + v | v ∈ L ,
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
affine
víi
M . Thø nguyªn (dimension) hay
ßn gäi lµ sè
hiÒu
ña tËp
M lµ thø nguyªn
ña kh«ng gian
on song song víi nã.
Bao affine (affine hull)
ña mét tËp
høa
E ⊆ Rn lµ giao
ña tÊt
¶
¸
tËp affine
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
3
VÝ d 1.2. Bao affine
ña tËp E = x ∈ R | 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
ña nã, ký hiÖu lµ
M ⊆ Rn lµ sè
hiÒu
ña bao affine
dim M . Cho tËp M ⊆ Rn
ã dim M < 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
trong t¬ng ®èi
ña
nÕu
ña tËp M , ký hiÖu lµ ri M , lµ tËp
høa tÊt
¶
¸
®iÓm
M . Mét tËp M ⊆ Rn ®î
gäi lµ
ã
thø nguyªn ®Çy ®ñ
dim M = n. DÔ thÊy r»ng tËp M
ã phÇn trong kh¸
rçng (int M 6= ∅) khi
vµ
hØ khi nã
ã thø nguyªn ®Çy ®ñ.
6
www.VNMATH.com
E = x ∈ R3 | 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x3 = 0 , ta
ã:
int E = ∅, ri E = x ∈ R3 | 0 < x1 < 1, 0 < x2 < 1, x3 = 0 , vµ dim E = 2.
VÝ d 1.3.
Cho
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 + (1 − λ)x2 ∈ M .
(a)
∀x1 , x2 ∈ M , 0 ≤ λ ≤ 1 ta
ã
(b)
(
)
H×nh 1.1. (a), (b) - TËp låi;
(d)
(
), (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
ha
h¾
lµ tËp låi.
Ta gäi ®iÓm
x ∈ Rn
ã d¹ng
x=
k
X
λi xi
i=1
víi
λ1 , λ2, · · · , λk ≥ 0 vµ
k
X
λi = 1
i=1
lµ tæ hîp låi
ña
¸
®iÓm x1 , x2, · · ·
th× ta nãi
x lµ
MÖnh ®Ò 1.1.
tæ hîp låi
hÆt
Mét tËp
ña
M ⊂ Rn
, xk ∈ Rn . NÕu λi ≥ 0 víi ∀i = 1, 2, · · · , k
x1, x2, · · · , xk ∈ 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
www.VNMATH.com
MÖnh ®Ò 1.2.
a) NÕu
M ⊂ Rn lµ tËp låi vµ sè thù
α ∈ Rn th× αM = {y | y = αx, x ∈ M}
òng lµ tËp låi.
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.
b) NÕu
Bao låi (
onvex hull)
ña tËp
vµ ®î
kÝ hiÖu lµ
E ⊂ Rn lµ giao
ña tÊt
¶
¸
tËp låi
høa E
conv E . §ã lµ tËp låi nhá nhÊt
høa E .
convE
E
convE
H×nh 1.2. VÝ d vÒ bao låi
MÖnh ®Ò 1.3.
tö thué
E.
Cho tËp låi
point)
ña
Bao låi
ña tËp
E ⊂ Rn
høa tÊt
¶
¸
tæ hîp låi
ña
¸
phÇn
M ⊂ Rn . Mét ®iÓm x ∈ M ®î
gäi lµ ®iÓm
ù
biªn (extreme
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
hØ khi nã kh«ng
høa
hän mét ®êng th¼ng nµo.
8
ã ®iÓm
ù
biªn khi vµ
www.VNMATH.com
(b)
(a)
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 ®Æ
trng 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
Rn
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 | < a, x > = α}
®î
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
a
< a, x >= α
x0
x
H×nh 1.4. Siªu ph¼ng trong
R2
{x ∈ Rn |< a, x > ≤ α} (hoÆ
{x ∈ Rn |< a, x > ≥ α})
víi
a ∈ Rn \ {0} vµ α ∈ Rn lµ
nöa kh«ng gian ®ãng
vµ tËp
{x ∈ Rn |< a, x > < α} (hoÆ
{x ∈ Rn |< a, x > > α})
lµ
nöa kh«ng gian më
Cho tËp
x¸
®Þnh bëi siªu ph¼ng
{x ∈ Rn | < a, x > = α}
M ⊂ Rn , v
t¬ a ∈ Rn \ {0} vµ sè thù
α ∈ R. Ta gäi siªu ph¼ng
H := {x ∈ Rn | < a, x > = α}
9
www.VNMATH.com
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µ
< a, x0 >= α vµ < a, x > ≤ α, ∀x ∈ M .
a
x0
M
H×nh 1.5. Siªu ph¼ng tùa
ña
§Þnh lý 1.2.
Qua mçi ®iÓm biªn
siªu ph¼ng tùa
ña
§Þnh lý 1.3.
M
t¹i
x0
M
t¹i
ña tËp låi
x0 .
Mét tËp låi ®ãng kh¸
rçng
x0
M ⊂ Rn
M ⊂ Rn
tån t¹i Ýt nhÊt mét
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
ã
λ1 x1 + λ2 x2 ∈ M .
0
0
(b) - Nãn kh«ng låi
H×nh 1.6. (a) - Nãn låi
VÝ d 1.4.
C¸
tËp sau ®©y lµ
¸
nãn låi
ã ®Ønh t¹i gè
10
0 trong Rn :
www.VNMATH.com
• 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
1
k v
t¬ v 1 , v 2, · · · , v k ∈ Rn . TËp
2
cone v , v , · · · , v
n
n
n
:= v ∈ R | v =
®î
gäi lµ nãn sinh bëi tËp
k
X
i=1
o
i
λi v , λi ≥ 0, i = 1, · · · , k ⊂ Rn
v 1, v 2, · · · , v k . V
t¬ v h ∈ v 1 , v 2, · · · , v k
gäi lµ kh«ng thiÕt yÕu (non essential) nÕu
cone v 1 , · · · , v h−1, v h+1, · · · , v k = cone v 1, v 2, · · · , v k .
v1
v1
v2
v3
0
v
0
(a)
H×nh 1.7. (a) - V
t¬
(b) - HoÆ
v
t¬
v2
v
2
v3
2
(b)
lµ kh«ng thiÕt yÕu
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
(re
ession dire
tion)
ña
D ⊆ Rn . V
t¬ d 6= 0 ®î
gäi lµ
ph¬ng lïi xa
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
®iÓm bÊt kú
ña
khi vµ
hØ khi
d xuÊt ph¸t tõ mét
D ®Òu n»m
hän trong D. Râ rµng r»ng tËp D kh«ng bÞ
hÆn
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
11
D vµ kÝ hiÖu lµ rec D.
www.VNMATH.com
Ta nãi hai ph¬ng
Ph¬ng lïi xa
ña
d1 vµ d2 kh¸
biÖt (distin
t) nÕu d1 6= αd2 víi α > 0.
d
ña tËp D ®î
gäi lµ
ph¬ng
ù
biªn
(extreme dire
tion)
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 = λ1d1 + λ2 d2 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 | < a, x > = α} 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
< a, x > ≤ α ≤ < a, y > ∀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
< a, x > < α < < a, y > ∀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, x > ≥ 0
sao
ho
víi mäi
a = AT y .
x
tho¶ m·n
a ∈ Rn
Ax ≥ 0
vµ ma trËn
A
Êp m × n.
khi vµ
hØ khi
Khi
∃y ∈ Rn , y ≥ 0
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 |< a, x > ≥ 0} khi vµ
hØ khi v
t¬ ph¸p tuyÕn
ña siªu ph¼ng
{x ∈ Rn |< a, x > = 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
www.VNMATH.com
tÝnh
< ai , x > ≥ bi , i = 1, 2, · · · , m.
Mçi bÊt ®¼ng thø
trong
(1.1)
(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 |< ai , x > ≥ bi , i = 1, 2, · · · , m
= x |< ai , x > ≥ bi, i ∈ {1, 2, · · · , m} \ {k}
Ta kÝ hiÖu A lµ ma trËn
Êp m×n víi ai
v
t¬
= (a1, a2 , · · · , an ), i = 1, 2, · · · , n,
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
< ai , x > = bi , i = 1, 2, · · · , m1
< ai , x > ≥ b , i = m + 1, · · · , m
i
1
ò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
a5
a2
4
a
a3
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
< ai , x0 >= bi, th× ta nãi ®iÓm x0 tho¶ m·n
hÆt rµng bué
i. TËp
13
www.VNMATH.com
I(x0) := i ∈ {1, 2, · · · , m} < ai , x0 >= bi
lµ tËp hîp
¸
hØ sè
¸
rµng bué
tho¶ m·n
hÆt t¹i
Mçi ®iÓm
ù
biªn
ña tËp låi ®a diÖn
on låi
F 6= ∅ ®î
gäi lµ mét
diÖn
ña
®èi
ña mét ®o¹n th¼ng nµo ®ã thué
x0 ∈ D .
D ®î
gäi lµ mét
®Ønh
ña
D. TËp
D nÕu F
høa mét ®iÓm trong t¬ng
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ú
Ta gäi
x1, x2 ∈ D vµ bÊt kú sè thù
λ ∈ [0, 1] ta
ã
f λx1 + (1 − λ)x2 ≤ λf (x1) + (1 − λ)f (x2).
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
f lµ dom f = {x ∈ D | f (x) < +∞}
hiÖu
ña hµm
Epigraph
∈ D, x1 6= x2 vµ bÊt kú sè thù
λ ∈ (0, 1). MiÒn x¸
®Þnh h÷u
(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
kh«ng gian
f : D −→ R ∪ {+∞}
ã thÓ ®î
më réng thµnh hµm låi trªn toµn
Rn b»ng
¸
h ®Æt f (x) = +∞, ∀x ∈
/ dom f . V× vËy ®Ó ®¬n gi¶n,
f lµ hµm låi trªn Rn .
ta thêng xt
MÖnh ®Ò 1.5.
a) Hµm
f
x¸
®Þnh trªn tËp låi kh¸
rçng
epi(f ) lµ tËp låi.
b) Hµm
g
D ⊆ Rn
x¸
®Þnh trªn tËp låi kh¸
rçng
lµ hµm låi khi vµ
hØ khi
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
www.VNMATH.com
hypo(g) := {(x, α) ∈ D × R | x ∈ D, α ≤ g(x)}.
(b)
(a)
(b) - Hypogrph
ña mét hµm lâm
H×nh 1.9. (a) - Epigraph
ña mét hµm låi;
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
låi
D1 ⊆ Rn , hµm låi f2 x¸
®Þnh trªn tËp
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
α > 0, β > 0. Khi ®ã,
¸
hµm αf1 + βf2
vµ
låi trªn
D2
vµ hai sè thù
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
§Þnh lý 1.5.
trªn
f x¸
®Þnh trªn tËp låi më D ⊆ Rn . Ta
ã:
NÕu
f
lµ hµm låi x¸
®Þnh trªn tËp låi më
D.
§Þnh lý 1.6.
NÕu
f : D −→ R
D ⊆ Rn
th×
f
lµ mét hµm låi x¸
®Þnh trªn tËp låi
th× nã
ã ®¹o hµm theo mäi híng
d ∈ R \ {0} t¹i
mäi ®iÓm
liªn t
D ⊆ Rn
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ë
hµm theo mäi híng
d ∈ R \ {0} t¹i mäi ®iÓm x0 ∈ dom f
D
vµ
< ▽f (x0), d >= f ′ (x0, d) ≤ f (x0 + d) − f (x0)
15
th×
f
ã ®¹o
www.VNMATH.com
1.2.4. Tiªu
huÈn nhËn biÕt hµm låi kh¶ vi
§Þnh lý 1.7.
hµm låi trªn
Cho
D
f
lµ hµm kh¶ vi trªn tËp låi më
D ⊆ Rn .
Khi ®ã hµm
f
lµ
khi vµ
hØ khi
f (y) − f (x) ≥ < ▽f (x), y − 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
lµ hµm låi trªn
trªn
f
lµ hµm kh¶ vi hai lÇn trªn tËp låi më
D ⊆ Rn .
Khi ®ã
f
D khi vµ
hØ khi ma trËn Hesse ▽2 f (x) lµ nöa x¸
®Þnh d¬ng
D, tø
víi ∀x ∈ D
th×
y T ▽2 f (x)y ≥ 0, ∀y ∈ Rn
f
Hµm
mäi
lµ hµm låi
hÆt trªn
D
nÕu
x ∈ D, th×
▽2 f (x) x¸
®Þnh d¬ng trªn D, tø
víi
y T ▽2 f (x)y > 0, ∀y ∈ Rn \ {0}.
HÖ qu¶ 1.3.
Cho hµm toµn ph¬ng
f (x) =
trong ®ã
Q
nÕu
< x, Qx > + < c, x > + α,
lµ ma trËn vu«ng ®èi xøng
Êp
hµm låi trªn
Rn
1
2
Rn
nÕu
n, c ∈ Rn
vµ
Q lµ ma trËn nöa x¸
®Þnh d¬ng (f
α ∈ R.
Khi ®ã,
f
lµ
lµ hµm låi
hÆt trªn
Q lµ ma trËn x¸
®Þnh d¬ng).
VÝ d 1.5.
Cho
f (x1, x2) = 2x21 + 3x1x2 + 4x22. Ta
ã:
4x1 3x2
▽f (x) =
3x1 8x2
▽2 f (x) =
V× ma trËn Hesses
hÆt trªn
R2 .
4 3
3 8
▽2 f (x) x¸
®Þnh d¬ng nªn hµm f ®·
ho lµ hµm låi
16
www.VNMATH.com
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
www.VNMATH.com
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
hoÆ
trong ®ã D
max f (x) víi x ∈ D
(P2)
⊆ Rn ®î
gäi lµ tËp nghiÖm
hÊp nhËn ®î
hay tËp rµng bué
vµ
f : D −→ R lµ
nhËn ®î
(P1 )
. Mçi ®iÓm
hµm m
tiªu
hay mét
x ∈ D ®î
gäi lµ mét nghiÖm
ph¬ng ¸n
hÊp nhËn ®î
(
ã thÓ gäi t¾t lµ mét
hÊp
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µ
18
nghiÖm
- Xem thêm -