Giao diện
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
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
Kiến thức nền tảng bao gồm bao affine và khái niệm quả cầu Euclid
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
Định nghĩa. Chiều affine của
, ký hiệu , là số chiều của bao affine .
Một đoạn thẳng nối hai điểm phân biệt trong
này có chiều affine bằng 2, vì nó nằm trọn trong mặt phẳ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
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
Đị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
- Khi xét trong không gian một chiều
, phần trong của là khoảng mở . - Nhưng khi đặt chính đoạn thẳng đó nằm trên trục hoành của mặt phẳng
, tức , phần trong của nó trong lại rỗng hoàn toàn. Quanh điểm , 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
Một đoạn thẳng không có điểm trong, nhưng có nội tương đối
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
, ký hiệu , là
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
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
Đ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
trong đó
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 độ
Bao affine của tập
và biên tương đối là khung viền bốn cạnh:
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
Hình vuông nằm phẳng trong R³
Đ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
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 đó.
| | Không gian | Phần trong | Nội tương đối |
|---|---|---|---|
| Đoạn thẳng | Khoảng mở | Khoảng mở | |
| Đoạn nối hai điểm | Rỗng | Đoạn thẳng bỏ hai đầu mút | |
| Một điểm đơn lẻ | Rỗng | Chính điểm | |
| Hình tròn đặc | Hình tròn mở | Hình tròn mở | |
| Đơn hình xác suất chuẩn tắc | Rỗng | ||
| Đường thẳng | Rỗng | Chính đường thẳng đó |
Trường hợp điểm đơn lẻ
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 (
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
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ở
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
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
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
Câu 2. Nếu
Xem lời giải thích
Khẳng định này không đúng. Lấy
Câu 3. Trong bài toán tối ưu có ràng buộc
Xem lời giải thích
là đoạn thẳng nối hai điểm
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
Xem lời giải thích
Không, trừ trường hợ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:
- :
- :
- Đoạn thẳng
nối hai điểm và trong .
Lời giải
- Tập
là một hình tròn đặc nằm trong mặt phẳng : Bao affine là mặt phẳng có chiều bằng 2, do đó chiều affine bằng 2. Phần trong trong bằng rỗng. Nội tương đối là: - Tập
là đơn hình xác suất trong : Bao affine là mặt phẳng có chiều bằng 2, chiều affine bằng 2. Phần trong trong bằng rỗng. Nội tương đối là: - Đoạn thẳng
: Bao affine là đường thẳng đi qua hai điểm, có chiều affine bằng 1. Phần trong trong bằng rỗng. Nội tương đối là:
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
Gợi ý
Sử dụng mối quan hệ kẹp giữa hai chuẩn: Bất đẳng thức
Lời giải
Ký hiệu
Giả sử điểm
Khi đó, vì
chứng tỏ
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.