Tài liệu Bài toán cực tiểu hàm lồi và hàm tựa lồi trên tập lồi

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGUYỄN THỊ HUYỀN BÀI TOÁN CỰC TIỂU HÀM LỒI VÀ HÀM TỰA LỒI TRÊN TẬP LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2020 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– NGUYỄN THỊ HUYỀN BÀI TOÁN CỰC TIỂU HÀM LỒI VÀ HÀM TỰA LỒI TRÊN TẬP LỒI 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 - 2020 Lời cam đoan Tôi xin cam đoan số liệu và kết quả nghiên cứu trong luận văn “Bài toán cực tiểu hàm lồi và hàm tựa lồi trên tập lồi” của riêng bản thân tôi dưới sự hướng dẫn khoa học của GS.TSKH. LÊ DŨNG MƯU là trung thực, không có bất kỳ sự sao chép hay sử dụng để bảo vệ một học vị nào và chưa từng được công bố dưới bất kì hình thức nào. Tất cả những sự giúp đỡ cho việc xây dựng cơ sở lý luận cho bài luận đều được trích dẫn đầy đủ và ghi nguồn gốc rõ ràng. Nếu phát hiện có sự sao chép kết quả nghiên cứu của đề tài khác, tôi xin hoàn toàn chịu trách nhiệm. Thái Nguyên, ngày 10 tháng 1 năm 2021 Tác giả NGUYỄN THỊ HUYỀN i Lời cảm ơn Trong thời gian hoàn thành luận văn tôi đã nhận được nhiều sự giúp đỡ, đóng góp ý kiến và chỉ bảo nhiệt tình của GS.TSKH. LÊ DŨNG MƯU. Ngoài ra, trong quá trình học tập và làm luận văn, từ các bài giảng của các Giáo sư, Phó Giáo sư đang công tác tại Viện Toán học, các Thầy Cô trong Trường Đại học Khoa học Thái Nguyên, tôi đã trau dồi thêm rất nhiều kiến thức, kỹ năng phục vụ cho việc nghiên cứu và công tác của bản thân. Từ đáy lòng mình, tôi xin bày tỏ lòng cảm ơn sâu sắc tới các Thầy Cô. Tôi cũng muốn gửi lời cảm ơn bộ môn Toán ứng dụng và tin học. Khoa Toán - Tin Trường Đại học Khoa học Thái Nguyên, đã tạo mọi điều kiện thuận lợi, hướng dẫn, phản biện để tôi có thể hoàn thành tốt luận văn này. Do thời gian có hạn, bản thân tôi còn hạn chế nên luận văn có thể có những thiếu sót. Tôi mong muốn nhận được ý kiến phản hồi, đóng góp và xây dựng của các thầy cô, và các bạn. Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 10 tháng 1 năm 2021 Tác giả NGUYỄN THỊ HUYỀN ii Mục lục Lời cam đoan i Lời cảm ơn ii Mục lục iv Danh mục các ký hiệu, các chữ viết tắt v Lời mở đầu 1 1 Hàm lồi, hàm tựa lồi trên tập lồi 3 1.1 1.2 1.3 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . 3 1.1.2 Tổ hợp lồi và các tính chất cơ bản . . . . . . . . . . 4 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Định nghĩa, ví dụ . . . . . . . . . . . . . . . . . . . 6 1.2.2 Các tính chất cơ bản . . . . . . . . . . . . . . . . . 8 1.2.3 Dưới vi phân của hàm lồi . . . . . . . . . . . . . . . 11 Hàm tựa lồi . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.1 Định nghĩa, ví dụ . . . . . . . . . . . . . . . . . . . 13 1.3.2 Các tính chất cơ bản . . . . . . . . . . . . . . . . . 14 1.3.3 Đạo hàm và dưới vi phân của hàm tựa lồi . . . . . . 16 2 Bài toán cực tiểu hàm lồi và hàm tựa lồi 2.1 Bài toán cực tiểu hàm lồi . . . . . . . . . . . . . . . . . . . iii 22 22 2.2 2.1.1 Phát biểu bài toán, ví dụ . . . . . . . . . . . . . . . 22 2.1.2 Một thuật toán chiếu dưới đạo hàm . . . . . . . . . 28 Bài toán cực tiểu hàm tựa lồi . . . . . . . . . . . . . . . . . 28 2.2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 29 2.2.2 Một thuật toán chiếu dưới đạo hàm . . . . . . . . . 29 Kết luận 36 Tài liệu tham khảo 37 iv Một số ký hiệu và chữ viết tắt Rn không gian Euclide n−chiều R = R ∪ {−∞, +∞} trục số thực mở rộng xT chuyển vị của x coA bao lồi của A coA bao lồi đóng của A ri(A) tập điểm trong tương đối của tập A int(A) tập hợp các điểm trong của A f hàm bao đóng của f domf miền hữu dụng của f epif trên đồ thị của f ∂f (x) dưới vi phân của f tại x 2 kết thúc chứng minh v Lời mở đầu Ngày nay, lý thuyết về các tập lồi, hàm lồi và hàm tựa lồi có một ví trí quan trọng trong toán học nói chung, trong giải tích nói riêng cụ thể liên quan đến hầu hết các ngành như giải tích hàm, hình học, toán kinh tế, giải tích lồi,...Trong đó có một tính chất cơ bản của hàm lồi được sử dụng rộng rãi trong toán học đó là: bất kì cực tiểu địa phương nào cũng có cực tiểu toàn cục. Cực tiểu hàm lồi và hàm tựa lồi trên tập lồi là một lớp bài toán cơ bản của tối ưu hóa. Cực tiểu hàm lồi trên tập lồi gọi là quy hoạch lồi, có tính chất cơ bản là mọi điểm cực tiểu địa phương đều là cực tiểu tuyệt đối. Tính chất quan trọng này cho phép các lý thuyết có tính địa phương như giới hạn, vi phân,... có thể áp dụng vào quy hoạch lồi. Lý thuyết về bài toán quy hoạch lồi đã được nghiên cứu nhiều và đã thu được nhiều kết quả quan trọng dựa trên lý thuyết của giải tích lồi và tối ưu hóa. Mục tiêu của luận văn là giới thiệu một số kiến thức cơ bản về hàm lồi và hàm tựa lồi. Đặc biệt nội dung chính của luận văn sẽ tập trung đi sâu vào dưới vi phân của hàm lồi và hàm tựa lồi. Tiếp đến sẽ giới thiệu hai thuật toán chiếu dưới đạo hàm để giải bài toán cực tiểu hàm lồi và hàm tựa lồi trên tập lồi. Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, luận văn gồm hai chương sau: Chương 1. Hàm lồi, hàm tựa lồi trên tập lồi Trong chương này chúng tôi giới thiệu tổng quan và trình bày về một 1 số khái niệm cơ bản, tính chất và ví dụ minh họa của tập lồi, hàm lồi, hàm tựa lồi được trích dẫn trong tài liệu số [1] và [2], đặc biệt đi sâu vào khái niệm dưới vi phân hàm lồi và hàm tựa lồi. Chương 2. Bài toán cực tiểu hàm lồi và hàm tựa lồi Đây là phần chính của luận văn, trong chương này, chúng tôi trình bày bài toán cực tiểu hàm lồi và hàm tựa lồi, các ví dụ minh họa. Phần cuối của luận văn sẽ trình bày về hai thuật toán chiếu dưới đạo hàm được trích dẫn trong tài liệu số [2], [3], [4], [5] và [6]. Tôi xin chân thành cảm ơn! 2 Chương 1 Hàm lồi, hàm tựa lồi trên tập lồi Chương mở đầu của luận văn chúng tôi trình bày khái niệm, một số tính chất cơ bản của tập lồi, hàm lồi, hàm tựa lồi và các ví dụ minh họa. Đặc biệt phần cuối của chương sẽ đi sâu vào khái niệm dưới vi phân hàm lồi và hàm tựa lồi. Các kiến thức ở chương này được tổng hợp từ các tài liệu [1] và [2]. 1.1 Tập lồi Phần mở đầu của chương này chúng tôi trình bày về một số định nghĩa, ví dụ và các tính chất cơ bản của tập lồi. 1.1.1 Định nghĩa và ví dụ Một đường thẳng nối hai điểm (hai véc tơ) a, b trong Rn là tập hợp tất cả các véc tơ x ∈ Rn có dạng {x ∈ Rn | x = αa + βb, α, β ∈ R, α + β = 1} . Đoạn thẳng nối hai điểm a và b trong Rn là tập hợp các véc tơ x có dạng {x ∈ Rn | x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1} . 3 Định nghĩa 1.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. Ví dụ 1.1.2. Các tam giác và hình tròn trong mặt phẳng là các tập lồi. Hình cầu đơn vị trong không gian Banach là tập lồi. Định nghĩa 1.1.3. Giả sử A ⊂ C , khi đó giao của tất cả các tập lồi chứa A được gọi là bao lồi (convex hull) của tập A và kí hiệu là coA. Nhận xét 1.1.4. Từ định nghĩa trên ta rút ra được nhận xét sau: • coA là một tập lồi. Đó là tập lồi nhỏ nhất chứa A. • A lồi khi và chỉ khi A = coA. Định nghĩa 1.1.5. Giả sử A ⊂ C , khi đó giao của tất cả các tập lồi đóng chứa A được gọi là bao lồi đóng của tập A và kí hiệu là coA. Nhận xét 1.1.6. coA là một tập lồi đóng. Đó là tập lồi đóng nhỏ nhất chứa A. 1.1.2 Tổ hợp lồi và các tính chất cơ bản Định nghĩa 1.1.7. Tổ hợp tuyến tính n P λi xi gọi là tổ hợp lồi của x1 , . . . , xn ∈ i=1 Rn nếu λi ≥ 0, ∀i, n X λi = 1. i=1 Mệnh đề 1.1.8. Giả sử C là tập lồi, x1 , . . . , xn ∈ C . Khi đó, C chứa tất cả các tổ hợp lồi của x1 , . . . , xn . 4 Định nghĩa 1.1.9. Một tập C được gọi là tập affine 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 affine là một trường hợp riêng của tập lồi. Định nghĩa 1.1.10. Tương tự như tổ hợp lồi, x được gọi là tổ hợp affine của các điểm (véc tơ) x1 , . . . , xn ∈ Rn nếu x= k X j=1 λj xj , k X λj = 1, λj > 0, ∀j = 1, . . . , k. j=1 Tập hợp của các tổ hợp affine của các điểm (véc tơ) x1 , . . . , xn ∈ Rn thường được gọi là bao affine của các điểm (véc tơ) này. Nhận xét 1.1.11. Một tổ hợp affine x = Pk j=1 λj xj với các λj > 0, ∀j = 1, . . . , k sẽ được gọi là một tổ hợp lồi của các điểm (véc tơ) x1 , ..., xk . Mệnh đề 1.1.12. Cho X là tập khác rỗng, X được gọi là tập affine khi và chỉ khi nó có dạng X = L + a với L là một không gian con và a ∈ X . Hơn nữa không gian con L này là duy nhất. Định nghĩa 1.1.13. (Toán tử chiếu lên tập lồi đóng) Cho C là một tập lồi đóng khác rỗng của R. Gọi y là một véc tơ bất kì, đặt dC (y) := inf||x − y|| ∀x ∈ C. Khi đó ta nói dC (y) là khoảng cách từ y tới 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 . Định lý 1.1.14. (Định lý tồn tại duy nhất) Cho C là một tập lồi đóng khác rỗng. Khi đó: 5 (i) Với mọi y ∈ R, π ∈ C hai tính chất sau là tương đương: a) π = pC (y), b) y − π ∈ NC (π), trong đó NC (π) là nón pháp tuyến của tập C tại π . (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) kpC (x) − pC (y)k ≤ kx − yk ∀x, ∀y , (tính không giãn). b) hpC (x) − pC (y), x − yi ≥ kpC (x) − pC (y)k2 , (tính đồng bức). 1.2 Hàm lồi Trong mục này chúng tôi trình bày định nghĩa về hàm lồi, các tính chất cơ bản của hàm lồi, ví dụ, đặc biệt đi sâu vào khái niệm, tính chất cơ bản của dưới vi phân hàm lồi. 1.2.1 Định nghĩa, ví dụ Cho C ⊆ Rn là tập lồi và một ánh xạ f : C → R. Ta kí hiệu domf := {x ∈ C | f (x) < +∞} Tập domf được gọi là miền hữu dụng (effective domain) của f. Tập epif := {(x, µ) ∈ C × R | f (x) ≤ µ} 6 được gọi là trên đồ thị (epigraph) của hàm f. Định nghĩa 1.2.1. Cho C là tập khác rỗng, C ⊆ Rn là lồi và f : C → R. Khi đó ta nói f là hàm lồi (convex function) trên C , nếu epif là một tập lồi trong Rn+1 . Xét hàm f : Rn → R ∪ {+∞}, định nghĩa trên là tương đương với f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1). (1.1) Hàm f : Rn → R ∪ {+∞} được gọi là lồi chặt (strictly convex function) trên C nếu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x, y ∈ C, ∀λ ∈ (0, 1). (1.2) Hàm f : Rn → R ∪ {+∞} được gọi là lồi mạnh (strongly convex function) trên C với hệ số η > 0, nếu ∀x, y ∈ C, ∀λ ∈ (0, 1) ta có: 1 f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − ηλ(1 − λ)kx − yk2 . 2 (1.3) Hàm f : Rn → R ∪ {+∞} được gọi là một hàm lõm (concave function) trên C , nếu −f lồi trên C . Ví dụ 1.2.2. Hàm affine f (x) := aT x + α trong đó a ∈ Rn , α ∈ R được gọi là hàm lồi. Hơn nữa khi α = 0, thì hàm trên được gọi là hàm tuyến tính. Định nghĩa 1.2.3. Cho f : Rn → R ∪ {+∞} và 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 ∈ C , ta có: 1 f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y) − ηλ(1 − λ)kx − yk2 . 2 Nếu η = 0 thì f là hàm lồi trên C . Hơn nữa nếu η > 0 thì f là hàm lồi mạnh trên C với hệ số η. 7 Một hàm f được gọi là chính thường (proper function) nếu domf 6= 0 và f (x) > −∞ với mọi x. Hàm f được gọi là đóng (closed function), nếu epif là một tập đóng trong Rn+1 . Mệnh đề 1.2.4. Nếu f là một hàm lồi trên Rn thì các tập mức Lf (α) := {x|f (x) ≤ α}, lf (α) := {x|f (x) < α} là lồi với mọi α ∈ R. 1.2.2 Các tính chất cơ bản Định nghĩa 1.2.5. Cho E là một tập lồi đóng khác rỗng, một hàm f : Rn → R được gọi là nửa liên tục dưới đối với E tại một điểm x, nếu như với mọi dãy xk ⊂ E , xk → x ta có lim inff (xk ) ≥ f (x). Hàm f được gọi là nửa liên tục trên, đối với E , tại x nếu −f nửa liên tục dưới, đối với E , tại x. Nói một cách khác với mọi dãy xk ⊂ E , xk → x thì lim supf (xk ) ≤ f (x). Hàm f được gọi là liên tục đối với E, tại x nếu như nó vừa nửa liên tục trên và nửa liên tục dưới, đối với E , tại x. Mệnh đề 1.2.6. (Tính liên tục) Cho f : Rn → R ∪ {+∞}, khi đó các điều kiện sau là tương đương: (i) Trên đồ thị của f là một tập đóng trên Rn+1 , tức là f = f . (ii) Với mọi số thực α, tập mức dưới Lf (α) := {x|f (x) ≤ α} là một tập đóng. (iii) Hàm f là nửa liên tục dưới trên R. Chứng minh. Ta sẽ tiến hành chứng minh các điều kiện trên là tương đương: (i) → (ii). Giả sử xj → x, f (xj ) ≤ α. Khi đó (xj , α) ∈ epif . 8 Do đó epif đóng nên (x, α) ∈ epif . Vậy x ∈ Lf (α). (ii) → (iii). Giả sử xj → x. Nếu lim inff (xj ) < f (x), khi đó tồn tại α < f (x) sao cho f (xj ) ≤ α với mọi j đủ lớn. Vậy xj ∈ Lf (α). Do xj → x và Lf (α) đóng nên x ∈ Lf (α). Tức là f (x) ≤ α điều này mâu thuẫn với giả thiết α < f (x). (iii) → (i). Giả sử (xj , µj ) ∈ epif và (xj , µj ) → (x, µ). Khi đó f (xj ) ≤ µj với mọi j. Do (iii), suy ra lim inff (xj ) ≥ f (x). Vậy µ ≥ f (x). Suy ra (x, µ) ∈ epif do đó epif là tập đóng. Mệnh đề 1.2.7. Cho f là một hàm lồi chính thường trên Rn và x0 ∈ int(domf ), khi đó các điều kiện sau là tương đương. (i) f liên tục tại điểm x0 . (ii) f bị chặn trên trong lân cận của x0 . (iii) int(epif ) 6= ∅. (iv) int(domf ) 6= ∅ và f liên tục trên tập int(domf ). Mệnh đề 1.2.8. Giả sử f là một hàm lồi chính thường trên Rn . Khi đó f liên tục tại mọi điểm x ∈ int(domf ). Nếu f nhận giá trị thực trên toàn không gian, thì nó liên tục tại mọi điểm. Hệ quả 1.2.9. Cho f là một hàm lồi chính thường trên Rn . Khi đó với mọi tập com-pắc C ⊆ int(domf ), tập f (C) là com-pắc. Định nghĩa 1.2.10. Một hàm f : Rn → R được gọi là Lipschitz địa phương tại x với hằng số Lipschitz L nếu tồn tại một lân cận U của x sao cho ||f (x) − f (y)|| 6 L||x − y|| ∀x, y ∈ U. Hàm f được gọi là Lipschitz địa phương trên D nếu nó Lipschitz địa phương tại mọi điểm thuộc D. 9 Hàm lồi còn có tính liên tục Lipschitz. Mệnh đề sau đây sẽ chỉ ra mối liên hệ đó. Mệnh đề 1.2.11. (Tính Lipschitz) Giả sử f là một hàm lồi chính thường trên Rn và bị chặn trên trong một lân cận của một điểm nào đó thuộc một tập mở D ⊆ domf . Khi đó f Lipschitz địa phương trên tập D. Chứng minh. Giả sử 0 ∈ D và f (x) ≤ γ < ∞ với mọi x ∈ B , trong đó  > 0 và B là quả cầu mở đơn vị có tâm ở gốc. Giả sử x ∈ D. Khi đó tồn tại ρ > 1 sao cho điểm y = ρx ∈ D, Với λ = 1 ρ tập hợp V := {v|v = (1 − λ)x0 + λy, x0 ∈ B}, là một lân cận của điểm x := λy. Do f lồi và bị chặn trên bởi γ trong tập B, nên với mọi v ∈ V, ta có: f (v) ≤ (1 − λ)f (x0 ) + λf (y) ≤ (1 − λ)γ + λf (y). (1.4) Vậy f bị chặn trên trong lân cận V của x. Hơn nữa với mọi z ∈ V , tồn tại z 0 ∈ V sao cho x = 1 (z + z 0 ). Vì f 2 là hàm lồi nên ta có: 1 1 f (x) ≤ f (z) + f (z 0 ). 2 2 Từ đây và (1.4), ta được f (z) ≥ 2f (x) − f (z 0 ) ≥ 2f (x) − (1 − λ)γ − λf (y). Vậy f bị chặn dưới trên V. Kết hợp lại ta có f bị chặn trong tập V. Do D mở thuộc domf . Chọn δ > 0 sao cho quả cầu B(x) := x + 2δB ⊂ D và |f (u)| ≤ L0 < ∞ với mọi u ∈ B(x). Lấy x1 , x2 ∈ x + δB, x1 6= x2 . Ký hiệu α = ||x1 − x2 || và đặt x3 = x2 + δ (x2 − x1 ). α 10 (1.5) Khi đó x3 ∈ B(x), bởi vì x2 ∈ x + δB. Theo (1.5) ta có: x2 = δ α x1 + x3 α+δ α+δ Do f lồi, nên f (x2 ) ≤ α δ f (x1 ) + f (x3 ) α+δ α+δ Suy ra α f (x2 ) − f (x1 ) ≤ [f (x3 ) − f (x1 )] α+δ α α ≤ |f (x3 ) − f (x1 )| ≤ (|f (x1 )| + |f (x3 )|) δ δ Do |f (x1 )| ≤ L0 , |f (x3 )| ≤ L0 và α = kx1 − x2 k , nên ta có: f (x2 ) − f (x1 ) ≤ 2L0 kx1 − x2 k δ Thay đổi vai trò của x1 và x2 , ta có: f (x1 ) − f (x2 ) ≤ 2L0 kx1 − x2 k δ Kết hợp lại |f (x1 ) − f (x2 )| ≤ 2L0 ||x1 − x2 || ∀x1 , x2 ∈ x + δB δ Vậy f Lipschizt trong lân cận x + δB của x với hằng số là L = 2L0 . δ Hệ quả 1.2.12. Nếu f : Rn → R lồi, thì f Lipschitz địa phương trên toàn Rn (do đó liên tục). 1.2.3 Dưới vi phân của hàm lồi Cho một hàm n biến. Khi cố định một hướng và xét hàm nhiều biến trên hướng đó, thì ta có một hàm một biến. Giả sử y 6= 0 là một hướng cho trước xuất phát từ điểm x0 . Khi đó mọi điểm x thuộc đường thẳng đi qua x0 và có hướng y đều có dạng x = x0 + λy với λ ∈ R. Nếu đặt ζ(λ) := f (x0 + λy) 11 suy ra ζ lồi trên R khi và chỉ khi f lồi trên Rn . Định nghĩa 1.2.13. (Đạo hàm theo hướng) Cho f : Rn → R ∪ {+∞} và x0 ∈ R sao cho f (x0 ) < +∞. Nếu với một véc tơ y ∈ Rn mà giới hạn f (x0 + λy) − f (x0 ) x→0 λ lim 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 . Ta sẽ ký hiệu giới hạn này là f 0 (x0 , y). Định nghĩa 1.2.14. (Dưới vi phân) Cho f : Rn → R ∪ {+∞} ta nói x∗ ∈ Rn là dưới đạo hàm của hàm f tại x nếu hx∗ , z − xi + f (x) 6 f (z) ∀z. Ký hiệu tập hợp tất cả các dưới đạo hàm của f tại x là ∂f (x). Tập ∂f (x) có thể bằng rỗng trong Rn . Khi ∂f (x) 6= ∅, thì ta nói hàm f khả dưới vi phân tại x. Theo định nghĩa trên, một điểm x∗ ∈ ∂f (x) khi và chỉ khi nó thỏa mãn một hệ vô hạn các bất đẳng thức tuyến tính. Như vậy ∂f (x) là giao của các nửa không gian đóng. Vậy ∂f (x) luôn là một tập lồi đóng. Ví dụ 1.2.15. Cho hàm f (x) = ||x||, x ∈ Rn . Tại điểm x = 0 hàm này không khả vi, nhưng nó khả dưới vi phân và ∂f (0) = {x∗ | hx∗ , xi 6 ||x||, ∀x} . Mệnh đề 1.2.16. Cho f : Rn → R ∪ {+∞} là hàm lồi, chính thường. Khi đó ta có: (i) x∗ ∈ ∂f (x) khi và chi khi f 0 (x, y) ≥ hx∗ , yi ∀y. Nếu x ∈ ri(domf ) thì 12 f 0 (x, y) = supx∗ ∈∂f (x) hx∗ , yi với mọi y. (ii) Nếu f là hàm lồi chính thường trên Rn thì với mọi x ∈ dom(∂f ), ta có: f (x) = f¯(x) và ∂f (x) = ∂ f¯(x). Mệnh đề 1.2.17. Cho f : Rn → R ∪ {+∞} là hàm lồi, chính thường. Khi đó (i) Nếu x ∈ / dom f thì ∂f (x) = ∅. (ii) Nếu x ∈ int(domf ) thì ∂f (x) 6= ∅ và com-pắc. Ngược lại, nếu ∂f (x) 6= ∅, com-pắc thì x ∈ ri(domf ). 1.3 Hàm tựa lồi Trong mục này chúng tôi trình bày định nghĩa về hàm tựa lồi, các tính chất cơ bản của hàm lồi, ví dụ minh họa, đặc biệt đi sâu vào khái niệm, tính chất cơ bản của dưới vi phân hàm tựa lồi. 1.3.1 Định nghĩa, ví dụ Định nghĩa 1.3.1. Cho Γ là một tập con của Rn , một hàm θ xác định trên Γ ⊂ Rn được gọi là tựa lồi (quasiconvex) tại x ∈ Γ nếu   x∈Γ      θ(x) ≤ θ(x̄)  ⇒ θ[(1 − λ)x̄ + λx] ≤ θ(x̄),   0≤λ≤1     (1 − λ)x̄ + λx ∈ Γ  θ được gọi là tựa lồi trên Γ nếu nó là tựa lồi tại mỗi điểm x ∈ Γ. Định nghĩa 1.3.2. Một hàm θ xác định trên Γ ⊂ Rn được gọi là tựa lồi 13