Tài liệu 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 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 ch­n 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 th­ng 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 nh­c 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 s­c 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 nh­c 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∗ . º ng­n 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 nh­c 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 ng­n 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 ch­n logarith Trong möc n y, chóng ta t¼m hiºu ph÷ìng ph¡p h m ch­n 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 ch­n 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 ch­n logarith. Khi â, h m k¸t hñp (cõa h m möc ti¶u v  h m ch­n) 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 ch­n trong h m têng hñp v  ÷ñc gåi l  gåi l  khi tham sè ch­n. H m k¸t hñp P (x; µ) công ÷ñc h m ch­n 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 ch­n 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 ch­n 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 b­t ¦u xs0 ; for k = 0, 1, 2, . . . T¼m mët tèi thiºu g¦n óng xk cõa P (.; µk ), b­t ¦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è ch­n mîi µk+1 ∈ (0, µk ); Chån iºm b­t ¦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