Giải tích lồi và các bài toán sơ cấp năm 2024
|
Giải tích lồi là một bộ môn cơ bản của giải tích hiện đại, nghiên cứu về tập lồi và hàm lồi cùng với những vấn đề liên quan. Bộ môn này có vai trò quan trọng trong nhiều lĩnh vực khác nhau của toán học ứng dụng, đặc biệt là trong tối ưu hoá, bất đẳng thức biến phân, các bài toán cân bằng v... Có thể nói, giải tích lồi là một trong những bộ môn quan trọng nhất làm cơ sở toán học của tối ưu hoá và một số lĩnh vực khác. Do phạm vi ứng dụng rộng rãi của giải tích lồi, nên hiện nay nhu cầu học tập, giảng dạy, nghiên cứu và ứng dụng bộ môn này ngày càng nhiều ở Việt Nam. Hiện đã có một số sách về giải tích lồi bằng tiếng nước ngoài, trong đó cuốn "Giải tích lồi" (Convex Analysis) của R. T. Rockafellar là một sách chuyên khảo tiếng Anh khá hoàn chỉnh về giải tích lồi trong không gian hữu hạn chiều. Tuy nhiên sách đã được viết từ năm 1970 và là một tài liệu khó đọc đối với những người mới bắt đầu làm quen lĩnh vực này. Về sách tiếng Việt, hiện mới chỉ có một quyển giải tích lồi viết trong không gian vô hạn chiều và do đó không đi sâu được vào những đặc tính riêng, cũng như những khía cạnh về mặt tính toán và những ứng dụng vốn rất phong phú của tập lồi và hàm lồi trong các không gian hữu hạn chiều. Cuốn sách "Nhập môn giải tích lồi ứng dụng" này sẽ giới thiệu những vấn đề cơ bản nhất, nhưng khá đầy đủ về tập lồi và hàm 8 Nhập môn giải tích lồi ứng dụng lồi trong không gian hữu hạn chiều. Trong cuốn sách, các kết quả của giải tích lồi được trình bày theo quan điểm nhấn mạnh vào các khía cạnh tính toán cũng như ứng dụng của tập lồi và hàm lồi trong tối ưu hoá, bất đẳng thức biến phân và bài toán cân bằng. Đối tượng của cuốn sách có thể là các sinh viên năm cuối, học viên cao học, nghiên cứu sinh các ngành toán ứng dụng. Sách cũng có thể làm tài liệu tham khảo cho các thầy cô giáo giảng dạy môn giải tích lồi. Những người làm trong các lĩnh vực khác như kinh tế, tài chính, quản lý và kỹ sư các ngành khoa học kỹ thuật muốn tìm hiểu về giải tích lồi để áp dụng vào ngành chuyên môn của mình cũng có thể dùng sách như một tài liệu tham khảo. Cuốn sách được biên soạn dựa theo bài giảng của các tác giả cho sinh viên các năm cuối bậc đại học, học viên cao học, nghiên cứu sinh tại Viện Toán học Hà Nội, các trường đại học tại Hà Nội, Huế, Quy Nhơn, thành phố Hồ Chí Minh và các đại học ở CHLB Đức, Cộng hoà Pháp, Vương quốc Bỉ, Canada, v... Chúng tôi xin chân thành cảm ơn Viện Toán học Hà Nội và Đại học Namur, FUNDP, Vương Quốc Bỉ đã tạo mọi điều kiện cho chúng tôi hoàn thành quyển sách này. Lời cảm ơn cũng xin gửi đến Giáo sư Jean-Jacques. Strodiot đã có những ý kiến quý báu cho nội dung và bố cục của cuốn sách. Xin cám ơn TS. Vũ Văn Đạt và anh Trần Văn Thành đã giúp đỡ rất nhiều trong quá trình soạn thảo cuốn sách này. Chúng tôi rất mong nhận được và chân thành cảm ơn mọi sự góp ý của độc giả. Namur, Vương Quốc Bỉ, tháng 8- Các tác giả Lê Dũng Mưu và Nguyễn Văn Hiền 10 Nhập môn giải tích lồi ứng dụng ri(A) tập điểm trong tương đối của tập A; V(A) tập các điểm cực biên (đỉnh) của A; coA: bao lồi đóng của A; coneA: bao nón lồi đóng của A; reA: nón lùi xa (nón các hướng vô hạn) của A; intA: tập hợp các điểm trong của A; riA: tập hợp các điểm trong tương đối của A; A∗: đối cực của A; dimA: thứ nguyên (số chiều) của tập A; linealityA: độ phẳng của tập A; linA: không gian thẳng của A; f : hàm bao đóng của f ; L( f ): không gian thẳng của f ; lin f : thứ nguyên của L( f ); rank f : hạng của f ; dom f : tập hữu dụng của f ; dim f : thứ nguyên của dom f ; f ∗: hàm liên hợp của f ; epi f : 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 f ′(x) : đạo hàm của f tại x; f ′(x, d): đạo hàm theo hướng d của f tại x; KKT: Karush-Kuhn-Tucker; KT: Kuhn-Tucker; QHTT: quy hoach tuyến tính; QHTP: quy hoach toàn phương. Chương 1CÁC KHÁI NIỆM CƠ BẢN
Trong giáo trình này, chúng ta sẽ làm việc với không gian Eu- clidean n-chiều trên trường số thực IR. Không gian này sẽ được ký hiệu là IRn. Như vậy mỗi véc-tơ x ∈ IRn sẽ gồm n tọa độ là các số thực. Thông thường khi viết một véc-tơ x, nếu không có qui định gì thêm, ta luôn hiểu đó là véc-tơ cột. Phần này nhằm giới thiệu những khái niệm cơ bản nhất của tập lồi cùng với những tính chất đặc trưng của nó. 1. Tổ hợp lồiMột đường thẳng nối hai điểm (hai véc-tơ) a, b trong IRn là tập hợp tất cả các véc-tơ x ∈ IRn có dạng {x ∈ IRn|x = αa + βb, α, β ∈ IR, α + β = 1 }. 1 Tổ hợp lồi 13 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 x 1 , ..., xk ∈ C. Tức là x = k ∑ j= 1 λj xj, λj > 0 ∀j = 1, ..., k, k ∑ j= 1 λj = 1. Đặt ξ = k− 1 ∑ j= 1 λj. Khi đó 0 < ξ < 1 và x = k− 1 ∑ j= 1 λj xj + λk xk \= ξ k− 1 ∑ j= 1 λj ξ xj + λk xk. (1) Do k− 1 ∑ j= 1 λj ξ \= 1và λj ξ > 0 với mọi j = 1, ..., k − 1 , nên theo giả thiết quy nạp, điểm y := k− 1 ∑ j= 1 λj ξ xj ∈ C. Ta có x = ξy + λk xk. Do ξ > 0, λk > 0 và ξ + λk = k ∑ j= 1 λj = 1, 14 Nhập môn giải tích lồi ứng dụng 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. 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ó mệnh đề sau: Mệnh đề 1. Nếu A, B là các tập lồi trong IRn, C là lồi trong IRm, 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, α, β ∈ IR}, A × C := {x ∈ IRn+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.
Trong giải tích cổ điển, ta đã làm quen với các không gian con, các siêu phẳng v... Đó là các trường hợp riêng của tập a-phin (đa tạp a-phin) được định nghĩa như sau: Định nghĩa 1. 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, ∀λ ∈ IR ⇒ λ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. Siêu phẳng trong không gian IRn là một tập hợp các điểm có dạng {x ∈ IRn | aT x = α}, trong đó a ∈ IRn là một véc-tơ khác 0 và α ∈ IR. 16 Nhập môn giải tích lồi ứng dụng Vậy ( 1 − λ)x + λy ∈ M. Suy ra M là tập a-phin. Không gian con L ở trên là duy nhất. Thật vậy, nếu M = a + L và M = a′ + L′, thì L′ = M − a′ = a + L − a′ = L + (a − a′). Do a′ ∈ M = a + L, nên a′ − a ∈ L. Suy ra L′ = L + a − a′ = L. Không gian L trong mệnh đề 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à dimM. Mệnh đề 1. Bất kỳ một tập a-phin M ⊂ IRn có số chiều r đều có dạng M = {x ∈ IRn | Ax = b}, (1) trong đó A là ma trận cấp (m × n), b ∈ IRm và rankA = n − r. Ngược lại, mọi tập hợp có dạng (1) với rankA = n − r đều là tập a-phin có số chiều là r. Chứng minh. Giả sử M là tập a-phin có số chiều là r và M = L + a với a ∈ M. Vậy L = M − a là một không gian con có số chiều là r. Theo đại số tuyến tính, không gian con r chiều này có dạng L = {x |Ax = 0 } với A là một ma trận cấp m × n và rankA = n − r. Từ M = L + a, suy ra M = {x |A(x − a) = 0 } = {x |Ax = Aa = b}. 1 Tập a-phin, tập lồi đa diện 17 Ngược lại, giả sử M được cho bởi (1). Dễ kiểm ta được rằng M là một tập a-phin và không gian con của M là tập {x|Ax = 0 }. Do rankA = n − r, nên dimL = r. Vậy dimM = r. Để tiện việc theo dõi, ta nhắc lại khái niệm độc lập a-phin đã quen biết trong đại số tuyến tính. Định nghĩa 1. Các điểm x 0 , x 1 , ..., xk trong IRn được gọi là độc lập a-phin, nếu bao a-phin của chúng có thứ nguyên là k. Mệnh đề dưới đây cho một tính chất đặc trưng của các điểm độc lập a-phin. Mệnh đề 1. Các điều sau đây là tương đương: (i) Các điểm x 0 , x 1 , ..., xk độc lập a-phin, (ii) Với mỗi i, các điểm xj − xi ( j = 0, 1, ..., k, j 6 = i) độc lập tuyến tính trong IRn. (iii) Các điểm (xj, 1) (j = 0, 1, ..., k) độc lập tuyến tính trong IRn+ 1. Chứng minh. Gọi S là tập hợp gồm các điểm x 0 , x 1 , ..., xk và L là không gian con của S. Không giảm tổng quát, cho i = 0. Đặt yj = xj − x 0 (j = 1, ..., k). Hiển nhiên yj ∈ L với mọi j. Cho x = ∑kj= 0 μj xj là một tổ hợp a-phin bất kỳ của các điểm x 0 , x 1 , ..., xk. Do ∑kj= 0 μj = 1 , nên μ 0 = 1 − ∑kj= 1 μj. Vậy x = x 0 + ∑kj= 1 μjyj. Suy ra affS = x 0 + span{y 1 , ..., yk}, trong đó span{y 1 , ..., yk} ký hiệu không gian con căng bởi các điểm {y 1 , ..., yk}. Theo mệnh đề 1 ta có L = span{y 1 , ..., yk}. Vậy dimL = k khi và chỉ khi các điểm y 1 , ..., yk độc lập tuyến tính. Chứng tỏ (i) và (ii) là tương đương. Sự tương đương giữa (ii) và (iii) dễ dàng được chứng minh, dựa trực tiếp vào định nghĩa về sự độc lập tuyến tính. 1 Nón lồi 19
Trong tối ưu hoá, bất đẳng thức biến phân, lý thuyết trò chơi và nhiều bộ môn toán ứng dụng khác, khái niệm về nón có một vai trò quan trọng. Định nghĩa 1. 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 ∈ IR | 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). Mệnh đề 1. 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. 20 Nhập môn giải tích lồi ứng dụng Chứng minh. Giả sử C là một nón lồi. Do C là một nón, nên ta có (i). Do C là một tập lồi, nên với mọi x, y ∈ C, thì 12 (x + y) ∈ C. Vậy 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". Định nghĩa 1. Cho C là một tập lồi trong IRn. 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ó mệnh đề sau: |
