Luận văn: PHÉP CHIẾU VUÔNG GÓC VÀ MỘT SỐ ỨNG DỤNG

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

Thêm vào BST

Báo xấu

132
lượt xem 24
download

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

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.

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: 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 2 1 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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 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. lµ mét ch¬ng chÝnh cña luËn v¨n. Trong ch¬ng nµy chóng Ch¬ng 2 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 Rn . hép, h×nh cÇu vµ kh«ng gian con cña Trong qu¸ tr×nh nghiªn cøu vÒ phÐp chiÕu vu«ng gãc, chóng ta biÕt r»ng Rn 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 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 Mu. 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. 28 th¸ng 09 n¨m 2009 Th¸i Nguyªn, Ngµy 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 trng 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. a vµ b trong Rn lµ tËp hîp tÊt c¶ • Mét nèi hai ®iÓm (vÐct¬) ®êng th¼ng x ∈ Rn cã d¹ng c¸c ®iÓm (vÐct¬) {x ∈ Rn | x = (1 − λ)a + λb, λ ∈ R}. a vµ b trong Rn lµ tËp hîp tÊt c¶ c¸c • Mét nèi hai ®iÓm (vÐct¬) ®o¹n th¼ng x ∈ Rn cã d¹ng ®iÓm (vÐct¬) {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
C ⊆ Rn ®îc gäi lµ mét tËp låi nÕu C chøa mäi Mét tËp §Þnh nghÜa 1.1.2. ®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 k k i i n λi x , x ∈ R , λi ≥ 0, ∀i = 1, . . . , k, x= λi = 1. i=1 i=1 C ⊆ Rn ( xem [2], Ch¬ng 1, MÖnh ®Ò 1.1). TËp MÖnh ®Ò 1.1.3. lµ låi khi C 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µ, lµ låi khi vµ chØ khi k k 1 k λi xi ∈ C. ∀k ∈ N, ∀λ1 , . . . , λk > 0 : λi = 1, ∀x , . . . , x ∈ C ⇒ i=1 i=1 Chøng minh. Suy ra tõ ®Þnh nghÜa cña tËp låi øng víi k = 2. §iÒu kiÖn ®ñ: Ta chøng minh b»ng ph¬ng ph¸p quy n¹p theo sè ®iÓm. §iÒu kiÖn cÇn: 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 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µ : ThËt vËy, nÕu k k i λi x , λi > 0, ∀i = 1, . . . , k, x= λi = 1. i=1 i=1 k −1 Gi¶ sö λk > 0, ®Æt : α = λi . Khi ®ã 0 < α < 1 vµ i=1 k −1 k −1 λi i i k x + λk xk . x= λi x + λk x = α α i=1 i=1 λi Do > 0 ∀i = 1, . . . , k − 1 vµ α k −1 λ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 λi i x ∈ C. y= α i=1 k x = αy + λk xk . Do α > 0, λk > 0 vµ α + λk = Ta cã : λ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. ( xem [2], Ch¬ng 1, MÖnh ®Ò 1.2). NÕu A, B MÖnh ®Ò 1.1.4. lµ c¸c tËp låi Rn , C Rm trong lµ tËp låi trong 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: Mét tËp C ®îc gäi lµ tËp a-phin nÕu nã chøa mäi ®êng §Þnh nghÜa 1.1.5. 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. Rn ®Òu lµ tËp a-phin. b) Mäi siªu ph¼ng trong 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
(xem [2], Ch¬ng 1, MÖnh ®Ò 1.3). TËp M = ∅ lµ tËp a-phin MÖnh ®Ò 1.1.7. a ∈ M. M = L+a L khi vµ chØ khi víi lµ mét kh«ng gian con vµ Kh«ng L ®îc x¸c ®Þnh duy nhÊt. gian con Chøng minh. Gi¶ sö M lµ tËp a-phin vµ a ∈ M . §iÒu kiÖn cÇn: Khi ®ã L = M − a chøa 0 vµ lµ tËp a-phin. Do ®ã, L lµ mét kh«ng gian con. VËy M = L + a. NÕu M = L + a víi a ∈ M , L lµ kh«ng gian con th× §iÒu kiÖn ®ñ: ∀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 = L + a , trong ®ã L, L lµ nh÷ng kh«ng gian con vµ a, a ∈ M th× L = M − a = L + a − a = L + (a − a ). Do a ∈ M = a + L nªn a − a ∈ L. =⇒ L = L + (a − a ) = L. Kh«ng gian con L trong mÖnh ®Ò trªn ®îc gäi lµ kh«ng gian con song víi tËp a-phin M. song §Þnh nghÜa 1.1.8. Thø nguyªn( hay chiÒu) cña kh«ng gian con L song song víi tËp a-phin M ®îc gäi lµ thø nguyªn( hay chiÒu) cña M vµ ®îc ký hiÖu lµ dimM . a ∈ Rn lµ tËp a- phin cã sè chiÒu b»ng 0 bëi v× kh«ng gian con §iÓm 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
(xem [2], Ch¬ng 1, MÖnh ®Ò 1.4). BÊt kú mét tËp a- phin MÖnh ®Ò 1.1.9. M ⊆ Rn cã sè chiÒu r ®Òu cã d¹ng M = {x ∈ Rn | Ax = b} (1.1) A lµ ma trËn cÊp (m × n), b ∈ Rm rank A = n − r. Trong ®ã: vµ rank A = n − r Ngîc l¹i, mäi tËp hîp cã d¹ng (1.1) víi ®Òu lµ tËp a-phin cã sè chiÒu lµ r. Chøng minh. Gi¶ sö M lµ tËp a-phin cã sè chiÒu lµ r vµ M = L + a víi §iÒu kiÖn cÇn: 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} . NÕu M ®îc cho bëi (1.1) víi a ∈ M , ta cã Aa = b, do ®ã §iÒu kiÖn ®ñ: 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 | a, x = α} a ∈ R n \ { 0} , α ∈ R . trong ®ã : VÐct¬ 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 | a, x ≤ α} , {x | a, x ≥ α} 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
a ∈ Rn \ {0} , α ∈ R. trong ®ã : • Nöa kh«ng gian më lµ mét tËp hîp cã d¹ng: {x | a, x > α} , {x | a, x < α} . a ∈ R n \ { 0} , α ∈ R . trong ®ã : 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. Mét tËp hîp ®îc gäi lµ tËp låi ®a diÖn, nÕu nã lµ giao §Þnh nghÜa 1.1.11. cña mét sè h÷u h¹n c¸c nöa kh«ng gian ®ãng. x0 ∈ C. Ta nãi siªu ph¼ng a, x = α lµ siªu ph¼ng Cho §Þnh nghÜa 1.1.12. x0 nÕu t¹i tùa a, x0 = α, a, x ≥ α, ∀x ∈ C. H = x | a, x − x0 ≤ 0 lµ nöa kh«ng gian tùa cña C t¹i x0 . Ta nãi C ⊆ Rn , giao cña tÊt c¶ c¸c tËp a-phin chøa C lµ TËp §Þnh nghÜa 1.1.13. tËp a-phin nhá nhÊt chøa C , gäi lµ bao a- phin cña C KH: aff C. (xem [2], Ch¬ng 3, MÖnh ®Ò 3.2 ). Bao a- phin cña tËp MÖnh ®Ò 1.1.14. C lµ tËp bao gåm tÊt c¶ c¸c ®iÓm cã d¹ng x = λ1 x1 + . . . + λk xk (1.2) xi ∈ C, λ1 + . . . + λk = 1 vµ k ∈ N. sao cho Cho M lµ tËp hîp c¸c ®iÓm cã d¹ng (1.2). Chøng minh. Gi¶ sö x, y ∈ M. Theo ®Þnh nghÜa cña M ta cã: k λi xi x= i=1 h y= µ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
trong ®ã xi ∈ C, ∀i = 1, . . . , k ; yj ∈ C, ∀j = 1, . . . , h vµ k h λi = µj = 1. i=1 j =1 Th× mçi α ∈ (0; 1), ta cã : k h i µj y j . z = (1 − α)x + αy = (1 − α)λi x + i=1 j =1 Do k h (1 − α)λi + αµj = (1 − α) + α = 1 i=1 j =1 nªn z = (1 − α)x + αy ∈ M. Tõ ®ã suy ra M lµ tËp a - phin , affC ⊂ M. k k λi xi víi xi ∈ C, MÆt kh¸c: DÔ dµng thÊy r»ng nÕu x= λi = 1 i=1 i=1 th× x ∈ affC. Do ®ã M ⊂ affC VËy M = affE. x1 , . . . , xk ®îc gäi lµ C¸c ®iÓm nÕu §Þnh nghÜa 1.1.15. ®éc lËp a-phin x1 , . . . , xk cã sè chiÒu lµ k, tøc lµ, nÕu c¸c vÐc t¬ x1 − xk , . . . , xk−1 − xk aff lµ ®éc lËp tuyÕn tÝnh. k ®iÓm ®éc lËp a-phin x1 , . . . , xk M HÖ qu¶ 1.1.16. Bao låi a-phin cña tËp Rn (k − 1)− chiÒu. trong lµ tËp a-phin x∈M Mäi ®iÓm cã thÓ biÓu diÔn duy nhÊt díi d¹ng : k k i x= λi x , λi = 1. i=1 i=1 1.1.3 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. Mét tËp C ®îc gäi lµ nãn nÕu §Þnh nghÜa 1.1.17. ∀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 = 0} lµ mét nãn nhng 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 C MÖnh ®Ò 1.1.18. lµ nãn låi khi vµ chØ khi nã cã c¸c tÝnh chÊt sau: λC ⊆ C, ∀λ > 0, (i) C + C ⊆ C. (ii) Chøng minh. Gi¶ sö C lµ mét nãn låi. Do C lµ mét nãn, nªn ta cã (i). §iÒu kiÖn cÇn: 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 Gi¶ sö ta cã (i) vµ (ii). §iÒu kiÖn ®ñ: Tõ (i) suy ra ngay C lµ mét nãn. Gi¶ sö x, y ∈ C vµ λ ∈ [ 0, 1] . Tõ (i) suy ra λx ∈ C vµ (1 − λ)y ∈ C . Theo (ii) cã λx + (1 − λ)y ∈ C . VËy C lµ mét nãn låi. C lµ mét tËp låi trong Rn . Mét vÐc t¬ y = 0 ®îc Cho §Þnh nghÜa 1.1.19. gäi lµ híng lïi xa cña C , nÕu mäi tia xuÊt ph¸t tõ mét ®iÓm bÊt kú cña C theo híng 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 C cïng víi ®iÓm gèc lµ re C . TËp hîp nµy ®îc gäi lµ nãn lïi xa cña 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 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 Chó ý 1.1.20. hái víi mäi x ∈ C , chØ cÇn ®ßi hái cho mét ®iÓm x ∈ C . ( xem [2], Ch¬ng 1, MÖnh ®Ò 1.7). Gi¶ sö C MÖnh ®Ò 1.1.21. lµ mét tËp C låi låi ®ãng. Khi ®ã y lµ mét híng lïi xa cña khi chØ khi x + λy ∈ C, ∀λ ≥ 0 C. víi mét ®iÓm x nµo ®ã thuéc Gi¶ sö x + λy ∈ C, ∀λ ≥ 0 víi x ∈ C . ThÕ th× víi ∀u ∈ C vµ Chøng minh. ∀µ > 0, do C låi, ta cã µ µ (x + λy ) + (1 − )u ∈ C. xλ = λ+µ λ+µ cho λ −→ ∞, do C ®ãng , ta thÊy u + µy ∈ C , víi mäi u ∈ C vµ µ > 0. Trong trêng hîp C kh«ng ®ãng, mÖnh ®Ò trªn kh«ng ®óng. Chó ý 1.1.22. R2 lÊy Trong VÝ dô 1.1.23. 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 = x ∈ C theo híng nµy ®Òu n»m trän trong C , nhng nÕu xuÊt ph¸t tõ x = 0 th× ®iÒu nµy kh«ng ®óng. C ⊆ Rn lµ tËp låi vµ x ∈ C . Ký hiÖu Cho NC (x) = {w | w, y − x ≤ 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 C t¹i x. TËp −NC (x) ®îc gäi lµ nãn ph¸p tuyÕn trong cña C t¹i x. −NC (x) = {w | w, y − x ≥ 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 | w, x ≥ 0 ∀x ∈ C } . §©y còng lµ mét nãn låi ®ãng chøa gèc. 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 Cho 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 C t¹i x. Ký hiÖu nãn nµy lµ TC (x), th× FC (x) = TC (x). Tõ ®©y suy ra TC (x) = d ∈ Rn | ∃dk → d, ∃tk 0 : x + tk dk ∈ C ∀k . ( xem [2], Ch¬ng 1, MÖnh ®Ò 1.8). Nãn ph¸p tuyÕn vµ MÖnh ®Ò 1.1.24. 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. Gi¶ sö tËp låi C ®îc cho bëi VÝ dô 1.1.25. C = x ∈ Rn | aj , x ≤ bj , j = 1, . . . , m víi x ∈ C , ®Æt J (x) = j | aj , x = bj gäi lµ tËp chØ sè tÝch cùc t¹i x. Khi ®ã TC (x) = x ∈ Rn | aj , x ≤ 0, j ∈ J (x) . 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
C ⊂ Rn vµ f : C → R Cho tËp §Þnh nghÜa 1.2.1. 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µ vµ trªn ®å thÞ cña miÒn h÷u hiÖu hµm f. B»ng c¸ch cho f (x) = +∞ nÕu x ∈ 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. ∅ = C ⊆ Rn låi vµ f : C → R. Ta nãi f lµ Cho §Þnh nghÜa 1.2.2. 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 trªn C nÕu −f lµ hµm låi trªn C. f : Rn → R ∪ {+∞}. DÔ thÊy ®Þnh nghÜa Sau ®©y chñ yÕu ta xÐt hµm trªn t¬ng ®¬ng víi: f (λx + (1 − λ)y ) ≤ λf (x) + (1 − λ)f (y ) trong ®ã ∀x, y ∈ C , ∀λ ∈ (0, 1). f : Rn → R ∪ {+∞} ®îc gäi lµ Hµm trªn C §Þnh nghÜa 1.2.3. låi chÆt nÕu f (λx + (1 − λ)y ) < λf (x) + (1 − λ)f (y ) ∀x, y ∈ C, ∀λ ∈ (0, 1). f : Rn → R ∪ {+∞} ®îc gäi lµ låi m¹nh trªn C víi hÖ sè η > 0 nÕu Hµm 1 2 f (λx + (1 − λ)y ) < λf (x) + (1 − λ)f (y ) − ηλ(1 − λ) x−y 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
DÔ dµng kiÓm tra r»ng, f låi m¹nh trªn C víi hÖ sè η > 0 NhËn xÐt 1.2.4. khi vµ chØ khi hµm 1 2 h(.) = f (.) − . 2 låi trªn 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: C th× ∀m ∈ N∗ , NÕu f lµ hµm låi vµ nhËn gi¸ trÞ h÷u h¹n trªn tËp låi m ∀x1 , . . . , xm ∈ C vµ ∀λj ≥ 0 tháa m·n λj = 1, ta cã: j =1 m m j λj f (xj ). λj x ) ≤ f( j =1 j =1 ( xem [2], Ch¬ng 8, MÖnh ®Ò 8.1). Mét hµm f :C→R MÖnh ®Ò 1.2.5. ∀x, y ∈ C , ∀α > f (x), ∀β > f (y ), ∀λ ∈ [ 0, 1] , lµ låi trªn C khi chØ khi ta cã f (λx + (1 − λ)y ≤ λα + (1 − λ)β. Chøng minh. Gi¶ sö f låi. chän x, y, α, β nh ®· nªu trong mÖnh ®Ò. §iÒu kiÖn cÇn: Chän α ∈ (f (x), α) vµ β ∈ (f (y ), β ). VËy (x, α ), (y, β ) ∈ epi f . Do epi f låi nªn ((1 − λ)x + λy, (1 − λ)α + λβ ) ∈ epi f. ⇒ f ((1 − λ)x + λy ) ≤ (1 − λ)α + λβ < (1 − λ)α + λβ. Chän (x, µ), (y, η ) ∈ epi f vµ λ ∈ (0, 1). Víi mäi > 0, ta §iÒu kiÖn ®ñ: 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 − λ)α + λβ ] < (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. f : Rn → R ∪ {+∞} ( kh«ng nhÊt thiÕt låi ). Hµm §Þnh nghÜa 1.2.6. 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 2 f (λx + (1 − λ)y ) < λf (x) + (1 − λ)f (y ) − ηλ(1 − λ) x−y . 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è η. Mét hµm f ®îc gäi lµ chÝnh thêng nÕu dom f = ∅ vµ §Þnh nghÜa 1.2.7. f (x) > −∞ víi mäi x. f ®îc gäi lµ ®ãng nÕu epi f lµ mét tËp ®ãng trong Rn+1 . Hµm Chó ý 1.2.8. a) Tõ ®Þnh nghÜa cña epi f , ta thÊy r»ng mét hµm låi hoµn toµn ®îc x¸c ®Þnh nÕu biÕt epi f. b) NÕu 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 f (x) nÕu x ∈ C fe (x) = nÕu +∞ x ∈ C. = f (x) víi ∀x ∈ C vµ fe låi trªn Rn . H¬n n÷a fe lµ chÝnh HiÓn nhiªn fe (x) thêng khi chØ khi 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 c) NÕu 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. Mét sè hµm låi VÝ dô 1.2.9. f (x) = a, x + α, trong ®ã a ∈ Rn , α ∈ R. DÔ 1. Hµm a-phin: dµng kiÓm tra ®îc r»ng f lµ hµm võa låi võa lâm trªn toµn kh«ng gian. Khi α = 0, th× hµm nµy ®îc gäi lµ hµm tuyÕn tÝnh. Cho C = ∅ lµ mét tËp låi. 2. Hµm chØ: §Æt nÕu x ∈ C, 0 δC (x) = +∞ nÕu x ∈ 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. S = {x ∈ Rn | 3. Hµm mÆt cÇu: Cho x = 1} lµ mét mÆt cÇu vµ h : S → R+ lµ mét hµm bÊt kú.  nÕu 0 x < 1,  f (x) = h(x) nÕu x = 1,  +∞ nÕu x > 1.  f lµ mét hµm låi trªn Rn , hµm nµy ®ùoc gäi lµ hµm mÆt cÇu. DÔ thÊy r»ng mÆc dï 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) = min x − y . y ∈C x = (x1 , . . . , xn ). 6. Hµm chuÈn: Gi¶ sö f (x) = x = max| xi | i hoÆc 1 f (x) = x = (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. Cho C = ∅ (kh«ng nhÊt thiÕt låi) vµ y lµ mét vÐc-t¬ bÊt §Þnh nghÜa 2.1.1. kú, ®Æt dC (y ) = inf x − y . 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 ) = π − y th× ta nãi π lµ h×nh chiÕu cña y trªn C . Ta ký hiÖu h×nh chiÕu cña y trªn C lµ pC (y ). vu«ng gãc Th«ng thêng sÏ 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. Chó ý r»ng, nÕu y ∈ C th× dC (y ) = 0. NÕu C = ∅ th× dC (y ) h÷u h¹n v× víi mäi 0 ≤ dC (y ) ≤ y − x 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