Luận văn Thạc sĩ Toán học: Về sự phát triển của điều kiện tối ưu trong bài toán quy hoạch lồi

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

Thêm vào BST

Báo xấu

16
lượt xem 3
download

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

Mục đích của luận văn là tổng kết lại giai đoạn phát triển của điều kiện tối ưu trong bài toán quy hoạch lồi và xét đến các ứng dụng của chúng trong việc xây dựng phương pháp giải. Trên cơ sở đó khảo sát đến một số ứng dụng trong việc giải bài toán quy hoạch lồi. 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: Về sự phát triển của điều kiện tối ưu trong bài toán quy hoạch lồi

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG THỊ HOA VỀ SỰ PHÁT TRIỂN CỦA ĐIỀU KIỆN TỐI ƯU TRONG BÀI TOÁN QUY HOẠCH LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG THỊ HOA VỀ SỰ PHÁT TRIỂN CỦA ĐIỀU KIỆN TỐI ƯU TRONG BÀI TOÁN QUY HOẠCH LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Toán ứng dụng Mã số: 60.46.01.12 NGƯỜI HƯỚNG DẪN KHOA HỌC GS. TSKH. LÊ DŨNG MƯU Thái Nguyên - 2017
i Mục lục Lời cảm ơn ii Bảng ký hiệu 1 Mở đầu 2 1 Các kiến thức chuẩn bị về giải tích lồi 3 1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Các định nghĩa cơ bản về tập lồi . . . . . . . . . 3 1.1.2 Toán tử chiếu tập lồi . . . . . . . . . . . . . . . . 12 1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Điều kiện tối ưu của bài toán quy họach lồi 23 2.1 Bài toán quy hoạch lồi . . . . . . . . . . . . . . . . . . . 23 2.2 Điều kiện cần và đủ tối ưu . . . . . . . . . . . . . . . . . 24 2.2.1 Điều kiện tối ưu theo nguyên lý Fermat của bài toán tối ưu không ràng buộc hàm một biến khả vi 24 2.2.2 Điều kiện với ràng buộc hình học . . . . . . . . . 33 2.2.3 Điều kiện có ràng buộc đẳng thức và bất đẳng thức . . . . . . . . . . . . . . . . . . . . . . . . . 37 Kết luận 56 Tài liệu tham khảo 57
ii Lời cảm ơn Trước khi trình bày nội dụng chính của bài luận văn, em xin bày tỏ lời lòng biết ơn sâu sắc tới GS.TSKH. Lê Dũng Mưu người đã tận tình hướng dẫn và giúp đỡ em trong suốt quá trình học tập và nghiên cứu để em có thể hoàn thành luận văn này. Em xin bày tỏ lòng biết ơn chân thành tới quý thầy, cô giáo trường Đại học Khoa Học - Đại học Thái Nguyên đã giảng dạy và giúp đỡ em hoàn thành khóa học. Em xin chân thành cảm ơn Ban Giám hiệu, quý thầy cô giáo khoa Toán - Tin trường Đại học Khoa Học - Đại học Thái Nguyên, gia đình và bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện cho em về mọi mặt trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp. Để hoàn thành được khóa luận bản thân em đã cố gắng rất nhiều nhưng Luận văn khó tránh khỏi những thiếu sót. Tác giả rất mong muốn nhận được ý kiến đóng góp của quý thầy, cô và bạn đọc để luận văn được hoàn thiện hơn. Xin trân trọng cảm ơn! Thái Nguyên, ngày ... tháng ... năm 2017 Tác giả luận văn DƯƠNG THỊ HOA
1 Bảng ký hiệu R trường số thực Rn không gian Euclide n-chiều B là hình cầu đơn vị mở trong Rn B(0, 1) hình cầu đơn vị, đóng tâm ở 0 Rm + orthant không âm của Rm ∂f (x) dưới vi phân của hàm lồi f tại x δC (.) hàm chỉ của tập C L(x, µ, ν) hàm Lagrange f 0 (x), f 00 (x), đạo hàm (bậc 1 và bậc 2) của hàm số f (x) ∇f Gradient của hàm f ∇2 f ma trận Hessian f h., .i tích vô hướng trong Rn ∂f dưới vi phân của hàm f
2 Mở đầu Bài toán quy hoạch lồi là phần quang trọng của lý thuyết tối ưu. Trong lý thuyết tối ưu, thì điều kiện tối ưu là rất quan trọng, nó nghiên cứu tính chất nghiệm, đề suất phương pháp giải. Lý thuyết về bài toán quy hoạch lồi đã được quan tâm nghiên cứu nhiều và từ lâu đã đạt được nhiều kết quả quan trọng dựa trên các kết quả của Giải tích lồi và tối ưu hóa. Về phương diện tính toán đã có khá nhiều phương pháp hữu hiệu cho lớp toán này. Trong quá trình học và tìm hiểu về điều kiện tối ưu trong bài toán quy hoạch lồi ta thấy sự phát triển của bài toán rất phong phú và nhiều vấn đề được nối tiếp rất khoa học và hay. Mục đích của luận văn là tổng kết lại giai đoạn phát triển của điều kiện tối ưu trong bài toán quy hoạch lồi và xét đến các ứng dụng của chúng trong việc xây dựng phương pháp giải. Trên cơ sở đó khảo sát đến một số ứng dụng trong việc giải bài toán quy hoạch lồi. Tổng hợp lại lý thuyết tối ưu thì điều kiện tối ưu là rất quan trọng vì chúng cho phép nghiên cứu tính chất nghiệm, xây dựng các phương pháp giải. Điều kiện tối ưu được dựa trên nguyên lý Fermat trong bài toán cực trị không có nghiệm ràng buộc của hàm một biến khả vi đã được học trong chương trình PTTH. Theo đó người ta đã phát triển nguyên lí này bài quy hoạch có ràng buộc của hàm nhiều biến không nhất thiết khả vi. Bản luận văn, ngoài phần mở đầu và tài liệu tham khảo còn có hai chương chính cụ thể là: Chương 1 trình bày các kiến thức cơ bản nhất về Giải tích lồi. Chương 2 giới thiệu bài toán tối ưu và đặc biệt đi sâu vào sự phát triển của các điều kiện tối ưu cho các lớp bài toán tối ưu lồi.
3 Chương 1 Các kiến thức chuẩn bị về giải tích lồi Chương này chủ yếu nhắc lại một số khái niệm, định nghĩa và kết quả cần thiết liên quan đến tập lồi và hàm lồi. Nội dung chương này tham khảo từ các tài liệu [1], [2]. 1.1 Tập lồi 1.1.1 Các định nghĩa cơ bản về tập lồi Đị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. Ta nói x là tổ hợp lồi của các điểm (véc - tơ) 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 a-phin của các điểm (véc - tơ) 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 a-phin của x1 , ..., xk thường được gọi là bao a-phin của các điểm này.
4 Định lý 1.1.2 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à: 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ử định lý đú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 . (1.1) j=1 j=1 ξ Do k−1 X λj =1 j=1 ξ λj và > 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 .
5 k X Do ξ > 0, λk > 0 và ξ + λk = λj = 1, nên x là một tổ hợp lồi của j=1 k hai điểm y và x đều thuộc C. Vậy x ∈ C. Lớp các tập lồi là đóng với các phép giao, phép cộng đại số và phép nhân tích Descartes. Cụ thể, ta có định lý sau: Định lý 1.1.3 Nếu A, B là các tập lồi trong Rn , C là lồi trong Rm , thì các tập sau là lồi: A ∩ B := {x|x ∈ A, x ∈ B}, λA + βB := {x|x = αa + βb, a ∈ A, b ∈ B, λ, β ∈ R}, A × C := {x ∈ Rn+m |x = (a, c) : a ∈ A, c ∈ C}. Chứng minh. Dễ dàng được suy ra trực tiếp từ định nghĩa. Định nghĩa 1.1.4 Một tập C được gọi là tập a-phin 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 a-phin là một trường hợp riêng của tập lồi. Như đã nêu, một ví dụ điển hình của tập a-phin là các không gian con. Một ví dụ khác về tập a-phin là siêu phẳng được định nghĩa dưới đây. Định nghĩa 1.1.5 Siêu phẳng trong không gian Rn là một tập hợp các điểm có dạng {x ∈ Rn |aT x = α}, trong đó a ∈ Rn là một véc - tơ khác 0 và α ∈ R. Véc - tơ a thường được gọi là véc - tơ 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.1.6 Nửa không gian là một tập hợp có dạng {x|aT x ≥ α},
6 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ư vậy một siêu phẳng chia không gian ra làm hai nửa không gian, mỗi nửa không gian ở về một phía của siêu phẳng. Nếu hai nửa không gian này là đóng thì phần chung của chúng chính là siêu phẳng đó. Mệnh đề dưới đây cho thấy tập a-phin chính là ảnh tịnh tiến của một không gian con. Định lý 1.1.7 M 6= ∅ là tập a-phin khi và chỉ khi nó có dạng M = L + a với L là một không gian con và a ∈ M . Không gian con L này được xác định duy nhất. Không gian L trong định lý trên được gọi là không gian con song song với M , hoặc nói ngắn gọn hơn là không gian con của M . Thứ nguyên (hay chiều) của một tập a-phin M được định nghĩa bởi thứ nguyên của không gian song song với M và được ký hiệu là dim M . Định nghĩa 1.1.8 Một tậ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. Như vậy, 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 |haj , xi ≤ bj , j = 1, ..., m}. Hoặc nếu ta ký hiệu A là ma trận có m hàng là các véc - tơ aj (j = 1, ..., m) và véc - tơ 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, xi = b 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,
7 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. Định nghĩa 1.1.9 Một tập C được gọi là nón nếu ∀λ > 0, ∀x ∈ C ⇒ λx ∈ C. Theo định nghĩa, ta thấy rằng gốc tọa độ có thể thuộc nón hoặc không thuộc nón. Dĩ nhiên một nón không nhất thiết là một tập lồi. Ví dụ C := {x ∈ R|x 6= 0} là một nón, nhưng không lồi. Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi. Một nón lồi được gọi là nón nhọn nếu nó không chứa đường thẳng. Khi đó ta nói 0 là đỉnh của nón. Nếu nón lồi này lại là một tập lồi đa diện thì ta nói nó là nón lồi đa diện. Một ví dụ điển hình của nón lồi đa diện, thường được sử dụng, là tập hợp nghiệm của hệ bất phương trình tuyến tính có dạng {x|Ax ≥ 0}, với A là một ma trận thực cấp hữu hạn (số dòng và số cột là hữu hạn). Định lý 1.1.10 Một tập C là nón lồi khi và chỉ khi nó có các tính chất sau: (i) λC ⊆ C ∀λ > 0, (ii) C + C ⊆ C. Chứng minh. Giả sử C là một nón lồi. Do C là một nón, nên ta có 1 (i). Do C là một tập lồi, nên với mọi x, y ∈ C, thì (x + y) ∈ C. Vậy 2 theo (i) ta có x + y ∈ C. Ngược lại, giả sử có (i) và (ii). Từ (i) suy ra ngay C là một nón. Giả sử x, y ∈ C và λ ∈ [0, 1]. Từ (i) suy ra λx ∈ C, và (1 − λ)y ∈ C. Theo (ii) có λx + (1 − λ)y ∈ C. Vậy C là một nón lồi. Một số nón điển hình. Dưới đây ta sẽ xét một số nón lồi điển hình thường được sử dụng trong giải tích lồi. Tập lồi có một đặc trưng là: một tia xuất phát từ một điểm thuộc nó, thì hoặc nằm hẳn trong tập này hoặc một khi đã ra khỏi tập này thì sẽ không "trở lại".
8 Định nghĩa 1.1.11 Cho C là một tập lồi trong Rn . Một véc - tơ y 6= 0 được gọi là hướng lùi xa của C, nếu mọi tia xuất phát từ một điểm bất kỳ của C theo hướng y đều nằm trọn trong C, tức là: y là hướng lùi xa khi và chỉ khi x + λy ∈ C ∀x ∈ C, ∀λ ≥ 0. Một hướng lùi xa còn được gọi là hướng vô hạn . Ta sẽ ký hiệu tập hợp của tất cả các hướng lùi xa của C cùng với điểm gốc là reC. Tập hợp này được gọi là nón lùi xa của C. Hiển nhiên nếu C là một tập bị chặn, thì reC chỉ gồm duy nhất điểm gốc. Chú ý rằng, nếu C là một tập lồi đóng, thì trong định nghĩa trên, thay vì đòi hỏi với mọi x ∈ C, chỉ cần đòi hỏi cho một điểm x ∈ C. Cụ thể ta có định lý sau: Định lý 1.1.12 Giả sử C là một tập lồi đóng. Khi đó y là một hướng lùi xa của C khi và chỉ khi x + λy ∈ C ∀λ ≥ 0, với một điểm x nào đó thuộc C. Chứng minh. Giả sử x + λy ∈ C ∀λ > 0, với x ∈ C. Thế thì với mọi u ∈ C và mọi µ > 0, do C lồi, ta có µ µ xλ := (x + λy) + (1 − )u ∈ C. λ+µ λ+µ Cho λ → ∞, do C đóng, ta thấy u + µy ∈ C, với mọi u ∈ C và µ > 0. Chú ý. Trong trường hợp C không đóng, định lý trên không đúng. Ví dụ, trong R2 lấy C := {x = (x1 , x2 )|x1 > 0, x2 > 0} ∪ {0}. Hiển nhiên véc - tơ y = (0, 1) có tính chất là mọi tia xuất phát từ một điểm 0 6= x ∈ C theo hướng này đều nằm trọn trong C, nhưng nếu xuất phát từ x = 0 thì điều này không đúng. Cho C ⊆ Rn là một tập lồi và x ∈ C. Ký hiệu NC (x) := {w|hw, y − xi ≤ 0 ∀y ∈ C}.
9 Hiển nhiên 0 ∈ NC (x). Dùng định nghĩa, dễ kiểm tra được rằng NC (x) là một nón lồi đóng. Nón này được gọi là nón pháp tuyến ngoài của C tại x. Tập −NC (x) được gọi là nón pháp tuyến trong của C tại x. Hiển nhiên −NC (x) := {w|hw, y − xi ≥ 0 ∀y ∈ C}. Một nón quan trọng khác là nón đối cực được định nghĩa như sau: C ∗ := {w|hw, xi ≤ 0 ∀x ∈ C}. Dễ thấy rằng đây cũng là một nón lồi đóng chứa gốc. Cho C là một tập lồi khác rỗng và x ∈ C. Ta nói d ∈ Rn là một hướng chấp nhận được của C nếu tồn tại t0 > 0 sao cho x + td ∈ C với mọi 0 ≤ t ≤ t0 . Tập tất cả các hướng chấp nhận được là một nón lồi (dễ kiểm tra) chứa gốc. Ta sẽ ký hiệu nón này là FC (x) và sẽ gọi là nón các hướng chấp nhận được hoặc nói ngắn gọn là nón chấp nhận được. Nón này có thể không đóng, tuy nhiên nếu lấy bao đóng, ta sẽ dược một nón khác gọi là nón tiếp xúc của C tại x. Ký hiệu nón này là TC (x), thì FC (x) = TC (x). Từ đây suy ra TC (x) = {d ∈ Rn |∃dk → d, ∃tk & 0 : x + tk dk ∈ C ∀k}. Định nghĩa 1.1.13 Bao lồi của một tập E là giao của tất cả các tập lồi chứa E. Tương tự, ta định nghĩa bao a-phin của E là giao của tất cả các tập a-phin chứa E, và bao nón lồi của tập E (còn gọi là nón lồi sinh bởi E) là giao của tất cả các nón lồi chứa E. Bao lồi của một tập E sẽ được ký hiệu là coE; bao a-phin của một tập E sẽ được ký hiệu là af f E, còn bao nón lồi của E sẽ được ký hiệu là coneE. Do tính chất của nón, nên nếu một điểm x ∈ coneE, thì λx ∈ coneE với mọi λ > 0. Do đó để tiện làm việc, người ta thường cho luôn điểm gốc vào bao nón lồi của một tập. Chú ý rằng giao của các tập lồi (tập a-phin, nón lồi) cũng là tập lồi (tập a-phin, nón lồi), nên bao lồi, bao a-phin và bao lồi được xác định một cách duy nhất. Như vậy bao lồi của một tập E là tập lồi nhỏ nhất chứa E. Tương tự bao a-phin của E là tập a-phin nhỏ nhất chứa E.
10 Bao nón lồi của E là tập hợp gồm gốc tọa độ và nón lồi nhỏ nhất chứa E. Như vậy khác với bao lồi và bao a-phin, bao nón lồi của một tập nói chung khác một chút với nón lồi nhỏ nhất chứa tập đó. Dĩ nhiên nếu E 6= ∅, thì bao lồi, bao a-phin và bao nón lồi luôn tồn tại duy nhất và khác rỗng vì các tập này đều chứa E và vì bản thân toàn bộ không gian đồng thời vừa là một tập lồi, một tâp a-phin và một nón lồi chứa E. Chú ý rằng có một số tác giả định nghĩa nón như sau: một tập C được gọi là một nón nếu với mọi x ∈ C thì λx ∈ C với mọi λ ≥ 0. Theo định nghĩa này, nón luôn chứa gốc. Khi đó bao nón lồi của một tập E chính là giao của các nón lồi chứa E. Nhắc lại rằng, thứ nguyên (còn gọi là chiều) của một tập E bất kỳ được định nghĩa như là thứ nguyên của bao a-phin của nó. Tức là dim E := dim(af f E). Định lý 1.1.14 Cho E là một tập lồi. Khi đó coneE = {λx|x ∈ E, λ ≥ 0}. Chứng minh. Gọi M := {λx|x ∈ E, λ > 0}. Hiển nhiên là bất kỳ nón nào chứa E, đều phải chứa M . Ta sẽ chỉ ra là bản thân M cũng là một nón lồi. Giả sử y 1 , y 2 ∈ M . Vậy y 1 = λ1 x1 , y 2 = λ2 x2 với λ1 , λ2 > 0 và x1 , x2 ∈ E. Khi đó, ta có ! λ1 λ2 y 1 + y 2 = (λ1 + λ2 ) x1 + x2 . λ1 + λ2 λ1 + λ2 Do E lồi, nên λ1 λ2 x1 + x2 ∈ E. λ1 + λ2 λ1 + λ2 Vậy y 1 + y 2 ∈ M . Suy ra M là nón lồi nhỏ nhất chứa E và do đó bao nón lồi của E là tập hợp gồm M và gốc tọa độ. Tức là coneE = {λx|x ∈ E, λ ≥ 0}. Định lý 1.1.15 (Carathéodory). Cho E là một tập bị chứa trong một tập a-phin có thứ nguyên là k. Khi đó mọi x ∈ coE đều có thể biểu diễn như là tổ hợp lồi của nhiều nhất (k + 1) phần tử của E.
11 Chứng minh định lý này sẽ dùng đến định lý sau, cũng là một dạng của định lý Carathéodory đối với bao nón lồi. Định lý 1.1.16 Giả sử E ⊂ Rk . Khi đó mỗi điểm x 6= 0 thuộc coneE đều có thể biểu diễn dưới dạng x = λ1 x1 + ... + λr xr , trong đó xi ∈ E, λi > 0 với mọi i và các điểm x1 , ..., xr độc lập tuyến tính. Nói riêng r ≤ k. Chứng minh. Bạn đọc tham khảo trong tài liêu [1]. Chứng minh định lý Carathéodory. Xét tập hợp B := {1} × E = {(1, x)|x ∈ E} ⊂ R × Rk . Ta có coB = {1} × coE. Giả sử coneB là nón lồi sinh bởi B. Do coB là tập lồi nhỏ nhất chứa B, nên coB ⊂ coneB. Với mọi (1, x) ∈ coB, theo định lý trên, tồn tại các điểm (1, x1 ), ..., (1, xr ) ∈ B và các số λ1 , ..., λr , với r ≤ k + 1 thỏa mãn: x = λ1 x1 + ... + λr xr , xi ∈ E ∀i, λ1 + ... + λr = 1, λi > 0 ∀i. Ta nhắc lại các khái niệm về điểm trong, điểm biên, tập compact v.v... trong giải tích cổ điển. Cho E ⊆ Rn . Điểm a được gọi là điểm trong của E nếu tồn tại một lân cận mở U (a) của a sao cho U (a) ⊂ E. Ký hiệu tập hợp các điểm trong của tập E là intE và B là quả cầu đơn vị, tâm ở gốc. Khi đó theo định nghĩa, ta có intE = {x : ∃r > 0, x + rB ⊂ E}.
12 Điểm a được gọi là điểm biên của E nếu mọi lân cận của a đều có điểm thuộc E và điểm không thuộc E. Tập E được gọi là tập mở nếu mọi điểm của E đều là điểm trong của E. Tập E được gọi là tập đóng, nếu E chứa mọi điểm biên của nó. Tập E ⊂ Rn được gọi là một tập compact, nếu E là một tập đóng và bị chặn. Ta nói điểm a thuộc bao đóng của tập E nếu mọi lân cận của a đều chứa điểm thuộc E. Ký kiệu E là bao đóng của E. Khi đó từ định nghĩa, suy ra E = ∩r>0 (E + rB). Chú ý rằng bao lồi của một tập đóng không nhất thiết đóng. Ví dụ, nếu E = {(x, 0) ∈ R2 , x ∈ R} ∪ {(0, 1)}, thì coE = {(x, y) ∈ R2 |x ∈ R, 0 ≤ y < 1} ∪ {(0, 1)}. Tuy nhiên nếu E là compact, thì coE cũng là compact theo hệ qủa sau đây: Hệ quả 1.1.17 Nếu E ⊂ R2 là một tập compact, thì coE cũng com- pact. 1.1.2 Toán tử chiếu tập lồi Định nghĩa 1.1.18 Cho C 6= ∅ (không nhất thiết lồi) và y là một véc-tơ bất kỳ, đặt dC (y) := inf kx − yk. 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) = kπ − yk, thì ta nói πlà hình chiếu (vuông góc) của y trên C . Định lý 1.1.19 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.
13 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). 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 kπ − yk ≤ ky − xλ k. Hay kπ − yk2 ≤ kλ(x − π) + (π − y)k2 . Khai triển vế phải, ước lược và chia hai vế cho λ > 0 , ta có λkx − πk2 + 2hx − π, π − 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 (π). Bây giờ giả sử có b). Với mọi x ∈ C, có 0 ≥ (y − π)T (x − π) = (y − π)T (x − y + y − π) = ky − πk2 + (y − π)T (x − y). Từ đây và b), dùng bất đẳng thức Cauchy-Schwarz ta có: ky − πk2 ≤ (y − π)T (y − x) ≤ ky − πkky − xk.
14 Suy ra ky − πk ≤ ky − xk ∀x ∈ C, và do đó π = p(y). ii) Do dC (y) = inf x∈C kx − yk, 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 kxk − yk = 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 kπ − yk = lim kxkj − yk = lim kxk − yk = 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à hπ − y, π 1 − πi ≥ 0 và hπ 1 − y, π − π 1 i ≥ 0. Cộng hai bất đẳng thức này ta suy ra kπ − π 1 k ≤ 0, và do đó π = π1. iii) Do y − π ∈ NC (π), nên hπ − y, x − πi ≥ 0 ∀x ∈ C. Vậy hπ − y, xi = hπ − y, πi là một siêu phẳng tựa của C tại π. Siêu phẳng này tách y khỏi C vì y 6= π, nên hπ − y, y − πi = −kπ − yk2 < 0.
15 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 kp(x) − p(y)k ≤ kx − yk. Để chứng minh 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 = hp(x) − p(y), y − xi + kp(x) − p(y)k2 ≤ 0. Chuyển vế ta có hp(x) − p(y), x − yi ≥ kp(x) − p(y)k2 . Đây chính là tính đồng bức cần được chứng minh. Định lý 1.1.20 (Định lý tách 1). Cho C và D là hai tập lồi khác rỗng trong Rn sao cho C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D. Định lý tách vừa nêu có thể suy ra ngay từ Bổ đề 1.1.21 dưới đây, chính là định lý tách một tập lồi và một phần tử không thuộc nó.
16 Bổ đề 1.1.21 (Bổ đề liên thuộc). Cho C ⊂ Rn là một tập lồi khác rỗng. Giả sử x0 ∈ C. Khi đó tồn tại t ∈ Rn , t 6= 0 thỏa mãn ht, xi ≥ ht, x0 i∀x ∈ C. (1.4) Chứng minh Định lý 1.1.20. Do C và D là lồi, nên C − D cũng lồi. Hơn nữa 0 ∈ / (C − D), vì C ∩ D = ∅. Theo bổ đề trên áp dụng với x0 = 0, tồn tại véc-tơ t ∈ Rn , t 6= 0 sao cho ht, zi ≥ 0 với mọi z ∈ C − D. Vì z = x − y với x ∈ C, y ∈ D, nên ta có ht, xi ≥ ht, yi ∀x ∈ C, y ∈ D. Lấy α := supht, yi, y∈D khi đó siêu phẳng ht, xi = α tách C và D. Định lý 1.1.22 (Định lý tách 2). Cho C và D là hai tập lồi đóng khác rỗng sao cho C ∩ D = ∅ . Giả sử có ít nhất một tập là compact. Khi đó hai tập này có thể tách mạnh được bởi một siêu phẳng Cũng như trên, định lý tách mạnh được dễ dàng suy ra từ bổ đề sau nói về sự tách mạnh giữa một tập lồi đóng và một điểm bên ngoài tập này. Bổ đề 1.1.23 Cho C ⊂ Rn là một tập lồi đóng khác rỗng sao cho / C. Khi đó tồn tại một véc-tơ t ∈ Rn , t 6= 0 và α > 0 sao cho 0∈ ht, xi ≥ α > 0, ∀x ∈ C. Chứng minh Định lý 1.1.22. Giả sử C là tập compact. Ta chỉ ra tập C −D đóng. Thật vậy, giả sử z k ∈ C −D và z k → z. Ta có z k = xk −y k với xk ∈ C, y k ∈ D. Vì C compact, nên có một dãy con xkj → x khi j → +∞. Vậy y kj = z kj − xkj → z − x ∈ D. Vậy z = x − y ∈ C − D. Chứng tỏ C − D là tập đóng. Do 0 ∈ / C − D, nên theo bổ đề trên, tồn tại t 6= 0, sao cho ht, x − yi ≥ α > 0 với mọi x ∈ C, y ∈ D. Vậy α α inf ht, xi − ≥ supht, yi + . x∈C 2 y∈D 2