Luận văn Thạc sĩ Toán học: Tính Lipschitz của ánh xạ đa trị đa diện

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

Thêm vào BST

Báo xấu

87
lượt xem 11
download

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

Luận văn Thạc sĩ Toán học: Tính Lipschitz của ánh xạ đa trị đa diện bao gồm những nội dung về kiến thức chuẩn bị; các tính chất Lipschitz của ánh xạ đa trị đa diện; tính Lipschitz của ánh xạ affine từng khúc và ứng dụng.

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: Tính Lipschitz của ánh xạ đa trị đa diện

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Đặng Thị Thão TÍNH LIPSCHITZ CỦA ÁNH XẠ ĐA TRỊ ĐA DIỆN LUẬN VĂN THẠC SĨ TOÁN HỌC Thành phố Hồ Chí Minh – 2014
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Đặng Thị Thão TÍNH LIPSCHITZ CỦA ÁNH XẠ ĐA TRỊ ĐA DIỆN Chuyên ngành : Toán Giải tích Mã số : 60 46 01 02 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. TRỊNH CÔNG DIỆU Thành phố Hồ Chí Minh - 2014
Lời cảm ơn Để hoàn thành luận văn này, tôi đã nhận được nhiều giúp đỡ từ những người Thầy, người thân và bạn bè. Tôi xin trân trọng cảm ơn TS. Trịnh Công Diệu, người hướng dẫn khoa học, đã dành nhiều thời gian, công sức và niềm tin để hướng dẫn tôi thực hiện luận văn. Tôi xin gửi lời cảm ơn chân thành đến quý thầy cô đã hết lòng giảng dạy tôi trong suốt khóa học. Tôi xin cảm ơn các thầy cô trong khoa toán - tin học đã tận tình giúp đỡ tôi trong quá trình tìm và nghiên cứu tài liệu. Cảm ơn các bạn về những năm tháng cùng học tập và nghiên cứu, tôi sẽ không quên khoảng thời gian đó. Tôi xin dành lời cảm ơn sau cùng cho những người luôn trong tim tôi, dù họ ở bất kỳ đâu.
Mục lục Lời nói đầu .......................................................................................................................1 Chương 1. Kiến thức chuẩn bị .........................................................................................2 1.1. Tập lồi đa diện và các tính chất ............................................................................2 1.2. Phép chiếu lên một tập lồi, đóng ........................................................................10 1.3. Ánh xạ đa trị và các tính chất liên tục ................................................................16 Chương 2. Các tính chất Lipschitz của ánh xạ đa trị đa diện ........................................23 2.1. Ánh xạ đa trị đa diện...........................................................................................23 2.2. Tính Lipschitz của ánh xạ đa trị đa diện.............................................................25 Chương 3. Tính Lipschitz của ánh xạ affine từng khúc và ứng dụng ...........................32 3.1. Tính Lipschitz của ánh xạ affine từng khúc .......................................................32 3.2. Bài toán bất đẳng thức biến phân affine .............................................................37 Kết luận và kiến nghị .....................................................................................................47 Tài liệu tham khảo .........................................................................................................48
1 Lời nói đầu Vai trò của giải tích đa trị trong vài thập niên gần đây đã được khẳng định thông qua việc công nhận các ứng dụng rộng rãi trong nhiều lĩnh vực như lý thuyết phương trình vi phân, phương trình đạo hàm riêng, bất đẳng thức biến phân và phương trình suy rộng, lý thuyết tối ưu, lý thuyết điều khiển, tối ưu đa mục tiêu, khoa học quản lý và toán kinh tế. Hiện nay, rất nhiều kết quả nghiên cứu về các lĩnh vực nói trên được viết bằng ngôn ngữ giải tích đa trị. Điều này cho thấy sức mạnh của công cụ mới này. Cùng sự phát triển của khoa học kĩ thuật mà nhu cầu nghiên cứu sâu các tính chất của một lớp các ánh xạ đa trị đặc biệt được đặt ra, chẳng hạn như ánh xạ đa trị đa diện. Robinson đã phát hiện ra một tính chất đặc biệt của lớp ánh xạ này, đó là tính Lipschitz địa phương trên. Điều đó đã tạo nền tảng và động lực cho nhiều nghiên cứu sau này về tính Lipschitz của ánh xạ đa trị đa diện và ứng dụng của nó trong nhiều bài toán, đặc biệt là bài toán bất đẳng thức biến phân affine. Mục tiêu của luận văn này là tìm hiểu và trình bày một cách hệ thống về tính Lipschitz của ánh xạ đa trị đa diện và ứng dụng của nó vào bài toán bất đẳng thức biến phân affine, cụ thể là việc xét tính duy nhất nghiệm của bài toán này. Luận văn gồm có ba chương. Chương 1 trình bày các kiến thức chuẩn bị để làm nền tảng cho hai chương sau. Trong đó giới thiệu các khái niệm, tính chất cơ bản của tập lồi đa diện, phép chiếu lên một tập lồi, đóng và ánh xạ đa trị. Chương 2 giới thiệu ánh xạ đa trị đa diện cùng các tính chất cơ bản. Sau đó đi sâu vào trình bày tính Lipschitz của lớp ánh xạ này. Chương 3 trình bày về tính Lipschitz của ánh xạ affine từng khúc và ứng dụng vào bài toán bất đẳng thức biến phân affine.
2 Chương 1. Kiến thức chuẩn bị Chương này trình bày một số kiến thức chuẩn bị liên quan đến tập lồi đa diện, phép chiếu lên tập lồi, đóng và ánh xạ đa trị. Nội dung được tham khảo và trích dẫn chủ yếu ở các tài liệu [1], [2], [5], [10], [12]. Trong toàn bộ chương, nếu không nói gì thêm, ta xét không gian Euclide R n được trang bị tích vô hướng cho bởi: x = ( x1 , x= 2 ,..., xn ) , y ( y1, y2 ,..., yn ) ∈ R n , x, y = x1 y1 + x2 y2 + ... + xn yn và chuẩn sinh bởi tích vô hướng x = x12 + x22 + ... + xn2 . 1.1. Tập lồi đa diện và các tính chất Định nghĩa 1.1.1. Cho S ⊂ R , ta định nghĩa: n m  lin S ∑ li si : m ∈ N , si ∈ S , li ∈ R  , =  i =1   m m  aff S ∑ li si : m ∈ N , si ∈ S , li ∈ R, = = ∑ li 1 , =  i 1 =i 1  m m  = conv S ∑ li si : m ∈ N , si ∈ S , li ∈ R+ , = ∑ li 1 , =  i 1 =i 1  m  = cone S ∑ li si : m ∈ N , si ∈ S , li ∈ R+   i =1  Các tập lin S , aff S , conv S lần lượt gọi là bao tuyến tính, bao affine, bao lồi của tập hợp S và cone S gọi là nón sinh bởi S. Một tập S ⊂ R n được gọi là lồi nếu conv S = S. Đặc biệt, lin S , aff S , conv S là các tập lồi với mọi S. Số chiều của một tập lồi S là số chiều của không gian con affine aff S. Điểm x ∈ S gọi là điểm trong tương đối của S nếu tồn tại số thực ε > 0 sao cho với mọi y ∈ aff S , y − x < ε thì y ∈ S . Tập tất cả các điểm trong tương đối của S kí hiệu là relint S.
3 Định nghĩa 1.1.2. Cho b ∈ R n \ {0} và β ∈ R, các tập =H1 {= n } , H { x ∈ R | x, b ≥ } x ∈ R | x, b ≤ bb 2 n gọi là các nửa không gian đóng cho bởi b và β . Nhận xét 1.1.1. Các nửa không gian đóng là các tập khác rỗng, lồi và đóng. Định nghĩa 1.1.3. Tập P ⊂ R gọi là lồi đa diện nếu P có thể biểu diễn dưới dạng giao của hữu hạn các nửa không gian đóng. m Nhận xét 1.1.2. Vậy P là tập lồi đa diện có thể viết dưới dạng P =  H i , H i là các nửa i =1 không gian đóng hay { P =x ∈ R n | x, bi ≤ bi , i =1, k } trong đó bi ∈ R n và βi ∈ R, i = 1, k . Ví dụ 1.1.1. Tập lồi đa diện bị chặn Tập lồi đa diện không bị chặn Hình 1.1. Định nghĩa 1.1.4. Cho tập lồi, đóng, khác rỗng S, với mỗi x ∈ S, tập N S ( x )= {y ∈ R n : yT x ≥ yT z , ∀z ∈ S } được gọi là nón pháp tuyến của S tại x. Nhận xét 1.1.3. (i) N S ( x ) là nón lồi, đóng.
4 (ii) S , S là hai tập con lồi, đóng trong R n và U là một lân cận của x ∈ R n sao cho S  U = S  U thì N S ( x ) = N S ( x ) . (iii) Nếu S là nón lồi, đóng thì N S ( x ) ⊂ N S ( 0 ) , ∀x ∈ S và N S ( 0 ) = S . n i { (iv) Cho tập lồi đa diện P =x ∈ R | x, b ≤ bi , i =1, k } và x ∈ P. Khi đó, cone {bi : i ∈ {1,..., k } , biT x = NP ( x) = bi } . {x ∈ R n : Ax ≤ b} với A ∈ M m×n có các vectơ Định nghĩa 1.1.5. Cho tập lồi đa diện P = dòng là a1 ,..., am và vectơ b ∈ R m . J ( A, b ) là họ các tập chỉ số I ⊂ {1,..., m} sao cho tồn tại x ∈ R n thỏa mãn aiT x =bi , i ∈ I , aTj x < b j , j ∈ {1,..., m} \ I . Tập hợp có dạng FI ={ x ∈ R n : aiT x =bi , i ∈ I , aTj x ≤ b j , j ∈ {1,..., m} \ I } , I ∈ J ( A, b ) , gọi là mặt khác rỗng của P. Một mặt khác rỗng FI của P gọi là mặt thật sự của P nếu FI ≠ P. Nhận xét 1.1.4. (i) Hai mặt FI , FJ tương ứng với hai tập chỉ số phân biệt I , J ∈ J ( A, b ) thì phân biệt. (ii) Với I ∈ J ( A, b ) , relint FI ={ x ∈ R n : aiT x =bi , i ∈ I , aTj x < b j , j ∈ {1,..., m} \ I } . (iii) Nón pháp tuyến của P tại các điểm trong tương đối của mặt FI được cho bởi thức N I cone {ai : i ∈ I } với N ∅ = {0} như định nghĩa. công = Từ tính chất của nửa không gian đóng, ta có kết quả sau. Mệnh đề 1.1.1. Tập lồi đa diện là tập lồi, đóng. Tuy nhiên, không phải tập lồi, đóng nào cũng là tập lồi đa diện.
5 Ví dụ 1.1.2. Quả cầu đơn vị trong R n ( n ≥ 2 ) là tập lồi, đóng nhưng không là tập lồi đa diện. Định lý 1.1.1. (Định lý Minskowki - Weyl về biểu diễn của tập lồi đa diện) Tập con P ⊂ Rn khác rỗng là tập lồi đa diện. Khi đó, tồn tại v1 , v2 ,..., v p , d1 , d 2 ,..., d q ∈ R n sao cho =P conv {v1 ,..., v p } + cone {d1 ,..., d q }  p q p  = ∑ x ∈ R : x = n λi vi + ∑ µ j d j , λi , µ j ≥ 0, ∑ λi = 1 .  =i 1 =j 1 =i 1  Các vi , i = 1, p gọi là các điểm sinh, các d j , j = 1, q gọi là các phương sinh của P. Các điểm sinh và phương sinh của một tập lồi đa diện không duy nhất.   − x + 2 ≤ 0    Ví dụ 1.1.3. Cho tập lồi đa diện=P ( x, y ) ∈ R 2 : − x − 2 y + 4 ≤ 0    x − y − 4 ≤ 0    Hình 1.2.
6 = Chọn v1 ( 4,= 0 ) , v2 (= 2,1) ; d1 ( 0,1 = ) , d 2 (1,1) thì = P {( x, = y) λλ1 ( 4, 0 ) + 2 ( 2,1) + µ1 ( 0,1) + µ 2 (1,1) , λλ 1 , 2 , µ1 , µ 2 ≥ 0, λλ 1 += 1} { { } 2 = ( x, y ) ∈ R 2 : xy == 4λλλ 1 + 2 2 + µ 2 , λλ 1 , 2 , µ1 , µ 2 ≥ 0, λλ1+ = 1. 2 + µ1 + µ 2 2 Ta có thể dùng phép khử Fourier-Motzkin để chứng minh định lý trên cũng như chuyển đổi từ dạng giao hữu hạn các nửa không gian đóng sang dạng hữu hạn sinh như trong định lý 1.1.1. của bất kì tập lồi đa diện nào nhưng ta không đề cập đến phương pháp này ở đây. Qua định lý 1.1.1., ta thấy rằng ánh xạ affine có thể bảo toàn tính lồi đa diện. Mệnh đề 1.1.2. Ảnh của tập lồi đa diện qua ánh xạ affine là tập lồi đa diện. Chứng minh {Bλ + C µ : λ , µ ≥ 0, ∑ λi = Cho tập P = 1} với B ∈ M n× p , C ∈ M n×q là tập lồi đa diện và f : Rn → Rd x  Mx + t với M ∈ M d ×n , t ∈ R là ánh xạ affine. Đặt T là ma trận cấp ( d × p ) với mỗi cột là vectơ t. d Đặt B :=MB + T , C :=MC. Khi đó f ( P= ) {M ( Bλ + C µ ) + t : λ , µ ≥ 0, ∑ λ= 1}i {Bλ + C µ : λ , µ ≥ 0, ∑ λ = = 1} i là một tập lồi đa diện. □ Hệ quả 1.1.1. Ảnh của tập lồi đa diện qua ánh xạ affine là tập lồi, đóng. Ví dụ 1.1.4. Trong R 2 xét tập X = {( x, y ) ∈ R 2 : x > 0, xy ≥ 1} và ánh xạ tuyến tính A : R2 → R2 cho bởi công thức A ( x, y ) = ( x, 0 ) thì X là tập lồi, đóng nhưng A( X ) = {( x, 0 ) ∈ R 2 : x > 0} không phải là tập đóng.
7 Hình 1.3. Mệnh đề 1.1.3. Tổng của hai tập lồi đa diện là một tập lồi đa diện. Chứng minh Cho conv {v1 ,..., v p } + cone {d1 ,..., d q } , P ' = P= conv {v '1 ,..., v ' p ' } + cone {d '1 ,..., d 'q ' } . Đặt Q : conv {vi + v ' j |1 ≤ i ≤ p,1 ≤ j ≤ p '} + cone {di , d ' j |1 ≤ i ≤ q,1 ≤ j ≤ q '} thì Q là tập lồi đa = diện. Ta sẽ chứng minh P + P ' = Q. Hiển nhiên Q ⊂ P + P '. Ta kiểm tra bao hàm thức ngược lại.  p q   p' q'  Lấy=p :  ∑ λi vi + ∑ µ j d j  +  ∑ λ 'i v 'i + ∑ µ ' j d ' j  ∈ P + P '  =i 1 =j 1   =i 1 =j 1  p p' với λi , µ j , λ 'i , µ ' j ≥ 0, =i 1 =i 1 ∑ λλ i =∑ 'i =1. i vi + ∑ 'i v 'i ∈ conv {vi + v ' j |1 ≤ i ≤ p,1 ≤ j ≤ p '} . Giả sử tất cả p p' Ta cần chứng minh=x: =i 1 =i 1 ∑ λλ các hệ số trong tổng này là dương, ta chọn hệ số nhỏ nhất giữa λλλλ 1 ,..., q , '1 ,..., 'q ' . Không mất tính tổng quát, giả sử đó là λ1.
8 q q' ''1= : '1 − 1 , ''i =: 'i , 2 ≤ i ≤ q ', η11 =: λ1 thì x − η11 ( v1 + v '1=) Đặt λλλλλ ∑ λλ =i 2=i 1 i vi + ∑ ''i v 'i và q q' ∑ λλ i = ∑ ''i . Tiếp tục quá trình trên hữu hạn lần, ta có biễu diễn mới của x là =i 2=i 1 =x ∑ η (v + v ' ) 1≤i ≤ q ij i j với ∑η 1≤i ≤ q ij = 1. Vậy x ∈ conv {vi + v ' j |1 ≤ i ≤ p,1 ≤ j ≤ p '} . Ta suy ra 1≤ j ≤ q ' 1≤ j ≤ q ' điều phải chứng minh. □ Hệ quả 1.1.2. Tổng của hai tập lồi đa diện là một tập lồi, đóng. Tổng của hai tập lồi, đóng chưa chắc đóng. Ví dụ sau sẽ làm rõ điều này. Ví dụ 1.1.5. Trong R2 xét tập X= {( x, y ) ∈ R 2 : x > 0, xy ≥ 1} và tập =Y {( x, y ) ∈ R 2 : x < 0, xy ≤ −1} là hai tập lồi, đóng nhưng tổng X += Y {( x, y ) ∈ R 2 : y > 0} không phải là tập đóng. Hình 1.4. Định lý sau nói về tính tách chặt hai tập lồi đa diện. Mệnh đề 1.1.4. Cho P1 , P2 là các tập lồi đa diện khác rỗng, rời nhau. Khi đó, tồn tại một siêu phẳng tách chặt chúng, nghĩa là, tồn tại a ∈ R n \ {0} , a > 0 sao cho ay > a > az, ∀y ∈ P1 , z ∈ P2 . Chứng minh:
9 P1 , P2 là các tập lồi đa diện nên theo mệnh đề P1 − P2 cũng là tập lồi đa diện, do đó đóng. Hơn nữa P1 − P2 không chứa 0 vì P1 , P2 rời nhau. Do đó tồn tại một siêu phẳng { x : ax = µ} với a ≠ 0, µ > 0 sao cho ax > µ > 0, ∀x ∈ P1 − P2 hay ay > µ + az, ∀y ∈ P1 , z ∈ P2 . Vì vậy inf {ay : y ∈ P1} ≥ sup {az + µ : z ∈ P2 } > sup {az : z ∈ P2 } . Đặt β= sup {az : z ∈ P2 } , γ= inf {ay : y ∈ P1} và α = β + γ thì β < α < γ . 2 Khi đó ay > a > az, ∀y ∈ P1 , z ∈ P2 . Vậy P1 , P2 bị tách chặt bởi siêu phẳng { x : ax = a } . □ Ví dụ sau cho ta thấy tính lồi đa diện đảm bảo cho tính tách chặt. Ví dụ 1.1.6. Ta xét hai tập hợp như sau trong R2 : A = {( x, { ) Î R 2 : x £ 0} , ïì 1 ïü B = í( x, y ) Î R 2 : y ³ , x > 0ý thì dễ thấy A, B là các tập lồi, đóng, tuy nhiên, không có ïîï x ïþï đường thẳng nào tách chặt chúng. Hình 1.5.
10 1.2. Phép chiếu lên một tập lồi, đóng Mệnh đề 1.2.1. Cho tập C ⊂ R n lồi, đóng, khác rỗng và x ∈ R n . Khi đó, tồn tại duy nhất y ∈ C sao cho y − x ≤ u − x , ∀u ∈ C. Chứng minh: Xét bài toán 1  2 min  y − x : y ∈ C  (*) 2  Ta chứng minh (*) có nghiệm duy nhất. 1 Thật vậy, đặt f x (= y) : y−x 2 thì f x liên tục trên C. 2 { y ∈ R n : f x ( y ) ≤ fc ( x )} thì S ≠ ∅ vì x ∈ S . Với c ∈ C , đặt S := Khi đó, ta có thể viết lại bài toán (*) là inf { f x ( y ) : y ∈ C ∩ S } . S compact nên C  S compact, fx liên tục, do đó, theo định lý Weierstrass min { f x ( y ) : y ∈ C ∩ S } tồn tại. Giả sử y1, y2 là hai ngiệm của (*) . Ta có: 1 1 ( y1 − x ) + ( y2 − x ) = ( y1 − x ) + ( y2 − x ) − ( y − x ) − ( y2 − x ) 2 2 2 2 2 2 1 Đặt= y0 1 ( y1 + y2 ) thì y0 ∈ K . Khi đó, 2 f x ( y= 0) 1 2 ( f x ( y1 ) + f x ( y2 ) ) − y2 − y1 1 8 2 ⇒ f x ( y0 ) ≤ ( f x ( y1 ) + f x ( y2 ) ) . 1 2
11 Mặt khác, vì y1, y2 là nghiệm nên f x ( y0 ) ≥ f x ( y1 ) , f x ( y0 ) ≥ f x ( y2 ) hay f x ( y0 ) ≥ 1 ( f ( y ) + f x ( y2 ) ) . 2 x 1 Suy ra f x ( y0 ) =1 ( f x ( y1 ) + f x ( y2 ) ) ⇒ y2 − y1 =0 ⇒ y2 =y1. □ 2 Định nghĩa 1.2.1. Cho tập C ⊂ R n lồi, đóng, khác rỗng và x ∈ R n . Vectơ y ∈ C thỏa mãn y − x ≤ u − x , ∀u ∈ C gọi là hình chiếu của x lên C , kí hiệu: PC ( x ) = y. Cho tập C lồi, đóng, khác rỗng, ta xét các mệnh đề sau. Mệnh đề 1.2.2. Cho x ∈ R , y ∈ C. Khi đó n PC ( x ) = y ⇔ x − y, u − y ≤ 0, ∀u ∈ C. Chứng minh: ( ⇒ ) Giả sử PC ( x ) = y, thì y là nghiệm của bài toán ( *) . Lấy u ∈ C , suy ra y + α ( u − y ) ∈ C với mọi α ∈ ( 0,1) ⇒ f x ( y ) ≤ f x ( y + α (u − y )) 1 y − x + α (u − y ) 2 = 2 1 1 2 = y − x + αα y − x, u − y + u−y 2 2 2 2 1 2 ⇒ 0 ≤ ααy − x, u − y + u−y 2 2 1 ⇒ 0 ≤ y − x, u − y + α u − y . 2 2 Cho α → 0, suy ra 0 ≤ y − x, u − y hay x − y, u − y ≤ 0, ∀y ∈ C. ( ⇐) Lấy y ∈ C thỏa mãn x − y, u − y ≤ 0, ∀u ∈ C. Nếu y = x thì y = PC ( x ) .
12 Nếu y ≠ x, lấy bất kì u ∈ C , ta có: 0 ≥ x − y, u − y = x − y, u − x + x − y = x − y + x − y, u − x ≥ x − y − x − y x − u 2 2 ⇒ x − y ≤ x − u , ∀u ∈ C. Vậy y = PC ( x ) . □ Hệ quả 1.2.1. PC ( x1 ) − PC ( x2 ) 2 ≤ PC ( x1 ) − PC ( x2 ) , x1 − x2 , ∀x1 , x2 ∈ R n . Chứng minh: Theo mệnh đề 1.2.2., ta có: PC ( x2 ) − PC ( x1 ) , x1 − PC ( x1 ) ≤ 0 và PC ( x1 ) − PC ( x2 ) , x2 − PC ( x2 ) ≤ 0. Cộng vế theo vế hai bất đẳng thức trên, ta được: PC ( x1 ) − PC ( x2 ) , x2 − x1 + PC ( x1 ) − PC ( x2 ) ≤ 0 ⇒ PC ( x1 ) − PC ( x2 ) − PC ( x1 ) − PC ( x2 ) , x1 − x2 ≤ 0. □ 2 Từ hệ quả này, ta có kết quả sau. Hệ quả 1.2.2. Phép chiếu P lên tập lồi đóng C là liên tục Lipschitz với hệ số Lipschitz là 1, nghĩa là PC ( x1 ) − PC ( x2 ) ≤ x1 − x2 , ∀x1 , x2 ∈ R n . Tính chất trên được gọi là tính không giãn của phép chiếu. Ta trình bày công thức của phép chiếu lên vài tập lồi, đóng đơn giản. Ví dụ 1.2.2. Phép chiếu lên quả cầu đơn vị B trong R n : P : Rn ® B ì ï x khi x Î B ï ï x  P ( x) = í x ï ï khi x Ï B ï î x ï
13 Hình 1.6. Thật vậy, ta kiểm tra thông qua mệnh đề 1.2.2.: (Dễ thấy, P ( x) Î B với mọi x Î R ) . n x Î B : x - P ( x ) , y - P ( x) = x - x, y - x = 0, y Î B. x Ï B : yÎB: x x x - P ( x), y - P ( x) = x - , y- x x x -1 = ( x, y - x ) . x x -1 Vì xÏ B nên x > 1, suy ra >0 và yÎB nên x y £ 1, suy ra x, y £ x y £ x hay x, y - x £ 0. Vậy x - P ( x) , y - P ( x) £ 0, "y Î B. □
14 Ví dụ 1.2.3. Cho a Î R n \ {0 Rn } , a Î R, phép chiếu lên nửa không gian đóng H = { x Î R n : x , a £ a} : P : Rn ® H ìï x khi x Î H ïï x  P ( x) = ïí x, a - a ïï x - 2 a khi x Ï H . ïïî a Hình 1.7. x, a - a x, a - a a = a nên P ( x ) Î H , "x Î R . 2 n Ta có x - 2 a , a = x, a - 2 a a Ta kiểm tra đây là phép chiếu lên H: x Î H : x - P ( x ) , y - P ( x) = x - x, y - x = 0, y Î H . x Ï H : y Î H : æ x, a - a ÷÷ö æ x, a - a ÷÷ö ç çç x - P ( x ) , y - P ( x ) = x - çç x - a ÷ ÷÷ , y - çç x - a÷÷ çè a 2 ø è a 2 ÷ø x, a - a æ x, a - a ö÷÷ ç = a, y - çç x - a÷÷ ÷ø 2 2 a çè a x, a - a x, a - a = 2 a, y - 2 a£0 ( a, y £ a ). a a
15 Vậy x - P ( x) , y - P ( x) £ 0, "y Î H . □ Mệnh đề 1.2.3. Cho S ⊂ R n là tập lồi, đóng, khác rỗng và s ∈ S . Khi đó, ta có: PS −1 ( = s) {s} + N S ( s ) Chứng minh Ta cần chứng minh PS ( x ) = s ⇔ ( x − s ) ∈ N S ( s ) . Theo định nghĩa nón pháp tuyến, { y ∈ R n : vT y ≤ vT s}. Tức là ta chứng vectơ v thuộc N S ( s ) khi và chỉ khi S ⊂ H ( s, v ) = minh với mỗi x ∈ R , đẳng thức PS ( x ) = s đúng khi và chỉ khi S ⊂ H ( s, x − s ) . Ta có n PS ( x ) = s ⇔ P[ s , s '] ( x ) = s ∀s ' ∈ S ⇔ ( x − s ) s ' ≤ ( x − s ) s ∀s ' ∈ S T T ⇔ S ⊂ H ( s, x − s ) . □. { x ∈ R n : Ax = Mệnh đề 1.2.4. Cho S = b} , với A ∈ M m×n với rank A = m và b ∈ R m . Khi ( I − AT ( AAT ) A z + AT ( AAT ) đó PS ( z ) = −1 ) ( −1 ) b. Chứng minh Theo mệnh đề 1.2.3., với mỗi , x PS ( z ) ⇔ z ∈ { x} + N S ( x ) , z ∈ R n= ta có NS ( x) = {A T y : y ∈ R m } . Vì vậy, phép chiếu PS ( z ) có thể định bởi nghiệm của phương trình:  z   I AT   PS ( z )   =  ,  b   A 0  y  Mặt khác:
16 −1  I − AT ( AAT )−1 A AT ( AAT )  −1 I AT   .   =  ( AAT ) A T −1  − ( AA )  −1 A 0   ( ) ( I − AT ( AAT ) A z + AT ( AAT ) Ta suy ra PS ( z ) = −1 −1 ) 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ạ F : X → 2Y ( 2Y là họ tất cả các tập con của Y ) đượ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 x n + a1 x n −1 + ... + an −1 x + an= 0, n ∈ N , ai ∈ R ( i= 1,..., n ) . Quy tắc cho tương ứng mỗi = vectơ a ( a1 ,..., an ) ∈ R n 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ừ R n 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 F = { y ∈ Y : ∃x ∈ X sao cho y ∈ F ( x )} . Định nghĩa 1.3.3. Cho F : X  Y , ánh xạ ngược F −1 : Y  X của ánh xạ đa trị F được xác định bởi công thức: { x ∈ X : y ∈ F ( x )} F −1 ( y ) = ( y ∈Y ).