Luận văn Thạc sĩ Toán học: Phương pháp biến đổi fourier nhanh giải phương trình parabolic tuyến tính

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

Thêm vào BST

Báo xấu

19
lượt xem 3
download

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

Mục đích của bản luận văn này là trình bày lại một cách có hệ thống các kết quả về mô hình Nash–Cournot trong trường hợp mô hình có thêm một ràng buộc chung, theo cách tiếp cận dựa trên việc mô tả mô hình dưới dạng bài toán cân bằng tách. Mời các bạn tham khảo!

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: Phương pháp biến đổi fourier nhanh giải phương trình parabolic tuyến tính

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN THÀNH HUẾ MỘT TIẾP CẬN CÂN BẰNG TÁCH CHO MÔ HÌNH NASH - COURNOT VỚI MỘT RÀNG BUỘC CHUNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN THÀNH HUẾ MỘT TIẾP CẬN CÂN BẰNG TÁCH CHO MÔ HÌNH NASH - COURNOT VỚI MỘT RÀNG BUỘC CHUNG Chuyên ngành: Toán ứng dụng Mã số : 8 46 01 12 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 - 2019
i Lời cảm ơn Luận văn này được hoàn thành dưới sự hướng dẫn của GS.TSKH. Lê Dũng Mưu (trường Đại học Thăng Long Hà Nội). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp cao học Toán, nhà trường và các phòng chức năng của trường, khoa Toán - Tin, trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Xin chân thành cảm ơn anh chị em trong lớp cao học và bạn bè đồng nghiệp đã trao đổi, động viên và khích lệ tác giả trong quá trình học tập, nghiên cứu và làm luận văn. Thái Nguyên, 10 tháng 4 năm 2019 Tác giả luận văn Nguyễn Thành Huế
ii Mục lục Lời cảm ơn i Bảng ký hiệu iii Lời nói đầu 1 Chương 1 Kiến thức chuẩn bị 3 1.1. Tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều . . 3 1.2. Các bổ đề hỗ trợ . . . . . . . . . . . . . . . . . . . . . . . . . 19 Chương 2 Một tiếp cận cân bằng tách cho mô hình Nash- Cournot với một ràng buộc chung 21 2.1. Bài toán chấp nhận lồi tách . . . . . . . . . . . . . . . . . . . 21 2.2. Một thuật toán giải mô hình Nash–Cournot có ràng buộc chung 22 2.2.1.Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2.2.Một mô hình thực tế . . . . . . . . . . . . . . . . . . . 31 Kết luận 36 Tài liệu tham khảo 37
iii Bảng ký hiệu Rn+ Góc không âm của Rn (tập các vectơ không âm) R Trục số thực R = R1 R Trục số thực mở rộng (R = R ∪ {−∞, +∞}) xi Tọa độ thứ i của x xT Vectơ hàng (chuyển vị của x ) ||x|| Chuẩn Euclid của x riA Tập hợp các điểm trong tương đối của A reA Nón lùi xa (nón các hướng vô hạn) của A A∗ Đối cực của A f Hàm bao đóng của f domf Tập hữu dụng của f f∗ Hàm liên hợp của f epif Trên đồ thị của f ∂f (x) Dưới vi phân của f tại x ∂∈ f (x) ε -dưới vi phân của f tại x ∇f (x) Hoặc đạo hàm của f tại x 0 f (x) Đạo hàm f tại x 0 f (x, d) Đạo hàm theo hướng d của f tại x
1 Lời nói đầu Bài toán chấp nhận tách là bài toán Tìm x∗ ∈ C sao cho Ax∗ ∈ Q, trong đó C là một tập lồi đóng trong không gian X, còn Q là một tập lồi đóng trong không gian Y và A là một toán tử tuyến tính từ X vào Y . Bài toán này có thể coi như một sự mở rộng của bài toán chấp nhận lồi, là một bài toán cơ bản trong Toán ứng dụng. Bài toán chấp nhận tách lần đầu tiên được nghiên cứu trong không gian Euclid hữu hạn chiều bởi Censor và Elving năm 1994 trong tài liệu [2]. Trong bài báo này các tác giả đã giới thiệu một số ứng dụng của bài toán chấp nhận tách trong không gian hữu hạn chiều, như ứng dụng trong xạ trị khối u, trong xử lý tín hiệu v.v... Sau công trình trên, bài toán chấp nhận tách được rất nhiều người quan tâm nghiên cứu, do tính lý thú về mặt toán học, và đặc biệt là phạm vi ứng dụng rộng rãi của bài toán này. Một hướng mở rộng được quan tâm nhiều là xét trường hợp khi các tập C và Q là nghiệm của những bài toán khác, như bài toán tối ưu lồi, bất đẳng thức biến phân đơn điệu, tập điểm bất động của ánh xạ không giãn, hoặc tổng quát hơn là tập nghiệm của bài toán cân bằng có một tính chất đơn điệu nào đó. Mục đích của bản luận văn này là trình bày lại một cách có hệ thống các kết quả về mô hình Nash–Cournot trong trường hợp mô hình có thêm một ràng buộc chung, theo cách tiếp cận dựa trên việc mô tả mô hình dưới dạng bài toán cân bằng tách. Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục
2 các tài liệu tham khảo. Chương 1 trình bày một số khái niệm cơ bản liên quan đến đề tài, đó là tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều. Chương 2 giới thiệu bài toán chấp nhận lồi tách, giới thiệu mô hình Nash–Cournot và trình bày một thuật toán giải bài toán mô hình Nash– Cournot có ràng buộc chung theo tiếp cận cân bằng tách.
3 Chương 1 Kiến thức chuẩn bị Chương này trình bày các khái niệm, các tính chất cơ bản nhất của giải tích lồi và các bổ đề hỗ trợ sẽ được dùng trong Chương 2. Các kiến thức ở chương này được tổng hợp từ tài liệu tham khảo [1], [3]. 1.1. Tập lồi và hàm lồi trong không gian Euclid hữu hạn chiều Định nghĩa 1.1 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. Ta nói x là tổ hợp lồi của các điểm (vectơ) x1 , ..., xk nếu k X k X j x= λj x , λj > 0 ∀j = 1, ..., k λj = 1. j=1 j=1 Tương tự, x là tổ hợp aphin của các điểm (vectơ) x1 , ..., xk nếu k X k X j x= λj x , λj = 1. j=1 j=1 Tập hợp của các tổ hợp aphin của x1 , ..., xk thường được gọi là bao aphin của các điểm này.
4 Mệnh đề 1.1 Tập hợp 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à tập C lồi khi và chỉ khi k X k X 1 k ∀k ∈ N, ∀λ1 , ..., λk > 0 : λj = 1, ∀x , ..., x ∈ C ⇒ λj xj ∈ C. j=1 j=1 Chứng minh. Điều kiện đủ là hiển nhiên từ định nghĩa. Ta chứng minh điều kiện cần bằng quy nạp theo số điểm. Với k = 2, điều 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 cần chứng minh với k điểm. Giả sử x là tổ hợp lồi của k điểm x1 , ..., xk ∈ C. Tức là k X k X j x= λj x , λj > 0 ∀j = 1, ..., k λj = 1. j=1 j=1 Đặt k−1 X ξ= λj . j=1 Khi đó 0 < ξ < 1 và k−1 k−1 X j k X λj x= λj x + λk x = ξ x j + λk x k j=1 j=1 ξ do k−1 X λj = 1. j=1 ξ λj Với ξ > 0 với mọi j = 1, ..., k − 1, nên theo giả thiết quy nạp, điểm k−1 X λj y := xj ∈ C. j=1 ξ Ta có x = ξy + λk xk . Do ξ > 0, λk > 0 và k X ξ + λk = λj = 1, j=1
5 nên x là một tổ hợp lồi của hai điểm y và xk đều thuộc C. Vậy x ∈ C. Định nghĩa 1.2 Một tập C được gọi là tập aphin nếu nó chứa đườ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. Vậy tập aphin là một trường hợp riêng của tập lồi. Ví dụ điển hình của tập aphin là các không gian con, siêu phẳng được định nghĩa dưới đây. Định nghĩa 1.3 Siêu phẳng trong không gian Rn là một tập hợp các điểm có đạng {x ∈ Rn |aT x = α}, trong đó a ∈ Rn là một vectơ khác 0 và α ∈ R. Vectơ a thường được gọi là vectơ pháp tuyến của siêu phẳng. Một siêu phẳng sẽ chia không gian ra hai nửa không gian. Nửa không gian được định nghĩa như sau: Định nghĩa 1.4 Nửa không gian là một tập hợp có dạng {x|aT x ≥ α}, trong đó a 6= 0 và α ∈ R. Đây là nửa không gian đóng. Tập {x| aT x > α} là nửa không gian mở. Định nghĩa 1.5 Các điểm x0 , x1 , ..., xk trong Rn được gọi là độc lập aphin, nếu bao aphin của chúng có thứ nguyên là k. Định nghĩa 1.6 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. Theo định nghĩa, tập lồi đa diện là tập hợp nghiệm của một hệ hữu hạn các bất phương trình tuyến tính. Dạng tường minh của một tập lồi đa diện được cho như sau: D := {x ∈ Rn | aj , x ≤ bj , j = 1, ..., m}.
6 Hoặc nếu ta ký hiệu A là ma trận có m hàng là các vectơ aj (j = 1, ..., m) và vectơ bT = (b1 , ..., bm ), thì hệ trên viết được là D = {x ∈ Rn |Ax ≤ b}. Chú ý rằng do một phương trình ha, x = bi có thể viết một cách tương đương dưới dạng hai bất phương trình ha, xi ≤ b, h−a, xi ≤ b, nên tập nghiệm của một hệ hữu hạn các phương trình và bất phương trình cũng là một tập lồi đa diện. Một số các tính chất của tập lồi đa diện sẽ được trình bày trong các phần tiếp theo. Định nghĩa 1.7 Cho C 6= (không nhất thiết lồi) và y là một vectơ bất 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 (vuông góc) của y trên C. Theo định nghĩa, ta có hình chiếu pC (y) của y trên C sẽ là nghiệm của bài toán tối ưu. 1 min{ ||x − y||2 |x ∈ C} x 2 Vậy việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực tiểu của hàm toàn phương ||x − y||2 trên C. Ta 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 C 6= , thì dC (y) hữu hạn, vì 0 ≤ dC (y) ≤ ||y − x|| với mọi x ∈ C. Cho C ⊆ Rn , x0 ∈ C. Nhớ lại là nón pháp tuyến (ngoài) của tập C tại x0 là tập hợp NC (x0 ) := {w|wT (x − x0 ) ≤ 0 ∀x ∈ C}.
7 Mệnh đề 1.2 Cho C là một tập lồi đóng khác rỗng. Khi đó: (i) Với mọi y ∈ Rn , π ∈ C hai tính chất sau là tương đương: a) π = PC (y), b) y − π ∈ NC (π). (ii) Với mọi y ∈ Rn , hình chiếu PC (y) của y trên C luôn tồn tại và duy nhất. (iii) Nếu y ∈ / C, thì hPC (y) − y, x − PC (y)i = 0 là siêu phẳng tựa của C tại PC (y) và tách hẳn y khỏi C, tức là hPC (y) − y, x − PC (y)i ≥ 0, ∀x ∈ C, và hPC (y) − y, y − PC (y)i < 0. (iv) Ánh xạ y ,→ PC (y) có các tính chất sau: a) ||PC (x) − PC (y)|| ≤ ||x − y|| ∀x, ∀y ( tính không giãn); b) hPC (x) − PC (y)i , x − y ≥ ||PC (x) − PC (y)||2 , (tính đồng bức). Chứng minh (i) Giả sử có a). Lấy x ∈ C và λ ∈ (0, 1). Đặt xλ := λx + (1 − λ)π. Do x, π ∈ C và C lồi, nên xλ ∈ C. Hơn nữa do π là hình chiếu của y, nên ||π − y|| ≤ ||y − xλ ||. Hay ||π − y||2 ≤ ||λ(x − π|| + (π − y)||2 . Khai triển vế phải, ước lược và chia hai vế cho λ > 0, ta có λ||x − π||2 + 2 hx − π, π − yi ≥ 0. Điều này đúng với mọi x ∈ C và λ ∈ (0, 1). Do đó khi cho λ tiến đến 0, ta được hπ − y, x − πi ≥ 0 ∀x ∈ C. Vậy y − π ∈ NC (π).
8 Bây giờ giả sử có b). Với mọi x ∈ C, có 0 ≥ (y − π)T (x − π) = (y − π)T (x − y + y − π) = ||y − π||2 + (y − π)T (x − y). Từ đây và b), dùng bất đẳng thức Cauchy–Schwarz ta có: ||y − π||2 ≤ (y − π)T (y − x) ≤ ||y − π||||(y − x)||. Suy ra ||(y − π)|| ≤ ||y − x|| ∀x ∈ C, và do đó π = p(y). (ii) Do dC (y) = infx∈C ||x − y||, nên theo định nghĩa của cận dưới đúng (infimum), tồn tại một dãy xk ∈ C sao cho lim ||xk − y|| = dC (y) < +∞ k Vậy dãy {xk } bị chặn, do đó nó có một dãy con {xkj } hội tụ đến một điểm π nào đó. Do C đóng, nên π ∈ C. Vậy ||π − y|| = lim ||xkj − y|| = lim ||xk − y|| = dC (y). j k Chứng tỏ π là hình chiếu của y trên C. Bây giờ ta chỉ ra tính duy nhất của hình chiếu. Thật vậy, nếu tồn tại hai điểm π và π 1 đều là hình chiếu của y trên C, thì y − π ∈ NC (π), y − π 1 ∈ NC (π 1 ). Tức là π − y, π 1 − π ≥ 0 và 1 π − y, π − π 1 ≥ 0. Cộng hai bất đẳng thức này ta suy ra ||π − π 1 || ≤ 0, và do đó π = π 1 . (iii) Do y − π ∈ NC (π), nên hπ − y, x − πi ≥ 0 ∀x ∈ C.
9 Vậy hπ − y, xi = hπ − y, πi là một siêu phẳng tựa của C tai π. Siêu phẳng này tách y khỏi C vì y 6= π, nên hπ − y, y − πi = −||π − y||2 < 0. (iv) Theo phần (ii) ánh xạ x ,→ p(x) xác định khắp nơi. Do z − p(z) ∈ NC (p(z)) với mọi z, nên áp dụng với z = x và z = y, ta có: hx − p(x), p(y) − p(x)i ≤ 0 và hy − p(y), p(x) − p(y)i ≤ 0. Cộng hai bất đẳng thức lại sẽ được hp(y) − p(x), p(y) − p(x) + x − yi ≤ 0. Từ đây và theo bất đẳng thức Cauchy–Schwarz, suy ra ||p(x) − p(y)|| ≤ ||x − y||. Để chứng mnh tính đồng bức, áp dụng tính chất b của (i), lần lượt với p(x) và p(y), ta có hp(x) − x, p(x) − p(y)i ≤ 0. hy − p(y), p(x) − p(y)i ≤ 0. Cộng hai bất đẳng thức ta được hp(x) − p(y) + y − x, p(x) − p(y)i ≤ 0 = hp(x) − p(y), y − xi + ||p(x) − p(y)||2 ≤ 0. Chuyển vế ta có hp(x) − p(y), x − yi ≥ ||p(x) − p(y)||2 . Đây chính là tính đồng bức cần được chứng minh.
10 Định nghĩa 1.8 Một ánh xạ F : C −→ Rn được gọi là đơn điệu trên C, nếu hF (x) − F (y), x − yi ≥ 0 ∀x, y ∈ C Ánh xạ F được gọi là đơn điệu mạnh trên C với hệ số β > 0, nếu hF (x) − F (y), x − yi ≥ β||x − y||2 ∀x, y ∈ C Cho C ⊆ Rn là tập lồi và f : C ,→ R. Ta sẽ ký hiệu domf := {x ∈ C| f (x) < +∞} Tập domf được gọi là miền hữu dụng của f . Tập epif := {(x, µ) ∈ C × R|f (x) ≤ µ} được gọi là trên đồ thị của 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à hiển nhiên là domf = {x ∈ Rn | f (x) < +∞} epif = {(x, µ) ∈ Rn | × R|f (x) ≤ µ} Do sẽ làm việc với hàm số nhận cả giá trị −∞ và +∞, ta có quy ước sau: Nếu λ = 0, thì λf (x) = 0 với mọi x. Định nghĩa 1.9 Cho 6= C ⊆ Rn lồi và f : C → R. Ta nói f là hàm lồi trên C, nếu epif là một tập lồi trong Rn+1 . Ta sẽ chủ yếu làm việc với hàm f : Rn → R ∪ {+∞} . Trong trường hợp này, dễ thấy rằng định nghĩa trên tương đương với 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 chặt trên C nếu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) ∀x, y ∈ C, ∀ λ ∈ (0, 1).
11 Hàm f : Rn → R ∪ {+∞} . được gọi là lồi mạnh trên C với hệ số η > 0, nếu ∀x, y ∈ C, ∀λ ∈ (0, 1) có: 1 f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − ηλ(1 − λ)||x − y||2 . 2 Kiểm tra được rằng, f lồi mạnh trên C với hệ số η > 0 khi và chỉ khi hàm η h(.) := f (.) − ||.||2 2 lồi trên C. Bằng quy nạp, dễ dàng chứng minh được rằng, nếu f nhận giá trị hữu hạn trên tập lồi C, thì với mọi số tự nhiên m và mọi x1 , ..., xm ∈ C thỏa mãn λ1 ≥ 0, ..., λm ≥ 0, m P j=1 λj = 1, ta có Xm m X j f( λj x ) ≤ λj f (xj ) (bất đẳng thức Jensen). j=1 j=1 Hàm f được gọi là một hàm lõm trên C, nếu −f lồi trên C. Dưới đây là một điều kiện cần và đủ về hàm lồi, rất tiện ích trong nhiều trường hợp. Mệnh đề 1.3 Một hàm f : C → R là lồi trên C khi và chỉ khi ∀x, y ∈ C, ∀α > f (x), ∀β > f (y), ∀λ ∈ [0, 1] =⇒ f (λx + (1 − λ)y) ≤ λα + (1 − λ)β). Chứng minh Chứng minh điều kiện cần. Giả sử f lồi. Chọn x, y, α, β 0 0 như đã nêu trong mệnh đề. Chọn α ∈ (f (x), α) và β ∈ (f (y), β). Vậy 0 0 (x, α ) và (y, β ) thuộc epif . Do epif lồi, nên; 0 0 ((1 − λ)x + λy), (1 − λ)α + λβ ) ∈ epif. Do đó 0 0 f ((1 − λ)x + λy) ≤ (1 − λ)α + λβ < (1 − λ)α + λβ.
12 Chứng minh điều kiện đủ. Chọn (x, µ) và (y, ν) thuộc epif và λ ∈ (0, 1). Thế thì với mọi ε > 0, ta có f (x) < µ + ε, f (y) 0, nên cho ε → 0, ta được 0 0 f [(1 − λ)α + λβ ] ≤ (1 − λ)µ + λν. Chứng tỏ (1 − λ)(x, µ) + λ(y, ν) ∈ epif. 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, Định nghĩa 1.10 Cho 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 mọi λ ∈ (0, 1), mọi x, y thuộc C, ta có 1 f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y) − ηλ(1 − λ)||x − y||2 . 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 domf 6= và f (x) > −∞ với mọi x. Hàm f được gọi là đóng, nếu epif là một tập đóng trong Rn+1 . Như đã nói ở trên, nếu f là một hàm lồi trên tập 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.
13 Hiển nhiên fe (x) = f (x) với ∀x ∈ C và fe lồi trên Rn . Hơn nữa fe là chính thường khi và chỉ khi f chính thường. Tương tự fe đóng khi và chỉ khi f đóng. Chú ý rằng, nếu f là một hàm lồi trên Rn thì domf là một tập lồi, vì domf chính là hình chiếu trên Rn của epif , tức là: domf = {x|∃µ ∈ R : (x, µ) ∈ epif }. Sau đây là một số ví dụ về hàm lồi. Ví dụ 1.1 1. Hàm aphin. f (x) := aT x + α, trong đó a ∈ Rn , α ∈ R. Dễ dàng kiểm tra được rằng f là một 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 6= là một tập lồi. 2. Hàm chỉ. Đặt ( 0, nếu x ∈ C, δ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. 3. Hàm mặt cầu. Cho S := {x ∈ Rn | ||x|| = 1} là một mặt cầu và h : S → R+ là một hàm bất kỳ. Định nghĩa hàm f như sau:   0, nếu ||x|| < 1,   f (x) := h(x), nếu ||x|| = 1,    +∞, nếu ||x|| > 1. Hàm này được gọi là hàm mặt cầu. Dễ thấy rằng f là một hàm lồi trên Rn , 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 hy, xi . x∈C
14 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 6. Hàm chuẩn. Giả sử x = (x1 , ..., xn ). f (x) := ||x||1 := max |xj | j hoặc 1 f (x) := ||x|| := (x21 + ... + x2n ) 2 . Định nghĩa 1.11 Cho f : Rn → R ∪ {+∞} và một điểm x0 ∈ Rn sao cho f (x0 ) < +∞. Nếu với một vectơ y ∈ Rn mà giới hạn f (x0 + λy) − f (x0 ) lim λ↓0 λ tồn tại (hữu hạn hay vô hạn), thì ta nói f có đạo hàm theo hướng y tại điểm x0 . 0 Ta sẽ ký hiệu giới hạn này là f (x0 , y). 0 Ví dụ sau đây cho thấy hàm f (x, .) có thể không phải là hàm chính thường mặc dù f là hàm chính thường và x ∈ domf . Cho   0, nếu x < 0,   f (x) := 1, nếu x = 0,    +∞, nếu x > 0. Ta thấy f là hàm lồi, chính thường, domf = (−∞, 0). Dễ thấy rằng 0 0 0 f (0, −1) = −∞, f (0, 0) = 0, f (0, 1) = +∞. Từ định nghĩa của hàm ξ ở trên, ta có 0 ξ(λ) − ξ(0) f (x0 , y) = lim . λ↓0 λ 0 0 Vậy f (x0 , y) chính là đạo hàm phải của ξ tại 0 nếu f (x0 , y) hữu hạn. Ta nhắc lại rằng một hàm f là thuần nhất dương (bậc 1), nếu f (tx) = tf (x) với mọi t > 0 và mọi x trên miền xác định của f . Hàm f
15 được gọi là dưới cộng tính, nếu f (x + y) ≤ f (x) + f (y) với mọi x, y trên miền xác định của f . Hàm dưới tuyến tính là một hàm vừa thuần nhất dương, vừa dưới cộng tính. Đặt f (x + λy) − f (x) ϕ(λ) := . λ Mệnh đề 1.4 Cho f : Rn → R ∪ {+∞} lồi. Khi đó với mọi x ∈ domf và mọi y ∈ Rn , ta có. 0 (i) ϕ là hàm đơn điệu không giảm trên (0, +∞); f (x, y) tồn tại với mọi y ∈ Rn và 0 f (x + λy) − f (x) f (x, y) := inf . λ>0 λ 0 0 (ii) Hàm f (x, .) thuần nhất dương bậc 1. Ngoài ra nếu f (x, .) > −∞ thì: 0 a) Hàm f (x, .) là dưới tuyến tính trên Rn (do đó nó là hàm lồi chính thường trên Rn ). 0 0 b)−f (x, −y) ≤ f (x, y) ∀y ∈ Rn . 0 c) Hàm f (x, .) nhận giá trị hữu hạn trên F khi và chỉ khi x ∈ ri(domf ), trong đó F là không gian con của domf. Chứng minh (i) Ta chứng minh hàm ϕ đơn điệu không giảm trên miền (0, +∞). Cho x ∈ domf và định nghĩa hàm h : R → R ∪ {+∞} bởi h(λ) := f (x + λy) − f (x). Khi đó h(0) = 0. 0 Giả sử 0 < λ ≤ λ. Khi đó, do h là hàm lồi không nhận giá trị −∞, nên ta có 0 0 0 λ λ h(λ ) = h( λ + (1 − )0) λ λ 0 0 0 λ λ λ ≤ h(λ) + (1 − )h(0) ≤ h(λ) λ λ λ