Tài liệu Hàm lồi suy rộng và ứng dụng

1 LÍI CƒM ÌN Tæi xin b y tä láng bi¸t ìn s¥u s­c tîi PGS.TS. Nguy¹n N«ng T¥m - tr÷íng ¤i håc s÷ ph¤m H  Nëi 2 ¢ h÷îng d¨n v  ch¿ b£o tªn t¼nh º tæi ho n th nh luªn v«n n y. Tæi xin ch¥n th nh c£m ìn c¡c Th¦y cæ cõa tr÷íng ¤i håc S÷ ph¤m H  Nëi 2 ¢ truy·n thö ki¸n thùc cho tæi trong suèt qu¡ tr¼nh håc tªp vøa qua. Tæi xin c£m ìn cì quan, b¤n b± çng nghi»p, gia ¼nh ¢ chia s´, gióp ï, ëng vi¶n, t¤o måi i·u ki»n thuªn lñi º tæi ho n thi»n luªn v«n n y. H  Nëi, ng y 05 th¡ng 11 n«m 2013 T¡c gi£ inh Thøa Vô 1 LÍI CAM OAN Luªn v«n ÷ñc ho n th nh t¤i tr÷íng ¤i håc s÷ ph¤m H  Nëi 2 d÷îi sü h÷îng d¨n cõa PGS.TS Nguy¹n N«ng T¥m. Tæi xin cam oan luªn v«n l  k¸t qu£ nghi¶n cùu cõa ri¶ng tæi . trong qu¡ tr¼nh nghi¶n cùu v  ho n th nh luªn v«n tæi ¢ k¸ thøa th nh qu£ khoa håc cõa c¡c nh  khoa håc vîi sü tr¥n trång v  bi¸t ìn. C¡c thæng tin tr½ch d¨n trong luªn v«n n y ¢ ÷ñc ch¿ rã nguçn gèc. H  Nëi, ng y 05 th¡ng 11 n«m 2013 T¡c gi£ inh Thøa Vô 2 Möc löc Líi c£m ìn 1 Líi cam oan 1 B£ng k½ hi»u 4 Mð ¦u 5 1 7 Mët sè ki¸n thùc chu©n bà 1.1 1.2 1.3 1.4 1.5 2 Khæng gian Ìclit . . . . . . . . . . . . . T½nh li¶n töc v  t½nh kh£ vi cõa h m sè . Tªp lçi . . . . . . . . . . . . . . . . . . . H m lçi . . . . . . . . . . . . . . . . . . B i to¡n tèi ÷u . . . . . . . . . . . . . . H m lçi suy rëng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 . 8 . 11 . 12 . 18 21 2.1 H m tüa lçi . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 H m gi£ lçi . . . . . . . . . . . . . . . . . . . . . . . . . 35 3 2.3 Mèi quan h» giúa nhúng h m lçi suy rëng . . . . . . . . 39 3 Ùng döng v o lþ thuy¸t tèi ÷u 41 3.1 Ùng döng v o b i to¡n tèi ÷u vîi r ng buëc h¼nh håc . . 41 3.2 Ùng döng v o b i to¡n tèi ÷u câ r ng buëc b§t ¯ng thùc 45 K¸t luªn 46 T i li»u tham kh£o 48 B£ng k½ hi»u R Rn R = R ∪ {−∞, +∞} f :X→R int A A dom(f ) epi(f ) ϕ0 (x) ∇f (x) ϕ00 (x) ∇2 f (x) ||.|| |x| af f (A) coA (x, y) = {λx + (1 − λ)y | λ ∈ (0, 1)} (x, y] = {λx + (1 − λ)y | λ ∈ (0, 1]} [x, y] = {λx + (1 − λ)y | λ ∈ [0, 1]} L(f, α) = {x ∈ X | f (x) 6 α} ÷íng th¯ng thüc khæng gian Euclid n - chi·u tªp sè thüc suy rëng ¡nh x¤ i tø X v o R ph¦n trong cõa A bao âng cõa A mi·n húu hi»u cõa f tr¶n ç thà cõa f ¤o h m cõa ϕ t¤i x gradient cõa f t¤i x ¤o h m bªc hai cõa varphi t¤i x ma trªn Hessian cõa f t¤i x chu©n trong khæng gian Rn trà tuy»t èi cõa sè x bao lçi affine cõa A bao lçi cõa A o¤n th¯ng mð nèi x v  y o¤n th¯ng mð nèi x v  y o¤n th¯ng âng nèi x v  y tªp mùc d÷îi 5 MÐ †U 1. Lþ do chån · t i C¡c h m lçi v  h m lçi suy rëng âng mët vai trá quan trång trong lþ thuy¸t tèi ÷u ho¡ (xem [8], [10] v  nhúng t i li»u tr½ch d¨n trong â). H m lçi suy rëng ¢ ÷ñc nhi·u nh  to¡n håc quan t¥m nghi¶n cùu v  thu ÷ñc nhi·u k¸t qu£ s¥u s­c. C¡c h m tüa lçi, h m gi£ lçi ¢ ÷ñc Mangasarian tr¼nh b y trong [10] . D. Aussel ¢ nghi¶n cùu c¡c t½nh ch§t °c tr÷ng cõa c¡c h m tüa lçi v  gi£ lçi khæng trìn qua t½nh tüa ìn i»u v  gi£ ìn i»u cõa d÷îi vi ph¥n cõa h m â v  mèi quan h» giúa c¡c kh¡i ni»m n y trong [5], [6]. A. Daniilidis v  N. Hadjisavvas nghi¶n cùu c¡c h m tüa lçi ch°t v  tüa lçi b¡n ch°t khæng trìn [2]... Sau khi ÷ñc håc nhúng ki¸n thùc v· To¡n gi£i t½ch, vîi mong muèn t¼m hiºu s¥u hìn v· nhúng ki¸n thùc ¢ håc, mèi quan h» v  ùng döng cõa chóng, tæi ¢ chån · t i nghi¶n cùu : H m lçi suy rëng v  ùng döng . 2. Möc ½ch nghi¶n cùu Hiºu bi¸t têng quan v· h m lçi suy rëng, n­m ÷ñc nhúng t½nh ch§t cì b£n cõa h m lçi suy rëng v  nhúng ùng döng v o tèi ÷u hâa. 3. Nhi»m vö nghi¶n cùu C¡c kh¡i ni»m h m lçi suy rëng, nhúng t½nh ch§t cì b£n cõa h m lçi suy rëng, nhúng ùng döng cõa h m lçi suy rëng v o b§t ¯ng thùc 6 bi¸n ph¥n v  tèi ÷u hâa. 4. èi t÷ñng v  ph¤m vi nghi¶n cùu H m lçi suy rëng trong khæng gian Euclid. 5. Ph÷ìng ph¡p nghi¶n cùu Thu thªp t i li»u v· h m lçi v  h m lçi suy rëng. åc, ph¥n t½ch v  têng hñp º ÷ñc mët nghi¶n cùu têng quan v· h m lçi suy rëng v  ùng döng. 6. Dü ki¸n âng gâp mîi cõa · t i + Nghi¶n cùu têng quan v· h m lçi suy rëng v  ùng döng. 7 Ch÷ìng 1 Mët sè ki¸n thùc chu©n bà Trong ch÷ìng n y chóng ta s³ tr¼nh b y nhúng kh¡i ni»m cì b£n nh§t cõa tªp lçi v  h m lçi tr¶n khæng gian Rn còng vîi nhúng t½nh ch§t °c tr÷ng cõa nâ. Nhúng ki¸n thùc tr¼nh b y trong ch÷ìng n y ÷ñc chån chõ y¸u tø c¡c t i li»u [1], [2], [8]. 1.1 Khæng gian Ìclit Tªp hñp Rn := {x = (x1 , ..., xn )T : x1 , ..., xn ∈ R}, trong â   x1 x   2 x = (x1 , ..., xn )T :=  .  . xn vîi hai ph²p to¡n (x1 , ..., xn )T + (y1 , ..., yn )T := (x1 + y1 , ..., xn + yn )T λ(x1 , ..., xn )T := (λx1 , ..., λxn )T , λ∈R 8 lªp th nh mët khæng gian v²c tì Ìclit n−chi·u. N¸u x = (x1, ..., xn)T ∈ Rn th¼ xi gåi l  th nh ph¦n ho°c tåa ë thù i cõa x. V²c tì khæng cõa khæng gian n y gåi l  gèc cõa Rn v  ÷ñc k½ hi»u ìn gi£n l  0, vªy 0 = (0, ..., 0)T . Trong Rn ta ành ngh¾a t½ch væ h÷îng ch½nh t­c h., .i nh÷ sau: vîi x = (x1 , ..., xn )T , y = (y1 , ..., yn )T ∈ Rn , hx, yi = Khi â vîi måi x = (x1, ..., xn)T ∈ n X xi y i . i=1 Rn ta ành ngh¾a v u n p uX kxk := hx, xi = t (xi )2 i=1 v  gåi l  chu©n Euclid cõa v²c tì x. ành ngh¾a 1.1. Cho x0 ∈ Rn , ε > 0, ta gåi tªp B(x0 , ε) := {x ∈ Rn : kx − x0 k < ε} l  h¼nh c¦u mð trong Rn câ t¥m t¤i x0, b¡n k½nh ε. ành ngh¾a 1.2. Tªp U ⊂ Rn gåi l  mð n¸u vîi måi x0 ∈ U , tçn t¤i ε > 0 sao cho B(x0 , ε) ⊂ U. Tªp F ⊂ Rn gåi l  âng n¸u U := Rn \ F l  mð. Tªp V ⊂ Rn gåi l  l¥n cªn cõa x ∈ Rn n¸u tçn t¤i ε > 0 sao cho B(x, ε) ⊂ V. 1.2 T½nh li¶n töc v  t½nh kh£ vi cõa h m sè i) H m f ÷ñc gåi l  nûa li¶n töc d÷îi t¤i x ∈ Rn (vîi f (x) < ∞), n¸u vîi måi ε > 0, tçn t¤i l¥n cªn U cõa x sao cho ành ngh¾a 1.3. 9 f (x) − ε ≤ f (y) (∀y ∈ U ) . ii) N¸u f (x) = +∞, th¼ f ÷ñc gåi l  nûa li¶n töc d÷îi t¤i x, n¸u vîi måi N > 0, tçn t¤i l¥n cªn U cõa x sao cho: f (y) ≥ N (∀y ∈ U ) . iii) H m f ÷ñc gåi l  nûa li¶n töc d÷îi, n¸u f nûa li¶n töc d÷îi t¤i måi x ∈ Rn. Cho f : X → R. Ta nâi f li¶n töc t¤i x0 ∈ X n¸u vîi måi ε > 0, tçn t¤i δ > 0 sao cho vîi måi x ∈ X ∩ B(x0, δ) ta câ f (x0 ) ∈ B(x0 , ε). Ta nâi f li¶n töc tr¶n X n¸u f li¶n töc t¤i måi x0 ∈ X . ành ngh¾a 1.4. Cho U ⊂ Rn l  tªp mð, h m sè f : U → R, v  x0 = (x01 , ..., x0n )T ∈ U . Khi â tçn t¤i δ > 0 sao cho vîi måi h ∈ R m  |h| < δ ta câ x(h) = (x0 , ..., x0i−1 , x0i + h, x0i+1 , ..., x0n ) ∈ U . N¸u tçn t¤i giîi h¤n ành ngh¾a 1.5. f (x0 , ..., x0i−1 , x0i + h, x0i+1 , ..., x0n ) − f (x0 ) lim h h→0 th¼ ta gåi nâ l  ¤o h m ri¶ng (c§p 1) theo bi¸n xi cõa f t¤i x0, k½ hi»u ∂f 0 (x ) ∂xi ho°c fx0 i (x0 ). ∂f N¸u f câ c¡c ¤o h m ri¶ng ∂x (x0 ), i = 1, ..., n, th¼ v²c tì i ( ∂f 0 ∂f 0 T (x ), ..., (x )) ∂x1 ∂xn gåi l  gradient cõa f t¤i x0 v  ÷ñc k½ hi»u l  ∇f (x0 ) = ( ∂f 0 ∂f 0 T (x ), ..., (x )) . ∂x1 ∂xn ∂f ∂f N¸u ¤o h m ri¶ng ∂x (x) tçn t¤i t¤i måi x ∈ U th¼ ta câ h m ∂x :U → ∂f R x¡c ành bði quy t­c x 7→ ∂x (x). N¸u tçn t¤i ¤o h m ri¶ng theo bi¸n i i i 10 ∂f thù j cõa h m ∂x t¤i x0 th¼ ta gåi nâ l  ¤o h m ri¶ng c§p 2 theo bi¸n xi v  xj cõa f t¤i x0 , k½ hi»u l  i ∂ 2f (x0 ) ho°c fx00i xj (x0 ). ∂xi ∂xj   2 ∂ f 0 ∂xi ∂xj (x ) , i, j = 1, ..., n gåi l  ma trªn Ma trªn x0 , k½ hi»u l  ∇2 f (x0 ). Hessian cõa f t¤i Cho U ⊂ Rn l  tªp mð, h m sè f : U → R, x0 = (x01, ..., x0n)T ∈ U . ành ngh¾a 1.6. Ta nâi f kh£ vi t¤i x0 n¸u vîi måi i = 1, ..., n tçn t¤i ¤o h m ri¶ng fx0 (x0) v  vîi måi h ∈ Rn \ {0} m  x0 + h ∈ U ta câ i f (x0 + h) = f (x0 ) + h∇f (x0 ), hi + r(khk), trong â r(khk) → 0 khi khk → 0. khk N¸u f kh£ vi t¤i måi x ∈ U th¼ ta nâi f kh£ vi tr¶n U . N¸u f kh£ vi tr¶n U v  c¡c h m fx0 (.) : U → R, i = 1, ..., n, ·u li¶n töc tr¶n U , th¼ ta nâi f kh£ vi li¶n töc tr¶n U . ành ngh¾a 1.7. Ta nâi f kh£ vi hai l¦n t¤i x0 n¸u vîi måi i, j = 1, ..., n tçn t¤i ¤o h m ri¶ng c§p hai fx00 x (x0) v  vîi måi h ∈ Rn \ {0} m  x0 + h ∈ U ta câ i i j hh, ∇2 f (x0 )hi f (x + h) = f (x ) + h∇f (x ), hi + + r(khk2 ), 2 0 0 0 ) trong â r(khk → 0 khi khk → 0. khk N¸u f kh£ vi hai l¦n t¤i måi x ∈ U th¼ ta nâi f kh£ vi hai l¦n tr¶n 2 2 U. N¸u f kh£ vi hai l¦n tr¶n U , c¡c h m fx0 (.) : U → R v  fx00 x (.) : U → R, i, j = 1, ..., n, ·u li¶n töc tr¶n U , th¼ ta nâi f kh£ vi li¶n töc hai l¦n tr¶n U . i i j 11 Cho f : Rn → R v  x0 ∈ Rn. Khi â (i) N¸u f kh£ vi li¶n töc tr¶n mët l¥n cªn n o â cõa h ∈ Rn m  khk õ nhä ta câ ành l½ 1.1. x0 th¼ vîi f (x0 + h) = f (x0 ) + h∇f (x0 ), hi + r(khk), trong â r(khk) → 0 khi khk → 0. khk (ii) N¸u f kh£ vi li¶n töc hai l¦n tr¶n mët l¥n cªn n o â cõa x0 th¼ vîi h ∈ Rn m  khk õ nhä ta câ hh, ∇2 f (ν)hi , f (x + h) = f (x ) + h∇f (x ), hi + 2 ν = tx0 + (1 − t)h, t ∈ (0, 1). 0 trong â 0 0 1.3 Tªp lçi ành ngh¾a 1.8. Tªp X ⊂ Rn ÷ñc gåi l  lçi, n¸u ∀x, y ∈ X, ∀λ ∈ R : 0 ≤ λ ≤ 1 ⇒ λx + (1 − λ) y ∈ X. Cho Xα ⊂ Rn (α ∈ I) l  c¡c tªp lçi, vîi I l  tªp ch¿ sè T b§t k¼. Khi â X = Xα công lçi. M»nh · 1.1. α∈I Cho c¡c tªp Xi ⊂ Rn lçi, λi ∈ R (i = 1, 2, ..., m). Khi â λ1X1 + ... + λmXm công l  tªp lçi. M»nh · 1.3. Cho c¡c tªp Xi ⊂ Rn lçi, (i = 1, 2, . . . , m). Khi â t½ch · c¡c X1 × ... × Xm l  tªp lçi trong Rn × ... × Rn . ành ngh¾a 1.9. V²c tì x ∈ Rn ÷ñc gåi l  tê hñp lçi cõa c¡c v²ctì m P n x1 , ..., xm thuëc R , n¸u ∃λi ≥ 0 (i = 1, 2, ..., m) , λi = 1 sao cho M»nh · 1.2. i 1 m i=1 x= m X i=1 λi xi . 12 Cho tªp X ⊂ Rn lçi; x1, ..., xm ∈ X . Khi â X chùa t§t c£ c¡c tê hñp lçi cõa x1, ..., xm. ành ngh¾a 1.10. Cho X ⊂ Rn . Giao cõa t§t c£ c¡c tªp lçi chùa X ÷ñc gåi l  bao lçi (convex hull) cõa tªp X , k½ hi»u l  coX . ành ngh¾a 1.11. Gi£ sû X ⊂ Rn . Giao cõa t§t c£ c¡c tªp lçi âng chùa X ÷ñc gåi l  bao lçi âng cõa tªp X v  k½ hi»u l  coX . M»nh · 1.4. Cho X ⊂ Rn lçi. Khi â, i) Ph¦n trong intX v  bao âng X cõa X l  c¡c tªp lçi; ii) N¸u x1 ∈ intX, x2 ∈ X , th¼ {λx1 + (1 − λ)x2 : 0 < x1 ≤ 1} ⊂ intX. ành ngh¾a 1.12. nh x¤ f : Rn → Rm ÷ñc gåi l  affine n¸u ành l½ 1.2. ∀x, y ∈ E1 , λ ∈ R; f ((1 − λ) x + λy) = (1 − λ) f x + λf y. Ph¦n trong t÷ìng èi cõa A ⊂ E l  ph¦n trong cõa A trong affA; k½ hi»u l  riA. ành ngh¾a 1.13. C¡c iºm thuëc riA ÷ñc gåi l  iºm trong t÷ìng èi cõa tªp A. ành ngh¾a 1.14. Tªp A \ riA ÷ñc gåi l  bi¶n t÷ìng èi cõa A. Tªp A ÷ñc gåi l  mð t÷ìng èi, n¸u riA = A. 1.4 H m lçi Cho h m R ∪ {−∞, +∞}, c¡c tªp ành ngh¾a 1.15. f : X → R, trong â epi(f ) = {(x, α) ∈ X × R| f (x) ≤ α} , dom(f ) = {x ∈ X| f (x) < +∞} X ⊂ Rn , R = 13 ÷ñc gåi l¦n l÷ñt l  tr¶n ç thà v  mi·n húu hi»u cõa f . Cho X ⊂ Rn l  mët tªp lçi, f : X → R. H m f ÷ñc gåi l  lçi tr¶n X n¸u tr¶n ç thà epi(f ) cõa nâ l  mët tªp lçi trong Rn × R. N¸u dom f 6= ∅ v  −∞ < f (x) vîi måi x ∈ X ta nâi h m f l  ch½nh th÷íng. H m f ÷ñc gåi l  lãm tr¶n X n¸u −f l  h m lçi tr¶n X . ành ngh¾a 1.16. V½ dö °t (H m ch¿). Cho C 6= ∅ l  mët tªp lçi trong Rn.  δC (x) := 0 khi x ∈ C, +∞ khi x ∈ / C. Ta nâi δC l  h m ch¿ cõa C . + ∀x, y ∈ C, ∀λ ∈ (0, 1), ta câ: δC (x) = 0, δC (y) = 0. Do C lçi n¶n λx + (1 − λ)y ∈ C. Suy ra δC [λx + (1 − λ)y] = 0 = λδC (x) + (1 − λ)δC (y) . + ∀x ∈ C, ∀y ∈/ C, ∀λ ∈ (0, 1), ta câ: δC (x) = 0, δC (y) = +∞, δC [λx + (1 − λ)y] ≤ +∞. Suy ra δC [λx + (1 − λ)y] ≤ λδC (x) + (1 − λ)δC (y) . + ∀x, y ∈/ C, ∀λ ∈ (0, 1), ta câ: δC (x) = +∞, δC (y) = +∞, δC [λx + (1 − λ)y] ≤ +∞. Suy ra δC [λx + (1 − λ)y] ≤ λδC (x) + (1 − λ)δC (y) . V½ dö (H m tüa). Cho C 6= ∅ l  mët tªp lçi trong Rn . °t SC (y) := supx∈C hy, xi vîi y ∈ Rn. Ta nâi SC l  h m tüa cõa 14 C. Vîi måi x, y ∈ C v  vîi måi , λ ∈ (0, 1), ta câ SC [λx + (1 − λ) y] = sup hλx + (1 − λ) y, zi z∈C = sup {hλx, zi + h(1 − λ) y, zi} z∈C ≤ sup hλx, zi + sup h(1 − λ) y, zi z∈C z∈C = λsup hx, zi + (1 − λ) sup hy, zi z∈C z∈C = λSC (x) + (1 − λ) SC (y) . Vªy SC l  h m lçi tr¶n C . Gi£ sû f1, ..., fm l  c¡c h m lçi ch½nh th÷íng tr¶n X . Khi â, têng f1 + ... + fm l  mët h m lçi. ành l½ 1.3. vi. Ta nh­c l¤i mët sè °c tr÷ng v  t½nh ch§t cõa h m lçi mët bi¸n kh£ Cho ϕ : (a, b) → R. i) N¸u ϕ kh£ vi tr¶n (a, b) th¼ ϕ lçi tr¶n (a, b) khi v  ch¿ khi ϕ0 khæng gi£m tr¶n (a, b). ii) N¸u ϕ câ ¤o h m bªc hai tr¶n (a, b) th¼ ϕ lçi tr¶n (a, b) khi v  ch¿ khi ϕ00(t) > 0 vîi måi t ∈ (a, b). iii) N¸u ϕ lçi tr¶n [a, b] th¼ ϕ li¶n töc tr¶n (a, b). ành l½ 1.4. Cho X l  tªp lçi trong khæng gian Rn v  f : X → R. Khi â, c¡c i·u ki»n sau l  t÷ìng ÷ìng: a) f (λx + (1 − λ) y) ≤ λf (x) + (1 − λ) f (y) ∀λ ∈ [0, 1] , ∀x, y ∈ X. b) f (λx + (1 − λ) y) > λf (x)+(1 − λ) f (y) ∀λ > 1, ∀x, y ∈ X sao cho ành l½ 1.5. λx + (1 − λ) y ∈ X. 15 c) f (λx + (1 − λ) y) > λf (x)+(1 − λ) f (y) ∀λ < 0, ∀x, y ∈ X sao cho λx + (1 − λ) y ∈ X. d)(B§t ¯ng thùc Jensen) Vîi b§t k¼ x1, . . . , xm ∈ X , i = 1, . . . , m v  vîi m P b§t k¼ λi ∈ [0, 1], i = 1, . . . , m, λi = 1 b§t ¯ng thùc sau óng: i=1 f (λ1 x1 + ... + λm xm ) ≤ λ1 f (x1 ) + ... + λm f (xm ) . e) Vîi måi x ∈ X , vîi måi y ∈ Rn, h m ϕx,y (t) = f (x + ty) l  h m lçi tr¶n o¤n Tx,y = {t ∈ R | x + ty ∈ X}. f) Vîi måi x, y ∈ X , h m ψx,y (λ) = f (λx + (1 − λ)y) lçi tr¶n o¤n [0, 1]. g) Tr¶n ç thà cõa f l  tªp lçi trong Rn+1. Gi£ sû X ⊂ Rn l  mët tªp lçi mð, f : X → R. Khi â, f lçi tr¶n X khi v  ch¿ khi h) vîi måi x0 ∈ X , tçn t¤i x∗ ∈ Rn sao cho ành l½ 1.6. f (x) − f (x0 ) > x∗ (x − x0 ), x ∈ X. Cho X ⊂ Rn l  mët tªp lçi v  f : X → R. Khi â, n¸u f lçi tr¶n X th¼, vîi måi α ∈ R tªp mùc d÷îi cõa f ành l½ 1.7. L(f, α) = {x ∈ X | f (x) ≤ α} l  tªp lçi. X²t h m sè f : R → R x¡c ành bði f (x) = x3. Ta câ f khæng lçi tr¶n R, trong khi L(f, α) = {x ∈ R | x3 ≤ α} = {x ∈ R | x ≤ α1/3} l  tªp lçi vîi måi α ∈ R. V½ dö. 16 Cho X ⊂ Rn l  mët tªp mð v  f : X → R kh£ vi tr¶n X . Khi â c¡c kh¯ng ành sau t÷ìng ÷ìng: a) f lçi tr¶n X b) Vîi måi x ∈ X v  vîi måi y ∈ Rn h m ành l½ 1.8. ϕ0x,y (t) = hy, ∇f (x + ty)i, bi¸n t, khæng gi£m tr¶n o¤n Tx,y = {t ∈ R | x + ty ∈ X}. c) Vîi måi x, y ∈ X , h m 0 ψx,y (λ) = h(x − y), ∇f (λx + (1 − λ)y)i, bi¸n λ, khæng gi£m tr¶n o¤n [0, 1] . d) Vîi måi x, y ∈ X , f (x) − f (y) > h(x − y), ∇f (y)i. e) Vîi måi x, y ∈ X , f (x) − f (y) 6 h(x − y), ∇f (x)i. f) Vîi måi x, y ∈ X , h(x − y), ∇f (x) − ∇f (y)i > 0. Cho f : X → R l  h m sè kh£ vi li¶n töc hai l¦n tr¶n tªp lçi mð X ⊂ Rn. Khi â, f lçi tr¶n X khi v  ch¿ khi ma trªn Hessian ∇2 f (x) nûa x¡c ành d÷ìng vîi måi x ∈ X . ành l½ 1.9. Cho X l  tªp lçi trong khæng gian Rn, f : X → R. Ta nâi f lçi ch°t tr¶n X n¸u ành ngh¾a 1.17. f (λx + (1 − λ) y) < λf (x)+(1 − λ) f (y) ∀λ ∈ [0, 1] , ∀x, y ∈ X, x 6= y. Cho X l  tªp lçi trong khæng gian Rn v  f : X → R. Khi â, c¡c i·u ki»n sau l  t÷ìng ÷ìng: a) f lçi ch°t tr¶n X b) Vîi måi x ∈ X , vîi måi y ∈ Rn, h m ϕx,y (t) = f (x + ty) l  h m lçi ch°t tr¶n o¤n Tx,y = {t ∈ R | x + ty ∈ X}. ành l½ 1.10. 17 c) Vîi måi x, y ∈ X , h m ψx,y (λ) = f (λx + (1 − λ)y) lçi tr¶n o¤n [0, 1] . Cho X ⊂ Rn l  mët tªp mð v  f : X → R kh£ vi tr¶n X . Khi â c¡c kh¯ng ành sau t÷ìng ÷ìng: a) f lçi ch°t tr¶n X b) Vîi måi x, y ∈ X , x 6= y, f (x) − f (y) > h(x − y), ∇f (y)i. c) Vîi måi x, y ∈ X , x 6= y, f (x) − f (y) < h(x − y), ∇f (x)i. d) Vîi måi x, y ∈ X , h(x − y), ∇f (x) − ∇f (y)i > 0. ành l½ 1.11. Cho f : X → R l  h m sè kh£ vi li¶n töc hai l¦n tr¶n tªp lçi mð X ⊂ Rn. Khi â, n¸u ma trªn Hessian ∇2f (x) x¡c ành d÷ìng vîi måi x ∈ X , ngh¾a l  vîi måi x ∈ X , hy, ∇2f (x)yi > 0 vîi måi y ∈ Rn , y 6= 0, th¼ f lçi ch°t tr¶n X . ành l½ 1.12. i·u ki»n n¶u tr¶n ch¿ õ chù khæng c¦n º f lçi ch°t. V½ dö nh÷, f (x) = x4 lçi ch°t tr¶n R, nh÷ng ∇2 f (x) = 12x2 khæng x¡c ành d÷ìng tr¶n R, v¼ ∇2f (0) = 0. H m f : X → R x¡c ành tr¶n tªp lçi X ⊂ Rn ÷ñc gåi l  h m aphin tr¶n X n¸u nâ vøa lçi vøa lãm tr¶n X , ngh¾a l  ành ngh¾a 1.18. f (λx + (1 − λ) y) = λf (x) + (1 − λ) f (y) ∀λ ∈ [0, 1] , ∀x, y ∈ X. H m f : Rn → R l  h m aphin khi v  ch¿ khi tçn t¤i c ∈ Rn v  sè α ∈ R sao cho f (x) = hc, xi + α. ành l½ 1.13. Gi£ sû f l  h m lçi ch½nh th÷íng tr¶n Rn. Khi â c¡c kh¯ng ành sau l  t÷ìng ÷ìng: i) f bà ch°n trong mët l¥n cªn cõa x ; ành l½ 1.14. 18 ii) f li¶n töc t¤i x ; iii) int(epif ) 6= ∅ ; iv) int(domf ) 6= ∅ v  f li¶n töc tr¶n int(domf ). çng thíi, int(epif) = {(x, µ) ∈ X × R : x ∈ int(domf ), f (x) < µ} . 1.5 B i to¡n tèi ÷u B i to¡n tèi ÷u l  b i to¡n ÷ñc mæ t£ d÷îi d¤ng: vîi x ∈ X, min f (x) (P) trong â f : Rn −→ R l  mët h m cho tr÷îc, X ⊂ Rn l  mët tªp con cho tr÷îc, Rn l  khæng gian Euclid n-chi·u. Ta cán vi¸t b i to¡n (P ) nh÷ sau: min{f (x) : x ∈ X}. B i to¡n (P ) ÷ñc gåi l  mët b i to¡n tèi ÷u. H m f gåi l  h m möc ti¶u, X l  tªp r ng buëc (hay mi·n ch§p nhªn ÷ñc cõa (P )). C¡c ph¦n tû cõa X ÷ñc gåi l  c¡c ph¦n tû ch§p nhªn ÷ñc cõa (P ). N¸u X = Rn th¼ ta nâi (P ) l  mët b i to¡n khæng câ r ng buëc, ng÷ñc l¤i, (P ) l  b i to¡n câ r ng buëc. ành ngh¾a 1.19. ành ngh¾a 1.20. iºm x∗ ∈ X m  f (x∗ ) 6 f (x) vîi måi x∈X ÷ñc gåi l  nghi»m, ho°c nghi»m tèi ÷u, ho°c nghi»m tèi ÷u to n cöc, ho°c cüc tiºu to n cöc cõa b i to¡n (P ). 19 Ta nâi x ∈ X l  mët nghi»m tèi ÷u àa ph÷ìng ho°c nghi»m cüc tiºu àa ph÷ìng cõa (P ) n¸u tçn t¤i mët l¥n cªn U cõa x sao cho f (x) ≤ f (x) vîi måi x ∈ X ∩ U. Ta nâi x ∈ X l  mët nghi»m tèi ÷u àa ph÷ìng ch°t ho°c nghi»m cüc tiºu àa ph÷ìng ch°t cõa (P ) n¸u tçn t¤i mët l¥n cªn U cõa x sao cho f (x) < f (x) vîi måi x ∈ X ∩ U, x 6= x. Hiºn nhi¶n r¬ng, nghi»m tèi ÷u to n cöc cõa b i to¡n (P) ·u l  nghi»m tèi ÷u àa ph÷ìng cõa (P). Ta d¹ d ng ÷a ra ÷ñc nhúng v½ dö º chùng tä r¬ng, i·u ng÷ñc l¤i khæng ph£i lóc n o công óng. Tuy nhi¶n, n¸u X l  mët tªp lçi v  f l  mët h m lçi tr¶n X th¼ måi nghi»m tèi ÷u àa ph÷ìng cõa (P) ·u l  nghi»m tèi ÷u to n cöc cõa (P). Kh¯ng ành sau ¥y chùng minh i·u â. Cho X ⊂ Rn l  tªp lçi, f : X → R l  mët h m lçi. Khi â, n¸u x∗ l  mët nghi»m tèi ÷u cõa b i to¡n (P): ành l½ 1.15. min{f (x) : x ∈ X}, th¼ nâ công l  mët nghi»m tèi ÷u to n cöc cõa b i to¡n â. Chùng minh. Gi£ sû x∗ l  nghi»m tèi ÷u àa ph÷ìng cõa (P). Khi â x∗ ∈ X v  tçn t¤i l¥n cªn mð V trong Rn cõa x∗ sao cho f (x∗ ) 6 f (x) ∀x ∈ V ∩ X. L§y x ∈ X tòy þ. V¼ X lçi n¶n vîi måi t ∈ (0, 1) õ nhä, ta câ xt := tx + (1 − t)x∗ ∈ V ∩ X.