..
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
-------------------------------
TRẦN VĂN PHƢỢNG
VỀ BÀI TOÁN TỐI ƢU
TRONG HỌC ĐỘ TƢƠNG TỰ
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KHOA HỌC
-------------------------------
TRẦN VĂN PHƢỢNG
VỀ BÀI TOÁN TỐI ƢU
TRONG HỌC ĐỘ TƢƠNG TỰ
Chuyên ngành: Toán ứng dụng
Mã số
: 8 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. Nguyễn Thanh Sơn
THÁI NGUYÊN - 2019
iii
Möc löc
B£ng kþ hi»u
1
Mð ¦u
2
Ch÷ìng 1 B i to¡n tèi ÷u trong khæng gian húu h¤n chi·u 6
1.1
Sì l÷ñc v· b i to¡n tèi ÷u
6
1.1.1
B i to¡n tèi ÷u
. . . . . . . . . . . . . . . . . . . .
6
1.1.2
Kh¡i qu¡t b i to¡n tèi ÷u câ r ng buëc . . . . . . .
8
1.1.3
Tèi ÷u h m möc ti¶u bªc hai vîi r ng buëc b§t
¯ng thùc
1.2
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . 10
Mët sè ph÷ìng ph¡p gi£i b i to¡n tèi ÷u
1.2.1
Ph÷ìng ph¡p Newton . . . . . . . . . . . . . . . . . 11
1.2.2
Ph÷ìng ph¡p gi£m s¥u nh§t . . . . . . . . . . . . . 13
1.2.3
Ph÷ìng ph¡p h m chn logarith . . . . . . . . . . . 15
1.2.4
Ph÷ìng ph¡p chi¸u gradient . . . . . . . . . . . . . 18
Ch÷ìng 2 B i to¡n håc ë t÷ìng tü
2.1
2.2
. . . . . . . . . . 11
21
B i to¡n håc ë t÷ìng tü v c¡c ki¸n thùc li¶n quan . . . . 21
2.1.1
Mët sè ki¸n thùc li¶n quan . . . . . . . . . . . . . . 21
2.1.2
B i to¡n håc ë t÷ìng tü . . . . . . . . . . . . . . . 25
2.1.3
T½nh lçi cõa b i to¡n . . . . . . . . . . . . . . . . . 26
2.1.4
Kho£ng c¡ch Mahalanobis
. . . . . . . . . . . . . . 27
Ph÷ìng ph¡p gi£i b i to¡n håc ë t÷ìng tü . . . . . . . . . 28
2.2.1
Tr÷íng hñp kho£ng c¡ch Euclide câ trång sè . . . . 28
iv
2.2.2
Ph÷ìng ph¡p chi¸u gradient cho b i to¡n håc ë
t÷ìng tü . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.3
V½ dö sè . . . . . . . . . . . . . . . . . . . . . . . . 32
K¸t luªn
T i li»u tham kh£o
36
37
B£ng kþ hi»u
H
khæng gian Hilbert thüc
∇f
gradient cõa h m sè, grad
∇2 f
Hessian cõa h m sè
kAk
chu©n Euclid cõa ma trªn
λ(A)
c¡c gi¡ trà ri¶ng cõa
A≥0
ma trªn nûa x¡c ành d÷ìng
A>0
ma trªn x¡c ành d÷ìng
x∗
iºm cüc tiºu hay cüc tiºu
f (x∗ )
gi¡ trà cüc tiºu
f
f
v l ma trªn cï
A
A
n×n
2
Mð ¦u
Th¸ giîi ang b÷îc v o Cuëc c¡ch m¤ng khoa håc l¦n thù t÷ vîi AI
(Artifical Intelligence - Tr½ tu» nh¥n t¤o) v IoT (Internet of Things Internet v¤n vªt) em ¸n nhúng ët ph¡ b§t ngí v· cæng ngh». Vai trá
cõa nâ èi vîi mët quèc gia, mët vòng l¢nh thê lîn ¸n mùc ÷ñc nhªn
ành, r¬ng ai d¨n ¦u v· cæng ngh» n y s³ chi¸n thng trong cuëc c¤nh
tranh v· cæng ngh», kinh t¸...
Trong thüc t¸, Tr½ tu» nh¥n t¤o m cö thº hìn núa l Håc m¡y
(Machine Learning) ¢ l mët ng nh con ph¡t triºn tø l¥u cõa khoa håc
m¡y t½nh. Luªn v«n n y s³ x²t mët b i to¡n nhä trong l¾nh vüc rëng lîn
n y d÷îi gâc ë to¡n håc, â l
Håc ë t÷ìng tü.
Trong mët khæng gian Euclide, hay têng qu¡t hìn l trong mët khæng
gian metric, kh¡i ni»m kho£ng c¡ch ÷ñc dòng º o kho£ng c¡ch giúa
hai èi t÷ñng. èi t÷ñng l tròng nhau n¸u kho£ng c¡ch b¬ng 0, ð g¦n
nhau n¸u kho£ng c¡ch nhä v xa nhau n¸u kho£ng c¡ch lîn.
B¥y gií, ta x²t mët tªp hñp têng qu¡t hìn nh÷ tªp c¡c h¼nh chöp
m°t ng÷íi, hay tªp c¡c v«n b£n. Gi£ sû ta câ thº bi¸n êi c¡c èi t÷ñng
â th nh c¡c èi t÷ñng to¡n håc nh÷ v²c tì ho°c ma trªn. Ta c¦n ph£i
x¥y düng mët ph²p o º câ thº ph¥n bi»t ÷ñc hai nhâm èi t÷ñng
t÷ìng tü nhau v kh¡c nhau. V· m°t ành l÷ñng, hai èi t÷ñng t÷ìng
tü nhau n¸u câ kho£ng c¡ch (theo ph²p o vøa ÷ñc x¥y düng) nhä v
hai èi t÷ñng kh¡c nhau s³ câ kho£ng c¡ch lîn.
C¥u häi ti¸p theo l x¥y düng ph²p o â nh÷ th¸ n o? Þ t÷ðng tü
3
nhi¶n l kh¡i qu¡t hâa kho£ng c¡ch Euclide. Ta câ vîi
kx − ykE =
trong â
I
q
kx − yk2 =
q
(x − y)T (x − y) =
q
x, y ∈ Rn
th¼
(x − y)T I(x − y),
I
b¬ng mët ma trªn
A v ành ngh¾a
q
kx − ykA = (x − y)T A(x − y).
(0.0.1)
l mët ma trªn ìn và. B¥y gií, ta thay
èi xùng nûa x¡c ành d÷ìng
L÷u þ r¬ng khi â (0.0.1) ch¿ l mët gi£ kho£ng c¡ch, tùc l hai iºm
0. Nh÷ vªy, vi»c x¥y düng kho£ng
kh¡c nhau câ thº câ kho£ng c¡ch b¬ng
c¡ch ÷ñc quy v· vi»c t¼m mët ma trªn èi xùng nûa x¡c ành d÷ìng.
N¸u khæng câ gñi þ g¼ th¼ ¥y l mët b i to¡n khæng câ líi gi£i. Ð
gâc ë Håc m¡y, muèn m¡y ph¥n bi»t ÷ñc th¸ n o l hai èi t÷ñng
l t÷ìng tü, th¸ n o l khæng t÷ìng tü th¼ ta ph£i d¤y nâ. Thæng tin
S
gñi þ ð ¥y l vi»c cho tr÷îc hai tªp con
èi t÷ñng (gi£ sû l
nhau, cán
D
Rn )
m trong â
S
v
D
cõa khæng gian c¡c
chùa nhúng èi t÷ñng t÷ìng tü
chùa nhúng èi t÷ñng khæng t÷ìng tü. Mët ph²p o tèt,
A,
trong tr÷íng hñp n y °c tr÷ng bði ma trªn
i) Kho£ng c¡ch giúa c¡c èi t÷ñng thuëc
S
ph£i thäa m¢n ba i·u:
theo ma trªn
A
c ng nhä
c ng tèt;
ii) Kho£ng c¡ch giúa c¡c èi t÷ñng thuëc
D theo ma trªn A ph£i t÷ìng
èi lîn;
iii) Ma trªn
A ph£i thäa m¢n c¡c i·u ki»n º x¥y düng ÷ñc gi£ kho£ng
c¡ch, tùc l
A
ph£i èi xùng v nûa x¡c ành d÷ìng.
Nhúng gñi þ tr¶n ¢ d¨n ¸n b i to¡n tèi ÷u sau:
arg min
A
X
kx − yk2A
(0.0.2)
(xi ,xj )∈S
sao cho
X
(xi ,xj )∈D
kx − ykA ≥ 1,
A ≥ 0.
(0.0.3)
4
Möc ½ch cõa · t i l tr¼nh b y vi»c gi£i b i to¡n tèi ÷u n£y sinh
trong håc ë t÷ìng tü (0.0.2), (0.0.3).
Nëi dung cõa · t i luªn v«n ÷ñc tr¼nh b y trong hai ch÷ìng.
Ch÷ìng 1. B i to¡n tèi ÷u trong khæng gian húu h¤n chi·u
Nëi dung ch½nh cõa ch÷ìng n y l c¡c ki¸n thùc v· tèi ÷u hâa. Chóng
tæi nhc l¤i mët c¡ch sì l÷ñc c¡c kh¡i ni»m cì b£n cõa b i to¡n tèi ÷u
v mët sè ph÷ìng ph¡p cho b i to¡n tèi ÷u khæng r ng buëc. Trong â,
chóng tæi i s¥u v o tr¼nh b y chi ti¸t ph÷ìng ph¡p chi¸u gradient s³
dòng ð Ch÷ìng 2. T i li»u tham kh£o ch½nh cho ch÷ìng n y l [2], [4].
Ch÷ìng 2. B i to¡n håc ë t÷ìng tü
Trong ch÷ìng n y, luªn v«n tr¼nh b y nhúng chõ · kh¡i qu¡t v· b i
to¡n håc ë t÷ìng tü. Sau â, chóng tæi i v o tr¼nh b y chi ti¸t b i
to¡n Håc ë t÷ìng tü theo lo¤t. Cán mët sè chõ · r§t thó và kh¡c nh÷
Håc ë t÷ìng tü online, Håc ë t÷ìng tü düa tr¶n lþ thuy¸t thæng tin
¢ khæng thº ÷ñc tr¼nh b y do khuæn khê câ h¤n cõa luªn v«n công
nh÷ sü h¤n ch¸ v· thíi gian v n«ng lüc. Sau còng, ch÷ìng n y tr¼nh
b y ph÷ìng ph¡p chi¸u gradient cho B i to¡n håc ë t÷ìng tü v v½ dö
sè minh håa cho ph÷ìng ph¡p â. Ch÷ìng n y tham kh£o c¡c t i li»u
[3], [5].
Luªn v«n ÷ñc ho n th nh t¤i Tr÷íng ¤i håc Khoa håc - ¤i håc
Th¡i Nguy¶n. Trong qu¡ tr¼nh håc tªp v thüc hi»n luªn v«n n y, Tr÷íng
¤i håc Khoa håc ¢ t¤o måi i·u ki»n tèt nh§t º t¡c gi£ håc tªp,
nghi¶n cùu. T¡c gi£ xin ÷ñc b y tä láng bi¸t ìn ch¥n th nh ¸n c¡c
th¦y, cæ trong khoa To¡n - Tin, trong Tr÷íng ¤i håc Khoa håc - ¤i
håc Th¡i Nguy¶n. °c bi»t, t¡c gi£ xin b y tä láng bi¸t ìn s¥u sc tîi
TS. Nguy¹n Thanh Sìn - Ng÷íi ¢ tªn t¼nh h÷îng d¨n t¡c gi£ ho n
5
th nh luªn v«n n y.
T¡c gi£ công xin ÷ñc gûi líi c£m ìn tîi Ban gi¡m hi»u tr÷íng THPT
Nguy¹n «ng ¤o v tªp thº c¡c th¦y cæ gi¡o trong tê To¡n-Tin cõa
Tr÷íng ¢ t¤o i·u ki»n gióp ï t¡c gi£ trong thíi gian t¡c gi£ tham
gia håc cao håc.
Th¡i Nguy¶n, th¡ng 04 n«m 2019
T¡c gi£ luªn v«n
Tr¦n V«n Ph÷ñng
6
Ch֓ng 1
B i to¡n tèi ÷u trong khæng gian
húu h¤n chi·u
Nëi dung ch½nh cõa ch÷ìng n y l c¡c ki¸n thùc v· tèi ÷u hâa. Chóng
tæi nhc l¤i mët c¡ch sì l÷ñc c¡c kh¡i ni»m cì b£n cõa b i to¡n tèi ÷u v
mët sè ph÷ìng ph¡p cho b i to¡n tèi ÷u bao gçm b i to¡n khæng r ng
buëc v b i to¡n câ r ng buëc. Trong â, chóng tæi i s¥u v o tr¼nh b y
chi ti¸t ph÷ìng ph¡p chi¸u gradient s³ dòng ð Ch÷ìng 2. T i li»u tham
kh£o ch½nh cho ch÷ìng n y l [2], [4].
1.1 Sì l÷ñc v· b i to¡n tèi ÷u
Möc n y s³ tr¼nh b y kh¡i ni»m, k¸t qu£ cì b£n º câ c¡i nh¼n kh¡i
qu¡t v· b i to¡n tèi ÷u.
1.1.1 B i to¡n tèi ÷u
Cho
f : Rn → R.
T¼m cüc tiºu àa ph÷ìng
x∗
f (x∗ ) ≤ f (x), ∀x ∈ Ux∗ ,
trong â,
U x∗
l l¥n cªn àa ph÷ìng n o â cõa
min f (x).
x
cõa
f,
ngh¾a l ,
(1.1.1)
x∗ . º ngn gån, ta vi¸t
(1.1.2)
7
h m möc ti¶u,
• x∗ : iºm cüc tiºu hay cüc tiºu,
• f (x∗ ) : gi¡ trà cüc tiºu,
• B i to¡n (1.1.1): B i to¡n cüc tiºu khæng r ng buëc.
B i to¡n cüc tiºu câ r ng buëc (constrained optimization) l b i to¡n
• f:
t¼m
x∗
sao cho
f (x∗ ) ≤ f (x), ∀x ∈ Ux∗ ∩ U,
vîi
U
(1.1.3)
cho tr÷îc. Nâ câ thº vi¸t d÷îi d¤ng
min f (x).
x∈U
B i to¡n cüc tiºu to n cöc (global optimization) l b i to¡n t¼m x∗
sao cho
f (x∗ ) ≤ f (x), ∀x.
(1.1.4)
i·u ki»n tèi ÷u
C¡c i·u ki»n c¦n thi¸t cho sü tèi ÷u ÷ñc rót ra b¬ng c¡ch gi£ sû
r¬ng
x∗
∇f (x∗ )
l iºm cüc tiºu àa ph÷ìng v sau â chùng minh t½nh ch§t cõa
v
∇2 f (x∗ ).
ành lþ 1.1.1 (i·u ki»n c¦n). Cho f ∈ C 2(Ux ) v x∗ l mët cüc tiºu
∗
àa ph÷ìng cõa f . Khi â
∇f (x∗ ) = 0.
Hìn núa, ta cán câ
∇2 f (x∗ ) ≥ 0.
Tø ành l½ tr¶n ta ành ngh¾a c¡c kh¡i ni»m sau:
8
ành ngh¾a 1.1.2 i·u ki»n ∇f (x∗) = 0 ÷ñc gåi l i·u ki»n c¦n c§p
mët. x∗ thäa m¢n i·u ki»n c¦n c§p mët ÷ñc gåi l iºm døng hay iºm
tîi h¤n.
ành lþ 1.1.3 (i·u ki»n õ). Cho f ∈ C 2(Ux ). Gi£ sû ∇f (x∗) = 0
∗
v ∇2f (x∗) > 0. Khi â, x∗ l mët cüc tiºu àa ph÷ìng cõa f .
1.1.2 Kh¡i qu¡t b i to¡n tèi ÷u câ r ng buëc
Tø möc n y cho ¸n h¸t ch÷ìng 1, ta s³ x²t b i to¡n tèi ÷u r ng buëc
têng qu¡t nh÷ sau
(
minn (f (x))
x∈R
trong â
f, ci , cj
nhc l¤i r¬ng
f
sao cho
ci (x) = 0, i ∈ E
l c¡c h m trìn v
I, E
l c¡c tªp ch¿ sè húu h¤n. Ta
÷ñc gåi l h m möc ti¶u,
buëc ¯ng thùc v
cj (x), j ∈ I
(1.1.5)
cj (x) ≥ 0, j ∈ I
ci (x), i ∈ E
l c¡c h m r ng
l c¡c h m r ng buëc b§t ¯ng thùc. Ta
k½ hi»u
Ω = {x ∈ Rn : ci (x) = 0, i ∈ E, cj (x) ≥ 0, j ∈ I},
v gåi nâ l
(1.1.6)
tªp ch§p nhªn ÷ñc. Theo â, B i to¡n (1.1.5) câ thº ÷ñc
vi¸t l¤i ð d¤ng
min f (x).
x∈Ω
iºm
x∗ ∈ Rn
÷ñc gåi l
v câ mët l¥n cªn
N
cõa
mët nghi»m àa ph÷ìng cõa (1.1.5) n¸u x ∈ Ω
x∗
trong
Rn
sao cho
f (x) ≥ f (x∗ ), ∀x ∈ N ∩ Ω.
N¸u ta thay d§u "≥" trong (1.1.8) bði ">" ta câ kh¡i ni»m
ph÷ìng ch°t.
(1.1.7)
(1.1.8)
nghi»m àa
9
ành ngh¾a 1.1.4 Cho x ∈ Ω, tªp ho¤t (active set) k½ hi»u A(x) ÷ñc
ành ngh¾a l
A(x) = E ∪ {i ∈ I : ci (x) = 0}.
R ng buëc b§t ¯ng thùc i ÷ñc gåi l ho¤t (active) n¸u ci(x) = 0 v
ng÷ñc l¤i n¸u ci(x) > 0 th¼ ÷ñc gåi l khæng ho¤t.
ành ngh¾a 1.1.5 Ta nâi t¤i iºm x i·u ki»n r ng buëc ëc lªp tuy¸n
t½nh (LICQ) ÷ñc thäa m¢n n¸u t¤i â tªp c¡c gradient cõa c¡c r ng
buëc ho¤t,
{∇ci (x), i ∈ A(x)}
l ëc lªp tuy¸n t½nh.
Vîi c¡c nguy¶n li»u tr¶n, ta câ thº ph¡t biºu ành lþ v· i·u ki»n c¦n
tèi ÷u cì b£n nh§t cõa b i to¡n tèi ÷u câ r ng buëc, i·u ki»n KarushKuhn- Tucker hay ngn gån l i·u ki»n KKT.
ành lþ 1.1.6 Gi£ sû x∗ l mët nghi»m àa ph÷ìng cõa b i to¡n
(1.1.5)
vîi h m möc ti¶u v h m r ng buëc thuëc lîp C 1 v i·u ki»n LICQ ÷ñc
thäa m¢n. Khi â câ mët nh¥n tû Lagrange λ∗ = (λ∗i ), i ∈ E ∪ I sao cho
c¡c i·u ki»n sau ¥y thäa m¢n t¤i iºm (x∗, λ∗)
∇x L(x∗ , λ∗ ) = 0,
ci (x∗ ) = 0, vîi
(1.1.10)
ci (x∗ ) ≥
(1.1.11)
λ∗i ≥
λ∗i ci (x∗ ) =
måi i ∈ E,
0, vîi måi i ∈ I,
0, vîi måi i ∈ I,
0, vîi måi i ∈ E ∪ I.
(1.1.9)
Chùng minh cõa ành lþ n y ÷ñc tr¼nh b y chi ti¸t trong [4].
(1.1.12)
(1.1.13)
10
1.1.3 Tèi ÷u h m möc ti¶u bªc hai vîi r ng buëc b§t ¯ng
thùc
Trong möc n y, º t«ng t½nh têng qu¡t chóng tæi s³ x²t b i to¡n sau
1
min q(x) = xT Gx + xT c,
x
2
(1.1.14)
aTi x = bi , i ∈ E,
(1.1.15)
aTi x ≥ bi , i ∈ I,
(1.1.16)
sao cho
trong â
G
l mët ma trªn èi xùng cï
n × n, c, ai , bi
l c¡c v²c tì cho
tr÷îc. N¸u b i to¡n khæng câ r ng buëc ¯ng thùc, ta ch¿ vi»c coi
E =∅
trong c¡c ph¡t biºu. So vîi b i to¡n têng qu¡t (1.1.5), h m möc ti¶u l
mët h m bªc hai v c¡c r ng buëc l c¡c h m tuy¸n t½nh. N¸u
G l mët
ma trªn nûa x¡c ành d÷ìng, ta nâi â l b i to¡n quy ho¤ch (tèi ÷u)
to n ph÷ìng lçi. N¸u
G l x¡c ành d÷ìng, b i to¡n ÷ñc gåi l lçi ch°t.
Tr÷íng hñp cán l¤i, vi»c gi£i B i to¡n (1.1.14)-(1.1.16) s³ khâ hìn v¼
nâ câ thº câ nhi·u cüc trà àa ph÷ìng ho°c iºm døng.
Tr÷îc h¸t, ta h¢y ¡p döng lþ thuy¸t têng qu¡t cõa tèi ÷u câ r ng
buëc v o B i to¡n (1.1.14)-(1.1.16). H m Lagrange cho b i to¡n n y l
X
1
L(x, λ) = xT Gx + xT c −
λi (aTi x − bi ).
2
i∈I∪E
Khi â, tªp ch¿ sè ho¤t t¤i
x∗ , A(x∗ )
bao gçm c¡c ch¿ sè thäa m¢n
A(x∗ ) = i ∈ E ∪ I : aTi x∗ = bi .
p döng c¡c i·u ki»n cõa ành lþ 1.1.6, ta suy ra i·u ki»n c¦n tèi ÷u
11
cho nghi»m
x∗
l tçn t¤i c¡c nh¥n tû Lagrange
Gx∗ + c −
X
λ∗i , i ∈ A(x∗ )
º cho
λ∗i ai = 0,
(1.1.17)
i∈A(x∗ )
aTi x∗ = bi , i ∈ A(x∗ ),
(1.1.18)
aTi x∗ ≥ bi , i ∈ I\A(x∗ ),
(1.1.19)
λ∗i ≥ 0, ∀i ∈ I ∩ A(x∗ ).
(1.1.20)
L÷u þ r¬ng ta khæng c¦n ¸n i·u ki»n LICQ nh÷ ành lþ 1.1.6 ð ¥y.
Sau ¥y, ta s³ ph¡t biºu mët tr÷íng hñp °c bi»t nh÷ng r§t hay g°p
trong thüc t¸ khi gi£i b i to¡n tèi ÷u to n ph÷ìng.
ành lþ 1.1.7 N¸u x∗ thäa m¢n c¡c i·u ki»n
vîi c¡c
λ∗i ∈ A(x∗ ) n o â v G l nûa x¡c ành d÷ìng (bao gçm x¡c ành
d÷ìng) th¼ x∗ l mët nghi»m to n cöc cõa B i to¡n (1.1.14)-(1.1.16).
(1.1.18) (1.1.20)
Chùng minh cõa ành lþ n y ÷ñc tr¼nh b y trong [4]. Công tø chùng
minh, ta suy r¬ng n¸u
G
x¡c ành d÷ìng th¼
x∗
l nghi»m duy nh§t.
1.2 Mët sè ph÷ìng ph¡p gi£i b i to¡n tèi ÷u
Nëi dung trong möc n y ÷ñc tr½ch d¨n tø t i li»u tham kh£o [2].
1.2.1 Ph÷ìng ph¡p Newton
Trong möc n y, ta gi£ sû r¬ng c¡c i·u ki»n sau ¥y luæn ÷ñc thäa
m¢n.
ành ngh¾a 1.2.1 C¡c i·u ki»n sau ªy ÷ñc gåi l gi£ thi¸t ti¶u
chu©n.
• f kh£ vi c§p hai v tho£ m¢n i·u ki»n Lipschitz vîi Hessian
k∇2 f (x) − ∇2 f (x)k ≤ γkx − yk.
12
•
H m f thäa m¢n i·u ki»n c¦n t¤i x∗
∇f (x∗ ) = 0.
•
H m f câ Hesian spd t¤i x∗
∇2 f (x∗ ) > 0.
Ph÷ìng ph¡p Newton x¥y düng mët d¢y l°p hëi tö tîi nghi»m. Ta s³
tªp trung ph¥n t½ch vi»c t¼m gi¡ trà ti¸p theo
x+
tø gi¡ trà hi»n t¤i
C¡ch l m ð ¥y l t¼m cüc tiºu cõa mët x§p x¿ bªc hai, m ta gåi l
h¼nh bªc hai, cõa f xung quanh xc
xc .
mæ
1
mc (x) = f (xc ) + ∇f (xc )T (x − xc ) + (x − xc )T ∇2 f (xc )(x − xc ).
2
2
N¸u ∇ f (xc ) > 0, cüc tiºu duy nh§t x+ cõa mc (x) l nghi»m duy nh§t
cõa ph÷ìng tr¼nh
∇mc (x) = 0.
i·u n y t÷ìng ÷ìng vîi
0 = ∇mc (x+ ) = ∇f (xc ) + ∇2 f (xc )(x+ − xc ).
Do â
x+ = xc − (∇2 f (xc ))−1 ∇f (xc ).
Khi â, b÷îc cªp nhªt s³ l
x+ = xc + s,
vîi
s = −(∇2 f (xc ))−1 ∇f (xc ).
L÷u þ r¬ng n¸u
nghi»m
x+
xc
xa cüc tiºu th¼
∇2 f (xc )
câ thº khæng l spd n¶n
câ thº l cüc ¤i ho°c iºm y¶n ngüa. Tuy nhi¶n i·u n y bà
lo¤i trø do gi£ thi¸t
∇2 f (x∗ ) > 0
cõa gi£ thi¸t ti¶u chu©n.
Sü hëi tö cõa ph÷ìng ph¡p Newton ÷ñc n¶u trong ành l½ sau.
ành lþ 1.2.2 Gi£ sû c¡c gi£ thi¸t ti¶u chu©n ÷ñc thäa m¢n. X²t d¢y
l°p
xk+1 = xk + pk ,
13
vîi pk = −∇2fk−1∇fk . Khi â:
• N¸u x0 õ g¦n x∗ th¼ d¢y {xk } hëi tö tîi x∗ .
• Tèc ë hëi tö l q -bªc hai.
• D¢y chu©n cõa gradient {k∇fk k} hëi tö q -bªc hai tîi 0.
1.2.2 Ph÷ìng ph¡p gi£m s¥u nh§t
Nh÷ ¢ bi¸t h÷îng gi£m s¥u nh§t (steepest descent) t¤i
d = −∇f (x).
Ph÷ìng ph¡p n y cªp nhªt
xc
λ>0
l
bði cæng thùc
x+ = xc − λ∇f (xc ),
trong â
x
(1.2.1)
l ë d i b÷îc.
M°c dò ta ¢ x¡c ành ÷ñc h÷îng gi£m s¥u nh§t, nh÷ng vi»c x¡c
ành ÷ñc ë d i b÷îc
chån tèt nh§t cho
λ
λ
l tèi quan trång cõa ph÷ìng ph¡p n y. Lüa
l nâ tèi thiºu hâa h m
φ(λ) = f (xc − λ∇f (xc )).
Nh÷ng b i to¡n n y trong h¦u h¸t tr÷íng hñp công khæng d¹ gi£i hìn
b i to¡n cüc trà ban ¦u. V¼ th¸, ng÷íi ta t¼m mët c¡ch ti¸p cªn nîi
läng. Ta x²t mæ h¼nh x§p x¿ bªc mët cõa
f (x)
mc (x) = f (xc ) + ∇f (xc )(x − xc ).
Qua b÷îc cªp nhªt (1.2.1), mæ h¼nh bªc mët (l x§p x¿ Taylor bªc mët
cõa h m möc ti¶u) s³ gi£m
pred = mc (xc ) − mc (x+ )
= ∇f (xx )(xc − x+ )
= λk∇f (xc )k2 .
V ë gi£m t÷ìng ùng cõa h m möc ti¶u l
ared = f (xc ) − f (x+ ).
14
Ta s³ r ng buëc i·u ki»n
ared > αλpred ,
hay t֓ng ֓ng
f (xc − λ∇) − f (xc ) < −αλk∇f (xc )k2 .
(1.2.2)
Þ ngh¾a cõa i·u ki»n n y l ë gi£m thüc sü cõa h m möc ti¶u ph£i
lîn hìn t½ch cõa ë gi£m mæ h¼nh bªc mët vîi h» sè
th÷íng, ng÷íi ta hay chån
º x¡c ành ë d i b÷îc
(backtracking). Ta chån
t¼m sè nguy¶n d÷ìng
cö thº hâa ð váng l°p
m
α
d÷ìng. Thæng
α = 10−4 .
λ,
ta câ thº sû döng mët
β ∈ (0; 1)
thõ töc truy ng÷ñc
(câ thº chån b¬ng
nhä nh§t sao cho
λ = β m.
0, 9)
v sau â,
Thõ töc n y ÷ñc
while trong cõa Thuªt to¡n 1. ¥y công l mët
c¡ch thæng döng º x¡c ành ë d i b÷îc èi vîi nhúng ph÷ìng ph¡p
t¼m theo ÷íng th¯ng kh¡c.
Algorithm 1 Thuªt to¡n gi£m s¥u-steep
Input:
x, f, τ, kmax , α, β
Output: mët x§p x¿ cõa
1:
r0 = k∇f (x)k
2:
tol = τa r0 + τr
3:
k = 2;
4: while
k∇f (x)k > tol
x∗
and
k < kmax
5:
m=1
6:
ared = f (x) − f (x − β∇f (x))
7:
pred = βk∇f (x)k2
8: while
9:
ared ≤ αpred
do
do
m=m+1
10:
ared = f (x) − f (x − β m ∇f (x))
11:
pred = β m k∇f (x)k2
12: end while
13:
x = x + λx
14: end while
15:
N¸u
k = kmax
th¼ b¡o ch÷ìng tr¼nh th§t b¤i
15
Kh¡i qu¡t i·u ki»n (1.2.2), ta câ i·u ki»n
f (xc + λd) − f (xc ) < αλ∇f (xc )T d,
trong â
α ∈ (0, 1) l tham sè thuªt to¡n. Công nh÷ ph÷ìng ph¡p gi£m
s¥u nh§t, ta th÷íng chån
α = 10−4 .
i·u ki»n n y ch½nh l
i·u ki»n
Armijo v th÷íng ÷ñc gåi l i·u ki»n gi£m õ (sufficient condition).
1.2.3 Ph÷ìng ph¡p h m chn logarith
Trong möc n y, chóng ta t¼m hiºu ph÷ìng ph¡p h m chn logarith
cho b i to¡n tèi ÷u r ng buëc d¤ng b§t ¯ng thùc. Cö thº ta x²t b i
to¡n tèi ÷u
min f (x),
x
sao cho
: ci (x) ≥ 0, i ∈ I.
(1.2.3)
Ta ành ngh¾a mi·n húu h¤n ng°t
F 0 := {x ∈ Rn : ci (x) > 0,
vîi måi
i ∈ I},
(1.2.4)
v gi£ sû r¬ng mi·n kh¡c réng. Ta s³ x¥y düng h m chn cho B i to¡n
(1.2.3), (1.2.4) vîi c¡c t½nh ch§t sau:
(i) gi¡ trà væ còng khi
(ii) trìn trong
F 0,
∞
khi
(iii) ti¸n tîi
x
x∈
/ F 0,
ti¸n ¸n bi¶n
F 0.
Câ thº th§y h m
−
X
log ci (x),
(1.2.5)
i∈I
vîi
log
l logarith cì sè tü nhi¶n, thäa m¢n c¡c t½nh ch§t (i)-(iii). Nâ
÷ñc gåi l h m chn logarith. Khi â, h m k¸t hñp (cõa h m möc ti¶u
v h m chn) cho B i to¡n (1.2.3), (1.2.4) ÷ñc cho bði
P (x; µ) = f (x) − µ
X
i∈I
log ci (x),
(1.2.6)
16
trong â
µ
l mët h¬ng sè i·u ch¿nh vai trá cõa h m chn trong h m
têng hñp v ÷ñc gåi l
gåi l
khi
tham sè chn. H m k¸t hñp P (x; µ) công ÷ñc
h m chn log cho B i to¡n tèi ÷u (1.2.3), (1.2.4). Ta nhªn th§y
µ ti¸n
v·
0,
h m chn
log P (x; µ) d¦n
v· h m möc ti¶u ban ¦u cõa
B i to¡n (1.2.3). Nh÷ vªy, c¡ch ti¸p cªn cõa ph÷ìng ph¡p h m chn
log
l thay th¸ b i to¡n tèi ÷u vîi r ng buëc b§t ¯ng thùc b¬ng mët hå
c¡c b i to¡n tèi ÷u khæng r ng buëc phö thuëc v o tham sè. Theo â,
ta câ thº mæ t£ l¤i quy tr¼nh n y trong Thuªt to¡n 2.
Algorithm 2 Ph÷ìng ph¡p Log-barrier
Cho µ0 > 0, dung sai τ0 > 0, iºm bt ¦u xs0 ;
for k = 0, 1, 2, . . .
T¼m mët tèi thiºu g¦n óng xk cõa P (.; µk ), bt ¦u tø xsk ,
v k¸t thóc khi k∇P (x; µk )k ≤ τk ;
if kiºm tra sü hëi tö cuèi còng ¢ thäa m¢n
stop vîi nghi»m g¦n óng x ;
k
Chån tham sè chn mîi µk+1 ∈ (0, µk );
Chån iºm bt ¦u mîi xsk+1 ;
end (for)
º t¼m iºm cüc tiºu ð b÷îc 3 trong Thuªt to¡n 2, ta câ thº sû döng
ph÷ìng ph¡p Newton cho b i to¡n tèi ÷u khæng r ng buëc tr¼nh b y ð
Möc 1.2.1.
ành lþ sau ¥y s³ cung c§p cho chóng ta mèi quan h» giúa B i to¡n
tèi ÷u khæng r ng buëc (1.1.5) v B i to¡n tèi ÷u câ r ng buëc (1.2.3).
ành lþ 1.2.3 Gi£ sû r¬ng f v −ci, i ∈ I ·u l c¡c h m lçi v mi·n
húu hi»u ng°t F 0 l khæng réng. °t {µk } l mët d¢y gi£m sao cho
µk ↓ 0, v gi£ sû r¬ng tªp hñp nghi»m M l khæng trèng v giîi nëi.
Khi â, c¡c kh¯ng ành sau l óng.
(i) Vîi måi µ > 0, P (x; µ) l lçi trong F 0 v câ mët cüc tiºu x(µ)
(khæng nh§t thi¸t ph£i l duy nh§t) tr¶n F 0. B§t ký cüc tiºu àa
- Xem thêm -