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

  • Số trang: 40 |
  • Loại file: PDF |
  • Lượt xem: 49 |
  • Lượt tải: 0
tailieuonline

Đã đăng 27429 tài liệu

Mô tả:

ĐẠ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: anhthubonghg@gmail.com 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).
- Xem thêm -