Tài liệu Phép chiếu vuông góc và một số ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM HOÀNG THỊ LIỄU PHÉP CHIẾU VUÔNG GÓC VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM HOÀNG THỊ LIỄU PHÉP CHIẾU VUÔNG GÓC VÀ MỘT SỐ ỨNG DỤNG Chuyên ngành: Giải tích Mã số: 60.46.01 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 - năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Môc lôc Lêi nãi ®Çu 1 2 C¸c kh¸i niÖm c¬ b¶n. 4 1.1 TËp låi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Tæ hîp låi. . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 TËp a-phin, tËp låi ®a diÖn. . . . . . . . . . . . . . . . . 6 1.1.3 Nãn låi. . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Hµm låi. 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 PhÐp chiÕu lªn tËp låi ®ãng. 18 2.1 §Þnh nghÜa vµ tÝnh chÊt. . . . . . . . . . . . . . . . . . . . . . 18 2.2 H×nh chiÕu cña mét ®iÓm lªn mét sè tËp quen thuéc. . . . . . . 24 3 Mét sè øng dông cña phÐp chiÕu. 28 3.1 §Þnh lý t¸ch tËp låi. . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 D­íi vi ph©n . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Gi¶i bÊt ®¼ng thøc biÕn ph©n. . . . . . . . . . . . . . . . . . . 39 Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 1 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Lêi nãi ®Çu Gi¶i tÝch låi lµ bé m«n c¬ b¶n cña gi¶i tÝch hiÖn ®¹i, nghiªn cøu vÒ tËp låi vµ hµm låi cïng nh÷ng vÊn ®Ò liªn quan. Bé m«n nµy cã vai trß quan träng trong nhiÒu lÜnh vùc kh¸c nhau cña to¸n häc øng dông, ®Æc biÖt lµ trong tèi ­u hãa, bÊt ®¼ng thøc biÕn ph©n, c¸c bµi to¸n c©n b»ng... Mét trong nh÷ng vÊn ®Ò quan träng cña gi¶i tÝch låi ®ã lµ phÐp chiÕu vu«ng gãc. §©y lµ mét c«ng cô s¾c bÐn vµ kh¸ ®¬n gi¶n ®Ó chøng minh nhiÒu ®Þnh lý quan träng nh­ §Þnh lý t¸ch, §Þnh lý xÊp xØ tËp låi, §Þnh lý vÒ tån t¹i nghiÖm cña BÊt ®¼ng thøc biÕn ph©n...Nh÷ng c¸ch chøng minh dùa vµo phÐp chiÕu th­êng mang tÝnh chÊt kiÕn thiÕt, gîi më ®Õn nhiÒu vÊn ®Ò kh¸c. Trong luËn v¨n nµy, chóng t«i tËp trung vµo viÖc tr×nh bµy ®Þnh nghÜa c¸c kh¸i niÖm, tÝnh chÊt cïng nh÷ng øng dông quan träng cña phÐp chiÕu. Dùa vµo ®ã, chóng t«i giíi thiÖu thuËt to¸n ®Ó t×m nghiÖm cña bµi to¸n bÊt ®¼ng thøc biÕn ph©n. Gi¶i quyÕt ®­îc bµi to¸n bÊt ®¼ng thøc biÕn ph©n th× chóng ta cã thÓ ®­a ra lêi gi¶i cho rÊt nhiÒu vÊn ®Ò kh¸c. Bëi v× nhiÒu bµi to¸n trong tèi ­u hãa, ph­¬ng tr×nh vËt lý to¸n vµ nhiÒu vÊn ®Ò trong kinh tÕ, kü thuËt giao th«ng ®« thÞ...®Òu ®­îc m« t¶ d­íi d¹ng ®ã. §Ò tµi bao gåm 3 ch­¬ng. Trong Ch­¬ng 1, tr­íc hÕt chóng t«i tr×nh bµy mét sè kiÕn thøc c¬ së cña tËp låi vµ hµm låi. Chóng lµ nh÷ng c«ng cô c¬ b¶n nhÊt cho nh÷ng nghiªn cøu ®­îc tr×nh bµy trong luËn v¨n. Ch­¬ng 2 lµ mét ch­¬ng chÝnh cña luËn v¨n. Trong ch­¬ng nµy chóng t«i dµnh ®Ó nãi riªng vÒ kh¸i niÖm, tÝnh chÊt c¬ b¶n cña phÐp chiÕu. §Æc biÖt chóng t«i tr×nh bµy c«ng thøc x¸c ®Þnh h×nh chiÕu cña mét ®iÓm lªn siªu hép, h×nh cÇu vµ kh«ng gian con cña Rn . Trong qu¸ tr×nh nghiªn cøu vÒ phÐp chiÕu vu«ng gãc, chóng ta biÕt r»ng h×nh chiÕu vu«ng gãc cña mét ®iÓm lªn tËp låi ®ãng, kh¸c rçng trong Rn lu«n tån t¹i vµ duy nhÊt. Dùa vµo ®ã, chóng t«i ®Ò cËp ®Õn nh÷ng øng dông 2 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn cña nã. Cô thÓ chóng t«i tr×nh bµy øng dông cña phÐp chiÕu vu«ng gãc vµo c¸c vÊn ®Ò sau: Chøng minh c¸c ®Þnh lý t¸ch, chøng minh sù tån t¹i cña d­íi vi ph©n cña hµm låi, x©y dùng thuËt to¸n gi¶i bÊt ®¼ng thøc biÕn ph©n. Nh÷ng vÊn ®Ò nµy ®­îc tr×nh bµy chi tiÕt ë Ch­¬ng 3. LuËn v¨n ®­îc hoµn thµnh d­íi sù h­íng dÉn tËn t×nh cña GS. TSKH. Lª Dòng M­u. Nhê ThÇy, t«i ®· b­íc ®Çu lµm quen vµ say mª trong c«ng viÖc nghiªn cøu to¸n. Nh©n dÞp nµy, t«i xin bµy tá lßng biÕt ¬n s©u s¾c tíi ThÇy. §ång thêi t«i còng ch©n thµnh c¶m ¬n c¸c thÇy c« gi¸o trong khoa To¸n Tr­êng §¹i häc S­ ph¹m Th¸i Nguyªn - §¹i häc Th¸i Nguyªn, ViÖn to¸n häc ®· tËn t×nh gi¶ng d¹y gióp t«i n¾m ®­îc nh÷ng kiÕn thøc c¬ së vµ t¹o ®iÒu kiÖn thuËn lîi cho hoµn thµnh luËn v¨n nµy. T«i xin c¶m ¬n ng­êi th©n, ®ång nghiÖp, b¹n bÌ ®· cæ vò ®éng viªn t«i trong qu¸ tr×nh lµm luËn v¨n. Th¸i Nguyªn, Ngµy 28 th¸ng 09 n¨m 2009 Häc viªn Hoµng ThÞ LiÔu 3 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ch­¬ng 1 C¸c kh¸i niÖm c¬ b¶n. Trong ch­¬ng nµy, chóng t«i tr×nh bµy nh÷ng kh¸i niÖm c¬ b¶n trong gi¶i tÝch låi cïng víi nh÷ng tÝnh chÊt ®Æc tr­ng cña nã nh­ tËp låi, tËp a-phin, nãn låi, hµm låi... 1.1 TËp låi. Nh÷ng tËp hîp quen thuéc mµ chóng ta ®· biÕt nh­ kh«ng gian con, siªu ph¼ng... ®Òu lµ tËp låi. Kh¸i niÖm vÒ tËp låi cã mét vai trß quan träng trong gi¶i tÝch låi. Trong phÇn nµy chóng t«i tr×nh bµy ®Þnh nghÜa, tÝnh chÊt cña tËp låi, tËp a-phin, tËp låi ®a diÖn, nãn låi... 1.1.1 Tæ hîp låi. §Þnh nghÜa 1.1.1. • Mét ®­êng th¼ng c¸c ®iÓm (vÐct¬) nèi hai ®iÓm (vÐct¬) a vµ b trong Rn lµ tËp hîp tÊt c¶ x ∈ Rn cã d¹ng {x ∈ Rn | x = (1 − λ)a + λb, λ ∈ R}. • Mét ®o¹n th¼ng ®iÓm (vÐct¬) nèi hai ®iÓm (vÐct¬) a vµ b trong Rn lµ tËp hîp tÊt c¶ c¸c x ∈ Rn cã d¹ng {x ∈ Rn | x = (1 − λ)a + λb, 0 ≤ λ ≤ 1} . 4 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn §Þnh nghÜa 1.1.2. 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 ∀x, y ∈ C, ∀λ ∈ [0; 1] =⇒ λx + (1 − λ)y ∈ C. x lµ tæ hîp låi cña c¸c ®iÓm (vÐct¬)x1 , . . . , xk nÕu Ta nãi x= k X i i n λi x , x ∈ R , λi ≥ 0, ∀i = 1, . . . , k, k X i=1 λi = 1. i=1 ( xem [2], Ch­¬ng 1, MÖnh ®Ò 1.1). TËp MÖnh ®Ò 1.1.3. C ⊆ Rn lµ låi khi 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µ, vµ chØ khi ∀k ∈ N, ∀λ1 , . . . , λk > 0 : k X 1 k λi = 1, ∀x , . . . , x ∈ C ⇒ i=1 k X λi xi ∈ C. i=1 Chøng minh. §iÒu kiÖn ®ñ: Suy ra tõ ®Þnh nghÜa cña tËp låi øng víi §iÒu kiÖn cÇn: k = 2. Ta chøng minh b»ng ph­¬ng ph¸p quy n¹p theo sè ®iÓm. k = 1 : HiÓn nhiªn. k = 2 : §iÒu kiÖn 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 ThËt vËy, nÕu k − 1 ®iÓm, ta chøng minh nã ®óng víi k ®iÓm. x lµ tæ hîp låi cña k ®iÓm x1 , . . . , xk ∈ C, tøc lµ : x= k X i λi x , λi > 0, ∀i = 1, . . . , k, i=1 Gi¶ sö k X λi = 1. i=1 λk > 0, ®Æt : α = k−1 P λi . Khi ®ã 0 < α < 1 vµ i=1 x= k−1 X i=1 Do k−1 X λi i x + λk xk . λi x + λk x = α α i=1 i k λi > 0 ∀i = 1, . . . , k − 1 vµ α k−1 X λi =1 α i=1 5 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn nªn theo gi¶ thiÕt quy n¹p th× ®iÓm k−1 X λi i x ∈ C. y= α i=1 Ta cã : x = αy + λk xk . Do α > 0, λk > 0 vµ α + λk = k P λi = 1 nªn i=1 x lµ tæ hîp låi cña y vµ xk ®Òu thuéc C . VËy x ∈ C. Tõ ®Þnh nghÜa cña tËp låi, ta suy ra líp c¸c tËp låi lµ ®ãng víi phÐp giao, phÐp céng ®¹i sè vµ phÐp nh©n tÝch Decastes. MÖnh ®Ò 1.1.4. trong Rn , C ( xem [2], Ch­¬ng 1, MÖnh ®Ò 1.2). NÕu lµ tËp låi trong A, B lµ c¸c tËp låi Rm th× c¸c tËp sau lµ låi A ∩ B = {x | x ∈ A, x ∈ B} , αA + βB = {x | x = αa + βb, a ∈ A, b ∈ B, α, β ∈ R} , A × C = {x ∈ Rm+n | x = (a; c), a ∈ A, c ∈ C} . 1.1.2 TËp a-phin, tËp låi ®a diÖn. Trong gi¶i tÝch cæ ®iÓn, ta ®· lµm quen víi c¸c kh«ng gian con, c¸c siªu ph¼ng...§ã lµ c¸c tr­êng hîp riªng cña tËp a-phin ®­îc ®Þnh nghÜa nh­ sau: §Þnh nghÜa 1.1.5. Mét tËp C ®­îc gäi lµ tËp a-phin nÕu nã chøa mäi ®­ê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. NhËn xÐt 1.1.6. a) TËp a-phin lµ mét tr­êng hîp riªng cña tËp låi. b) Mäi siªu ph¼ng trong Rn ®Òu lµ tËp a-phin. MÖnh ®Ò d­íi ®©y cho ta thÊy tËp a-phin chÝnh lµ ¶nh tÞnh tiÕn cña mét kh«ng gian con. 6 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MÖnh ®Ò 1.1.7. khi vµ chØ khi gian con (xem [2], Ch­¬ng 1, MÖnh ®Ò 1.3). TËp M M = L+a víi L 6= ∅ lµ tËp a-phin lµ mét kh«ng gian con vµ a ∈ M. Kh«ng L ®­îc x¸c ®Þnh duy nhÊt. Chøng minh. §iÒu kiÖn cÇn: Khi ®ã VËy Gi¶ sö M lµ tËp a-phin vµ a ∈ M . L = M − a chøa 0 vµ lµ tËp a-phin. Do ®ã, L lµ mét kh«ng gian con. M = L + a. §iÒu kiÖn ®ñ: NÕu M = L + a víi a ∈ M , L lµ kh«ng gian con th× ∀x, y ∈ M, λ ∈ R, ta cã: (1 − λ)x + λy = a + (1 − λ)(x − a) + λ(y − a). Do x − a, y − a ∈ L vµ L lµ kh«ng gian con nªn (1 − λ)(x − a) + λ(y − a) ∈ L. =⇒ (1 − λ)x + λy ∈ M. VËy M lµ tËp a-phin. Kh«ng gian con L ë trªn lµ duy nhÊt. ThËt vËy, nÕu M = L + a vµ M = L0 + a0 , trong ®ã L, L0 lµ nh÷ng kh«ng gian con vµ a, a0 ∈ M th× L0 = M − a = L + a − a0 = L + (a − a0 ). Do a0 ∈ M = a + L nªn a0 − a ∈ L. =⇒ L0 = L + (a − a0 ) = L. Kh«ng gian con song víi tËp a-phin L trong mÖnh ®Ò trªn ®­îc gäi lµ M. §Þnh nghÜa 1.1.8. Thø nguyªn( víi tËp a-phin kh«ng gian con song M ®­îc gäi lµ hay chiÒu) cña kh«ng gian con thø nguyªn( hay chiÒu) cña L song song M vµ ®­îc ký hiÖu lµ dimM . §iÓm a ∈ Rn lµ tËp a- phin cã sè chiÒu b»ng 0 bëi v× kh«ng gian con song song víi M = {a} lµ L = {0}. 7 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn MÖnh ®Ò 1.1.9. M ⊆ Rn (xem [2], Ch­¬ng 1, MÖnh ®Ò 1.4). BÊt kú mét tËp a- phin cã sè chiÒu r ®Òu cã d¹ng M = {x ∈ Rn | Ax = b} Trong ®ã: A lµ ma trËn cÊp (m × n), b ∈ Rm Ng­îc l¹i, mäi tËp hîp cã d¹ng (1.1) víi vµ (1.1) rank A = n − r. rank A = n − r ®Òu lµ tËp a-phin cã sè chiÒu lµ r. Chøng minh. §iÒu kiÖn cÇn: Gi¶ sö M lµ tËp a-phin cã sè chiÒu lµ r vµ M = L + a víi a ∈ M . VËy L = M − a lµ kh«ng gian con cã sè chiÒu lµ r. Theo ®¹i sè tuyÕn tÝnh kh«ng gian con r - chiÒu nµy cã d¹ng : L = {x | Ax = 0} trong ®ã A lµ ma trËn cÊp m × n vµ rank A = n − r. Tõ M = L + a suy ra M = {x | A(x − a) = 0} = {x | Ax = Aa = b} . §iÒu kiÖn ®ñ: NÕu M ®­îc cho bëi (1.1) víi a ∈ M , ta cã Aa = b, do ®ã M = {x | A(x − a) = 0} = a + L víi L = {x | Ax = 0} . Do rankA = n − r nªn L lµ kh«ng gian con cã sè chiÒu r. VËy dim M = r. §Þnh nghÜa 1.1.10. • Siªu ph¼ng trong kh«ng gian Rn lµ tËp hîp c¸c ®iÓm cã d¹ng {x ∈ Rn | ha, xi = α} trong ®ã : VÐct¬ a ∈ Rn \ {0} , α ∈ R. a ë trªn ®­îc gäi lµ vÐct¬ ph¸p tuyÕn cña siªu ph¼ng. •Nöa kh«ng gian ®ãng lµ mét tËp hîp cã d¹ng: {x | ha, xi ≤ α} , {x | ha, xi ≥ α} 8 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn trong ®ã : a ∈ Rn \ {0} , α ∈ R. • Nöa kh«ng gian më lµ mét tËp hîp cã d¹ng: {x | ha, xi > α} , {x | ha, xi < α} . trong ®ã : a ∈ Rn \ {0} , α ∈ R. Nh­ vËy mét siªu ph¼ng 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. NÕu hai nöa kh«ng gian nµy ®ãng th× phÇn chung cña chóng chÝnh lµ siªu ph¼ng. §Þnh nghÜa 1.1.11. Mét tËp hîp ®­îc gäi lµ tËp låi ®a diÖn, nÕu nã lµ giao cña mét sè h÷u h¹n c¸c nöa kh«ng gian ®ãng. §Þnh nghÜa 1.1.12. tùa t¹i Cho x0 ∈ C. Ta nãi siªu ph¼ng ha, xi = α lµ siªu ph¼ng x0 nÕu ha, x0 i = α, ha, xi ≥ α, ∀x ∈ C.  Ta nãi H = x | ha, x − x0 i ≤ 0 lµ nöa kh«ng gian tùa cña C t¹i x0 . §Þnh nghÜa 1.1.13. TËp tËp a-phin nhá nhÊt chøa KH: aff C , gäi lµ bao a- phin cña C C. MÖnh ®Ò 1.1.14. C C ⊆ Rn , giao cña tÊt c¶ c¸c tËp a-phin chøa C lµ (xem [2], Ch­¬ng 3, MÖnh ®Ò 3.2 ). Bao a- phin cña tËp lµ tËp bao gåm tÊt c¶ c¸c ®iÓm cã d¹ng x = λ1 x1 + . . . + λk xk sao cho xi ∈ C, λ1 + . . . + λk = 1 vµ k ∈ N. Chøng minh. Gi¶ sö Cho M lµ tËp hîp c¸c ®iÓm cã d¹ng (1.2). x, y ∈ M. Theo ®Þnh nghÜa cña M ta cã: x= k X λi xi i=1 y= h X µj yj j=1 9 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (1.2) trong ®ã xi ∈ C, ∀i = 1, . . . , k; yj ∈ C, ∀j = 1, . . . , h vµ k X λi = i=1 Th× mçi h X µj = 1. j=1 α ∈ (0; 1), ta cã : z = (1 − α)x + αy = k X i (1 − α)λi x + i=1 Do k X (1 − α)λi + h X i=1 nªn h X µj y j . j=1 αµj = (1 − α) + α = 1 j=1 z = (1 − α)x + αy ∈ M. Tõ ®ã suy ra M lµ tËp a - phin , affC ⊂ M. k k P P MÆt kh¸c: DÔ dµng thÊy r»ng nÕu x = λi xi víi xi ∈ C, λi = 1 th× i=1 x ∈ affC. Do ®ã M ⊂ affC VËy M = affE. §Þnh nghÜa 1.1.15.  aff i=1 x1 , . . . , x k C¸c ®iÓm x1 , . . . , xk ®­îc gäi lµ ®éc lËp a-phin nÕu cã sè chiÒu lµ k, tøc lµ, nÕu c¸c vÐc t¬ x1 −xk , . . . , xk−1 −xk lµ ®éc lËp tuyÕn tÝnh. HÖ qu¶ 1.1.16. Bao låi a-phin trong Rn lµ tËp a-phin Mäi ®iÓm x∈M M cña tËp (k − 1)− chiÒu. cã thÓ biÓu diÔn duy nhÊt d­íi d¹ng : x= k X i λi x , i=1 1.1.3  k ®iÓm ®éc lËp a-phin x1 , . . . , xk k X λi = 1. i=1 Nãn låi. Trong tèi ­u hãa, bÊt ®¼ng thøc biÕn ph©n, lý thuyÕt trß ch¬i vµ nhiÒu bé m«n to¸n øng dông kh¸c, kh¸i niÖm vÒ nãn cã mét vai trß quan träng. §Þnh nghÜa 1.1.17. Mét tËp C ®­îc gäi lµ nãn nÕu ∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C. 10 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Theo ®Þnh nghÜa, ta thÊy r»ng gèc täa ®é cã thÓ thuéc nãn hoÆc kh«ng thuéc nãn. DÜ nhiªn mét nãn kh«ng nhÊt thiÕt lµ mét tËp låi. VÝ dô C = {x ∈ R | x 6= 0} lµ mét nãn nh­ng kh«ng låi. Mét nãn ®­îc gäi lµ nãn nhän nÕu nã kh«ng chøa ®­êng th¼ng. Khi ®ã ta nãi 0 lµ ®Ønh cña nãn. 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. NÕu nãn låi nµy l¹i lµ mét tËp låi ®a diÖn th× ta nãi nã lµ nãn låi ®a diÖn. (xem [2], Ch­¬ng 1, MÖnh ®Ò 1.6). Mét tËp MÖnh ®Ò 1.1.18. C lµ nãn låi khi vµ chØ khi nã cã c¸c tÝnh chÊt sau: (i) (ii) λC ⊆ C, ∀λ > 0, C + C ⊆ C. Chøng minh. C lµ mét nãn låi. Do C lµ mét nãn, nªn ta cã (i). 1 Do C lµ mét tËp låi nªn víi mäi x, y ∈ C th× (x + y) ∈ C . 2 VËy theo (i) ta cã x + y ∈ C §iÒu kiÖn cÇn: §iÒu kiÖn ®ñ: Gi¶ sö Gi¶ sö ta cã (i) vµ (ii). Tõ (i) suy ra ngay Tõ (i) suy ra VËy C lµ mét nãn. Gi¶ sö x, y ∈ C vµ λ ∈ [ 0, 1] . λx ∈ C vµ (1 − λ)y ∈ C . Theo (ii) cã λx + (1 − λ)y ∈ C . C lµ mét nãn låi. §Þnh nghÜa 1.1.19. Cho gäi lµ h­íng lïi xa cña theo h­íng C lµ mét tËp låi trong Rn . Mét vÐc t¬ y 6= 0 ®­îc C , nÕu mäi tia xuÊt ph¸t tõ mét ®iÓm bÊt kú cña C y ®Òu n»m trän trong C . Tøc lµ : y lµ h­íng lïi xa khi chØ khi x + λy ∈ C, ∀x ∈ C, ∀λ ≥ 0. TËp hîp cña tÊt c¶ c¸c h­íng lïi xa cña hîp nµy ®­îc gäi lµ nãn lïi xa cña C cïng víi ®iÓm gèc lµ re C . TËp C. 11 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn HiÓn nhiªn nÕu Chó ý 1.1.20. hái víi mäi C lµ mét tËp bÞ chÆn th× re C chØ gåm duy nhÊt ®iÓm gèc. NÕu C lµ tËp låi ®ãng th× trong ®Þnh nghÜa trªn, thay v× ®ßi x ∈ C , chØ cÇn ®ßi hái cho mét ®iÓm x ∈ C . MÖnh ®Ò 1.1.21. ( xem [2], Ch­¬ng 1, MÖnh ®Ò 1.7). Gi¶ sö låi låi ®ãng. Khi ®ã y lµ mét h­íng lïi xa cña C C lµ mét tËp khi chØ khi x + λy ∈ C, ∀λ ≥ 0 víi mét ®iÓm x nµo ®ã thuéc Chøng minh. Gi¶ sö C. x + λy ∈ C, ∀λ ≥ 0 víi x ∈ C . ThÕ th× víi ∀u ∈ C vµ ∀µ > 0, do C låi, ta cã xλ = cho µ µ (x + λy) + (1 − )u ∈ C. λ+µ λ+µ λ −→ ∞, do C ®ãng , ta thÊy u + µy ∈ C , víi mäi u ∈ C vµ µ > 0. Chó ý 1.1.22. VÝ dô 1.1.23. Trong tr­êng hîp Trong C kh«ng ®ãng, mÖnh ®Ò trªn kh«ng ®óng. R2 lÊy C = {x = (x1 , x2 ) | x1 > 0, x2 > 0} ∪ {0} . HiÓn nhiªn, vÐc t¬ y = (0, 1) cã tÝnh chÊt lµ mäi tia xuÊt ph¸t tõ mét ®iÓm 0 6= x ∈ C theo h­íng nµy ®Òu n»m trän trong C , nh­ng nÕu xuÊt ph¸t tõ x = 0 th× ®iÒu nµy kh«ng ®óng. Cho C ⊆ Rn lµ tËp låi vµ x ∈ C . Ký hiÖu NC (x) = {w | hw, y − xi ≤ 0, ∀y ∈ C} . HiÓn nhiªn 0 ∈ NC (x). Dïng ®Þnh nghÜa dÔ kiÓm tra ®­îc r»ng NC (x) lµ nãn låi ®ãng. Nãn nµy ®­îc gäi lµ nãn ph¸p tuyÕn ngoµi cña gäi lµ nãn ph¸p tuyÕn trong cña C t¹i x. TËp −NC (x) ®­îc C t¹i x. −NC (x) = {w | hw, y − xi ≥ 0 ∀y ∈ C} . 12 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mét nãn quan träng kh¸c lµ nãn ®èi cùc ®­îc ®Þnh nghÜa nh­ sau: C ∗ = {w | hw, xi ≥ 0 ∀x ∈ C} . §©y còng lµ mét nãn låi ®ãng chøa gèc. Cho C lµ tËp låi, kh¸c rçng vµ x ∈ C . Ta nãi d ∈ Rn lµ mét h­íng chÊp nhËn ®­îc cña C nÕu ∃t0 > 0 sao cho x + td ∈ C víi mäi 0 ≤ t ≤ t0 . TËp tÊt c¶ c¸c h­íng chÊp nhËn ®­îc lµ mét nãn låi chøa gèc vµ gäi lµ nãn chÊp nhËn ®­îc. Ký hiÖu lµ FC (x). Nãn nµy cã thÓ kh«ng ®ãng, tuy nhiªn nÕu lÊy bao ®ãng, ta sÏ ®­îc mét nãn kh¸c gäi lµ nãn tiÕp xóc cña Ký hiÖu nãn nµy lµ C t¹i x. TC (x), th× FC (x) = TC (x). Tõ ®©y suy ra  TC (x) = d ∈ Rn | ∃dk → d, ∃tk & 0 : x + tk dk ∈ C ∀k . MÖnh ®Ò 1.1.24. ( xem [2], Ch­¬ng 1, MÖnh ®Ò 1.8). Nãn ph¸p tuyÕn vµ nãn tiÕp xóc lµ ®èi cùc cña nhau. DÔ dµng suy trùc tiÕp tõ ®Þnh nghÜa. VÝ dô 1.1.25. Gi¶ sö tËp låi C ®­îc cho bëi  C = x ∈ Rn | haj , xi ≤ bj , j = 1, . . . , m víi x ∈ C , ®Æt  J(x) = j | haj , xi = bj gäi lµ tËp chØ sè tÝch cùc t¹i x. Khi ®ã  TC (x) = x ∈ Rn | haj , xi ≤ 0, j ∈ J(x) . P NC (x) = cone (aj , j ∈ J(x)) = {y = λj aj : λj ≥ 0}. j∈J(x) 1.2 Hµm låi. Trong ch­¬ng tr×nh to¸n phæ th«ng, chóng ta ®· lµm quen víi kh¸i niÖm hµm låi mét c¸ch c¬ b¶n. Môc nµy, chóng t«i tr×nh bµy kh¸i niÖm tæng qu¸t vÒ hµm låi vµ mét sè tÝnh chÊt cña nã. 13 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Cho tËp §Þnh nghÜa 1.2.1. C ⊂ Rn vµ f : C → R Ta sÏ ký hiÖu : dom f = {x ∈ C | f (x) < +∞} , epi f = {(x, µ) ∈ C × R | f (x) ≤ µ} . C¸c tËp dom f , epi f lÇn l­ît ®­îc gäi lµ miÒn h÷u hiÖu vµ trªn ®å thÞ cña hµm f. B»ng c¸ch cho f (x) = +∞ nÕu x 6∈ C , ta cã thÓ coi f ®­îc x¸c ®Þnh trªn toµn kh«ng gian vµ dom f = {x ∈ Rn | f (x) < +∞} , epi f = {(x, µ) ∈ Rn × R | f (x) ≤ µ} . Quy ­íc nÕu λ = 0 th× λf (x) = 0 víi mäi x. §Þnh nghÜa 1.2.2. trªn Cho ∅= 6 C ⊆ Rn låi vµ f : C → R. Ta nãi f lµ hµm låi C nÕu epif lµ mét tËp låi trong Rn+1 . Hµm f ®­îc gäi lµ hµm lâm trªn C nÕu −f lµ hµm låi trªn C. Sau ®©y chñ yÕu ta xÐt hµm f : Rn → R ∪ {+∞}. DÔ thÊy ®Þnh nghÜa trªn t­¬ng ®­¬ng víi: f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) trong ®ã ∀x, y ∈ C , ∀λ ∈ (0, 1). §Þnh nghÜa 1.2.3. Hµm f : Rn → R ∪ {+∞} ®­îc gäi lµ låi chÆt trªn C nÕu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀λ ∈ (0, 1). Hµm f : Rn → R ∪ {+∞} ®­îc gäi lµ låi m¹nh trªn C víi hÖ sè η > 0 nÕu 1 f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) − ηλ(1 − λ) k x − y k2 2 ∀x, y ∈ C, ∀λ ∈ (0, 1). 14 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn NhËn xÐt 1.2.4. DÔ dµng kiÓm tra r»ng, f låi m¹nh trªn khi vµ chØ khi hµm h(.) = f (.) − låi trªn C víi hÖ sè η > 0 1 k . k2 2 C. Sau ®©y, ta sÏ ®Ò cËp ®Õn mét bÊt ®¼ng thøc quen thuéc trong ch­¬ng tr×nh phæ th«ng. §©y lµ bÊt ®¼ng thøc t­¬ng ®èi tæng qu¸t trong c¸c bÊt ®¼ng thøc vÒ hµm låi. C¸c bÊt ®¼ng thøc Cauchy, Bunhia...lµ nh÷ng tr­êng hîp riªng cña bÊt ®¼ng thøc nµy. BÊt ®¼ng thøc Jensen: NÕu f lµ hµm låi vµ nhËn gi¸ trÞ h÷u h¹n trªn tËp låi ∀x1 , . . . , xm ∈ C vµ ∀λj ≥ 0 tháa m·n m P C th× ∀m ∈ N∗ , λj = 1, ta cã: j=1 m m X X j f( λj x ) ≤ λj f (xj ). j=1 MÖnh ®Ò 1.2.5. j=1 ( xem [2], Ch­¬ng 8, MÖnh ®Ò 8.1). Mét hµm lµ låi trªn C khi chØ khi f :C →R ∀x, y ∈ C , ∀α > f (x), ∀β > f (y), ∀λ ∈ [ 0, 1] , ta cã f (λx + (1 − λ)y ≤ λα + (1 − λ)β. Chøng minh. §iÒu kiÖn cÇn: Chän Gi¶ sö f låi. chän x, y, α, β nh­ ®· nªu trong mÖnh ®Ò. α0 ∈ (f (x), α) vµ β 0 ∈ (f (y), β). VËy (x, α0 ), (y, β 0 ) ∈ epi f . Do epi f låi nªn ((1 − λ)x + λy, (1 − λ)α0 + λβ 0 ) ∈ epi f. ⇒ f ((1 − λ)x + λy) ≤ (1 − λ)α0 + λβ 0 < (1 − λ)α + λβ. §iÒu kiÖn ®ñ: Chän (x, µ), (y, η) ∈ epi f vµ λ ∈ (0, 1). Víi mäi  > 0, ta cã: f (x) < µ + , f (y) < η + . 15 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Do ®ã: f [ (1 − λ)α0 + λβ 0 ] < (1 − λ)(µ + ) + λ(η + ) = (1 − λ)µ + λη + . ⇒ (1 − λ)(x, µ) + λ(y, η) ∈ epi f. VËy f låi. D­íi ®©y lµ mét ®Þnh nghÜa kh¸c, t­¬ng ®­¬ng vÒ hµm låi, låi m¹nh dùa vµo kh¸i niÖm hÖ sè låi. Hµm §Þnh nghÜa 1.2.6. f : Rn → R ∪ {+∞} ( kh«ng nhÊt thiÕt låi ). C ⊆ Rn lµ mét tËp låi kh¸c rçng vµ η lµ mét sè thùc. Ta nãi η lµ hÖ sè låi cña f trªn C , nÕu víi ∀λ ∈ (0, 1), ∀x, y ∈ C , ta cã: 1 f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) − ηλ(1 − λ) k x − y k2 . 2 HiÓn nhiªn nÕu η = 0 th× f låi trªn C . NÕu f cã hÖ sè låi trªn C lµ η > 0 th× f låi m¹nh trªn C víi hÖ sè η. §Þnh nghÜa 1.2.7. Mét hµm f ®­îc gäi lµ chÝnh th­êng nÕu dom f 6= ∅ vµ f (x) > −∞ víi mäi x. Hµm f ®­îc gäi lµ ®ãng nÕu epi f lµ mét tËp ®ãng trong Rn+1 . Chó ý 1.2.8. a) Tõ ®Þnh nghÜa cña ®Þnh nÕu biÕt b) NÕu epi f , ta thÊy r»ng mét hµm låi hoµn toµn ®­îc x¸c epi f. f lµ mét hµm låi trªn mét tËp låi C th× cã thÓ th¸c triÓn f lªn toµn kh«ng gian b»ng c¸ch ®Æt fe (x) = HiÓn nhiªn fe (x) +∞ nÕu x 6∈ C. = f (x) víi ∀x ∈ C vµ fe låi trªn Rn . H¬n n÷a fe lµ chÝnh th­êng khi chØ khi c) NÕu ( f (x) nÕu x ∈ C f chÝnh th­êng. T­¬ng tù fe ®ãng khi vµ chØ khi f ®ãng. f låi trªn Rn suy ra domf låi. V× domf lµ h×nh chiÕu trªn C cña epif . dom f = {x : f (x) < +∞} = {x : ∃µ, (x, µ) ∈ epif } . 16 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn VËy domf lµ ¶nh cña tËp låi epif qua mét ¸nh x¹ tuyÕn tÝnh. Do ®ã, domf låi. VÝ dô 1.2.9. Mét sè hµm låi 1. Hµm a-phin: f (x) = ha, xi + α, trong ®ã a ∈ Rn , α ∈ R. DÔ dµng kiÓm tra ®­îc r»ng Khi f lµ hµm võa låi võa lâm trªn toµn kh«ng gian. α = 0, th× hµm nµy ®­îc gäi lµ hµm tuyÕn tÝnh. Cho C 6= ∅ lµ mét tËp låi. 2. Hµm chØ: §Æt ( 0 nÕu x ∈ C, δC (x) = +∞ nÕu x 6∈ C. Ta nãi δC lµ hµm chØ cña C . Do C låi nªn δC lµ mét hµm låi. 3. Hµm mÆt cÇu: Cho S = {x ∈ Rn | k x k= 1} lµ mét mÆt cÇu vµ h : S → R+ lµ mét hµm bÊt kú.  nÕu k x k< 1,  0 f (x) = h(x) nÕu k x k= 1,   +∞ nÕu k x k> 1. hµm nµy ®ùoc gäi lµ hµm mÆt cÇu. DÔ thÊy r»ng mÆc dï f lµ mét hµm låi trªn Rn , h lµ mét hµm kh«ng ©m bÊt kú trªn mÆt cÇu S . 4. Hµm tùa: Hµm d­íi ®©y ®­îc gäi lµ hµm tùa cña C SC (y) = sup< y, x >. x∈C 5. Hµm kho¶ng c¸ch: Cho C låi ®ãng, hµm kho¶ng c¸ch ®Õn tËp C ®­îc ®Þnh nghÜa bëi dC (x) = mink x − y k. y∈C 6. Hµm chuÈn: Gi¶ sö x = (x1 , . . . , xn ). f (x) =k x k= max| xi | i hoÆc 1 f (x) =k x k= (x1 2 + . . . + xn 2 ) 2 . 17 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Ch­¬ng 2 PhÐp chiÕu lªn tËp låi ®ãng. Bµi to¸n t×m h×nh chiÕu vu«ng gãc cña mét ®iÓm xuèng tËp låi cã vai trß quan träng trong tèi ­u vµ nhiÒu lÜnh vùc kh¸c nh­ bÊt ®¼ng thøc biÕn ph©n, c©n b»ng...Bµi to¸n nµy cã rÊt nhiÒu øng dông, ®Æc biÖt nã xuÊt hiÖn nh­ mét bµi to¸n phô trong rÊt nhiÒu ph­¬ng ph¸p sè tèi ­u, bÊt ®¼ng thøc biÕn ph©n. §©y còng lµ c«ng cô s¾c bÐn vµ kh¸ ®¬n gi¶n ®Ó chøng minh nhiÒu ®Þnh lý quan träng nh­ ®Þnh lý t¸ch,...mµ ta sÏ xÐt ë ch­¬ng sau. Nh÷ng c¸ch chøng minh dùa trªn phÐp chiÕu vu«ng gãc th­êng mang tÝnh chÊt kiÕn thiÕt. 2.1 §Þnh nghÜa vµ tÝnh chÊt. §Þnh nghÜa 2.1.1. 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 k x − y k . x∈C Ta nãi dC (y) lµ kho¶ng c¸ch tõ NÕu tån t¹i vu«ng gãc y ®Õn C . π ∈ C sao cho dC (y) =k π − y k th× ta nãi π lµ cña y trªn C . Ta ký hiÖu h×nh chiÕu cña y trªn C lµ pC (y). Th«ng th­êng sÏ ký hiÖu π cÇn nhÊn m¹nh ®Õn tËp chiÕu Chó ý r»ng, nÕu h×nh chiÕu = pC (y) hoÆc ®¬n gi¶n h¬n lµ p(y) nÕu kh«ng C. y ∈ C th× dC (y) = 0. NÕu C 6= ∅ th× dC (y) h÷u h¹n v× 0 ≤ dC (y) ≤k y − x k víi mäi x ∈ C. Theo ®Þnh nghÜa, ta thÊy r»ng h×nh chiÕu pC (y) cña y trªn C sÏ lµ nghiÖm 18 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn