Tài liệu Quan hệ biến phân tuyến tính

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ----------------------- TẠ THỊ HOÀN QUAN HỆ BIẾN PHÂN TUYẾN TÍNH Chuyên ngành: TOÁN GIẢI TÍCH Mã số: 60460102 LUẬN VĂN THẠC SỸ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. TẠ DUY PHƯỢNG Hà Nội – Năm 2014 Mục lục Mở đầu 3 1 Kiến thức chuẩn bị 6 1.1 Không gian véctơ tôpô . . . . . . . . . . . . . . . . . . . . 6 1.2 Không gian metric . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1 Không gian metric . . . . . . . . . . . . . . . . . . . 11 1.2.2 Ánh xạ Lipschitz . . . . . . . . . . . . . . . . . . . 11 1.3 Giải tích lồi . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Ánh xạ đa trị . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.1 Định nghĩa ánh xạ đa trị . . . . . . . . . . . . . . . 15 1.4.2 Tính liên tục của ánh xạ đa trị . . . . . . . . . . . . 20 1.4.3 Một số định lí về ánh xạ đa trị . . . . . . . . . . . . 21 1.5 Định lý Hoffman . . . . . . . . . . . . . . . . . . . . . . . . 22 2 Sự tồn tại nghiệm của bài toán quan hệ biến phân 23 2.1 Bài toán quan hệ biến phân tổng quát . . . . . . . . . . . . 23 2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 23 2.1.2 Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . 25 2.2 Bài toán quan hệ biến phân tuyến tính . . . . . . . . . . . 36 2.2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 36 2.2.2 Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . 37 1 3 Cấu trúc tập nghiệm của bài toán quan hệ biến phân tuyến tính 53 3.1 Tính đóng của tập nghiệm . . . . . . . . . . . . . . . . . . 53 3.2 Tính lồi của tập nghiệm . . . . . . . . . . . . . . . . . . . . 55 3.3 Tính liên thông của tập nghiệm . . . . . . . . . . . . . . . 61 Tài liệu tham khảo 68 2 Mở đầu Bài toán quan hệ biến phân là bài toán xuất phát từ việc tổng quát hóa một số bài toán có ứng dụng thực tế như bài toán tối ưu, bài toán cân bằng, bài toán bất đẳng thức biến phân, bài toán tựa cân bằng,...Mô hình những bài toán này có ý nghĩa sâu sắc trong nghiên cứu toán học lý thuyết và toán học ứng dụng. Bài toán " Quan hệ biến phân" được đề xuất lần đầu tiên vào năm 2008 bởi Giáo sư Đinh Thế Lục [7]. Môt dạng đặc biệt của bài toán quan hệ biến phân là bài toán quan hệ biến phân tuyến tính. Dựa chủ yếu trên các tài liệu [4], [6], [7], luận văn trình bày các tính chất định tính bài toán quan hệ biến phân tuyến tính như sự tồn tại nghiệm của bài toán, cấu trúc tập nghiệm và tìm hiểu tính chất của tập nghiệm như tính đóng, tính lồi, liên thông,...Đây là những thông tin cần thiết cho việc nghiên cứu về mặt định lượng bài toán, hay việc tìm nghiệm của bài toán. Luận văn được trình bày theo 3 chương: Chương 1. Kiến thức chuẩn bị. Chương này trình bày một cách hệ thống kiến thức cơ sở có dùng đến ở chương sau như ánh xạ đa trị, tập lồi, Định lý Hoffman.... Chương 2. Sự tồn tại nghiệm của bài toán quan hệ biến phân. Chương này gồm hai phần. Phần đầu phát biểu và trình bày sự tồn tại nghiệm của bài toán quan hệ biến phân tổng quát. Phần sau phát biểu và 3 trình bày sự tồn tại nghiệm của bài toán quan hệ biến phân tuyến tính. Chương 3. Cấu trúc tập nghiệm của bài toán quan hệ biến phân tuyến tính. Trong chương này ta tìm hiểu một số tính chất của tập nghiêm bài toán quan hệ biến phân tuyến tính như tính đóng, tính lồi, tính liên thông. Bên cạnh đó là các ví dụ minh họa cho các kết quả trên. 4 Lời cảm ơn Luận văn được hoàn thành dưới sự hướng dẫn nhiệt tình của PGS. TS. Tạ Duy Phượng. Thầy đã dành nhiều thời gian, tâm huyết hướng dẫn cũng như giải đáp các thắc mắc của tôi trong suốt quá trình làm luận văn. Tôi muốn bày tỏ lòng biết ơn sâu sắc đến thầy. Qua đây, tôi xin gửi tới quý thầy cô Khoa Toán-Cơ-Tin học, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, cũng như các thầy cô đã tham gia giảng dạy khóa cao học 2012-2014, lời cảm ơn sâu sắc nhất đối với công lao dạy dỗ trong suốt quá trình học tập của tôi tại Nhà trường. Tôi xin cảm ơn gia đình, bạn bè và các bạn đồng nghiệp thân mến đã quan tâm, tạo điều kiện và cổ vũ, động viên tôi để tôi hoàn thành tốt nhiệm vụ của mình. Hà Nội, tháng 12 năm 2014 Tác giả luận văn Tạ Thị Hoàn 5 Chương 1 Kiến thức chuẩn bị 1.1 Không gian véctơ tôpô Một số định nghĩa và định lý dưới đây được trình bày dựa theo tài liệu [2]. Định nghĩa 1.1.1. Quan hệ hai ngôi trên tập A là tập hợp con R của tích Đềcác A × A. Ta gọi đơn giản là quan hệ hai ngôi. Ký hiệu aRb hoặc R(a, b) hoặc (a, b) ∈ R. Ta thường nói là "a − R quan hệ b. Định nghĩa 1.1.2. Cho một tập V khác rỗng, K là một trường. Các phần tử thuộc V được gọi là véctơ. Trên V trang bị hai phép toán: phép cộng hai véctơ (ký hiệu là "+") và phép nhân vô hướng k ∈ K với một véctơ (ký hiệu là "."). Khi đó (V, +, .) được gọi là một K - không gian véctơ nếu 10 tính chất sau thỏa mãn: 1) Nếu x, y ∈ V thì x + y ∈ V. 2) Với mọi x, y, z ∈ V ta có x + (y + z) = (x + y) + z. 3) Với mọi x, y ∈ V ta có x + y = y + x. 4) Tồn tại một phần tử θ ∈ V, gọi là phần tử trung hòa (hoặc véctơ không), sao cho x + θ = x với mọi x ∈ V. 5) Với mọi x ∈ V, tồn tại phần tử y ∈ V, gọi là phần tử đối xứng (phần tử 6 đối) của x, sao cho x + y = θ. 6) Nếu a ∈ K, x ∈ V thì ax ∈ V. 7) Với mọi a ∈ K và x, y ∈ V, ta có a(x + y) = ax + ay. 8) Với mọi a, b ∈ K và x ∈ V, ta có (a + b)x = ax + bx. 9) Với mọi a, b ∈ K và x ∈ V, ta có a(bx) = (ab)x. 10) Với mọi x ∈ V, ta có 1x = x1 = x, trong đó 1 là ký hiệu phần tử đợn vị của phép nhân trong K. Định nghĩa 1.1.3. (Không gian tôpô) Cho tập X 6= ∅. Một họ τ các tập con của X được gọi là một tôpô trên X nếu nó thỏa mãn các tính chất sau: (i) ∅, X ∈ τ ; (ii) Giao của một số hữu hạn các phần tử thuộc τ thì thuộc τ ; (iii) Hợp của một họ tùy ý các phần tử thuộc τ thì thuộc τ . Tập X được trang bị một tôpô τ được gọi là không gian tôpô và ký hiệu là (X, τ ) . Định nghĩa 1.1.4. Cho (X, τ ) là không gian tôpô. • Tập G được gọi là tập mở trong X nếu G ∈ τ. • Tập F được gọi là tập đóng trong X nếu X\F ∈ τ. Định nghĩa 1.1.5. Cho hai tôpô τ1 và τ2 ta nói τ1 yếu hơn τ2 (hay τ2 mạnh hơn τ1 ) nếu τ1 ⊂ τ2 , nghĩa là mọi tập mở trong tôpô τ1 đều là tập mở trong τ2 . Định nghĩa 1.1.6. Cho không gian tôpô (X, τ ), tập A là tập con của X . Tập U được gọi là một lân cận của tập A nếu tồn tại một tập mở nằm trong U chứa A. Khi A = {x} thì ta nói U là một lân cận của điểm x. 7 Định lý 1.1.1. Tập con G của không gian tôpô (X, τ ) là mở khi và chỉ khi G là lân cận của mọi điểm thuộc nó. Định lý 1.1.2. Nếu Vx là họ tất cả các lân cận của điểm x thì: (i) x ∈ V với mọi V ∈ Vx ; (ii) Nếu V1 , V2 ∈ Vx thì V1 ∩ V2 ∈ Vx ; (iii) Nếu V1 ∈ Vx và V2 ⊃ V1 thì V2 ∈ Vx . Định nghĩa 1.1.7. Cho Ux là một họ tất cả các lân cận của điểm x. Một họ Vx ⊆ Ux được gọi là cơ sở lân cận của x nếu với mọi U ∈ Ux đều tồn tại V ∈ Vx sao cho V ⊆ U. Chẳng hạn, họ các tập mở chứa x bao giờ cũng là cơ sở lân cận của x. Định nghĩa 1.1.8. Cho không gian tôpô (X, τ ), A là một tập con bất kì của X . Đối với mỗi phần tử bất kì x ∈ X ta nói: (i) x là điểm trong của A nếu tồn tại tập mở của x nằm trong A. (ii) x là điểm ngoài của A nếu tồn tại một lân cận của x nằm trong X\A. (iii) x là điểm biên của A nếu x đồng thời không là điểm trong và không là điểm ngoài của A. Hay nói cách khác x là điểm biên của A nếu mọi lân cận của x đều giao khác rỗng (chứa điểm khác x) với A và X\A. Định nghĩa 1.1.9. Giả sử A là tập con bất kì của không gian tôpô (X, τ ). Ta gọi phần trong của A là hợp của tất cả các tập mở nằm trong A, và nó o là tập mở lớn nhất nằm trong A. Kí hiệu là A hoặc intA. Định nghĩa 1.1.10. Giả sử A là tập con bất kì của không gian tôpô (X, τ ). Ta gọi bao đóng của A là giao của tất cả các tập đóng nằm trong A, và nó là tập đóng nhỏ nhất chứa A. Kí hiệu là Ā hoặc clA. 8 Định nghĩa 1.1.11. Cho X , Y là hai không gian tô pô. Một ánh xạ f từ X vào Y được gọi là liên tục tại điểm x0 nếu với mọi lân cận V của f (x0) đều tồn tại một lân cận U của x0 sao cho f (U ) ⊆ V. Ánh xạ f được gọi là liên tục trên X nếu nó liên tục tại mọi điểm x ∈ X . Định nghĩa 1.1.12. Cho {(Xα , τα )}α∈I là một họ các không gian tôpô. Q Xét X = Xα = {x = (xα )α∈I , xα ∈ Xα } và các phép chiếu pα : x 7→ xα . α∈I Tô pô τ yếu nhất trên X để tất cả các ánh xạ pα liên tục được gọi là tôpô tích. Khi đó (X, τ ) được gọi là không gian tôpô tích (hay không gian Q Xα . Tikhonov ) của các không gian tôpô {(Xα , τα )}α∈I . Kí hiệu là α∈I Định nghĩa 1.1.13. Không gian tôpô (X, τ ) được gọi là không gian Hausdorff (hay T2 − không gian) nếu mọi cặp điểm x khác y trong X đều tồn tại một lân cận U của x và V của y sao cho U ∩ V = ∅. Định nghĩa 1.1.14. Ta nói một tôpô τ trên không gian véctơ X tương hợp với cấu trúc đại số, nếu các phép toán đại số trong X liên tục trong tôpô đó, tức là nếu: 1. x + y là một hàm liên tục của hai biến x, y. Cụ thể, với mọi lân cận V của điểm x + y đều có một lân cận Ux của x và một lân cận Uy của y sao cho nếu x′ ∈ Ux , y ′ ∈ Uy thì x′ + y ′ ∈ V. 2. αx là một hàm liên tục của hai biến α, x. Cụ thể, với mọi lân cận V của αx đều có một số ε > 0 và một lân cận U của x sao cho |α − α′ | < ε, x′ ∈ U thì α′ x′ ∈ V. Một không gian véctơ X trên đó có một tôpô tương hợp với cấu trúc đại số được gọi là một không gian véctơ tôpô (hay không gian tôpô tuyến tính). Định nghĩa 1.1.15. Một tập A được gọi là hấp thu nếu với mọi x ∈ A 9 tồn tại một số λ > 0 sao cho nếu |α| ≥ λ thì x ∈ αA. Tập A được gọi là cân đối nếu với mọi x ∈ A ta có αx ∈ A khi |α| ≤ 1. Định nghĩa 1.1.16. Một không gian véctơ tôpô X được gọi là không gian véctơ tôpô lồi địa phương nếu trong X có một cơ sở lân cận của gốc gồm toàn tập lồi. Định nghĩa 1.1.17. Không gian tôpô X gọi là tách được (hay khả li) nếu nó chứa một tập hợp con đếm được trù mật trong X. Nghĩa là, tồn tại {xn} ⊂ X sao cho với mọi tập con mở, khác rỗng của X đều chứa ít nhất một phần tử của dãy {xn} . Định nghĩa 1.1.18. Tập I khác rỗng được gọi là tập định hướng nếu trên nó xác định một quan hệ ” ≥ ” thỏa mãn các tính chất sau: (i)) với mọi m, n, p ∈ I sao cho m ≥ n, n ≥ p thì m ≥ p; (ii) nếu m ∈ I thì m ≥ m; (iii) với mọi m, n ∈ I thì tồn tại p ∈ I sao cho p ≥ m, p ≥ n. Khi đó ta nói tập I được định hướng bởi quan hệ ” ≥ ” và kí hiệu là (I, ≥) hoặc viết tắt là I. Định nghĩa 1.1.19. Cho I là tập định hướng bởi quan hệ ” ≥ ”. Khi đó ánh xạ x xác định trên I và nhận giá trị trong tập X được gọi là lưới (hay dãy suy rộng) trong X. Ta viết xi = x(i) và kí hiệu lưới là (xn)n∈I . Nếu miền giá trị của lưới là không gian tôpô X thì (xn)n∈I được gọi là lưới trong không gian tôpô. Định nghĩa 1.1.20. Cho I là một tập định hướng bởi quan hệ ” ≥ ” và X là một không gian tôpô. Khi đó lưới (xn)n∈I được gọi là hội tụ trong không gian tôpô đến điểm x đối với tô pô τ nếu với mọi lân cận U của x 10 tồn tại n0 ∈ I sao cho với mọi n ∈ I mà n ≥ n0 thì xn ∈ U. Kí hiệu là lim xn = x hay xn → x. n→∞ 1.2 1.2.1 Không gian metric Không gian metric Định nghĩa 1.2.1. Cho tập X 6= ∅, ánh xạ d từ tích Descartes X × X vào tập hợp các số thực R được gọi là một metric trên X nếu thỏa mãn các tiên đề sau đây: 1) (∀x, y ∈ X) d(x, y) ≥ 0, d(x, y) = 0 ⇔ x = y , (tiên đề đồng nhất); 2) (∀x, y ∈ X) d(x, y) = d(y, x), (tiên đề đối xứng); 3) (∀x, y, z ∈ X) d(x, y) ≤ d(x, z) + d(z, y), (tiên đề bất đẳng thức tam giác); Tập X với metric d trang bị trên X được gọi là không gian metric, kí hiệu là (X, d) hay thường được viết là X. Số d(x, y) gọi là khoảng cách giữa hai phần tử x và y . Các phần tử của X gọi là các điểm. Các tiên đề 1), 2), 3) gọi là hệ tiên đề metric. 1.2.2 Ánh xạ Lipschitz Định nghĩa 1.2.2. Cho X là không gian metric, một điểm x ∈ X và A là một tập con của X . Khoảng cách từ điểm x đến tập A được xác định bởi d(x, A) = inf d(x, a). a∈A Định nghĩa 1.2.3. (Khoảng cách Hausdorff) Cho X và Y là hai không gian metric, một điểm x ∈ X và A, B lần lượt là các tập con trong X , Y . Khoảng cách từ tập A đến tập B được xác định bởi   dH (A, B) = max sup inf d(a, b), sup inf d(a, b) , a∈A b∈B 11 b∈B a∈A hay   dH (A, B) = max sup d(a, B), sup d(b, A) . a∈A b∈B Định nghĩa 1.2.4. Trong không gian metric X . Một dãy {xn}, với n ∈ N và N là tập số tự nhiên, được gọi là dãy cơ bản nếu (∀ε > 0) (∃N ) (∀n ≥ N ) (∀m ≥ N ) thì d (xn , xm) < ε. Nhận xét 1.2.1. Một dãy hội tụ bao giờ cũng là dãy cơ bản, vì nếu xn → x thì theo bất đẳng thức tam giác ta có d (xn , xm) ≤ d (xn , x) + d (x, xm) → 0 (n, m → ∞). Nhưng ngược lại một dãy cơ bản trong một không gian bất kỳ không nhất thiết hội tụ. Chẳng hạn nếu xét khoảng (0, 1) là một không gian metric 1 , mặc dù là dãy cơ với d(x, y) = |x − y| với mọi x, y ∈ (0, 1) thì dãy n bản, nhưng không hội tụ trong không gian ấy. Định nghĩa 1.2.5. Không gian metric X trong đó mọi dãy cơ bản đều hội tụ (tới một phần tử của X ) được gọi là một không gian đủ. Định nghĩa 1.2.6. Cho hai không gian metric (X, d1 ) , (Y, d2), ánh xạ f từ không gian X đến không gian Y . Ánh xạ f được gọi là liên tục tại điểm x0 ∈ X, nếu (∀ε > 0) (∃δ > 0) (∀x ∈ X : d1(x, x0) < δ) thì d2 (f (x), f (x0)) < ε. Hay nói cách khác: Ánh xạ f được gọi là liên tục tại điểm x0 ∈ X, nếu với ε > 0, tồn tại δ > 0 sao cho f (x) ∈ S(y0 , ε) với mọi x ∈ S(x0, δ), trong đó S(y0 , ε) là hình cầu tâm y0 , bán kính ε, nghĩa là S(y0 , ε) = {y ∈ Y : d(y, y0) < ε} . 12 Định nghĩa 1.2.7. Ánh xạ f được gọi là liên tục trên tập A ⊂ X , nếu ánh xạ f liên tục tại mọi điểm x ∈ A. Khi A = X thì ánh xạ f được gọi là liên tục. Định nghĩa 1.2.8. Ánh xạ P : X → X được gọi là ánh xạ Lipschitz nếu ∃k > 0 : d (P (x), P (y)) ≤ kd(x, y). • k = 1: f được gọi là ánh xạ không giãn. • 0 < k < 1: f được gọi là ánh xạ co. 1.3 Giải tích lồi Dựa trên tài liệu [1], ta trình bày một số kiến thức cơ sở về giải tích lồi như sau. Định nghĩa 1.3.1. Một tập con M của không gian véc tơ X được gọi là đa tạp affine, hay đơn giản là tập affin, nếu với mọi cặp điểm x, y ∈ M ta có L(x, y) ⊆ M. Ở đây, ký hiệu L(x, y) là đường thẳng đi qua x, y. Tức là L(x, y) = {z ∈ X, z = αx + (1 − α)y, α ∈ R}. Chẳng hạn, trong không gian ba chiều, tập hợp một điểm, đường thẳng, mặt phẳng là các tập affin. Trong khi đó, hình cầu, hình đa giác nói chung không phải là tập affin. Định nghĩa 1.3.2. Ta gọi véc tơ có dạng x = i ≤ m, thỏa mãn m X Pm i=1 λi ai với λi ∈ R, 1 ≤ λi = 1, i=1 là một tổ hợp affin của các vec tơ {a1 , a2 , ..., am}. Mệnh đề 1.3.1. Giao của một họ bất kỳ các tập affin là một tập affin. 13 Định nghĩa 1.3.3. Một tập hợp C ⊆ X được gọi là lồi nếu với mọi cặp điểm x, y ∈ C ta có [x, y] ⊆ C. Ở đây. ký hiệu [x, y] là khoảng đóng nối hai điểm x và y . Nói cách khác, C lồi nếu với mọi x, y ∈ C và λ ∈ [0, 1] ta có λx + (1 − λ)y ∈ C. Trong không gian hữu hạn chiều, mặt phẳng, đoạn thẳng, đường thẳng, tam giác, hình cầu cho ta các hình ảnh về tập lồi. Trong khi mặt cầu, đường cong nói chung không phải là tập lồi. Mệnh đề 1.3.2. Giao của một họ bất kỳ các tập lồi là tập lồi. Định nghĩa 1.3.4. Ta gọi bao lồi của tập A ⊆ X, kí hiệu coA, là giao của tất cả các tập lồi chứa A. Từ Mệnh đề 1.3.2, coA cũng là một tập lồi và là tập lồi nhỏ nhất chứa A. Định nghĩa 1.3.5. Một tổ hợp affin x = Pm i=1 λi ai với các hệ số λi không âm, được gọi là một tổ hợp lồi của các véc tơ {a1 , a2 , ..., am}. Mệnh đề 1.3.3. a) Một tập lồi thì chứa mọi tổ hợp lồi của các véc tơ của nó, b) coA = {x | x là tổ hợp lồi của các véc tơ thuộc A}, c) C là tập lồi khi và chỉ khi C = coC. Định lý 1.3.1 (Carathéodory). Giả sử dimX = n <∝ và A ⊆ X. Khi đó, với mọi x ∈ coA, x là tổ hợp lồi của một họ có không quá n + 1 vec-tơ thuộc A. Tức là tồn tại hệ {a0 , a1 , ..., am} ⊆ A với m ≤ n, và các số λ0 , λ1, ..., λm ≥ 0 sao cho m X λi = 1 và x = i=0 1.4 m X λi ai . i=0 Ánh xạ đa trị Một số kiến thức về ánh xạ đa trị trong phần này được trình bày dựa trên tài liệu [3]. 14 1.4.1 Định nghĩa ánh xạ đa trị Định nghĩa 1.4.1. Cho X ,Y là hai tập hợp bất kì. Tập tất cả các tập con của Y được kí hiệu là 2Y . Ta nói F là ánh xạ đa trị từ X vào Y là một quy tắc cho tương ứng với mỗi x ∈ X một tập con F (x) của Y và ký hiệu F :X ⇒Y hoặc F : X → 2Y . Nhận xét 1.4.1. Nếu với mỗi x ∈ X tập F (x) chỉ gồm đúng một phần tử của Y , thì ta nói F là ánh xạ đơn trị từ X vào Y . Khi đó, thay cho kí hiệu F : X ⇒ Y ta sử dụng kí hiệu quen thuộc F : X → Y . Ví dụ 1.4.1. Ánh xạ F : R2 ⇒ R2 xác định bởi F (x) = {y ∈ R2 : ky − xk ≤ 1}, là một ánh xạ đa trị trên R2 . Định nghĩa 1.4.2. Đồ thị gphF , miền hữu hiệu domF và miền ảnh rgeF của ánh xạ đa trị F : X ⇒ Y tương ứng được xác định bằng các công thức gphF = {(x, y) ∈ X × Y : y ∈ F (x)} , domF = {x ∈ X : F (x) 6= ∅} và rgeF = {y ∈ Y : ∃x ∈ X sao cho y ∈ F (x)} . Định nghĩa 1.4.3. Cho F : X ⇒ Y là ánh xạ đa trị, X và Y là các không gian tôpô. 15 1. F được gọi là ánh xạ đóng (hoặc ánh xạ có đồ thị đóng) nếu gphF là tập đóng trong không gian tôpô tích X × Y. 2. F được gọi là ánh xạ có giá trị đóng nếu F (x) là tập đóng với mọi x ∈ domF. 3. F được gọi là ánh xạ mở (hoặc ánh xạ có đồ thị mở ) nếu gphF là tập mở trong không gian tôpô tích X × Y. 4. F được gọi là ánh xạ có giá trị mở nếu F (x) là tập mở với mọi x ∈ domF. Ví dụ 1.4.2. Ánh xạ đa trị F : R2 ⇒ R2 xác định bởi F (x) = {y ∈ R2 : ky − xk < 1}, là ánh xạ có giá trị mở. Ánh xạ đa trị F : R2 ⇒ R2 xác định bởi F (x) = {y ∈ R2 : ky − xk ≤ 1}, là ánh xạ có giá trị đóng. Nhận xét 1.4.2. Nếu ánh xạ đa trị F có gphF đóng thì F (x) là đóng với mọi x ∈ domF. Thật vậy, để cho tiện, ta giả thiết X, Y là các không gian hữu hạn chiều. Giả sử tồn tại x0 ∈ domF mà F (x0 ) không đóng, nghĩa là tồn tại dãy yn ∈ F (x0 ) mà yn → ȳ nhưng ȳ ∈ / F (x0). Đặt zn = (x0, yn ) thì dãy {zn } hội tụ tới z̄ = (x0 , ȳ). Vì yn ∈ F (x0) nên zn = (x0 , yn) ∈ gphF. Vì gphF đóng nên z = (x0, y) ∈ gphF, hay ȳ ∈ F (x0 ), mâu thuẫn với điều giả sử. Vậy F (x) là đóng với mọi x ∈ domF. Ta đã biết 16 Định nghĩa 1.4.4. Cho X, Y là hai không gian tuyến tính. Ánh xạ f : X → Y được gọi là hàm lồi nếu domf là lồi và f (αx1 + (1 − α)x2) ≤ αf (x1) + (1 − α)f (x2) với mọi x ∈ domf , mọi α ∈ [0, 1]. Nhận xét 1.4.3. Cho f là một ánh xạ, f : X → Y. Khi đó f lồi khi và chỉ khi epif lồi, trong đó epif = {(x, y) ∈ X × Y : y ≥ f (x), x ∈ domf }. Chứng minh. 1) Giả sử f là hàm lồi. Ta sẽ chứng minh epif lồi. Thật vậy, vì f lồi nên theo định nghĩa ta có f (αx1 + (1 − α)x2) ≤ αf (x1) + (1 − α)f (x2). Lấy z1 = (x1 , y1 ) ∈ epif và z2 = (x2 , y2 ) ∈ epif . Tức là y1 ≥ f (x1 ) và y2 ≥ f (x2). Ta phải chứng minh z = (x, y) = αz1 + (1 − α)z2 ∈ epif . Ta có αy1 + (1 − α)y2 ≥ αf (x1) + (1 − α)f (x2). Vì x1 , x2 ∈ domf và domf lồi nên x = αx1 + (1 − α)x2 ∈ domf. Do f là hàm lồi nên ta có f (x) = f (αx1 + (1 − α)x2) ≤ αf (x1) + (1 − α)f (x2) ≤ y1 + (1 − α)y2 = y. Hay f (x) ≤ y. Suy ra z = (x, y) ∈ epif. Vậy epif lồi. 2) Đảo lại, cho epif lồi. Ta sẽ chứng minh f là hàm lồi. Thật vậy, chọn z1 = (x1, y1) với y1 = f (x1), z2 = (x2, y2 ) với y2 = f (x2). Khi ấy z1 , z2 ∈ epif. Vì epif lồi nên z = αz1 + (1 − α)z2 ∈ epif. Suy ra αf (x1) + (1 − α)f (x2) = αy1 + (1 − α)y2 ≥ f (αx1 + (1 − αx2 )) với mọi x1 , x2 ∈ domf và với mọi α ∈ [0, 1]. Tức là f là hàm lồi. 17 Từ định nghĩa và nhận xét trên, ta đi đến khái niệm ánh xạ đa trị lồi như sau: Định nghĩa 1.4.5. Cho F : X ⇒ Y là ánh xạ đa trị. Khi đó, F được gọi là ánh xạ đa trị lồi nếu gphF = {(x, y) : y ∈ F (x), x ∈dom F } là tập lồi. Định nghĩa trên tương đương với định nghĩa sau. Định nghĩa 1.4.6. Cho F : X ⇒ Y là ánh xạ đa trị. Khi đó F là ánh xạ đa trị lồi nếu i) domF là tập lồi; ii) F (αx1 + (1 − α)x2 ) ⊇ αF (x1 ) + (1 − α)F (x2 ) với mọi x1 , x2 ∈ X. Nhận xét 1.4.4. Giả sử f : X −→ Y là hàm lồi. Khi ấy F :X ⇒Y F (x) = {f (x) + α : α ≥ 0} là ánh xạ đa trị lồi. Chứng minh. Giả sử x1 , x2 ∈ X. Lấy u ∈ F (x1) và v ∈ F (x2 ), khi ấy tồn tại s1 ≥ 0, s2 ≥ 0 sao cho u = f (x1) + s1 v = f (x2) + s2 Do f là hàm lồi nên tf (x1) + (1 − t)f (x2) ≥ f (tx1 + (1 − t)x2). 18 Suy ra tồn tại α > 0 sao cho tf (x1) + (1 − t)f (x2) = f (tx1 + (1 − t)x2) + α. Xét w = tu + (1 − t)v = tf (x1) + ts1 + (1 − t)f (x2) + (1 − t)s2 = f (tx1 + (1 − t)x2) + α + ts1 + (1 − t)s2 = f (tx1 + (1 − t)x2) + β, với β = α + ts1 + (1 − t)s2 ≥ 0 ∈ F (tx1 + (1 − t)x2). Vậy tF (x1 ) + (1 − t)F (x2 ) ⊆ F (tx1 + (1 − t)x2 ). Như vậy, định nghĩa ánh xạ đa trị lồi tương thích với định nghĩa hàm lồi. Định nghĩa 1.4.7. Cho ánh xạ F : X ⇒ Y là ánh xạ đa trị. Khi đó, ánh xạ F được gọi là ánh xạ đa trị lõm nếu ta có F (αx1 + (1 − α)x2) ⊆ αF (x1) + (1 − α)F (x2) với mọi x1, x2 ∈ X. Ví dụ 1.4.3. Ánh xạ đa trị F : R2 ⇒ R2 xác định bởi F (x) = {y ∈ R2 : ky − xk ≤ 1}, là ánh xạ đa trị lồi. Ánh xạ đa trị F : R2 ⇒ R2 xác định bởi F (x) = {y ∈ R2 : y ≤ −x2} là ánh xạ đa trị lõm. 19