Tài liệu Về toán tử chiếu metric lên tập lồi đóng và ứng dụng vào bài toán bất đẳng thức biến phân

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- VÀNG VĂN HÀ VỀ TOÁN TỬ CHIẾU METRIC LÊN TẬP LỒI ĐÓNG VÀ ỨNG DỤNG VÀO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2020 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- VÀNG VĂN HÀ VỀ TOÁN TỬ CHIẾU METRIC LÊN TẬP LỒI ĐÓNG VÀ ỨNG DỤNG VÀO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN 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 GS.TSKH. Lê Dũng Mưu THÁI NGUYÊN - 2020 Möc löc B£ng kþ hi»u Líi c£m ìn Líi nâi ¦u Ch÷ìng 1. Mët sè ki¸n thùc chu©n bà i ii 1 3 1.1 Tªp lçi v  h m lçi . . . . . . . . . . . . . . . . . . . . . . 3 1.2 To¡n tû chi¸u kho£ng c¡ch . . . . . . . . . . . . . . . . . 15 Ch÷ìng 2. Ùng döng v o b i to¡n b§t ¯ng thùc bi¸n ph¥n 22 2.1 B i to¡n b§t ¯ng thùc bi¸n ph¥n . . . . . . . . . . . . . 2.2 Mët thuªt to¡n chi¸u gi£i b i to¡n b§t ¯ng thùc bi¸n ph¥n para-ìn i»u . . . . . . . . . . . . . . . . . . . . . T i li»u tham kh£o 22 25 37 i B£ng kþ hi»u R tªp sè thüc Rn khæng gian Euclide ∅ tªp réng ∀x vîi måi ∃x tçn t¤i kxk chu©n cõa vectì hx, yi t½ch væ h÷îng cõa hai v²c-tì kxk chu©n cõa v²c-tì V IP (F ; C) b i to¡n b§t ¯ng thùc bi¸n ph¥n S(F ; C) tªp nghi»m cõa b i to¡n n-chi·u x x x x v  y x V IP (F ; C) ii Líi c£m ìn 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 d÷îi sü h÷îng d¨n cõa GS.TSKH. L¶ Dông M÷u. T¡c gi£ xin b y tä láng bi¸t ìn s¥u s­c tîi Th¦y, ng÷íi ¢ d nh nhi·u thíi gian, tªn t¼nh h÷îng d¨n v  gióp ï t¡c gi£ trong suèt qu¡ tr¼nh nghi¶n cùu v  ho n thi»n luªn v«n. T¡c gi£ công xin b y tä láng bi¸t ìn ch¥n th nh tîi c¡c Th¦y Cæ trong khoa To¡n-Tin tr÷íng ¤i håc Khoa håc, ¤i håc Th¡i Nguy¶n ¢ gi£ng d¤y v  gióp ï cho t¡c gi£ trong suèt thíi gian håc tªp t¤i Tr÷íng. çng thíi, tæi công xin gûi líi c£m ìn tîi gia ¼nh, b¤n b± v  çng nghi»p ¢ t¤o i·u ki»n thuªn lñi nh§t cho tæi trong thíi gian håc tªp v  trong qu¡ tr¼nh ho n th nh luªn v«n. Xin ch¥n th nh c£m ìn! Th¡i Nguy¶n, th¡ng 05 n«m 2020. T¡c gi£ V ng V«n H  1 Líi nâi ¦u Trong ch÷ìng tr¼nh to¡n phê thæng, chóng ta ¢ l m quen vîi ph²p chi¸u vuæng gâc xuèng mët m°t ph¯ng trong khi gi£i c¡c b i to¡n h¼nh håc v  l÷ñng gi¡c. Kh¡i ni»m n y ¢ ÷ñc mð rëng l¶n khæng gian nhi·u chi·u, thªm ch½ væ h¤n chi·u còng vîi vi»c thay m°t ph¯ng b¬ng mët tªp lçi âng v  vîi mët kho£ng c¡ch (metric) khæng nh§t thi¸t l  kho£ng c¡ch Ì-cì-lit. nh x¤ chuyºn mët iºm b§t ký cho tr÷îc trong khæng gian ¸n mët iºm trong mët tªp cho tr÷îc vîi kho£ng c¡ch nhä nh§t ÷ñc gåi l  to¡n tû chi¸u l¶n tªp â. Ng÷íi ta ¢ ch¿ ra r¬ng, trong khæng gian Hilbert thüc, to¡n tû chi¸u l¶n mët tªp lçi âng ÷ñc x¡c ành duy nh§t. To¡n tû chi¸u chi¸u l¶n tªp lçi âng câ nhi·u °c tr÷ng thó và, do â nâ câ vai trá quan trång trong nhi·u v§n · cõa to¡n håc v  thüc t¸ nh÷ trong lþ thuy¸t x§p x¿, tèi ÷u hâa, b§t ¯ng thùc bi¸n ph¥n, c¥n b¬ng v  nhi·u l¾nh vüc kh¡c. Nëi dung cõa b£n luªn v«n bao gçm c¡c ki¸n thùc cì b£n nh§t v· tªp lçi trong khæng gian Ì-cì-lit Rn , c¡c k¸t qu£ v· to¡n tû chi¸u l¶n tªp lçi âng. Nëi dung ch½nh ti¸p theo li¶n quan ¸n vi»c ¡p döng to¡n tû chi¸u v o vi»c gi£i b i to¡n b§t ¯ng thùc bi¸n ph¥n para-ìn i»u trong khæng gian Rn . Ngo i ph¦n mð ¦u, k¸t luªn v  t i li»u tham kh£o, c¡c k¸t qu£ nghi¶n 2 cùu trong b£n luªn v«n ÷ñc tr¼nh b y th nh hai ch÷ìng vîi ti¶u ·: Ch÷ìng 1: Mët sè ki¸n thùc chu©n bà. Ch÷ìng 2: Ùng döng v o b i to¡n b§t ¯ng thùc bi¸n ph¥n. Nëi dung ch½nh cõa c¡c ch÷ìng nh÷ sau: Trong ch÷ìng 1, tæi tr¼nh b y ành ngh¾a tªp lçi, mët sè t½nh ch§t cì b£n cõa tªp lçi, h m lçi. Ti¸p theo l  tr¼nh b y ành lþ t¡ch c¡c tªp lçi. Mët ph¦n cõa ch÷ìng tr¼nh b y v· ành ngh¾a to¡n tû chi¸u, mët sè t½nh ch§t cì b£n cõa to¡n tû chi¸u. Ch÷ìng 2 cõa luªn v«n tr¼nh b y ùng döng cõa to¡n tû chi¸u metric l¶n mët tªp lçi âng v o vi»c gi£i b i to¡n b§t ¯ng thùc bi¸n ph¥n. B§t ¯ng thùc bi¸n ph¥n l  mët lîp b i to¡n quan trång cõa Gi£i t½ch ùng döng. B i to¡n n y l  mët lîp b i to¡n têng qu¡t cõa b i to¡n quy ho¤ch lçi; hìn núa nhi·u b i to¡n trong ph÷ìng tr¼nh vi ph¥n, ¤o h m ri¶ng ·u câ thº mæ t£ d÷îi b i to¡n b§t ¯ng thùc bi¸n ph¥n. 3 Ch÷ìng 1. Mët sè ki¸n thùc chu©n bà Nëi dung ch½nh cõa ch÷ìng tr¼nh b y ành ngh¾a, mët sè t½nh ch§t cì b£n, ành lþ v  bê · li¶n quan ¸n tªp lçi v  h m lçi. Mët ph¦n cõa ch÷ìng · cªp ¸n ph²p chi¸u metric, chùng minh sü tçn t¤i v  t½nh duy nh§t cõa h¼nh chi¸u l¶n mët tªp lçi âng v  kh£o s¡t mët sè t½nh ch§t cì b£n cõa to¡n tû chi¸u. Nëi dung ch½nh cõa ch÷ìng n y ÷ñc tham kh£o chõ y¸u tø c¡c t i li»u [1, 3]. 1.1 Tªp lçi v  h m lçi Tr÷îc h¸t, chóng tæi giîi thi»u kh¡i ni»m v· tªp lçi v  mët sè t½nh ch§t c¦n thi¸t. Nh­c l¤i r¬ng, mët Rn ÷íng th¯ng l  tªp hñp t§t c£ c¡c v²c-tì nèi hai iºm (hai v²c-tì) x ∈ Rn a, b trong câ d¤ng {x ∈ Rn |x = αa + βb, α, β ∈ Rn , α + β = 1}. o¤n th¯ng nèi hai iºm a v  b trong Rn l  tªp hñp c¡c v²c-tì x câ d¤ng {x ∈ Rn |x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}. ành ngh¾a 1.1. Mët tªp C ⊆ Rn ÷ñc gåi l  mët måi o¤n th¯ng i qua hai iºm b§t ký cõa nâ. Tùc l  tªp lçi, n¸u C chùa C lçi khi v  ch¿ khi 4 ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C. V½ dö 1.1. a) Tªp ∅ v  o¤n th¯ng Rn l  c¡c tªp con lçi cõa AB Rn . l  mët tªp lçi. H¼nh trán bao gçm c£ bi¶n m u n¥u l  mët tªp lçi, v¼ o¤n th¯ng nèi hai iºm X, Y trong h¼nh trán n¬m trån vµn trong h¼nh trán. H¼nh 1.1: Tªp lçi b) H¼nh d÷îi ¥y l  hai tªp khæng lçi, v¼ c¡c ÷íng n²t ùt chùa nhi·u iºm khæng n¬m trong c¡c tªp â. H¼nh 1.2: Tªp khæng lçi ành ngh¾a 1.2. x= Ta nâi k X j=1 j x l  tê hñp lçi cõa c¡c iºm x1, . . . , xk n¸u λj x , λj > 0 ∀j = 1, . . . , k, k X j=1 λj = 1. 5 M»nh · 1.1. Tªp hñp C l  lçi khi v  ch¿ khi nâ chùa måi tê hñp lçi cõa c¡c iºm cõa nâ. Tùc l : C lçi khi v  ch¿ khi ∀k ∈ N, ∀λ1 , . . . , λk > 0 : k X 1 k λj = 1, ∀x , . . . , x ∈ C ⇒ j=1 k X λj xj ∈ C. j=1 Chùng minh. i·u ki»n õ l  hiºn nhi¶n tø ành ngh¾a. Ta chùng minh i·u ki»n c¦n b¬ng quy n¤p theo sè iºm. Vîi k = 2, i·u c¦n chùng minh suy ra ngay tø ành ngh¾a cõa tªp lçi v  tê hñp lçi. Gi£ sû m»nh · óng vîi Gi£ sû x k−1 iºm. Ta c¦n chùng minh vîi l  tê hñp lçi cõa x= k X k k iºm. x1 , . . . , x k ∈ C . iºm j λj x , λj > 0 ∀j = 1, . . . , k, j=1 k X Tùc l  λj = 1. j=1 °t ξ= k−1 X λj . j=1 Khi â 0<ξ<1 v  x= k−1 X λj xj + λk xk j=1 =ξ k−1 X λj j=1 ξ xj + λk xk . (1.1) Do k−1 X λj j=1 v  λj ξ >0 vîi måi j = 1, . . . , k − 1, y := ξ n¶n theo gi£ thi¸t quy n¤p, iºm k−1 X λj j=1 =1 ξ xj ∈ C. 6 Ta câ x = ξy + λxk . Do ξ > 0, λk > 0 v  ξ + λk = k X λj = 1, j=1 n¶n x l  mët tê hñp lçi cõa hai iºm y v  xk ·u thuëc C . Vªy x ∈ C . Lîp c¡c tªp lçi l  âng vîi c¡c ph²p giao, ph²p cëng ¤i sè v  ph²p nh¥n t½ch Descartes. Cö thº, ta câ m»nh · sau: M»nh · 1.2. N¸u A, B l  c¡c tªp lçi trong R , C l  lçi trong R , th¼ n m c¡c tªp sau l  lçi: (i) (ii) (iii) A ∩ B := {x|x ∈ A, x ∈ B}, λA + βB := {x|x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R}, A × C := {x ∈ Rn+m |x = (a, c) : a ∈ A, c ∈ C}. Chùng minh. D¹ d ng ÷ñc suy ra trüc ti¸p tø ành ngh¾a. ành ngh¾a 1.3. x1 , . . . , xk Ta nâi x l  tê hñp a-phin cõa c¡c iºm (v²c-tì) n¸u x= k X j λj x , j=1 Tªp hñp cõa c¡c tê hñp a-phin cõa k X λj = 1. j=1 x1 , . . . , xk th÷íng ÷ñc gåi l  bao a-phin cõa c¡c iºm n y. ành ngh¾a 1.4. Mët tªp C ÷ñc gåi l  tªp a-phin n¸u nâ chùa ÷íng th¯ng i qua hai iºm b§t ký cõa nâ, tùc l  ∀x, y ∈ C, ∀λ ∈ R ⇒ λx + (1 − λ)y ∈ C. 7 Vªy tªp a-phin l  mët tr÷íng hñp ri¶ng cõa tªp lçi. V½ dö 1.2. M»nh · 1.3. M 6= ∅ l  tªp a-phin khi v  ch¿ khi nâ câ d¤ng M = L+a Mët v½ dö iºn h¼nh cõa tªp a-phin l  c¡c khæng gian con. vîi L l  mët khæng gian con v  a ∈ M , khæng gian con L n y ÷ñc x¡c ành duy nh§t. Khæng gian song vîi L M , ho°c nâi ng­n gån hìn l  khæng gian con cõa M . Chi·u cõa mët tªp a-phin vîi M trong m»nh · tr¶n ÷ñc gåi l  khæng gian con song M ÷ñc ành ngh¾a bði chi·u cõa khæng gian song song v  ÷ñc kþ hi»u l  dimM . M»nh · 1.4. B§t ký mët tªp a-phin M ⊂ R n câ sè chi·u r ·u câ d¤ng M = {x ∈ Rn : Ax = b}, (1.2) trong â A l  ma trªn c§p (m × n), b ∈ Rm v  rankA = n − r. Ng÷ñc l¤i, måi tªp hñp câ d¤ng (1.2) vîi rankA = n − r ·u l  tªp a-phin câ sè chi·u l  r. ành ngh¾a 1.5. Mët tªp C ÷ñc gåi l  nân n¸u ∀λ > 0, ∀x ∈ C ⇒ λx ∈ C. Mët nân ÷ñc gåi l  V½ dö 1.3. nân lçi n¸u nâ çng thíi l  mët tªp lçi. a) Tªp Rn+ = {x ∈ Rn : x ≥ 0} b) Cho bα ∈ Rn (α ∈ I) vîi I l  mët nân lçi. l  tªp ch¿ sè n o â. Khi â tªp K = {x ∈ Rn : hx, bα i ≤ 0, ∀α ∈ I} 8 l  mët nân lçi v¼ Kα , vîi Kα = {x ∈ Rn : hx, bα i ≤ 0} l  nân lçi. T K= M»nh · 1.5. Mët tªp C l  nân lçi khi v  ch¿ khi nâ câ c¡c t½nh ch§t sau: α∈I (i) (ii) λC ⊆ C , ∀λ > 0; C + C ⊆ C. Ti¸p theo, chóng tæi giîi thi»u kh¡i ni»m h m lçi v  ành l½ t¡ch c¡c tªp lçi. ành ngh¾a 1.6. (i) Cho h m ÷ñc gåi l  f :C →R x¡c ành tr¶n mët tªp lçi C ⊆ Rn . Khi â f h m lçi n¸u vîi måi x, y ∈ C v  måi λ ∈ (0, 1) ta câ f [λx + (1 − λ)y] ≤ λf (x) + (1 − λ)f (y). H¼nh d÷îi ¥y l  mët h m lçi. H¼nh 1.3: H m lçi (ii) H m f ÷ñc gåi l  v  måi sè thüc h m lçi ch°t tr¶n C n¸u vîi måi x, y ∈ C , x 6= y λ ∈ (0, 1) ta câ f [λx + (1 − λ)y] < λf (x) + (1 − λ)f (y). (iii) H m f ÷ñc gåi l  h m lçi m¤nh tr¶n C vîi h» sè η >0 n¸u vîi 9 måi x, y ∈ C , x 6= y v  måi sè thüc λ ∈ (0, 1) ta câ 1 f [λx + (1 − λ)y] < λf (x) + (1 − λ)f (y) − ηλ(1 − λ)kx − yk2 . 2 ành ngh¾a 1.7. h m lãm tr¶n C n¸u −f l  h m lçi tr¶n C . (ii) H m f ÷ñc gåi l  h m tuy¸n t½nh a-phin (hay h m a-phin ) tr¶n C (i) H m n¸u f f ÷ñc gåi l  húu h¤n v  vøa lçi, vøa lãm tr¶n V½ dö 1.4. a) Måi h m chu©n ·u l  h m lçi tr¶n kxkp = n X C. Rn : !1/p |xi |p vîi p≥1 v  kxk∞ = max |xi |. C ÷ñc x¡c ành bði 1≤i≤n i=1 b) H m kho£ng c¡ch tø iºm inf y∈C kx − yk x ∈ Rn tîi dC (x) = l  h m lçi. ành ngh¾a 1.8. Cho f : Rn → R ∪ {+∞}. Ta nâi x∗ ∈ Rn h m cõa f t¤i x n¸u l  d÷îi ¤o hx∗ , z − xi + f (x) ≤ f (z), ∀z ∈ Rn . Tªp hñp t§t c£ c¡c d÷îi ¤o h m cõa cõa f t¤i x v  ÷ñc k½ hi»u l  f t¤i x ÷ñc gåi l  d÷îi vi ph¥n ∂f (x). Bê · 1.1. Cho C l  mët tªp con lçi cõa R . Mët h m kh£ vi f : C → R n l  lçi khi v  ch¿ khi f (x) − f (y) ≥ h5f (y), x − yi, ∀x, y ∈ C. ành ngh¾a 1.9. Si¶u ph¯ng trong khæng gian iºm câ d¤ng {x ∈ Rn : aT x = α}, Rn l  mët tªp hñp c¡c 10 trong â V²c-tì a ∈ Rn a l  mët v²c-tì kh¡c th÷íng ÷ñc gåi l  0 v  α ∈ R. v²c-tì ph¡p tuy¸n cõa si¶u ph¯ng. Mët si¶u ph¯ng s³ chia khæng gian ra hai nûa khæng gian. Nûa khæng gian ÷ñc ành ngh¾a nh÷ sau: ành ngh¾a 1.10. Nûa khæng gian l  mët tªp hñp câ d¤ng {x ∈ Rn : aT x ≥ α}, trong â a 6= 0 v  α ∈ R. ành ngh¾a 1.11. aT x = α Cho hai tªp C v  D kh¡c réng, ta nâi t¡ch C v  D n¸u aT x ≤ α ≤ aT y, Ta nâi si¶u ph¯ng aT x = α (1.3) t¡ch ch°t C v  D n¸u aT x < α < aT y, ành lþ 1.1. ∀x ∈ C, ∀y ∈ D. si¶u ph¯ng ∀x ∈ C, ∀y ∈ D. (ành lþ t¡ch 1) Cho C v  D l  hai tªp lçi kh¡c réng trong Rn sao cho C ∩ D = ∅. Khi â câ mët si¶u ph¯ng t¡ch C v  D. ành lþ t¡ch vøa n¶u câ thº suy ra ngay tø Bê · 1.2 d÷îi ¥y, ch½nh l  ành lþ t¡ch mët tªp lçi v  mët ph¦n tû khæng thuëc nâ. Bê · 1.2. Cho C (Bê · li¶n thuëc) l  mët tªp lçi kh¡c réng. Gi£ sû x0 ∈ C . Khi â tçn t¤i t ∈ Rn , t 6= 0 tho£ m¢n ⊂ Rn ht, xi ≥ ht, x0 i ∀x ∈ C. (1.4) 11 Chùng minh ành lþ 1.1. Do C v  D l  lçi, n¶n C − D công lçi. Hìn núa 0∈ / (C − D), v²c-tì vîi v¼ C ∩ D = ∅. t ∈ Rn , t 6= 0 x ∈ C, y ∈ D, sao cho Theo bê · tr¶n ¡p döng vîi ht, zi ≥ 0 vîi måi x0 = 0, z ∈ C − D. V¼ tçn t¤i z =x−y n¶n ta câ ht, xi ≥ ht, yi ∀x ∈ C, y ∈ D. L§y α := supht, yi, y∈D khi â si¶u ph¯ng ành lþ 1.2. ht, xi t¡ch C v  D. (ành lþ t¡ch 2) Cho C v  D l  hai tªp lçi, âng, kh¡c réng sao cho C ∩ D = ∅. Gi£ sû câ ½t nh§t mët tªp l  compact. Khi â hai tªp n y câ thº t¡ch m¤nh ÷ñc bði mët si¶u ph¯ng. Công nh÷ tr¶n, ành lþ t¡ch m¤nh ÷ñc d¹ d ng suy ra tø bê · sau nâi v· sü t¡ch m¤nh giúa mët tªp lçi âng v  mët iºm b¶n ngo i tªp n y. Bê · 1.3. Cho C ⊂ R l  mët tªp lçi, âng, kh¡c réng sao cho 0 ∈/ C . Khi â tçn t¤i mët v²c-tì t ∈ Rn, t 6= 0 v  α > 0 sao cho n ht, xi ≥ α > 0, ∀x ∈ C. Theo bê · n y, th¼ si¶u ph¯ng ht, xi = C v  iºm gèc to¤ ë câ thº t¡ch m¤nh, v½ dö bði α . 2 Chùng minh bê ·. Do C âng v  0 ∈ C , n¶n tçn t¤i qu£ c¦u B t¥m ð gèc, b¡n k½nh r>0 sao cho C ∩ B = ∅. p döng ành lþ t¡ch 1 cho hai 12 tªp C v  B, ta câ t ∈ Rn \ {0} v  α ∈ R, sao cho ht, xi ≥ α ≥ ht, yi∀x ∈ C, ∀y ∈ B. B¬ng c¡ch chu©n hâa ta câ thº xem gèc ¸n si¶u ph¯ng ½t nh§t l  b¬ng ktk = 1 α ≥ r. v  do â kho£ng c¡ch tø Vªy th¼ ht, xi ≥ α ≥ r > 0. Chùng minh ành lþ 1.2. Gi£ sû C l  tªp compact. Ta ch¿ ra tªp C − D âng. Thªt vªy, gi£ sû vîi xk ∈ C, y k ∈ D. V¼ zk ∈ C − D C y kj = z kj − xkj → z − x ∈ D. Vªy Chùng tä C −D l  tªp âng. Do t 6= 0, sao cho ht, x − yi ≥ α > 0 inf ht, xi − x∈C Chùng tä C Chó þ 1.1. v  zk → z. D Ta câ z k = xk − y k compact, n¶n câ mët d¢y con j → +∞. t¤i v  0∈ / C − D, vîi måi Vªy xkj → x khi z = x − y ∈ C − D. n¶n theo bê · tr¶n, tçn x ∈ C, y ∈ D. Vªy α α ≥ supht, yi + . 2 2 y∈D câ thº t¡ch m¤nh. i·u ki»n mët trong hai tªp l  compact trong ành lþ l  khæng thº bä ÷ñc. H¢y x²t v½ dö trong â C := {(x, t) ∈ R2 : x ≥ 0, t = 0}, D := {(x, t) ∈ R2 : t ≥ 1 , t > 0, x > 0}. x Rã r ng hai tªp n y lçi, âng khæng câ iºm chung, nh÷ng chóng khæng thº t¡ch m¤nh ÷ñc. (Xem h¼nh 1.4). Tø ành ngh¾a ta th§y r¬ng, n¸u hai tªp n¬m trong còng mët si¶u ph¯ng, th¼ chóng v¨n t¡ch ÷ñc, v½ dö ch½nh b¬ng si¶u ph¯ng â. º lo¤i bä tr÷íng hñp cüc oan n y, ng÷íi ta ÷a ra kh¡i ni»m t¡ch óng sau: 13 (a) T¡ch nh÷ng khæng t¡ch m¤nh (b) T¡ch m¤nh H¼nh 1.4: T¡ch v  t¡ch m¤nh Ta nâi hai tªp C v  D ÷ñc t¡ch óng bði si¶u ph¯ng aT x = α n¸u (1.12) thäa m¢n v  c£ hai tªp n y khæng còng n¬m trån trong si¶u ph¯ng t¡ch. Chó þ r¬ng n¸u A v  B l  hai tªp lçi m  v¨n câ thº t¡ch ÷ñc, v½ dö A v  B riA∩riB 6= ∅, th¼ hai tªp n y l  hai ÷íng ch²o cõa mët h¼nh chú nhªt trong m°t ph¯ng 2 chi·u. Tuy nhi¶n chóng khæng thº t¡ch óng. Mët h» qu£ r§t quan trång cõa ành lþ t¡ch l  bê · chån mang t¶n nh  to¡n håc Farkas ng÷íi Hungary, ÷ñc chùng minh tø n«m 1892 d÷îi d¤ng mët ành lþ h¼nh håc. Bê · n y r§t trüc quan, d¹ ¡p döng trong nhi·u l¾nh vüc nh÷ tèi ÷u, i·u khiºn, lþ thuy¸t to¡n tû v.v... H» qu£ 1.1. Cho A l  mët ma trªn thüc c§p m × n v  a ∈ R . Khi â n trong hai h» d÷îi ¥y câ mët h» v  ch¿ duy nh§t mët h» câ nghi»m: Ax ≥ 0, aT x < 0 AT y = a, y ≥ 0 vîi mët x ∈ Rn, vîi mët y ∈ Rm. (1.5) (1.6) Mët c¡ch ph¡t biºu t÷ìng ÷ìng, d÷îi ngæn ngú h¼nh håc, cõa Bê · Farkas l : 14 Nûa khæng gian v²c-tì a {x|aT x ≥ 0} {x|Ax ≥ 0} chùa nân n¬m trong nân sinh bði c¡c h ng cõa ma trªn A T x ≥ 0 ⇒ aT x ≥ 0 khi v  ch¿ khi khi v  ch¿ khi A. Tùc l  AT y = a, y ≥ 0. T½nh ch§t h¼nh håc cõa bê · n y r§t rã. Nâ nâi r¬ng nân lçi, âng {x|Ax ≥ 0} n¬m trong nûa khæng gian v²c-tì ph¡p tuy¸n a {x|aT x ≥ 0} khi v  ch¿ khi ð trong nân sinh bði c¡c h ng cõa ma trªn A. H¼nh 1.5: Bê · Farkas Chùng minh bê · Farkas. Gi£ sû (1.6) câ mët nghi»m y nh÷ Ax ≥ 0, 0, y ≥ 0, ta câ th¼ tø AT y = a, nh¥n t½ch væ h÷îng vîi aT x = y T Ax ≥ 0. Hiºn nhi¶n C l  tªp lçi âng v  Do (1.6) khæng câ nghi»m, n¶n v  do Ax ≥ Vªy (1.5) khæng thº câ nghi»m. B¥y gií ta gi£ sû h» (1.6) khæng câ nghi»m. L§y tªp AT y = x}. x, n o â. N¸u C = {x|∃y ≥ 0 : 0 ∈ C. a∈ / C . Theo ành lþ t¡ch m¤nh, tçn t¤i p 6= 0 v  mët sè α ∈ R sao cho pT a < α < pT x vîi måi x ∈ C . Do 0 ∈ C , n¶n α < 0. Thay x = AT y , vîi y ≥ 0, ta vi¸t ÷ñc α ≤ pT AT y = y T Ap. 15 Chó þ r¬ng n¸u ξx = AT ξy . x ∈ C, p ξx ∈ C Vªy c¡c to¤ ë cõa α ≤ pT AT y = y T Ap, v²c-tì th¼ sao cho suy ra Ap ≥ 0 v  y vîi måi ξ ≥ 0, v¼ tø x = AT y , câ câ thº lîn tuý þ, n¶n tø b§t ¯ng thùc Ap ≥ 0. Vªy ta ¢ ch¿ ra sü tçn t¤i cõa mët aT p < 0 . Chùng tä h» (1.5) câ nghi»m. 1.2 To¡n tû chi¸u kho£ng c¡ch B i to¡n t¼m h¼nh chi¸u l¶n mët tªp lçi câ vai trá quan trång v  câ r§t nhi·u ùng döng trong tèi ÷u, c¥n b¬ng v  b§t ¯ng thùc bi¸n ph¥n,... Cö thº, ta s³ chùng minh sü tçn t¤i v  t½nh duy nh§t cõa h¼nh chi¸u l¶n mët tªp lçi âng v  kh£o s¡t mët sè t½nh ch§t cì b£n cõa to¡n tû chi¸u. ành ngh¾a 1.12. Cho C 6= ∅ (khæng nh§t thi¸t lçi) v  y l  mët v²c-tì b§t ký, °t dC (y) := inf kx − yk. x∈C Ta nâi dC (y) l  kho£ng c¡ch tø y ¸n C . N¸u tçn t¤i π ∈ C sao cho dC (y) = kπ − yk, th¼ ta nâi π Chó þ 1.2. C l  h¼nh chi¸u cõa y tr¶n C . (Xem h¼nh 1.6). Theo ành ngh¾a 1.12, ta th§y h¼nh chi¸u pC (y) cõa y tr¶n s³ l  nghi»m cõa b i to¡n tèi ÷u 1 min{ kx − yk2 : x ∈ C}. x 2 Do â, vi»c t¼m h¼nh chi¸u cõa cõa h m to n ph÷ìng Ta kþ hi»u kx − yk2 y tr¶n tr¶n C câ thº ÷a v· vi»c t¼m cüc tiºu C. π = PC (y), ho°c ìn gi£n hìn l  P (y) n¸u khæng c¦n nh§n m¤nh ¸n tªp chi¸u C.