Luận văn Thạc sĩ Toán học: Về bài toán tối ưu trong học độ tương tự

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST

Báo xấu

9
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục tiêu nghiên cứu của luận văn là trình bày việc giải toán tối ưu nảy sinh trong độ học tương tự. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung luận văn này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Về bài toán tối ưu trong học độ tương tự

ĐẠ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 . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Mët sè ph÷ìng ph¡p gi£i b i to¡n tèi ÷u . . . . . . . . . . 11 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ü 21 2.1 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 2.2 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 36 T i li»u tham kh£o 37
B£ng kþ hi»u H khæng gian Hilbert thüc ∇f gradient cõa h m sè, grad f ∇2 f Hessian cõa h m sè f v l ma trªn cï n×n kAk chu©n Euclid cõa ma trªn A λ(A) c¡c gi¡ trà ri¶ng cõa 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
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 x, y ∈ Rn th¼ q q q kx − ykE = kx − yk2 = (x − y)T (x − y) = (x − y)T I(x − y), trong â I l mët ma trªn ìn và. B¥y gií, ta thay I b¬ng mët ma trªn èi xùng nûa x¡c ành d÷ìng A v ành ngh¾a q kx − ykA = (x − y)T A(x − y). (0.0.1) L÷u þ r¬ng khi â (0.0.1) ch¿ l mët gi£ kho£ng c¡ch, tùc l hai iºm kh¡c nhau câ thº câ kho£ng c¡ch b¬ng 0. Nh÷ vªy, vi»c x¥y düng kho£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 gñi þ ð ¥y l vi»c cho tr÷îc hai tªp con S v D cõa khæng gian c¡c èi t÷ñng (gi£ sû l Rn ) m trong â S chùa nhúng èi t÷ñng t÷ìng tü nhau, cán D chùa nhúng èi t÷ñng khæng t÷ìng tü. Mët ph²p o tèt, trong tr÷íng hñp n y °c tr÷ng bði ma trªn A, ph£i thäa m¢n ba i·u: i) Kho£ng c¡ch giúa c¡c èi t÷ñng thuëc S 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: X arg min kx − yk2A (0.0.2) A (xi ,xj )∈S sao cho X kx − ykA ≥ 1, A ≥ 0. (0.0.3) (xi ,xj )∈D
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∗ cõa f, ngh¾a l , f (x∗ ) ≤ f (x), ∀x ∈ Ux∗ , (1.1.1) trong â, U x∗ l l¥n cªn àa ph÷ìng n o â cõa x∗ . º ngn gån, ta vi¸t min f (x). (1.1.2) x
7 • f: 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 t¼m x∗ sao cho f (x∗ ) ≤ f (x), ∀x ∈ Ux∗ ∩ U, (1.1.3) vîi U 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∗ l iºm cüc tiºu àa ph÷ìng v sau â chùng minh t½nh ch§t cõa ∇f (x∗ ) 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 ( ci (x) = 0, i ∈ E minn (f (x)) sao cho (1.1.5) x∈R cj (x) ≥ 0, j ∈ I trong â f, ci , cj l c¡c h m trìn v I, E l c¡c tªp ch¿ sè húu h¤n. Ta nhc l¤i r¬ng f ÷ñc gåi l h m möc ti¶u, ci (x), i ∈ E l c¡c h m r ng buëc ¯ng thùc v cj (x), j ∈ I 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}, (1.1.6) v gåi nâ l 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). (1.1.7) x∈Ω iºm x∗ ∈ Rn ÷ñc gåi l mët nghi»m àa ph÷ìng cõa (1.1.5) n¸u x ∈ Ω v câ mët l¥n cªn N cõa x∗ trong Rn sao cho f (x) ≥ f (x∗ ), ∀x ∈ N ∩ Ω. (1.1.8) N¸u ta thay d§u "≥" trong (1.1.8) bði ">" ta câ kh¡i ni»m nghi»m àa ph÷ìng ch°t.
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 Karush- Kuhn- 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, (1.1.9) ci (x∗ ) = 0, vîi måi i ∈ E, (1.1.10) ci (x∗ ) ≥ 0, vîi måi i ∈ I, (1.1.11) λ∗i ≥ 0, vîi måi i ∈ I, (1.1.12) λ∗i ci (x∗ ) = 0, vîi måi i ∈ E ∪ I. (1.1.13) Chùng minh cõa ành lþ n y ÷ñc tr¼nh b y chi ti¸t trong [4].
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, (1.1.14) x 2 sao cho aTi x = bi , i ∈ E, (1.1.15) aTi x ≥ bi , i ∈ I, (1.1.16) 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 1 X 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 λ∗i , i ∈ A(x∗ ) º cho X Gx∗ + c − λ∗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 (1.1.18) (1.1.20) λ∗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). 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 xc . 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 mæ h¼nh bªc hai, cõa f xung quanh xc 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 xc xa cüc tiºu th¼ ∇2 f (xc ) câ thº khæng l spd n¶n nghi»m x+ 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 x l d = −∇f (x). Ph÷ìng ph¡p n y cªp nhªt xc bði cæng thùc x+ = xc − λ∇f (xc ), (1.2.1) trong â λ>0 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 λ l tèi quan trång cõa ph÷ìng ph¡p n y. Lüa chån tèt nh§t cho λ 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è α d÷ìng. Thæng th÷íng, ng÷íi ta hay chån α = 10−4 . º x¡c ành ë d i b÷îc λ, ta câ thº sû döng mët thõ töc truy ng÷ñc (backtracking). Ta chån β ∈ (0; 1) (câ thº chån b¬ng 0, 9) v sau â, t¼m sè nguy¶n d÷ìng m nhä nh§t sao cho λ = β m. Thõ töc n y ÷ñc cö thº hâa ð váng l°p 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 x∗ 1: r0 = k∇f (x)k 2: tol = τa r0 + τr 3: k = 2; 4: while k∇f (x)k > tol and k < kmax do 5: m=1 6: ared = f (x) − f (x − β∇f (x)) 7: pred = βk∇f (x)k2 8: while ared ≤ αpred do 9: 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), sao cho : ci (x) ≥ 0, i ∈ I. (1.2.3) x 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 / F 0, x∈ (ii) trìn trong F 0, (iii) ti¸n tîi ∞ khi x 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 X P (x; µ) = f (x) − µ log ci (x), (1.2.6) i∈I
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 tham sè chn. H m k¸t hñp P (x; µ) công ÷ñc gåi l h m chn log cho B i to¡n tèi ÷u (1.2.3), (1.2.4). Ta nhªn th§y khi µ 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