Luận văn Tính Lipschitz của ánh xạ đa trị đa diện

y P x x y x x x x y x x Î - - = - - = Î Ï Î - - = - - - = -   Vì x BÏ nên 1 1, suy ra 0 x x x - > > và y BÎ nên 1, suy ra , hay , 0.y x y x y x x y x£ £ £ - £ Vậy ( ) ( ), 0, .x P x y P x y B- - £ Î □ 14 Ví dụ 1.2.3. Cho { } \ 0 , ,nn Ra R RaÎ Î phép chiếu lên nửa không gian đóng { }: , :nH x R x a a= Î £ ( ) 2 : khi , khi . nP R H x x H x ax P x x a x H a a ® ì Îïïïï -=í - Ïïïïïî  Hình 1.7. Ta có 22 2 , , , , x a x a x a a x a a a a a a a - - - = - = nên ( ) , .nP x H x RÎ Î Ta kiểm tra đây là phép chiếu lên H: ( ) ( ) ( ) ( ) ( ) 2 2 2 2 2 2 : , , 0, . : : , , , , , , , , , , 0 , . x H x P x y P x x x y x y H x H y H x a x a x P x y P x x x a y x a a a x a x a a y x a a a x a x a a y a y a a a a a a a a a a Î - - = - - = Î Ï Î æ ö æ ö- -÷ ÷ç ç÷ ÷ç ç- - = - - - -÷ ÷ç ç÷ ÷ç ç÷ ÷ç çè ø è ø æ ö- - ÷ç ÷ç= - - ÷ç ÷ç ÷çè ø - - = - £ £   15 Vậy ( ) ( ), 0, .x P x y P x y H- - £ Î □ Mệnh đề 1.2.3. Cho nS R⊂ là tập lồi, đóng, khác rỗng và .s S∈ Khi đó, ta có: ( ) { } ( )1S SP s s N s− = + Chứng minh Ta cần chứng minh ( ) ( ) ( ).S SP x s x s N s= ⇔ − ∈ Theo định nghĩa nón pháp tuyến, vectơ v thuộc ( )SN s khi và chỉ khi ( ) { }, : .n T TS H s v y R v y v s⊂ = ∈ ≤ Tức là ta chứng minh với mỗi ,nx R∈ đẳng thức ( )SP x s= đúng khi và chỉ khi ( ), .S H s x s⊂ − Ta có ( ) [ ] ( ) ( ) ( ) ( ) , ' ' ' ' , . S s s T T P x s P x s s S x s s x s s s S S H s x s = ⇔ = ∀ ∈ ⇔ − ≤ − ∀ ∈ ⇔ ⊂ − □. Mệnh đề 1.2.4. Cho { }: ,nS x R Ax b= ∈ = với m nA M ×∈ với rank A m= và .mb R∈ Khi đó ( ) ( )( ) ( )( )1 1 .T T T TSP z I A AA A z A AA b− −= − + Chứng minh Theo mệnh đề 1.2.3., với mỗi ,nz R∈ ( ) { } ( ) ,S Sx P z z x N x= ⇔ ∈ + ta có ( ) { }: .T mSN x A y y R= ∈ Vì vậy, phép chiếu ( )SP z có thể định bởi nghiệm của phương trình: ( ) , 0 T SP zz I A b A y     =          Mặt khác: 16 ( ) ( ) ( ) ( ) 1 11 1 1 . 0 T T T TT T T I A AA A A AAI A A AA A AA − −− − −  −   =      −  Ta suy ra ( ) ( )( ) ( )( )1 1 .T T T TSP z I A AA A z A AA b− −= − + □ Tính chất trên chỉ ra rằng phép chiếu lên không gian con affine là một hàm affine. Ta sẽ chứng minh phép chiếu lên tập lồi đa diện là ánh xạ affine từng khúc ở chương 3. 1.3. Ánh xạ đa trị và các tính chất liên tục Định nghĩa 1.3.1. Cho ,X Y là các tập khác rỗng, ánh xạ : 2YF X → ( 2Y là họ tất cả các tập con củaY ) được gọi là ánh xạ đa trị từ X vào ,Y kí hiệu là : .F X Y Ví dụ 1.3.1. Xét phương trình đa thức ( )11 1... 0, , 1,..., .n n n n ix a x a x a n N a R i n− −+ + + + = ∈ ∈ = Quy tắc cho tương ứng mỗi vectơ ( )1,..., nna a a R= ∈ với tập nghiệm, kí hiệu ( ) ,F a của phương trình trên là một ánh xạ đa trị từ nR vào C. Nhận xét 1.3.1. Ánh xạ đơn trị được xem là ánh xạ đa trị đặc biệt với ảnh của mỗi điểm là tập chỉ có một phần tử. Định nghĩa 1.3.2. Cho : ,F X Y ta định nghĩa đồ thị gph ,F miền hữu hiệu dom F và miền ảnh rge F của ánh xạ đa trị F như sau: ( ) ( ){ }gph , : ,F x y X Y y F x= ∈ × ∈ ( ){ }dom : ,F x X F x= ∈ ≠∅ và ( ){ }rge : sao cho .F y Y x X y F x= ∈ ∃ ∈ ∈ Định nghĩa 1.3.3. Cho : ,F X Y ánh xạ ngược 1 :F Y X−  của ánh xạ đa trị F được xác định bởi công thức: ( ) ( ){ } ( )1 : .F y x X y F x y Y− = ∈ ∈ ∈ 17 Ví dụ 1.3.2. Ánh xạ { }, khi 0 khi 0 ( ) x x x x F x − ≥  ∅ < = là ánh xạ đa trị từ R vào .R Ta có ( ){ }2 :gph , ,y xF x y R == ∈ dom ,F R+= rge .F R= Ánh xạ ngược 1 :F R R−  xác định bởi ( ) { } ( )1 : .x yF y x R y R− == ∈ ∈ Tiếp theo, ta sẽ trình bày các khái niệm liên tục của ánh xạ đa trị. Cho ,X Y là các không gian topo, : ,F X Y Định nghĩa 1.3.4. F gọi là nửa liên tục trên tại dom x FÎ nếu với mọi lân cận V trong Y sao cho ( ) ,F x VÌ tồn tại một lân cận U của x sao cho ( ) ( ): . x U F U F x V Î = Ì F gọi là nửa liên tục trên nếu F nửa liên tục trên tại mọi dom .x FÎ Định nghĩa 1.3.5. F gọi là nửa liên tục dưới tại dom x FÎ nếu với mọi lân cận V trong Y sao cho ( ) ,F x V ¹Æ tồn tại một lân cận U của x sao cho ( ) , dom .F x V x U F¹Æ Î  F gọi là nửa liên tục dưới nếu F nửa liên tục trên tại mọi dom .x FÎ Định nghĩa 1.3.6. F gọi là liên tục tại dom x FÎ nếu F vừa nửa liên tục trên vừa nửa liên tục dưới tại điểm đó. Nếu F liên tục tại mọi điểm thuộc dom F thì F được gọi là liên tục trên X. Ví dụ 1.3.3. Ánh xạ đa trị ( ) { } [ ] { } 0 0 1,1 0 1 0 khi x F x khi x khi x <  = − =  > từ R vào R là nửa liên tục trên nhưng không nửa liên tục dưới tại 0.x = 18 Hình 1.8. Ví dụ 1.3.4. Ánh xạ đa trị ( ) [ ] { } 0,1 0 0 0 khi x F x khi x  ≠=  = từ R vào R là nửa liên tục dưới nhưng không nửa liên tục trên tại 0.x = Hình 1.9. Nhận xét 1.3.2. (i) F nửa liên tục trên khi và chỉ khi với mọi V mở trong Y thì ( ) ( ){ }: :F V x X F x V- = Î Ì mở trong .X (ii) F nửa liên tục dưới khi và chỉ khi với mọi V mở trong Y thì ( ) ( ){ }1 : :F V x X F x V- = Î ¹Æ mở trong .X Chứng minh: (i) ( )Þ Giả sử F nửa liên tục trên, 19 Lấy ( ) ( ), suy ra .x F V F x V-Î Ì Vì F nửa liên tục trên tại x nên tồn tại một lân cận mở U của x sao cho ( ) , .F x V x UÌ Î Suy ra ( ) ( ), hay .F x V x U U F V-¹Æ Î Ì Vậy ( )F V- mở. ( )Ü Lấy , x X VÎ là mở bất kì trong Y và ( ) .F x VÌ Ta có ( ) ( ){ }:F V x X F x V- = Î Ì mở. Mặt khác, ( )x F V-Î nên tồn tại một lân cận U của x sao cho ( ) ( ) hay , .U F V F x V x U-Ì Ì Î Vậy F nửa liên tục trên tại x bất kì. Do đó, F nửa liên tục trên. □ (ii) Chứng minh tương tự (i). □ Định nghĩa 1.3.7. F là Lipschitz trên dom D F⊂ nếu tồn tại 0a > sao cho: ( ) ( ) YF y F z y z Ba⊂ + − với mọi , .y z D∈ ( YB là quả cầu đơn vị đóng trong Y.) Nếu dom ,D F= ta nói F là ánh xạ Lipschitz. Định nghĩa 1.3.8. F là Lipschitz trên địa phương tại dom Fx∈ nếu tồn tại 0a > và một lân cận U của x sao cho: ( ) ( ) YF x F x x x Ba⊂ + − với mọi .x U∈ Định nghĩa 1.3.9. F là Lipschitz dưới địa phương tại dom Fx∈ nếu tồn tại 0a > và một lân cận U của x sao cho: ( ) ( ) YF x F x x x Ba⊂ + − với mọi dom .x U F∈  Tiếp theo, ta xét các tính chất tương đương với tính Lipschitz. Định nghĩa 1.3.10. Cho hai tập hợp , trong .nC D R Ta nói khoảng cách excess từ C đến D là ( ) ( ), sup , x C C D d x De ∈ = 20 ( ) 0 , khi D e D khi D =∅ ∅ = ∞ ≠ ∅ và khoảng cách Hausdoff từ C đến D là ( ) ( ) ( ){ }, max , , , .C D e C D e D Ch = Ta dễ dàng nhận thấy ( ) ( ), ,C D h D Ch = nhưng ( ),e D C có thể khác ( ), .e C D Hơn nữa, ta kiểm tra được ( ) { }, inf 0 :e C D C D Bτ τ= ≥ ⊂ + và ( ) { }, inf 0 : , .C D C D B D C Bh τ τ τ= ≥ ⊂ + ⊂ + Ví dụ 1.3.5. Ta xem một minh họa khoảng cách excess và khoảng cách Hausdoff giữa hai tập C và D qua hình sau. Hình 1.9. Từ định nghĩa trên, ta suy ra trực tiếp các tính chất sau. Mệnh đề 1.3.1. F Lipschitz trên địa phương tại x khi và chỉ khi tồn tại 0a > và một lân cận U của x sao cho: ( ) ( )( ), , dom .e F x F x x x x U Fa£ - Î  21 F Lipschitz dưới địa phương tại x khi và chỉ khi tồn tại 0a > và một lân cận U của x sao cho: ( ) ( )( ), , dom .e F x F x x x x U Fa£ - Î  F Lipschitz trên dom D F⊂ khi và chỉ khi tồn tại 0a > sao cho ( ) ( )( ), , , .F y F z y z y z Dh a≤ − ∀ ∈ Nhận xét 1.3.3. Nhờ vào mệnh đề trên, ta thấy rằng nếu với mọi x, ( )F x là tập chỉ gồm một phần tử, tức F là ánh xạ đơn trị thì các khái niệm Lipschitz của ánh xạ đa trị trùng với tính liên tục Lipschitz của ánh xạ đơn trị mà ta đã biết. Mối quan hệ giữa tính liên tục và tính Lipschitz của ánh xạ đa trị thể hiện qua mệnh đề sau. Mệnh đề 1.3.2. Cho : ,F X Y dom .x F∈ i) F Lipschitz trên địa phương tại x và ( )F x đóng thì F nửa liên tục trên tại .x ii) F Lipschitz dưới địa phương tại x thì F nửa liên tục dưới tại .x Chứng minh i) Giả sử F không nửa liên tục trên tại ,x tức là tồn tại tập V Y⊂ mở sao cho ( )F x V⊂ và với mọi lân cận U của x luôn tồn tại ( ): .x U F x V∈ ⊄ Do đó, ta xây dựng được dãy { } , n nx X x x⊂ → và ( ) , .nF x V n⊄ ∀ Suy ra tồn tại ( ) : , .n n ny F x y V n∈ ∉ ∀ Mặt khác, F Lipschitz trên địa phương tại x nên tồn tại 0a > sao cho: ( ) ( )( ) ( )( ) ( )( ) , , , , lim , 0. n n n n n e F x F x x x n d y F x x x n d y F x a a ≤ − ∀ ⇒ ≤ − ∀ ⇒ = Vì ( )F x đóng và V mở, ( )V F x⊃ nên ny V∈ khi n đủ lớn. Điều này mâu thuẫn với tính chất của dãy{ }.ny Vậy F nửa liên tục trên tại .x 22 ii) Giả sử F không nửa liên tục dưới tại ,x tức là tồn tại tập mở ( ):V Y F x V⊂ ≠∅ và với mọi lân cận U của x sẽ tồn tại ( )dom : .x U F F x V∈ =∅  Ta xây dựng được dãy { } ( ), , .n n nx X x x F x V⊂ → =∅ Mặt khác, F Lipschitz dưới địa phương tại x nên tồn tại 0a > sao cho: ( ) ( )n nF x F x x x Ba⊂ + − khi n đủ lớn. Do đó, với mỗi ( ) ,y F x V∈  tồn tại ( ) :n ny F x∈ n ny y x x B∈ + − khi n đủ lớn. Suy ra .ny y→ Ta lại có V mở nên { } \ny X V⊂ đóng, do đó \ .y X V∈ Điều này vô lý. Vậy F nửa liên tục dưới tại .x □ 23 Chương 2. Các tính chất Lipschitz của ánh xạ đa trị đa diện Chương này trình bày lại về ánh xạ đa trị đa diện, một lớp ánh xạ đa trị đặc biệt. Đầu tiên khảo sát các tính chất cơ bản của nó, sau đó đi sâu vào tìm hiểu các tính chất Lipschitz, làm rõ tính mở của ánh xạ đa trị đa diện với tính Lipschitz dưới địa phương của ánh xạ ngược. Chương này được viết dựa trên các tài liệu [1], [3], [4], [6], [7], [9], [13]. 2.1. Ánh xạ đa trị đa diện Định nghĩa 2.1.1. Ánh xạ đa trị : n mF R R được gọi là ánh xạ đa trị đa diện nếu đồ thị của F là hợp của hữu hạn các tập lồi đa diện, nghĩa là, 1 gph k i i F G = = G với iG là các tập lồi đa diện. Ánh xạ đa trị có đồ thị chỉ gồm một tập lồi đa diện được gọi là ánh xạ đa trị đa diện lồi. Đây là một lớp ánh xạ đa trị đa diện đặc biệt. Ví dụ 2.1.1. Ánh xạ :F R R cho bởi công thức ( ) [ ] [ ] [ ] khi 2 0,1 khi 2 1 0,2 khi 1 2 0, 1 khi 2 x x F x x x x ∅ < −  − ≤ < −=  − ≤ <  + ≥ là một ví dụ đơn giản của ánh xạ đa trị đa diện. Hình 2.1. 24 Ví dụ 2.1.2. Ánh xạ :F R R cho bởi công thức ( ) khi 0 khi 0 x F x R x ∅ < =  ≥ là một ví dụ đơn giản của ánh xạ đa trị đa diện lồi. Hình 2.2. Ta xét một số tính chất cơ bản của ánh xạ đa trị đa diện. Mệnh đề 2.1.1. Các tính chất cơ bản của ánh xạ đa trị đa diện. (i) F(x) đóng với mọi x thuộc dom F. Thật vậy, với mỗi x thuộc dom F, xét dãy { } ( ) , .n ny F x y y⊂ → Ta có ( ), gph ,nx y F n∈ ∀ và ( ) ( ), , ;nx y x y→ gph F là hợp hữu hạn các tập lồi đa diện nên đóng. Do vậy ( ) ( ), gph hay .x y F y F x∈ ∈ Vậy ( )F x đóng. □ 25 (ii) Ánh xạ ngược của ánh xạ đa trị đa diện là ánh xạ đa trị đa diện. Thật vậy, giả sử : n mF R R là ánh xạ đa trị đa diện thì ( ) ( ){ } 1 gph , : k n m i i F x y R R y F x G = = ∈ × ∈ = G với , 1,iG i k= là các tập lồi đa diện. Ánh xạ ngược 1 : m nF R R−  định bởi công thức ( ) ( ){ }1 :nF y x R y F x− = ∈ ∈ và có đồ thị là ( ) ( ){ }1gph , : .m nF y x R R y F x− = ∈ × ∈ Xét : n m m nR R R Rϕ × → × định bởi ( ) ( ) ( ), , , , n mx y y x x y R Rϕ = ∀ ∈ × thì ϕ là ánh xạ tuyến tính. Ta có ( ) ( )1 1 1 gph gph k k i i i i F F G Gϕ ϕ ϕ− = =  = = =    G G với ( ) ( ) 1,iG i kϕ = là các tập lồi đa diện. Ta đã chứng minh được 1F − là ánh xạ đa trị đa diện. □ (iii) Gọi 1 2,∏ ∏ lần lượt là phép chiếu chính tắc từ n mR R× lên , . n mR R Ta có: ( )1 1 dom k i i F G = = ∏G và ( )2 1 1 rge , k l i i i i F G V = = = ∏ =G G với iV là các tập lồi đa diện trong .mR 2.2. Tính Lipschitz của ánh xạ đa trị đa diện Theo Walkup và Wets trong [13], ta có kết quả sau. Định lý 2.2.1. Cho W là tập lồi đa diện trong nR và : n mh R R® là hàm affine. Khi đó, ánh xạ ( )1y h y-W  từ ( )h W vào nR là ánh xạ Lipschitz. Lớp các ánh xạ đa trị đa diện có một số tính chất đặc biệt mà không phải bất kì ánh xạ đa trị nào cũng có, chẳng hạn như tính Lipschitz trên. Sau đây là kết quả của Robinson trong [7]. Định lý 2.2.2. Cho : n mF R R là ánh xạ đa trị đa diện. Khi đó, F Lipschitz trên địa phương tại mỗi 0 dom .x FÎ Để chứng minh định lý này, trước hết, ta xét bổ đề sau. 26 Bổ đề 2.2.1. Cho : n mP R R là ánh xạ đa trị đa diện khác rỗng với 1 gph , k i i F G = = G ( ) 1iG i k£ £ là các tập lồi đa diện. Lấy 0 dom .x FÎ đặt ( ){ }0 1: .iI i x G= ÎÕ Khi đó tồn tại một lân cận U của 0x sao cho ( ) gph .m i i I U R P G Î ´ Ì  Chứng minh Với mỗi i , { }0 mx R´ và iG là các tập lồi đa diện khác rỗng trong .n mR R´ Nếu i IÏ thì ( )0 1 ix GÏÕ suy ra ( )0 .m ix R G´ ¹Æ Do đó, ( )0 mx R´ và iG bị tách ngặt. Vì vậy có một lân cận iU của 0x sao cho ( ) .mi iU R G´ ¹Æ Đặt i i I U U Ï =  (các iU hữu hạn) thì U là một lân cận của 0x và ( ) 1 gph . k m i i i i i I i I U R P G G G = Ï Î æ ö æ ö÷ ÷ç ç´ Ì Ì÷ ÷ç ç ÷÷ç è øè ø   R □ Chứng minh định lý: Nếu gph F =Æ suy ra dom ,F =Æ định lý hiển nhiên đúng. Nếu gph ,F ¹Æ đặt 1 gph , k i i F G = = G ( ) 1iG i k£ £ là các tập lồi đa diện. Với mỗi i, đặt : ni mF R R xác định bởi: ( ) ( ){ } ( )( )12 1: ,i i iF w z w z G G w-= Ì =Õ Õ Theo định lý 2.2.1., ( )11iG w-Õ là Lipschitz và 2Õ là ánh xạ không giãn nên iF Lipschitz trong không gian 2.T Vì vậy tồn tại 0ia > sao cho nếu ( ) ( )1 0i iF w F w¹Æ¹ thì ( ) ( )1 0 1 0 .i i iF w F w w w BaÌ + - Đặt 1, max ii ka a== và chọn 0 dom x FÎ bất kì, đặt ( ){ }0 1: .iI i x G= ÎÕ Theo bổ đề 1, tồn tại một lân cận U của 0x sao cho ( ) gph .m i i I U R F G Î ´ Ì  Lấy x UÎ bất kì, ta cần chứng minh ( ) ( )0 0 .F x F x x x Ba⊂ + − Nếu dom x FÏ suy ra ( ) ,F x =Æ bao hàm thức trên hiển nhiên đúng. 27 Nếu dom x FÎ , lấy y là điểm bất kì thuộc ( ),F x ta có ( ) ( ), gph m ix y U R F GÎ ´ Ì với i nào đó thuộc .I Ta biết ( ) ( )0,i iF x F x đều khác rỗng vì 0, dom .x x FÎ Do đó, ( ) ( ) ( )0 0 0 0 ,i i i x x x By F x F x x x B F aa + −∈ ⊂ + − ⊂ vì ( ) ( )0 0 .i i I F x F x Î =  Do y bất kì nên ( ) ( )0 0 .x x x BF x F a+ −⊂ Vậy F Lipschitz trên địa phương tại mỗi dom .x FÎ □ Gowda và Sznajder đã tìm ra mối liên hệ giữa tính mở của ánh xạ đa trị với tính Lipschitz của ánh xạ ngược của nó trong [4]. Bổ đề 2.2.2. Cho : n mF R R là ánh xạ đa trị đa diện với rge F là tập lồi. Cho ( )1 1 dom L i i F G = = ∏G và 1 rge , T j j F V = = G với iG là các tập lồi đa diện trong , m nR R´ jV là các tập lồi đa diện trong .mR Khi đó tồn tại 0g> sao cho với mỗi ( )1*, * rge , * * ,p q F x F p-Î Î có một phân hoạch { }0 1* , ,..., *lp p p p q= = của đoạn thẳng [ ]*, *p q và tập hợp { }0 1* , ,..., lx x x x= thỏa mãn: (i) 0 ,l T£ £ (ii) ( )1 ,0 ,j jx F p j l-Î £ £ (iii) Với mỗi { } ( ) ( ){ }1 10,1,.., 1 , , , ,j j j jj l x p x p+ +Î - chứa trong iG nào đó, (iv) 1 1 ,0 1.j j j jx x p p j lg+ +- £ - £ £ - Chứng minh Trước tiên, ta mô tả .g Với mỗi ,j theo định lý 1, ánh xạ ( )12iy G y-Õ  là Lipschitz. Vì ánh xạ 2Õ không giãn nên ánh xạ ( )( )11 2iy G y-Õ Õ  là Lipschitz. Gọi ig là hệ số Lipschitz của ánh xạ này. Đặt 1, : max ,ii Lg g== kí hiệu dom , rge .X F Y F= = 28 Nếu * *:p q= bổ đề hiển nhiên đúng. Nếu * *,p q¹ đặt 0 0 0: *, : *,x x p p A= = là họ các iG chứa ( )0 0, .x p Do có hữu hạn iG và iG đóng với mọi i nên tồn tại tập mở U V´ trong n mR R´ sao cho ( ) ( ) 0 0 0, gph . i i G A x p U V F G Î Î ´ Ì  (Thật vậy, ta có 0i i G A G Ï  đóng, suy ra ( ) 0i i G A n m GR R Ï ´ R mở chứa ( )0 0,x p nên tồn tại tập mở U V´ chứa ( )0 0,x p và ( ) 0i i G A U V G Ï æ ö÷ç´ =Æ÷ç ÷çè ø  hay( ) ( ) 0 0 0, gph i i G A x p U V F G Î Î ´ Ì  ). Suy ra ( )( ) ( ) 0 0 2 2gph . i i G A p U V F G Î ÎÕ ´ Ì Õ  Vì F là ánh xạ mở nên ( )( ) ( )2 gph U V F V F U XÕ ´ = ´  mở trong Y và ( )( ) { }2 gph , 1, 2,..., .j j J U V F V J T Î Õ ´ Ì Ì  Mặt khác, Y lồi, 0 , *p q Yé ù Ìê úë û nên đoạn thẳng mở ( )0 , * jp q V ¹Æ với .j JÎ Đặt 0t là số thực [ ]0,1t Î lớn nhất thỏa mãn tính chất ( )0 0, 1 * jp t p tq Vé ù- + Ìê úë û với j JÎ ( ( )2j iV G=Õ với 0iG AÎ ), thì 0 0t > và vì các jV lồi, đóng nên có 0 : , jV V j J= Î chứa ( )0 00 0, 1 * .p t p t qé ù- +ê úë û Khi đó, có 0 0G AÎ nào đó để ( )00 2 .V G=Õ ( ) ( )1 0 00 0 2: 1 * ,p t p t q G= - + ÎÕ vì vậy ( )0 1 12 .G p-Õ ¹Æ Ta có ( )( )0 1 00 1 2x G p-ÎÕ Õ và ( )( ) ( )( )0 1 0 0 1 1 1 01 2 1 2G p G p p p Bg- -Õ Õ ÌÕ Õ + -  nên tồn tại ( )( )0 1 11 1 2x G p-ÎÕ Õ sao cho 0 1 0 1 .x x p pg- £ - Ta có ( )1 1 0,x p GÎ và vì vậy ( )1 1 .p F xÎ (Dĩ nhiên, ( )0 0 0, .x p GÎ ) Nếu 1 *,p q= ta có (i) – (iv). Nếu 1 *,p q¹ bắt đầu với 1 1, ,x p lặp lại quá trình trên, ta tìm được các 1 1, , , , , , 1, 2,...j j jj j jA t V G p x j+ + = Ta có ( ) ( ) ( ){ }1 1 1, , , ,j j j j j j jx F p x p x p G- + +Î Ì và 1 1 , 1, 2,...j j j jx x p p jg+ +- £ - = Quá trình này chỉ lặp lại hữu hạn bước. Thật vậy, ở mỗi bước 0jt > xác định tương 29 ứng xác định một jV khác với các ( )0 1 .iV i j£ £ - Do đó chỉ có thể có nhiều nhất T bước. Bổ đề được chứng minh xong. □ Định lý 2.2.3. Cho : n mF R R là ánh xạ đa trị đa diện với rge F là tập lồi. Khi đó, các phát biểu sau tương đương: (a) 1F- Lipschitz dưới địa phương tại mỗi điểm thuộc rge ,F (b) F là ánh xạ mở từ dom F vào rge ,F (c) 1F- Lipschitz trên rge .F Chứng minh ( ) ( ):a bÞ Lấy U là tập mở trong nR và ( )* ;y F UÎ chọn ( )* sao cho * * .x U y F xÎ Î Giả sử không có lân cận nào của *y (với topo cảm sinh trong rge F ) chứa trong ( ).F U Khi đó tồn tại dãy { } ( ) trong rge sao cho k ky F y F UÏ và * khi .ky y k® ®¥ Vì 1F- Lipschitz dưới địa phương tại *y nên với k đủ lớn, ta có thể tìm được ( )1k kx F y-Î tồn tại * 0a > thỏa mãn * * * .kx x y ya- £ - Do đó, *kx x® và kx UÎ với k đủ lớn. Do đó, ( ) ( )k ky F x F UÎ Ì với k đủ lớn. Điều này mâu thuẫn với cách xây dựng dãy { }.ky Vậy F là ánh xạ mở từ dom F vào rge .F ( ) ( ):b cÞ Giả sử F mở, chọn 0g> như trong bổ đề 2. Ta sẽ chứng minh, với *, * rge p q FÎ bất kì, thì: ( ) ( )1 1* * * * .F p F q p q Bg- -Ì + - Thật vậy, lấy ( )1* * ,x F p-Î áp dụng bổ đề 2, tồn tại 0g> sao cho với mỗi ( )1*, * rge , * * ,p q F x F p-Î Î có một phân hoạch { }0 1* , ,..., *lp p p p q= = của đoạn thẳng [ ]*, *p q và tập hợp { }0 1* , ,..., lx x x x= thỏa mãn các tính chất từ (i) đến (iv). Ta đặt *: ly x= thì ( )1* *y F q-Î và 1 1 1 1 0 0 * * * * l l j j j j j j x y x x p p p qg g - - + + = = - £ - £ - = -å å 30 Do *x bất kì nên ( ) ( )1 1* * * * .F p F q p q Bg- -Ì + - ( ) ( ):c aÞ Hiển nhiên.□ Nhận xét 2.2.1. Robinson đã chứng minh kết quả tổng quát hơn cho định lý trên trong [9] như sau. Cho : n mF R R có giá trị đóng (F(x) đóng với mọi x thuộc dom F) và dom F lồi. Khi đó, các phát biểu sau tương đương: (a) Tại mỗi điểm x thuộc dom F, F liên tục Lipschitz trên địa phương và nửa liên tục dưới. (b) F Lipschitz. Chứng minh Giả sử dom F khác rỗng. ( ) ( ) :a b⇒ Lấy 0 1, dom .x x F∈ Với mỗi ( )0,1 ,t∈ đặt ( ) 0 11tx t x tx= − + . Vì F liên tục Lipschitz trên địa phương tại mọi x nên với mỗi [ ]0,1 ,t∈ tồn tại quả cầu ( ) ( ), , 0t t tB x ρ ρ > sao cho ( ) ( ) ( )' , , ' ' .t t t tx X B x F x F x x x Bρ l∀ ∈ ∩ ⊂ + − Đặt [ ] [ ] ( ) ( ){ }0 0sup 0,1 : 0,1 , .s st s F x F x x x Bτ l= ∈ ∀ ∈ ⊂ + − Ta có 0τ > vì 0 0.ρ > Đầu tiên, ta chứng minh ( ) ( ) ( )0 0 . *F x F x x x Bτ τl⊂ + − Vì ( )0F x là tập đóng nên ( )0 0F x x x Bτl+ − đóng. Đặt Q là phần bù của tập ( )0 0F x x x Bτl+ − thì Q mở. Nếu ( )* không đúng thì ( )F x Qτ ≠ ∅ . Từ tính nửa liên tục dưới của F ta suy ra tồn tại của số [ )0,σ τ∈ thỏa mãn ( )0 .F x Q ≠ ∅ Điều này vô lý vì tất cả các σ luôn thỏa mãn điều kiện: ( ) ( ) ( )0 0 0 0 .F x F x x x B F x x x Bσ σ τl l⊂ + − ⊂ + − 31 Vậy ( )* đúng. Nếu 1τ < , tồn tại ( ),1κ τ∈ với x xκ τ τρ− < sao cho ( ) ( ) ( )0 0 . **F x F x x x Bκ κl⊄ + − Mặt khác, từ ( )* và định nghĩa τρ ta có ( ) ( ) ( ) ( ) ( ) 0 0 0 0 = F x F x x x B F x x x x x B F x x x B κ τ κ τ κ τ τ κ l l l ⊂ + − ⊂ + − − − + − vì 0 , ,x x xτ κ cộng tuyến. Điều này mâu thuẫn với ( )** , do đó 1.τ = Từ ( )* suy ra ( ) ( )1 0 1 0 .F x F x x x Bl⊂ + − ( ) ( ) :b a⇒ F Lipschitz nên F Lipschitz trên địa phương. Lấy dom x F∈ và Q là tập mở có giao khác rỗng với ( ),F x tồn tại ( )y F x Q∈  và quả cầu ( ) ( ), , 0B y η η > sao cho ( ), .B y Qη ⊂ Lấy 0 : ,ν lν η> ≤ đặt ( )dom , .V F B x ν=  Nếu ' ,x V∈ từ ( )b suy ra ( ) ( ) ( )' ' ' .y F x F x x x B F x Bl η∈ ⊂ + − ⊂ + Tức là có ( )' 'y F x∈ với ' ,y y η− < để ( )' ,y B y η∈ và vì vậy ( )' ' .y F x Q∈  Vậy ( )' .F x Q ≠ ∅ Do đó F nửa liên tục dưới tại x. Với 1G F-= định lý trên dẫn tới kết quả sau: Định lý 2.2.4. Giả sử : n mG R R là ánh xạ đa trị đa diện với dom G là tập lồi. Khi đó, G liên tục nếu và chỉ nếu G là ánh xạ Lipschitz. 32 Chương 3. Tính Lipschitz của ánh xạ affine từng khúc và ứng dụng Chương này trình bày về tính Lipschitz của ánh xạ affine từng khúc, một lớp ánh xạ liên quan mật thiết đến ánh xạ đa trị. Sau đó trình bày các ứng dụng của nó vào bài toán bất đẳng thức biến phân affine cũng như bài toán bù tuyến tính. Tài liệu tham khảo chủ yếu của phần này là [4], [8], [11]. 3.1. Tính Lipschitz của ánh xạ affine từng khúc Định nghĩa 3.1.1. Ánh xạ : n mf R R→ liên tục được gọi là ánh xạ affine từng khúc nếu tồn tại bộ ba ( ), ,j j jA aΩ ( )1,...,j K= sao cho mỗi jΩ là tập lồi đa diện có phần trong khác rỗng trong , , n mj m n jR A M a R×∈ ∈ và (a) 1 K n j j R = = ΩG (b) Với mỗi ,i j≠ i jΩ Ω là rỗng hoặc là một mặt chung thực sự của iΩ và .jΩ (c) ( ) j jf x A x a= + trên , 1,..., .j j KΩ = Họ { }: 1,...,j j KΩ = gọi là thứ phân đa diện của nR tương ứng với f. Khi ,m n= ta nói f là coherently oriented nếu tất cả các định thức khác 0 của các ma trận jA có cùng dấu. Định nghĩa khác của ánh xạ affine từng khúc. Ánh xạ : n mf R R→ liên tục được gọi là ánh xạ affine từng khúc nếu tồn tại hữu hạn các ánh xạ affine (gọi là các hàm chọn) ( ): , 1,..., In mif R R i→ = sao cho ( ) ( ) ( ){ }1 ,..., f If x f x x∈ với mọi .nx R∈ 33 Nhận xét 3.1.1. Từ định nghĩa 3.1.1. ta dễ dàng suy ra định nghĩa 3.1.2., bây giờ ta sẽ kiểm tra chiều ngược lại. Cho ánh xạ : n mf R R→ là ánh xạ như trong định nghĩa 3.1.2., ( )1,..., ,mf f f= với jf là các hàm số thành phần của f từ nR vào R. Giả sử các hàm chọn của jf là ( ) , 1,...,Tj ji i jv x i ka+ = với ( ) ( )' ', , khi '.j j j ji i i iv v i ia a≠ ≠ Cho ( )1,..., mπ π π= với , 1,...,i i mπ = là phép hoán vị của tập { }1,..., ,jk ta định nghĩa tập ( ) ( )( ) ( ) ( )( ) ( )1 1: ... ,1 .j j j j j j TT n j j j j k k M x R v x v x j mπ π π ππ a a   = ∈ + ≤ ≤ + ≤ ≤    Ta sẽ chứng minh họ tất cả các tập ( )M π với phần trong khác rỗng là một thứ phân đa diện của nR tương ứng ánh xạ f. Dễ thấy ( )M π là tập lồi đa diện vì ta dễ dàng chuyển nó thành dạng tập nghiệm của hệ hữu hạn các bất phương trình tuyến tính. Vì các hàm chọn của mỗi hàm thành phần jf đôi một phân biệt nên ta có ( ) ( )( ) ( ) ( )( ) ( )1 1int : ... ,1 .j j j j j j TT n j j j j k k M x R v x v x j mπ π π ππ a a   = ∈ + < < + ≤ ≤    Do đó mỗi hàm thành phần đồng nhất trên ( )int M π với chỉ một hàm chọn và vì vậy f đồng nhất với một hàm affine trên ( )M π nếu ( )int .M π ≠ ∅ Ta có họ tất cả các tập ( )M π phủ nR và tính chất phủ này khi ta bỏ các ( )M π có phần trong rỗng. Bây giờ ta sẽ chứng minh hai tập phân biệt ( )M π và ( )M π với ( ) ( )M Mπ π ≠ ∅ sẽ có giao là một mặt thật sự. Ta có thể biểu diễn ( )M π dưới dạng ( ) ( )( ) ( )( ), ', j ' , ', j ': , . 1 ,1 , ' , ' Tn j j j j i i i i i i i i j x R s v v x s M j m i i k i i π π a a π  ∈ − ≤ − + =   ≤ ≤ ≤ ≤ ≠   34 Trong đó ( ) ( ) ( ) ( ) ( ) 1 1 , ', j 1 1 1 khi ' . 1 khi ' j j i i j j i i s i i π π π π π − − − −  <=  − > Khi đó ( ) ( )M Mπ π nhận được bằng cách chuyển các bất phương trình thành các phương trình khi ( ) ( ), ', j , ', ji i i is sπ π= −  trong biểu diễn của ( ).M π Vì vậy ( ) ( )M Mπ π là một mặt của ( ).M π Hơn nữa, ,π π phân biệt nên tồn tại ít nhất một bộ ba ( ), ',i i j sao cho ( ) ( ), ', j , ', ji i i is sπ π= −  và vì ( )int M π ≠ ∅ là nghiệm của hệ bất phương trình ngặt trên, nên ( ) ( )M Mπ π là một mặt thật sự. Ví dụ 3.1.1. Cho các hàm affine từ R vào R: ( ) ( ) ( ) 1 2 3 2 2, 2, 5. f x x f x f x x = + = = − + Khi đó hàm f từ R vào R định bởi ( ) ( ) ( ) ( ){ }1 2 3min , , ,f x f x f x f x x R= ∀ ∈ là hàm affine từng khúc. 35 Hình 3.1. Mệnh đề 3.1.1. Ánh xạ chiếu lên một tập lồi đa diện là ánh xạ affine từng khúc. Chứng minh Trước tiên, ta chứng minh tính chất sau: Cho { }:nP x R Ax b= ∈ ≤ với , ,mm nA M b R×∈ ∈ đặt ( ), , ,I IJ A