Không gian tự học dành cho sinh viên UET

Chào mừng đến với UETệ

Tìm bài giảng theo học phần, hiểu lại những kiến thức nền và ôn tập theo nhịp học của bạn.

Bài giảng
Đọc Notes, ôn nhanh với Slides và luyện tập qua các bài có lời giải.
Wiki kiến thức
Tra cứu thuật ngữ và bổ sung kiến thức nền ngay khi cần.
Góc học tập
Ôn bằng flashcard, lưu ghi chú và hẹn giờ tập trung.

Bạn có thể xem lại phần giới thiệu ở cuối trang.

Buy me a coffee

Website hoàn toàn miễn phí. Nếu thấy hữu ích, bạn có thể tặng tôi một cốc cà phê theo thông tin dưới đây nhé!

Mã QR chuyển khoản Momo
Ngân hàng
Momo
Tên người nhận
MOMO - TKTH DO MINH TRI
Số tài khoản
01MMTTT0060405229
Skip to content

Chiều affine và nội tương đối

Chủ đề 4 / 25
  1. 1. Bài toán tối ưu và những gì cần viết ra
  2. 2. Bình phương tối thiểu và quy hoạch tuyến tính
  3. 3. Đường thẳng, đoạn thẳng và tập affine
  4. 4. Chiều affine và nội tương đối
  5. 5. Tập lồi, tổ hợp lồi và bao lồi
  6. 6. Nón và nón lồi
  7. 7. Siêu phẳng và nửa không gian
  8. 8. Quả cầu và ellipsoid
  9. 9. Quả cầu chuẩn và nón chuẩn
  10. 10. Đa diện và đơn hình
  11. 11. Nón các ma trận nửa xác định dương
  12. 12. Các phép toán giữ tính lồi của tập
  13. 13. Phép phối cảnh và hàm phân tuyến tính
  14. 14. Nón chính quy và bất đẳng thức tổng quát
  15. 15. Siêu phẳng phân tách và siêu phẳng tựa
  16. 16. Nón đối ngẫu và lựa chọn Pareto
  17. 17. Hàm lồi và bất đẳng thức dây cung
  18. 18. Điều kiện bậc nhất: Tiếp tuyến nằm dưới đồ thị
  19. 19. Điều kiện bậc hai và độ cong
  20. 20. Những hàm lồi thường gặp
  21. 21. Epigraph, tập mức dưới và bất đẳng thức Jensen
  22. 22. Các phép toán giữ tính lồi của hàm
  23. 23. Cực tiểu cục bộ và cực tiểu toàn cục
  24. 24. Điều kiện tối ưu bậc nhất trên miền lồi
  25. 25. Nhận diện tính lồi trong mô hình học máy

Hãy tưởng tượng một tờ giấy phẳng đặt trong không gian ba chiều: Tờ giấy có "phần bên trong" hay không? Trực giác thường trả lời là có, đó là toàn bộ diện tích tờ giấy trừ đi bốn mép viền ngoài cùng. Thế nhưng, nếu áp dụng máy móc định nghĩa điểm trong quen thuộc của giải tích topo, thì trong không gian ba chiều tờ giấy không có bất kỳ điểm trong nào. Quanh một điểm bất kỳ trên mặt giấy, quả cầu mở bán kính r>0 dù nhỏ đến đâu cũng sẽ nhô ra phía trên và chìm xuống phía dưới mặt phẳng chứa giấy, tức là luôn chứa những điểm không thuộc tờ giấy.

Mâu thuẫn giữa trực giác hình học và định nghĩa topo không dừng lại ở khía cạnh câu chữ. Trong tối ưu hóa, rất thường có dạng "phẳng và mỏng" như tờ giấy, điển hình là khi xuất hiện các ràng buộc đẳng thức tuyến tính dạng x1+x2+x3=1. Nếu chỉ bám vào khái niệm điểm trong thông thường, những miền khả thi này sẽ có phần trong rỗng, khiến mọi định lý yêu cầu "tồn tại điểm nằm hẳn bên trong miền khả thi" đều bị vô hiệu hóa. Khái niệm thay thế chuẩn mực là nội tương đối (relative interior), tức phần trong được xác định cục bộ bên trong chính bao affine của . Đi cùng với khái niệm này là chiều affine, thước đo số chiều không gian phẳng tối thiểu cần thiết để bao trọn một tập.

Kiến thức nền tảng bao gồm bao affine và khái niệm quả cầu Euclid B(x,r)={y∣∥y−x∥2≤r}.

1. Chiều affine ​

Số chiều của một tập affine được định nghĩa là số chiều của không gian con phương đi kèm. Với một tập C bất kỳ, ta xác định số chiều thông qua tập affine nhỏ nhất bao bọc nó.

Định nghĩa. Chiều affine của C, ký hiệu affdim(C), là số chiều của bao affine affC.

Một đoạn thẳng nối hai điểm phân biệt trong R3 có chiều affine bằng 1, bởi bao affine của nó là một đường thẳng. Một tam giác đặc trong R3 có chiều affine bằng 2. Xét tập các phân phối xác suất rời rạc trên ba biến cố, tức tập các p∈R3 thỏa mãn pi≥0 và có tổng thành phần bằng 1:

∑i=13pi=p1+p2+p3=1.

này có chiều affine bằng 2, vì nó nằm trọn trong mặt phẳng p1+p2+p3=1 và không suy biến về một đường thẳng.

Cần phân biệt rõ: Chiều affine không nhất thiết trùng khớp với khái niệm số chiều topo hay số chiều vi phân của đa tạp. Xét đường tròn đơn vị phẳng {x∈R2∣x12+x22=1}. Theo quan điểm giải tích vi phân, đường tròn là một đối tượng một chiều, vì vị trí mỗi điểm trên đường tròn được xác định duy nhất qua một góc φ∈[0,2π). Tuy nhiên, bao affine của đường tròn là toàn bộ mặt phẳng R2, kéo theo chiều affine của nó bằng 2. Sự khác biệt này hoàn toàn tự nhiên: Chiều affine đo kích thước của không gian phẳng nhỏ nhất có thể chứa trọn vẹn , chứ không đo số bậc tự do cục bộ. Đường tròn bị uốn cong trong mặt phẳng, do đó không có đường thẳng một chiều nào có thể chứa nổi nó.

2. Điểm trong và hiện tượng các tập bị dẹp ​

Nhắc lại định nghĩa topo cơ bản: Một điểm x được gọi là điểm trong của tập C⊆Rn nếu tồn tại bán kính r>0 sao cho quả cầu mở B(x,r)={y∣∥y−x∥2<r} nằm hoàn toàn trong C. tất cả các điểm trong được gọi là phần trong của C, ký hiệu là intC.

Định nghĩa này phụ thuộc trực tiếp vào không gian bao quanh mà ta đang đứng để quan sát. Xét đoạn thẳng C=[0,1]:

  • Khi xét trong không gian một chiều R, phần trong của C là khoảng mở intC=(0,1).
  • Nhưng khi đặt chính đoạn thẳng đó nằm trên trục hoành của mặt phẳng R2, tức C={(x1,0)∣0≤x1≤1}, phần trong của nó trong R2 lại rỗng hoàn toàn. Quanh điểm (12,0), bất kỳ hình tròn mở nào dù bán kính nhỏ đến đâu cũng chứa các điểm có tung độ khác 0, và những điểm đó không thuộc đoạn thẳng.

Mô phỏng dưới đây trực quan hóa hiện tượng này. Quả cầu mở quanh điểm x luôn tràn ra ngoài đường thẳng chứa đoạn thẳng. Thế nhưng, nếu ta chỉ thu hẹp tầm nhìn vào phần giao giữa quả cầu và đường thẳng đó, câu chuyện lại hoàn toàn khác.

Một đoạn thẳng không có điểm trong, nhưng có nội tương đối

xaff C

Hình tròn bán kính r quanh x luôn có điểm nằm ngoài đường thẳng chứa đoạn, nên x không phải điểm trong của C khi xét trong R².

Phần giao của hình tròn với đường thẳng aff C là đoạn màu xanh, và nó nằm trọn trong C. Với bán kính này, x thỏa điều kiện của nội tương đối.

3. Nội tương đối và biên tương đối ​

Ý tưởng khắc phục hiện tượng trên rất mạch lạc: Khi kiểm tra xem một điểm có nằm "bên trong" hay không, ta chỉ xét các điểm lân cận thuộc bao affine của tập, bỏ qua những hướng không gian mà tập hợp vốn dĩ không bao giờ vươn tới.

Định nghĩa. Nội tương đối của tập C, ký hiệu relintC, là

relintC={x∈C∣∃r>0:B(x,r)∩affC⊆C}.

So với định nghĩa điểm trong thông thường, điểm khác biệt duy nhất nằm ở chỗ quả cầu B(x,r) được thay bằng phần giao B(x,r)∩affC. Quay lại hình ảnh tờ giấy trong R3, phần giao này chính là một hình tròn phẳng nằm trọn trên mặt phẳng của tờ giấy. Bài toán kiểm tra điểm trong trở thành: "Liệu có tồn tại một hình tròn phẳng nhỏ quanh x nằm trọn trên tờ giấy hay không?". Cách đặt vấn đề này đem lại câu trả lời hoàn toàn ăn khớp với trực giác ban đầu.

Về mặt giải tích, việc lựa chọn chuẩn để định nghĩa quả cầu không làm thay đổi kết quả. Trong không gian hữu hạn chiều Rn, bất kỳ chuẩn nào cũng đều dẫn tới cùng một tập nội tương đối. Tính chất này bắt nguồn từ tính tương đương của mọi chuẩn trên không gian hữu hạn chiều: Quả cầu theo chuẩn này luôn chứa một quả cầu đồng tâm nhỏ hơn theo chuẩn khác.

Đi cùng với nội tương đối là khái niệm biên tương đối (relative boundary), ký hiệu relbdC, được định nghĩa là:

relbdC=clC∖relintC,

trong đó clC là bao đóng topo thông thường của C. Biên tương đối chính là "mép ngoài" của khi quan sát từ bên trong bao affine của nó.

Ví dụ: Hình vuông phẳng trong không gian ba chiều

Xét hình vuông nằm phẳng trên mặt phẳng tọa độ x3=0 của không gian R3:

C={x∈R3∣−1≤x1≤1, −1≤x2≤1, x3=0}.

Bao affine của tập C là mặt phẳng affC={x∈R3∣x3=0}. Phần trong của C trong R3 rỗng hoàn toàn, và biên topo thông thường của C trong R3 chính là toàn bộ tập C. Trong khi đó, nội tương đối của tập là:

relintC={x∈R3∣−1<x1<1, −1<x2<1, x3=0},

và biên tương đối là khung viền bốn cạnh:

relbdC={x∈R3∣max{|x1|,|x2|}=1, x3=0}.

Nội tương đối là hình vuông đã loại bỏ bốn cạnh bao quanh, đúng như cảm nhận tự nhiên về "phần bên trong của một mặt phẳng hữu hạn".

Người học có thể trực tiếp tương tác với từng điểm trong mô phỏng dưới đây. Hình vẽ sử dụng phép chiếu không gian: Đường tròn nét đứt biểu diễn quả cầu trong R3, còn hình tròn đặc tô màu là phần giao giữa quả cầu và mặt phẳng x3=0.

Hình vuông nằm phẳng trong R³

x₁x₂x₃

Điểm đang xét là (0.30, −0.20, 0). Quả cầu bán kính r (đường tròn nét đứt) luôn có điểm với x₃ ≠ 0, nên nó không nằm trong hình vuông: hình vuông không có điểm trong nào trong R³.

Phần giao của quả cầu với mặt phẳng x₃ = 0 là hình tròn màu xanh, và nó nằm trọn trong hình vuông. Điểm này thuộc nội tương đối.

Một điểm (a,b,0) với |a|<1 và |b|<1 luôn thuộc nội tương đối, bởi ta chỉ cần chọn bán kính r≤min{1−|a|,1−|b|} thì phần giao hình tròn sẽ nằm gọn trong hình vuông. Ngược lại, điểm nằm trên cạnh, chẳng hạn (1,0,0), không thuộc nội tương đối: Bất kể bán kính r>0 nhỏ thế nào, phần giao hình tròn cũng chứa những điểm có x1>1, tức nằm ngoài hình vuông.

4. Bảng đối chiếu các tập hình học cơ bản ​

Bảng sau so sánh phần trong thông thường và nội tương đối trên các tập hình học quen thuộc. Hai khái niệm này trùng nhau khi và chỉ khi chiều affine của tập bằng đúng số chiều của không gian bao quanh, nghĩa là khi tập không bị dẹp trong không gian đó.

CKhông gianPhần trong intCNội tương đối relintC
Đoạn thẳng [a,b] (a<b)RKhoảng mở (a,b)Khoảng mở (a,b)
Đoạn nối hai điểm x1≠x2R2Rỗng ∅Đoạn thẳng bỏ hai đầu mút
Một điểm đơn lẻ {x0}Rn (n≥1)Rỗng ∅Chính điểm {x0}
Hình tròn đặc {x∣|x|2≤1}R2Hình tròn mở {x∣|x|2<1}Hình tròn mở {x∣|x|2<1}
Đơn hình xác suất chuẩn tắcR3Rỗng ∅{p∈R3∣pi>0, ∑i=13pi=1}
Đường thẳng {x∣aTx=b}R2Rỗng ∅Chính đường thẳng đó

Trường hợp điểm đơn lẻ {x0} trong bảng mang một ý nghĩa đặc biệt: Bao affine của một điểm là chính điểm đó, do đó B(x0,r)∩aff{x0}={x0}⊆{x0} với mọi bán kính r>0. Vì thế, một điểm đơn lẻ chính là toàn bộ phần trong của chính nó khi nhìn từ bao affine không chiều của nó. Kết quả này phản ánh bản chất topo nhất quán: Trong không gian không chiều, một điểm không có mép biên.

Trường hợp đơn hình xác suất liên hệ trực tiếp với các mô hình phân loại trong học máy: Đầu ra của hàm softmax là một xác suất thỏa mãn mọi thành phần đều dương chặt (pi>0). Do đó, phân phối dự đoán của mô hình luôn nằm bên trong nội tương đối của đơn hình xác suất, không bao giờ chạm tới biên tương đối. Mô hình softmax không bao giờ gán xác suất bằng 0 cho bất kỳ lớp nào. Đó cũng là lý do vì sao hàm mất mát cross-entropy không thể đạt giá trị đúng bằng 0 với các trọng số hữu hạn, mà chỉ tiệm cận về 0 khi các trọng số tiến tới vô hạn.

5. Vai trò quyết định của nội tương đối trong tối ưu hóa ​

Nội tương đối không phải là một sự phức tạp hóa toán học, mà là công cụ thiết yếu để giải quyết ba vấn đề nền tảng trong giải tích lồi và tối ưu hóa:

Điều kiện tư cách ràng buộc Slater ​

Khi xét bài toán tối ưu lồi có ràng buộc đẳng thức affine Ax=b và các ràng buộc bất đẳng thức lồi fi(x)≤0, luôn nằm trong tập affine {x∣Ax=b}. Nếu hệ ràng buộc đẳng thức không tầm thường, miền khả thi này có phần trong topo thông thường bằng rỗng. Điều kiện tư cách ràng buộc Slater (Slater's constraint qualification) bảo đảm đối ngẫu mạnh đòi hỏi tồn tại một điểm khả thi chặt nằm trong nội tương đối của miền xác định. Nếu phát biểu điều kiện này bằng phần trong thông thường, mọi bài toán có ràng buộc đẳng thức đều vi phạm điều kiện, dù bài toán hoàn toàn giải được và thỏa mãn đối ngẫu mạnh.

Tính liên tục của hàm lồi ​

Một định lý kinh điển của giải tích lồi khẳng định: Mọi hữu hạn trên một luôn liên tục trên nội tương đối của miền xác định, và hiện tượng gián đoạn chỉ có thể xảy ra trên biên tương đối. Xét nhận giá trị 0 trên khoảng mở (0,1) và nhận giá trị 1 tại hai đầu mút x=0 và x=1. Đây là một hàm lồi trên đoạn [0,1], nhưng bị gián đoạn đúng tại hai đầu mút, tức ngay trên biên tương đối của miền xác định.

Tính tách được của các tập lồi ​

Định lý siêu phẳng tách phát biểu rằng: Hai C1,C2 khác rỗng có thể tách được bằng một siêu phẳng khi và chỉ khi nội tương đối của chúng rời nhau, tức:

relintC1∩relintC2=∅.

Nếu thay bằng điều kiện phần trong thông thường rời nhau, định lý sẽ mất hiệu lực khi hai đều mỏng (chẳng hạn hai đoạn thẳng chéo nhau trong không gian ba chiều).

Một kết quả nền tảng của giải tích lồi cần ghi nhớ: Mọi khác rỗng trong Rn đều có nội tương đối khác rỗng. Trong khi phần trong thông thường rất dễ bị rỗng khi bị dẹp, nội tương đối luôn được bảo toàn, khẳng định vị thế trung tâm của khái niệm này đối với hình học lồi.

6. Những câu hỏi để đào sâu ​

Câu 1. Nội tương đối của một có thể rỗng hay không? Hãy tìm một tập hợp không lồi có nội tương đối rỗng.

Xem lời giải thích

Nội tương đối có thể rỗng nếu không lồi. Xét đường tròn đơn vị trong R2: Bao affine của nó là toàn bộ mặt phẳng R2, do đó nội tương đối trùng với phần trong thông thường, và tập này rỗng vì quanh mỗi điểm trên đường tròn luôn có những điểm ngoài đường tròn. Một ví dụ khác là tập gồm hai điểm phân biệt {(0,0),(1,0)}: Bao affine là trục hoành, và quanh mỗi điểm, phần giao của quả cầu với trục hoành là một đoạn thẳng chứa vô số điểm không thuộc tập. Định lý "nội tương đối luôn khác rỗng" bắt buộc phải có giả thiết tập hợp lồi.

Câu 2. Nếu C1⊆C2, liệu có thể suy ra relintC1⊆relintC2 hay không? Hãy kiểm tra với C1 là một cạnh của hình vuông và C2 là toàn bộ hình vuông trong R2.

Xem lời giải thích

Khẳng định này không đúng. Lấy C1=[0,1]×{0} là cạnh dưới của hình vuông đơn vị C2=[0,1]2. Nội tương đối của C1 là cạnh đó bỏ đi hai đầu mút, chứa điểm (12,0). Tuy nhiên, điểm (12,0) nằm trên biên của hình vuông, do đó không thuộc relintC2=(0,1)2. Phép lấy nội tương đối không có tính bảo toàn quan hệ bao hàm như phép lấy phần trong thông thường, bởi bao affine của tập con có thể có số chiều nhỏ hơn hẳn bao affine của tập mẹ.

Câu 3. Trong bài toán tối ưu có ràng buộc x1+x2=1 và x1,x2≥0, những điểm nào thuộc nội tương đối của ? Điểm (12,12) có phải là điểm trong của miền khả thi xét trong R2 hay không?

Xem lời giải thích

là đoạn thẳng nối hai điểm (1,0) và (0,1). Nội tương đối của miền này là đoạn thẳng bỏ đi hai đầu mút, gồm các điểm thỏa mãn x1+x2=1 và x1>0,x2>0. Điểm (12,12) thuộc nội tương đối của miền khả thi, nhưng không phải là điểm trong trong R2 vì miền khả thi là một đoạn thẳng không có độ dày trong mặt phẳng. Với những miền khả thi như vậy, điều kiện Slater bắt buộc phải phát biểu thông qua nội tương đối mới phản ánh đúng bản chất bài toán.

Câu 4. Nếu ta thử thay đổi định nghĩa điểm trong tương đối bằng cách lấy không gian con phương V đi kèm affC thay vì chính affC, định nghĩa đó có cho cùng kết quả hay không?

Xem lời giải thích

Không, trừ trường hợp affC đi qua gốc tọa độ. Chẳng hạn với đoạn thẳng nối (1,0) và (0,1), bao affine là đường thẳng x1+x2=1, trong khi không gian con phương đi kèm là đường thẳng x1+x2=0 đi qua gốc tọa độ. Hai đường thẳng này song song và không có điểm chung. Do đó, việc giao quả cầu quanh một điểm của tập với không gian con phương sẽ cho kết quả rỗng hoặc không liên quan gì tới tập ban đầu. Định nghĩa nội tương đối bắt buộc phải sử dụng bao affine, một không gian phẳng bao bọc trực tiếp .

7. Bài tập tự luyện ​

Bài tập 1: Xác định nội tương đối của các tập hình học

Tìm chiều affine, phần trong và nội tương đối của các sau:

  1. :
    S1={(x1,x2,x3)∈R3∣x12+x22≤1, x3=2}.
  2. :
    S2={x∈R3∣xi≥0, x1+x2+x3=1}.
  3. Đoạn thẳng S3 nối hai điểm (1,1) và (3,2) trong R2.
Lời giải
  1. Tập S1 là một hình tròn đặc nằm trong mặt phẳng x3=2: Bao affine là mặt phẳng {x∣x3=2} có chiều bằng 2, do đó chiều affine bằng 2. Phần trong trong R3 bằng rỗng. Nội tương đối là:
    relintS1={x∈R3∣x12+x22<1, x3=2}.
  2. Tập S2 là đơn hình xác suất trong R3: Bao affine là mặt phẳng x1+x2+x3=1 có chiều bằng 2, chiều affine bằng 2. Phần trong trong R3 bằng rỗng. Nội tương đối là:
    relintS2={x∈R3∣xi>0, x1+x2+x3=1}.
  3. Đoạn thẳng S3: Bao affine là đường thẳng đi qua hai điểm, có chiều affine bằng 1. Phần trong trong R2 bằng rỗng. Nội tương đối là:
    relintS3={(1−t)(1,1)+t(3,2)∣0<t<1}.

Bài tập 2: Tính bất biến của nội tương đối đối với việc chọn chuẩn

Chứng minh rằng nếu thay ∥⋅∥2 bằng chuẩn cực đại ∥x∥∞=max1≤i≤n|xi| trong định nghĩa nội tương đối, thu được không thay đổi.

Gợi ý

Sử dụng mối quan hệ kẹp giữa hai chuẩn: Bất đẳng thức ∥x∥∞≤∥x∥2≤n∥x∥∞ giúp so sánh các quả cầu đồng tâm.

Lời giải

Ký hiệu B2(x,r) và B∞(x,r) lần lượt là các quả cầu mở theo và chuẩn cực đại. Từ bất đẳng thức ∥y−x∥∞≤∥y−x∥2, ta có quan hệ bao hàm B2(x,r)⊆B∞(x,r). Mặt khác, từ ∥y−x∥2≤n∥y−x∥∞, ta suy ra B∞(x,r/n)⊆B2(x,r).

Giả sử điểm x thỏa mãn điều kiện nội tương đối với chuẩn cực đại và bán kính r>0, tức:

B∞(x,r)∩affC⊆C.

Khi đó, vì B2(x,r)⊆B∞(x,r), ta có ngay:

B2(x,r)∩affC⊆B∞(x,r)∩affC⊆C,

chứng tỏ x cũng thỏa mãn điều kiện nội tương đối với . Ngược lại, nếu x thỏa mãn điều kiện với chuẩn Euclid ở bán kính r, thì quả cầu chuẩn cực đại với bán kính r′=r/n sẽ thỏa mãn B∞(x,r′)⊆B2(x,r), kéo theo x thuộc nội tương đối theo chuẩn cực đại. Do đó, hai chuẩn xác định cùng một tập nội tương đối.

Tóm tắt ​

Chiều affine của một là số chiều của bao affine của nó, thể hiện số chiều tối thiểu của không gian phẳng cần thiết để chứa trọn vẹn tập. Phần trong topo thông thường phụ thuộc vào không gian bao quanh, khiến các tập hợp bị dẹp có phần trong rỗng dù chúng có diện tích hay thể tích bên trong không gian riêng. Nội tương đối khắc phục triệt để nhược điểm này bằng cách giới hạn lân cận khảo sát bên trong bao affine. Hai khái niệm trùng nhau khi và chỉ khi chiều affine của tập bằng số chiều của không gian bao quanh.

Mọi khác rỗng trong không gian hữu hạn chiều đều có nội tương đối khác rỗng. Nội tương đối giữ vai trò quyết định trong việc thiết lập điều kiện tư cách ràng buộc Slater cho bài toán quy hoạch lồi, khẳng định tính liên tục của và phát biểu định lý siêu phẳng tách giữa các tập lồi.

Tài liệu tham khảo ​

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, Cambridge University Press.
  • R. Tyrrell Rockafellar, Convex Analysis, Princeton University Press.
Toàn bộ chủ đề của Lecture 01Về trang chương: bản đồ, Slides và Kiến thức nền
Ảnh & sơ đồ
100%
Ảnh tài liệu được phóng to