ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN LÂM HÀ
VAI TRÒ CỦA TÍNH LỒI
TRONG BÀI TOÁN TỐI ƯU
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN – 2015
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN LÂM HÀ
VAI TRÒ CỦA TÍNH LỒI
TRONG BÀI TOÁN TỐI ƯU
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
GS. TSKH. LÊ DŨNG MƯU
THÁI NGUYÊN – 2015
i
Möc löc
Líi c£m ìn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Mð ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Ch÷ìng 1. Tªp lçi v h m lçi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. ành ngh¾a v t½nh ch§t cõa tªp lçi . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.1. ành ngh¾a v t½nh ch§t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.1.2. C¡c ành lþ t¡ch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2. ành ngh¾a v t½nh ch§t cõa h m lçi . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.1. H m lçi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.2. C¡c t½nh ch§t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.3. C¡c ành lþ cì b£n v· d÷îi vi ph¥n h m lçi . . . . . . . . . . . . . . . . .
14
2.1. B i to¡n tèi ÷u lçi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.1.1. B i to¡n tèi ÷u hâa ìn möc ti¶u . . . . . . . . . . . . . . . . . . . . . . .
16
2.1.2. V½ dö . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2. i·u ki»n c¦n v õ cho b i to¡n tèi ÷u lçi . . . . . . . . . . . . . . . . .
18
2.3. Thuªt to¡n chi¸u d÷îi ¤o h m . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.3.1. Ph÷ìng ph¡p chi¸u d÷îi ¤o h m . . . . . . . . . . . . . . . . . . . . . . .
30
2.3.2. Thuªt to¡n chi¸u d÷îi ¤o h m . . . . . . . . . . . . . . . . . . . . . . . . .
30
Ch÷ìng 2. Vai trá cõa t½nh lçi trong b i to¡n tèi ÷u . . . . 16
K¸t luªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
T i li»u tham kh£o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
ii
Líi c£m ìn
Luªn v«n n y ÷ñc ho n th nh t¤i tr÷íng ¤i håc Khoa håc, ¤i
håc Th¡i Nguy¶n d÷îi sü h÷îng d¨n cõa GS.TSKH. L¶ Dông M÷u. Tæi
xin b y tä láng bi¸t ìn s¥u sc èi vîi th¦y v· sü tªn t¥m v nhi»t t¼nh
h÷îng d¨n, cung c§p t i li»u, truy·n ¤t nhúng kinh nghi»m v· m°t
nghi¶n cùu trong suèt qu¡ tr¼nh t¡c gi£ thüc hi»n luªn v«n.
Tæi xin ch¥n th nh c£m ìn Ban Gi¡m hi»u, pháng o t¤o Khoa håc,
Khoa To¡n - tin tr÷íng ¤i håc Khoa håc, ¤i håc Th¡i nguy¶n còng
c¡c th¦y, cæ gi¡o tham gia gi£ng d¤y cao håc khâa 2013 - 2015 ¢ quan
t¥m v gióp ï trong suèt thíi gian håc tªp t¤i tr÷íng.
Cuèi còng, tæi xin gûi líi c£m ìn tîi gia ¼nh, b¤n b±, l¢nh ¤o tr÷íng
THPT Hòng An, Bc Quang, H Giang v c¡c b¤n çng nghi»p ¢ gióp
ï t¤o i·u ki»n cho tæi khi håc tªp v nghi¶n cùu.
Tæi xin ch¥n th nh c£m ìn!
Th¡i Nguy¶n, th¡ng 06 n«m 2015
Håc vi¶n
Nguy¹n L¥m H
1
Mð ¦u
Trong thíi ¤i ng y nay, to¡n håc ng y c ng câ nhi·u ùng döng ð c¡c
l¾nh vüc kh¡c nhau cõa íi sèng x¢ hëi. °c bi»t, lþ thuy¸t v· c¡c tªp
lçi v h m lçi câ mët và tr½ quan trång trong to¡n håc, li¶n quan ¸n
h¦u h¸t c¡c ng nh nh÷ gi£i t½ch lçi, tèi ÷u hâa, gi£i t½ch h m, h¼nh håc,
to¡n kinh t¸, . . . Mët c¡ch têng qu¡t, c¡c h m lçi vîi mët sè t½nh ch§t
cì b£n ÷ñc sû döng rëng r¢i trong to¡n håc lþ thuy¸t công nh÷ to¡n
håc ùng döng.
Trong nhi·u v§n · ùng döng ta th÷íng g°p c¡c b i to¡n tèi ÷u lçi,
t½nh ch§t b i to¡n tèi ÷u lçi, i·u ki»n c¦n v õ cho b i to¡n tèi ÷u
lçi, công nh÷ vai trá cõa t½nh lçi trong b i to¡n tèi ÷u, nhúng d¤ng to¡n
tr¶n câ nhúng t½nh ch§t cì b£n r§t kh¡c nhau.
Tuy nhi¶n t½nh lçi k²o theo nhúng °c thò ri¶ng cho méi b i to¡n.
Düa tr¶n c¡c t½nh ch§t n y, ng÷íi ta ¢ ÷a ra ÷ñc nhúng ph÷ìng ph¡p
gi£i quy¸t kh¡c nhau cho méi b i to¡n.
Nh¬m möc ½ch t¼m hiºu v· t½nh lçi trong b i to¡n tèi ÷u to n di»n
v logic hìn, tæi ¢ chån · t i "Vai trá cõa t½nh lçi trong b i to¡n tèi
÷u" cho luªn v«n cõa m¼nh.
Luªn v«n bao gçm ph¦n mð ¦u, hai ch÷ìng nëi dung, ph¦n k¸t luªn
v danh möc t i li»u tham kh£o.
Ch÷ìng 1. Luªn v«n tr¼nh b y c¡c ki¸n thùc cì b£n v· gi£i t½ch lçi:
ành ngh¾a tªp lçi, h m lçi, c¡c t½nh ch§t cõa h m lçi, d÷îi vi ph¥n cõa
h m lçi, i¸u ki»n c¦n v õ cho b i to¡n tèi ÷u lçi, b i to¡n tèi ÷u lçi
nh÷ c§u tróc tªp nghi»m, cho ph÷ìng ph¡p chi¸u ¤o h m v d÷îi ¤o
h m, gi£i b i to¡n tèi ÷u lçi.
Ch÷ìng 2. Giîi thi»u v· b i to¡n tèi ÷u lçi, i·u ki»n c¦n v õ cho
2
b i to¡n tèi ÷u lçi v °c bi»t l giîi thi»u thuªt to¡n chi¸u d÷îi ¤o
h m cho b i to¡n kh£ vi v thuªt to¡n chi¸u d÷îi ¤o h m cho b i to¡n
tèi ÷u lçi khæng kh£ vi, ...
Th¡i Nguy¶n, th¡ng 06 n«m 2015
Nguy¹n L¥m H
Håc vi¶n Cao håc To¡n K7A
Chuy¶n ng nh To¡n ùng döng
Tr÷íng ¤i håc Khoa håc - ¤i håc Th¡i Nguy¶n
Email:
[email protected]
3
Ch֓ng 1
Tªp lçi v h m lçi
Trong luªn v«n n y, chóng ta s³ l m vi»c vîi khæng gian Euclide n chi·u tr¶n tr÷íng sè thüc
R,
k½ hi»u l
Rn .
Ch÷ìng 1 tr¼nh b y mët sè
ki¸n thùc cì b£n nh§t v· tªp lçi v h m lçi còng vîi mët sè t½nh ch§t
°c tr÷ng cõa nâ s³ ÷ñc sû döng trong luªn v«n. Nëi dung cõa ch÷ìng
÷ñc tr½ch d¨n chõ y¸u tø t i li»u tham kh£o [1] v [2].
1.1. ành ngh¾a v t½nh ch§t cõa tªp lçi
1.1.1. ành ngh¾a v t½nh ch§t
ành ngh¾a 1.1. Cho A ⊂ X , x1, x2 ∈ A.
(i) o¤n th¯ng nèi hai iºm x1, x2 câ d¤ng
{x ∈ X : x = αx1 + βx2 , α, β ∈ R, α + β = 1}.
(ii) ÷íng th¯ng i qua hai iºm x1, x2 ÷ñc ành ngh¾a
{x ∈ R : x = αx1 + βx2 , α ≥ 0, β ≥ 0, α + β = 1}.
ành ngh¾a 1.2. Mët tªp A ÷ñc gåi l affine n¸u A chùa måi ÷íng
th¯ng i qua hai iºm x1, x2 b§t k¼ thuëc A, tùc l :
∀x1 , x2 ∈ A, ∀λ ∈ R th¼ λx1 + (1 − λ)x2 ∈ A.
ành ngh¾a 1.3. Gi£ sû a ∈ Rn l mët vectì kh¡c 0 v α ∈ R. Khi â:
4
l nûa khæng gian âng.
• {x : aT x > α} l nûa khæng gian mð.
ành ngh¾a 1.4. Tªp A ⊂ X ÷ñc gåi l lçi n¸u
• {x : aT x ≥ α}
∀x1 , x2 ∈ A, ∀λ ∈ R : 0 ≤ λ ≤ 1
th¼ λx1 + (1 − λ)x2 ∈ A.
V½ dö 1.1.
(i) Tªp
X
v
∅
l c¡c tªp lçi.
(ii) C¡c nûa khæng gian trong
R2
v
R3
l c¡c tªp lçi.
(iii) C¡c h¼nh trán trong m°t ph¯ng, h¼nh c¦u ìn và trong khæng gian
Banach, h¼nh c¦u trong khæng gian Hillbert l c¡c tªp lçi.
M»nh · 1.1. Tªp lçi l âng vîi ph²p giao, ph²p cëng, ph²p nh¥n
vîi mët sè thüc, tùc l , n¸u C v D l hai tªp lçi trong Rn th¼ C ∩ D,
λC + βD công l c¡c tªp lçi.
ành l½ 1.1. Giao cõa mët hå tòy þ c¡c tªp lçi trong Rn l mët tªp lçi
trong Rn.
Chùng minh. Gi£ sû Aα ∈ Rn(α ∈ I) l c¡c tªp lçi vîi I l tªp ch¿ sè
A = ∩α∈I Aα l lçi.
L§y tòy þ x1 , x2 ∈ A. Khi â, x1 , x2 ∈ Aα , vîi ∀α ∈ I . Do Aα l lçi
cho n¶n λx1 + (1 − λ)x2 ∈ Aα vîi ∀λ ∈ [0, 1] → λx1 + (1 − λ)x2 ∈ A.
V¼ vªy, A l tªp lçi.
b§t k¼, ta c¦n chùng minh tªp
ành l½ 1.2. Gi£ sû Ai
lçi; λi ∈ R(i = 1, 2, . . . , m). Khi â,
λ1 A1 + λ2 A2 + . . . + λm Am l lçi.
ành ngh¾a 1.5. Vectì x ∈ Rn ÷ñc gåi l tê hñp lçi cõa c¡c vectì
x1 , x2 , . . . , xm ∈ Rn n¸u
⊂ Rn
∃λi ≥ 0, i = 1, 2, . . . , m,
m
X
i=1
λi = 1 : x =
m
X
i=1
λi xi .
5
ành l½ 1.3. Tªp A ⊂ Rn l lçi khi v ch¿ khi nâ chùa måi tê hñp lçi
cõa c¡c vectì cõa nâ, tùc l A ⊂ Rn lçi khi v ch¿ khi
∀m ∈ N, ∀λ1 , . . . , λm ≥ 0 :
m
X
λi = 1, ∀x1 , . . . , xm ∈ A →
i=1
m
X
λi xi ∈ A.
i=1
Chùng minh. Chån m = 2, hiºn nhiºn óng.
A l tªp lçi, ta l§y tòy þ x1 , . . . , xm ∈
m
P
λi = 1; x = . Ta chùng minh x ∈ A.
Ta chùng minh quy n¤p. Gi£ sû
A; λ1 , . . . , λm ≥ 0
m
P
v
i=1
i=1
m = 1 : x1 ∈ A; λ1 = 1 → x ∈ A.
m = 2 : x1 , x2 ∈ A; λ1 + λ2 = 1 m A
Gi£ sû x ∈ A óng vîi m − 1, ta câ
m
X
λi xi ∈ A; ∀xi ∈ A;
i=1
X²t
x=
m
P
Vîi
Vîi
Vîi
x = λ1 x1 + λ2 x2 ∈ A.
λi = 1; λi ≥ 0; i ∈ N.
i=1
λi xi =
i=1
m
X
lçi suy ra
m−1
P
λi xi + λm xm .
i=1
λm = 0 → x ∈ A.
λm = 1 → λ1 = . . . = λm−1 = 0 → x = xm ∈ A.
0 < λ < 1, ta câ:
1 − λm = λ1 + . . . + λm−1 > 0,
λi
≥ 0(i = 1, . . . , m − 1).
1 − λm
m−1
P
λi
= 1 n¶n
i=1 1 − λm
y ∈ A v xm ∈ A, ta câ
V¼
1 − λm > 0
v
theo gi£ thi¸t quy n¤p
y =
m−1
P
xi ∈ A.
Vîi
i=1
(1 − λm ) + λm = 1 → x = (1 − λm )y + λm xm ∈ A.
ành ngh¾a 1.6. Chi·u cõa mët tªp lçi A ÷ñc cho bði chi·u cõa a
t¤p affine nhä nh§t chùa A (khæng gian con song song vîi A), ÷ñc k½
hi»u l dimA. a t¤p affine n y ÷ñc gåi l bao affine cõa A, ÷ñc k½
hi»u af f A.
6
ành ngh¾a 1.7. iºm x0 cõa tªp lçi A ⊂ Rn ÷ñc gåi l iºm trong
t÷ìng èi cõa
A n¸u vîi måi x ∈ af f A câ mët sè λ > 0 sao cho
x0 + λ(x − x0 ) ∈ A. Ph¦n trong t÷ìng èi cõa A l tªp c¡c iºm trong
t÷ìng èi cõa A, ÷ñc k½ hi»u riA.
ành ngh¾a 1.8. Tªp A ⊂ Rn ÷ñc gåi l nân n¸u:
∀a ∈ A, ∀λ > 0
th¼ λx ∈ A.
Nân A ÷ñc gåi l nân nhån n¸u nâ khæng chùa ÷íng th¯ng. Nân A
÷ñc gåi l nân lçi n¸u A l tªp lçi. N¸u A l mët tªp lçi a di»n th¼ ta
nâi nân sinh bði A l nân lçi a di»n.
Mët v½ dö quan trång v· nân lçi trong
Rn
l nân orthant d÷ìng
Rn+ = {(x1 , x2 , . . . , xn ) : xi ≥ 0, i = 1, 2, . . . , n}.
ành ngh¾a 1.9. Gi£ sû A ⊆ Rn l tªp lçi v x0 ∈ A. Tªp
NA (x0 ) = {x∗ ∈ Rn : hx∗ , x − x0 i ≤ 0, ∀x ∈ A},
÷ñc gåi l nân ph¡p tuy¸n cõa A t¤i x0.
Hiºn nhi¶n, 0 ∈ NA(x0) n¶n ta câ NA(x0) l nân lçi âng.
1.1.2. C¡c ành lþ t¡ch
C¡c ành lþ t¡ch tªp lçi l mët trong nhúng nëi dung cì b£n v quan
trång nh§t cõa gi£i t½ch lçi.
ành ngh¾a 1.10. Si¶u ph¯ng trong khæng gian Rn l tªp t§t c£ c¡c
iºm câ d¤ng
{x ∈ Rn : aT x = α},
trong â, a ∈ Rn l vectì kh¡c 0 v α ∈ R.
ành ngh¾a 1.11. Tªp câ d¤ng
{x ∈ Rn : ha, xi ≥ α},
÷ñc gåi l nûa khæng gian âng, trong â a 6= 0 v α ∈ R.
7
Tªp
{x ∈ Rn : ha, xi > α},
÷ñc gåi l nûa khæng gian mð.
Mët si¶u ph¯ng s³ chia khæng gian ra l m hai nûa khæng gian, méi
nûa khæng gian ð v· mët ph½a cõa si¶u ph¯ng. Si¶u ph¯ng l ph¦n chung
cõa hai nûa khæng gian n¸u hai nûa khæng gian n y l âng.
ành ngh¾a 1.12. Cho hai tªp S v T kh¡c réng. Ta nâi si¶u ph¯ng
ht, xi = α
(i) t¡ch S v T n¸u
ht, xi ≤ α ≤ ht, yi, ∀x ∈ S, ∀y ∈ T.
(ii) t¡ch ch°t S v T n¸u
ht, xi < α < ht, yi, ∀x ∈ S, ∀y ∈ T.
(iii) t¡ch m¤nh S v T n¸u
supht, xi < α < inf ht, yi, ∀x ∈ S, ∀y ∈ T.
x∈S
y∈T
ành l½ 1.4. (ành lþ t¡ch 1). Cho S v T l hai tªp lçi kh¡c réng trong
sao cho S ∩ T = ∅. Khi â, ta câ mët si¶u ph¯ng t¡ch S v T .
ành l½ 1.5. (ành lþ t¡ch 2). Cho S v T l hai tªp lçi âng kh¡c réng
sao cho S ∩ T = ∅. Gi£ sû câ ½t nh§t mët tªp compact. Khi â, hai tªp
n y câ thº t¡ch m¤nh bði mët si¶u ph¯ng.
Rn
Chó þ 1.1.
N¸u gi£ thi¸t "mët trong hai tªp l compact" khæng thäa
m¢n th¼ ành lþ 1.5 khæng cán óng.
V½ dö 1.2. S = {(x, y) ∈ R2 | xy ≥ 1}
v
T = {(x, y) ∈ R2 | y ≤ 0}
l
hai tªp âng, ríi nhau nh÷ng khæng t¡ch m¤nh.
H» qu£ 1.1. (Bê · Farkas) Cho a ∈ Rn v A l ma trªn c§p m × n.
Khi â ha, xi ≥ 0 vîi måi x thäa m¢n Ax ≥ 0 khi v ch¿ khi tçn t¤i
y ≥ 0 thuëc Rm sao cho a = AT y .
8
H¼nh 1.1: T¡ch h¯n ÷ñc v khæng t¡ch h¯n ÷ñc
Þ ngh¾a h¼nh håc cõa Bê · Farkas: Si¶u ph¯ng i qua gèc tåa ë
ha, xi = 0 º nân Ax ≥ 0 v· mët ph½a cõa nâ khi v ch¿ khi vectì ph¡p
tuy¸n a cõa si¶u ph¯ng n¬m trong nân sinh bði c¡c h ng cõa ma trªn
A.
1.2. ành ngh¾a v t½nh ch§t cõa h m lçi
1.2.1. H m lçi
ành ngh¾a 1.13. H m f
A ⊆ Rn .
H m f ÷ñc gåi l
(i) h m lçi tr¶n A n¸u
: A → R ∪ {+∞}
x¡c ành tr¶n tªp lçi
f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y), ∀x, y ∈ A, x 6= y, ∀λ ∈ [0, 1].
(ii) h m lçi ch°t tr¶n A n¸u
f [(1 − λ)x + λy] < (1 − λ)f (x) + λf (y), ∀x, y ∈ A, x 6= y, ∀λ ∈ (0, 1).
(iii) h m lãm (lãm ch°t) tr¶n A n¸u h m −f l h m lçi (lçi ch°t) tr¶n
A.
(iv) h m affine tr¶n A n¸u f húu h¤n v vøa lçi vøa lãm tr¶n A.
9
f : A → R ∪ {+∞} câ thº ÷ñc mð rëng th nh h m
n
ành tr¶n to n bë R b¬ng c¡ch °t f (x) = +∞ vîi måi x ∈
/ A.
n
º ìn gi£n ta x²t h m lçi tr¶n to n R .
H m lçi
lçi x¡c
Do â,
Nhªn x²t 1.1.
•
H m affine khæng lçi ch°t hay lãm ch°t.
•
H m lçi ch°t l lçi nh÷ng i·u ng÷ñc l¤i khæng óng.
ành ngh¾a 1.14. Cho h m f : A → R ∪ {+∞} vîi A ⊆ Rn. Mi·n húu
döng cõa f l tªp
domf = {x ∈ A : f (x) < +∞}.
Tªp tr¶n ç thà cõa f l
epif = {(x, α) ∈ AxR : f (x) ≤ α}.
H m f ÷ñc gåi l h m lçi ch½nh th÷íng n¸u domf 6= ∅ v f (x) >
−∞, ∀x ∈ A.
ành l½ 1.6. H m lçi ch½nh th÷íng f tr¶n RnR li¶n töc t¤i måi iºm trong
cõa mi·n húu döng cõa nâ (f li¶n töc tr¶n domf ).
Nhªn x²t 1.2.
• epif
• f(
m
P
f
lçi tr¶n
A
n¸u v ch¿ n¸u
l mët tªp lçi, hay
λi xi ) ≤
i=1
i,
Ta câ thº chùng minh h m
trong â
m
P
λi f (xi ) vîi måi xi ∈ A,
λi = 1 v λi ≥ 0 vîi måi
i=1
i=1
m
m
P
l sè nguy¶n (b§t ¯ng thùc Jensen).
V½ dö 1.3.
a) H m
f :R→R
f (x) = x2
epif = {(x, µ) ∈ R × R; f (x) = x2 ≤ µ},
l tªp lçi trong
R×R⇒f
l h m lçi.
10
b) H m
f :R→R
f (x) = x3
khæng l h m lçi v¼
epif = {(x, µ) ∈ R × R; f (x) = x3 ≤ µ},
l khæng lçi trong
R × R.
ành ngh¾a 1.15. H m f (x) x¡c ành tr¶n tªp lçi C ⊂ Rn ÷ñc gåi l
lçi m¤nh tr¶n C , n¸u tçn t¤i h¬ng sè ρ > 0 (h¬ng sè lçi m¤nh) sao cho
vîi måi x, y ∈ C v vîi måi λ ∈ [0, 1] ta câ
f [λx + (1 − λ)y] ≤ λf (x) + (1 − λ)f (y) − λ(1 − λ)ρ||x − y||2 .
Chó þ 1.2.
H m lçi m¤nh th¼ lçi ch°t nh÷ng i·u ng÷ñc l¤i khæng óng.
V½ dö, h m
ex , x ∈ R
lçi ch°t nh÷ng khæng lçi m¤nh.
1.2.2. C¡c t½nh ch§t
ành l½ 1.7. Cho f v g l c¡c h m lçi tr¶n tªp lçi S v T t÷ìng ùng.
Khi â, c¡c h m αf + βg, (∀α, β ≥ 0) v max{f, g} l lçi tr¶n S ∩ T .
ành l½ 1.8. Mët h m lçi x¡c ành tr¶n tªp lçi A th¼ li¶n töc t¤i måi
iºm trong cõa A.
T½nh ch§t 1.1. Bèn ph²p to¡n cì b£n b£o to n h m lçi
• N¸u fi : Rn → R (i = 1, . . . , m) l h m lçi th¼ α1 f1 + . . . + αm fm lçi
vîi måi αi v lçi ch°t n¸u ½t nh§t mët trong c¡c h m fi lçi ch°t vîi
αi > 0.
• N¸u fi (i ∈ I) : Rn → R l h m lçi th¼ h m f (x) = sup fi (x) l h m
i∈I
lçi.
• N¸u S : Rn → R l bi¸n êi tuy¸n t½nh v f : Rn → R l h m lçi
th¼ h m hñp g(x) = f (Ax) l h m lçi.
11
N¸u f : T ⊆ Rn → R l h m lçi v g : R → R l h m lçi khæng
gi£m th¼ h m hñp h(x) = g(f (x)) l h m lçi.
ành l½ 1.9. X²t h m f : A → R∪{+∞} l lçi tr¶n Rn v α ∈ R∪{+∞}.
Khi â, câ c¡c tªp lçi:
• tªp c¡c mùc d÷îi
•
Cα = {x : f (x) < α}, Cα = {x : f (x) ≤ α},
•
tªp c¡c mùc tr¶n
Dβ = {x : f (x) > β}, Dβ = {x : f (x) ≥ α},
n¸u f l mët h m lãm tr¶n Rn
Chó þ 1.3.
H m
f
thäa m¢n måi tªp mùc d÷îi l tªp lçi ÷ñc gåi l
h m tüa lçi. V½ dö h m
f (x) = x3
tr¶n
R
l h m tüa lçi.
ành l½ 1.10. H m f (x), x ∈ Rn l h m lçi n¸u v ch¿ n¸u h m mët
bi¸n sè ϕ ≡ f (x + λd) l h m lçi theo λ vîi méi x, d ∈ Rn.
ành ngh¾a 1.16. Cho f l h m lçi ch½nh th÷íng tr¶n Rn; vectì t ∈ Rn
gåi l mët d÷îi gradient (d÷îi ¤o h m) cõa f t¤i x0 ∈ Rn n¸u
ht, x − x0 i + f (x0 ) ≤ f (x), ∀x ∈ Rn .
Tªp t§t c£ c¡c d÷îi gradient gåi l d÷îi vi ph¥n cõa h m f t¤i x0, k½
hi»u
∂f (x0 ) = {t ∈ Rn : ht, x − x0 if (x0 ) ≤ f (x), ∀x ∈ Rn }.
H m f ÷ñc gåi l kh£ d÷îi vi ph¥n t¤i x0 n¸u ∂f (x0) 6= ∅.
ành l½ 1.11. Cho f l mët h m lçi (húu h¤n) tr¶n tªp lçi C . Lóc â
f câ d÷îi vi ph¥n t¤i måi iºm thuëc riC .
Tø ành lþ n y ch¿ ra r¬ng n¸u
Rn
f
l mët h m lçi tr¶n to n khæng gian
th¼ nâ câ d÷îi vi ph¥n t¤i måi iºm v¼
riRn = Rn .
ành l½ 1.12. Cho f : Rn → R l lçi v x∗ ∈ domf th¼
f (x∗ ) = minn f (x) ⇔ 0 ∈ ∂f (x∗ ).
x∈R
12
Chùng minh. Thªt vªy, do f ¤t cüc tiºu t¤i x∗ ∈ domf n¶n
f (x) − f (x∗ ) ≥ 0 ⇔ f (x) − f (x∗ ) ≥ h0, x − x∗ i ⇔ 0 ∈ ∂f (x∗ ).
ành ngh¾a 1.17. Cho D ⊆ R l lçi, f : D → R l h m lçi v ≥ 0.
X²t b i to¡n:
min f (x).
(P)
x∈D
Mët iºm x∗ ∈ D ÷ñc gåi l - nghi»m cõa b i to¡n (P) khi
f (x∗ ) ≤ min f (x) + .
x∈D
M»nh · 1.2. Vectì x∗ ∈ D l - nghi»m cõa b i to¡n
khi 0 ∈ ∂f (x∗).
(P)
khi v ch¿
ành ngh¾a 1.18. Cho D l mët tªp lçi âng kh¡c réng tr¶n Rn, x ∈ Rn
v ≥ 0. Mët iºm px ∈ D ÷ñc gåi l - chi¸u cõa x tr¶n D n¸u px l
mët - nghi»m cõa b i to¡n
1
min{ ||x − y||2 },
y∈D 2
ngh¾a l ,
trong â,
(Q)
1
1
||x − px ||2 ≤ ||x − PD (x)||2 + ,
2
2
PD (x) l h¼nh chi¸u cõa x tr¶n D.
M»nh · 1.3. Cho D l tªp lçi âng kh¡c réng. Khi â, px l - chi¸u
cõa x tr¶n D khi v ch¿ khi
hx − px , px − yi ≥ −, ∀y ∈ D.
ành ngh¾a 1.19. Vîi t ∈ Rn\{0}, n¸u tçn t¤i giîi h¤n (húu h¤n hay
væ h¤n)
f (x0 + λt) − f (x0 )
,
λ→0
λ
lim
th¼ giîi h¤n â ÷ñc gåi l ¤o h m theo h÷îng t cõa h m f t¤i x0, k½
hi»u f 0(x0, t).
13
ành l½ 1.13. Cho f l mët h m lçi ch½nh th÷íng v x0 ∈ domf . Khi
â,
(i) f 0(x0, t) tçn t¤i vîi méi h÷îng t ∈ Rn v thäa m¢n
f (x0 + λt) − f (x0 )
.
λ>0
λ
f 0 (x0 , t) = inf
(ii) H m t 7→ f 0(x0, t) l lçi v thu¦n nh§t d÷ìng v x∗ ∈ ∂f (x0) n¸u
v ch¿ n¸u
hx∗ , ti ≤ f 0 (x0 , t), ∀t ∈ Rn .
(iii) N¸u f li¶n töc t¤i x0 th¼ f 0(x0, t) l húu h¤n v li¶n töc t¤i méi
t ∈ Rn , d÷îi vi ph¥n ∂f (x0 ) l compact v
f 0 (x0 , t) = max{hx∗ , ti|x∗ ∈ ∂f (x0 )}.
ành l½ 1.14. N¸u f l h m lçi tr¶n tªp lçi C th¼ vîi måi x ∈ C v måi
sao cho x + t ∈ C , ¤o h m theo h÷îng t cõa f t¤i x luæn tçn t¤i v
nghi»m óng
t
f 0 (x, t) ≤ f (x + t) − f (x).
Ngo i ra, vîi méi iºm x cè ành, f 0(x, .) l mët h m lçi tr¶n tªp lçi
{t : x + t ∈ C}.
Tø ành lþ n y suy ra n¸u
f
kh£ vi th¼
f 0 (x, t) = hOf (x), ti, ∀t.
ành l½ 1.15. Cho mët tªp lçi C ⊂ Rn v h m f : Rn → R kh£ vi tr¶n
C.
a) H m f lçi tr¶n C n¸u v ch¿ n¸u
f (y) ≥ f (x) + hOf (x), y − xi,
vîi måi x, y ∈ C .
b) N¸u
f (y) > f (x) + hOf (x), y − xi,
vîi måi x, y ∈ C v x 6= y th¼ h m f lçi ch°t tr¶n C .
14
1.3. C¡c ành lþ cì b£n v· d÷îi vi ph¥n h m lçi
Cho
f : Rn → R
l lçi, ch½nh th÷íng v
λ > 0,
ta câ
x ∈ domf , do f lçi, ch½nh th÷íng v
công lçi, ch½nh th÷íng v x ∈ dom(λf ).
0
0
Ta câ (λf ) (x, .) = λf (x, .), suy ra ∂(λf )(x) = λ∂f (x).
N¸u x ∈
/ domf th¼ ∂(λf )(x) = λ∂f (x) = ∅.
λ∂f (x).
Thªt vªy, vîi
∂(λf )(x) =
λ > 0 th¼ λf
ành lþ sau s³ gióp ta chùng minh mët sè t½nh ch§t cõa d÷îi vi ph¥n.
ành l½ 1.16. Cho f1, f2, . . . , fk l c¡c h m lçi húu h¤n tr¶n tªp lçi kh¡c
réng S trong Rn v cho A l ma trªn c§p m × n, b ∈ riA(S). N¸u h»:
x ∈ S, Ax = b, fi (x) < 0, i = 1, 2, . . . , k,
væ nghi»m th¼ tçn t¤i mët vectì t ∈ Rk v nhúng sè khæng ¥m λ1, λ2, . . . , λk
câ têng b¬ng 1 sao cho
ht, Ax − bi +
k
X
λi fi (x) ≥ 0, ∀x ∈ S.
i=1
Tø ành lþ n y ta câ thº chùng minh mët sè ành lþ sau.
ành l½ 1.17. (Moreau - Rockafellar) Cho f1, f2 l c¡c h m lçi ch½nh
th÷íng tr¶n Rn th¼ vîi méi x ∈ Rn câ
∂f1 (x) + ∂f2 (x) ⊂ ∂(f1 + f2 )(x).
Hìn núa, n¸u tçn t¤i mët iºm a ∈ domf1 ∩ domf2 v mët trong hai
h m l li¶n töc t¤i a ta câ bao h m thùc ng÷ñc l¤i.
ành l½ 1.18. Cho A : Rm → Rn l to¡n tû tuy¸n t½nh li¶n töc v f l
h m lçi ch½nh th÷íng tr¶n Rn th¼ vîi méi x ∈ Rm, ta câ
AT ∂f (Ax) ⊂ ∂(f ◦ A)(x).
N¸u f li¶n töc t¤i mët sè iºm trong Im(A) th¼ bao h m thùc tr¶n l
¯ng thùc vîi x ∈ Rn, trong â Im(A) l mi·n x¡c ành cõa A.
15
ành ngh¾a 1.20. Mët tªp con G cõa R × R ÷ñc gåi l ìn i»u khi
hx̄ − ȳ, x − yi ≥ 0,
nâ
trong â (x, x̄), (y, ȳ) ∈ G.
Mët ¡nh x¤ a trà T : R ⇒ 2R l mët to¡n tû ìn i»u n¸u ç thà cõa
G(T ) = {(x, x̄) ∈ R × R : x̄ ∈ T (x)},
l mët tªp ìn i»u. Mët tªp ìn i»u ÷ñc gåi l ìn i»u cüc ¤i n¸u
nâ l cüc ¤i trong hå cõa nhúng tªp con ìn i»u cõa R × R. Ta nâi
r¬ng mët to¡n tû ìn i»u T l ìn i»u cüc ¤i khi ç thà cõa nâ l
mët tªp ìn i»u cüc ¤i.
ành l½ 1.19. N¸u f l h m lçi, li¶n töc tr¶n R th¼ ¡nh x¤ d÷îi vi ph¥n
cõa nâ l ìn i»u cüc ¤i.
16
Ch֓ng 2
Vai trá cõa t½nh lçi trong b i to¡n
tèi ÷u
Ch÷ìng n y tr¼nh b y mët sè nëi dung v· vai trá cõa t½nh lçi trong
b i to¡n tèi ÷u ÷ñc tr½ch d¨n chõ y¸u tø t i li»u tham kh£o [2], [3], [4],
[5] v [6].
2.1. B i to¡n tèi ÷u lçi
2.1.1. B i to¡n tèi ÷u hâa ìn möc ti¶u
X²t b i to¡n d÷îi d¤ng
min{f (x) : x ∈ D},
trong â,
D
D⊆X
(th֒ng
: mi·n r ng buëc,
f
(P)
X ≡ Rn ), f : D → R.
: h m möc ti¶u.
ành ngh¾a 2.1. iºm x∗ ∈ D ÷ñc gåi l nghi»m tèi ÷u àa ph÷ìng
cõa (P) n¸u tçn t¤i l¥n cªn U cõa x∗ sao cho
f (x∗ ) ≤ f (x), ∀x ∈ U ∩ D.
N¸u
f (x∗ ) ≤ f (x), ∀x ∈ D,
th¼ x∗ ÷ñc gåi l nghi»m tèi ÷u to n cöc cõa (P).