Luận văn Thạc sĩ Toán học: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:42

Thêm vào BST

Báo xấu

15
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung luận văn trình bày định nghĩa lập lồi, một số tính chất của tập lồi, hàm lồi. Tiếp theo là trình bày định lý tách các lập lồi. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: 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 i Líi c£m ìn ii Líi nâi ¦u 1 Ch÷ìng 1. Mët sè ki¸n thùc chu©n bà 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 . . . . . . . . . . . . . 22 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 . . . . . . . . . . . . . . . . . . . . . 25 T i li»u tham kh£o 37
i B£ng kþ hi»u R tªp sè thüc Rn khæng gian Euclide n-chi·u ∅ tªp réng ∀x vîi måi x ∃x tçn t¤i x kxk chu©n cõa vectì x hx, yi t½ch væ h÷îng cõa hai v²c-tì x v y kxk chu©n cõa v²c-tì x 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 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 sc 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. Nhc l¤i r¬ng, mët ÷íng th¯ng nèi hai iºm (hai v²c-tì) a, b trong Rn l tªp hñp t§t c£ c¡c v²c-tì x ∈ Rn 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 tªp lçi, n¸u C chùa måi o¤n th¯ng i qua hai iºm b§t ký cõa nâ. Tùc l 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 Rn l c¡c tªp con lçi cõa Rn . o¤n th¯ng AB 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. Ta nâi x l tê hñp lçi cõa c¡c iºm x1, . . . , xk n¸u k X k X j x= λj x , λj > 0 ∀j = 1, . . . , k, λj = 1. 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 X k X 1 k ∀k ∈ N, ∀λ1 , . . . , λk > 0 : λj = 1, ∀x , . . . , x ∈ C ⇒ λj xj ∈ C. j=1 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 k−1 iºm. Ta c¦n chùng minh vîi k iºm. Gi£ sû x l tê hñp lçi cõa k iºm x1 , . . . , x k ∈ C . Tùc l k X k X j x= λj x , λj > 0 ∀j = 1, . . . , k, λj = 1. j=1 j=1 °t k−1 X ξ= λj . j=1 Khi â 0
6 Ta câ x = ξy + λxk . Do ξ > 0, λk > 0 v k X ξ + λk = λ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) A ∩ B := {x|x ∈ A, x ∈ B}, (ii) λA + βB := {x|x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R}, (iii) 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. Ta nâi x l tê hñp a-phin cõa c¡c iºm (v²c-tì) x1 , . . . , xk n¸u k X k X j x= λj x , λj = 1. j=1 j=1 Tªp hñp cõa c¡c tê hñp a-phin cõa 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ët v½ dö iºn h¼nh cõa tªp a-phin l c¡c khæng gian con. M»nh · 1.3. M 6= ∅ l tªp a-phin khi v ch¿ khi nâ câ d¤ng M = L+a 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 L trong m»nh · tr¶n ÷ñc gåi l khæng gian con song song vîi M , ho°c nâi ngn gån hìn l khæng gian con cõa M . Chi·u cõa mët tªp a-phin M ÷ñc ành ngh¾a bði chi·u cõa khæng gian song song vîi M 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 nân lçi n¸u nâ çng thíi l mët tªp lçi. V½ dö 1.3. a) Tªp Rn+ = {x ∈ Rn : x ≥ 0} l mët nân lçi. b) Cho bα ∈ Rn (α ∈ I) vîi I l tªp ch¿ sè n o â. Khi â tªp K = {x ∈ Rn : hx, bα i ≤ 0, ∀α ∈ I}
8 Kα , vîi Kα = {x ∈ Rn : hx, bα i ≤ 0} l nân lçi. T l mët nân lçi v¼ 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) λC ⊆ C , ∀λ > 0; (ii) 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 f :C →R x¡c ành tr¶n mët tªp lçi C ⊆ Rn . Khi â f ÷ñc gåi l 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 h m lçi ch°t tr¶n C n¸u vîi måi x, y ∈ C , x 6= y v måi sè thüc λ ∈ (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. (i) H m f h m lãm tr¶n C n¸u −f l h m lçi tr¶n C . ÷ñc gåi l (ii) H m f ÷ñc gåi l h m tuy¸n t½nh a-phin (hay h m a-phin ) tr¶n C n¸u f húu h¤n v vøa lçi, vøa lãm tr¶n C. V½ dö 1.4. a) Måi h m chu©n ·u l h m lçi tr¶n Rn : n !1/p X kxkp = |xi |p vîi p≥1 v kxk∞ = max |xi |. 1≤i≤n i=1 b) H m kho£ng c¡ch tø iºm x ∈ Rn tîi C ÷ñc x¡c ành bði dC (x) = inf y∈C kx − yk l h m lçi. ành ngh¾a 1.8. Cho f : Rn → R ∪ {+∞}. Ta nâi x∗ ∈ Rn l d÷îi ¤o h m cõa f t¤i x n¸u 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 f t¤i x ÷ñc gåi l d÷îi vi ph¥n cõa f t¤i x v ÷ñc k½ hi»u l ∂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 Rn l mët tªp hñp c¡c iºm câ d¤ng {x ∈ Rn : aT x = α},
10 trong â a ∈ Rn l mët v²c-tì kh¡c 0 v α ∈ R. V²c-tì a th÷íng ÷ñc gåi l 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. Cho hai tªp C v D kh¡c réng, ta nâi si¶u ph¯ng aT x = α t¡ch C v D n¸u aT x ≤ α ≤ aT y, ∀x ∈ C, ∀y ∈ D. (1.3) Ta nâi si¶u ph¯ng aT x = α t¡ch ch°t C v D n¸u aT x < α < aT y, ∀x ∈ C, ∀y ∈ D. ành lþ 1.1. (à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. (Bê · li¶n thuëc) Cho C ⊂ Rn 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 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 ∩ D = ∅. Theo bê · tr¶n ¡p döng vîi x0 = 0, tçn t¤i v²c-tì t ∈ Rn , t 6= 0 sao cho ht, zi ≥ 0 vîi måi z ∈ C − D. V¼ z =x−y vîi x ∈ C, y ∈ D, n¶n ta câ ht, xi ≥ ht, yi ∀x ∈ C, y ∈ D. L§y α := supht, yi, y∈D khi â si¶u ph¯ng ht, xi t¡ch C v D. ành lþ 1.2. (à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 . n Khi â tçn t¤i mët v²c-tì t ∈ Rn, t 6= 0 v α > 0 sao cho ht, xi ≥ α > 0, ∀x ∈ C. Theo bê · n y, th¼ C v iºm gèc to¤ ë câ thº t¡ch m¤nh, v½ dö bði α si¶u ph¯ng ht, xi = . 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 ktk = 1 v do â kho£ng c¡ch tø gèc ¸n si¶u ph¯ng ½t nh§t l b¬ng α ≥ r. 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û zk ∈ C − D v zk → z. Ta câ z k = xk − y k vîi xk ∈ C, y k ∈ D. V¼ C compact, n¶n câ mët d¢y con xkj → x khi j → +∞. Vªy y kj = z kj − xkj → z − x ∈ D. Vªy z = x − y ∈ C − D. Chùng tä C −D l tªp âng. Do 0∈ / C − D, n¶n theo bê · tr¶n, tçn t¤i t 6= 0, sao cho ht, x − yi ≥ α > 0 vîi måi x ∈ C, y ∈ D. Vªy α α inf ht, xi − ≥ supht, yi + . x∈C 2 y∈D 2 Chùng tä C v D câ thº t¡ch m¤nh. Chó þ 1.1. 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 â 1 C := {(x, t) ∈ R2 : x ≥ 0, t = 0}, D := {(x, t) ∈ R2 : t ≥ , 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 riA∩riB 6= ∅, th¼ hai tªp n y v¨n câ thº t¡ch ÷ñc, v½ dö A v B 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 vîi mët x ∈ Rn, (1.5) AT y = a, y ≥ 0 vîi mët y ∈ Rm. (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 {x|aT x ≥ 0} chùa nân {x|Ax ≥ 0} khi v ch¿ khi v²c-tì a n¬m trong nân sinh bði c¡c h ng cõa ma trªn A. Tùc l A T x ≥ 0 ⇒ aT x ≥ 0 khi v ch¿ khi 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 {x|aT x ≥ 0} khi v ch¿ khi v²c-tì ph¡p tuy¸n a ð 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 n o â. N¸u nh÷ Ax ≥ 0, th¼ tø AT y = a, nh¥n t½ch væ h÷îng vîi x, v do Ax ≥ 0, y ≥ 0, ta câ aT x = y T Ax ≥ 0. 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 C = {x|∃y ≥ 0 : AT y = x}. Hiºn nhi¶n C l tªp lçi âng v 0 ∈ C. Do (1.6) khæng câ nghi»m, n¶n 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 ∈ C, th¼ ξx ∈ C vîi måi ξ ≥ 0, v¼ tø x = AT y , câ ξx = AT ξy . Vªy c¡c to¤ ë cõa y câ thº lîn tuý þ, n¶n tø b§t ¯ng thùc α ≤ pT AT y = y T Ap, suy ra Ap ≥ 0. Vªy ta ¢ ch¿ ra sü tçn t¤i cõa mët v²c-tì p sao cho Ap ≥ 0 v 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 π l h¼nh chi¸u cõa y tr¶n C . (Xem h¼nh 1.6). Chó þ 1.2. Theo ành ngh¾a 1.12, ta th§y h¼nh chi¸u pC (y) cõa y tr¶n C 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 y tr¶n C câ thº ÷a v· vi»c t¼m cüc tiºu cõa h m to n ph÷ìng kx − yk2 tr¶n C. Ta kþ hi»u π = 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.