Tài liệu Vai trò của tính lồi trong bài toán tối ưu

.. ĐẠ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 s­c è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, B­c 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).