Đa diện và đơn hình

Đa diện là tập nghiệm của hữu hạn bất đẳng thức và đẳng thức tuyến tính, $\{x:Ax⪯b,Cx=d\}$, tức giao của hữu hạn và siêu phẳng. Đơn hình là của các điểm affine, chẳng hạn đơn hình xác suất $\{x⪰0:x_1+\cdots +x_n=1\}$.

Lĩnh vực: Tối ưu hóa

Định nghĩa trên trang này được dùng trong lĩnh vực vừa nêu. Một từ giống nhau ở môn khác có thể mang nghĩa khác.

Giải thích kỹ thuật

Hai cách mô tả. Một đa diện bị chặn có thể mô tả bằng các bất đẳng thức, tức giao của , hoặc bằng các đỉnh, tức của hữu hạn điểm. Hai cách mô tả có thể chênh lệch rất lớn về kích thước: Khối lập phương trong ${\mathbb{R}}^n$ có $2n$ mặt nhưng $2^n$ đỉnh.

Đơn hình xác suất. Mỗi điểm của đơn hình xác suất là một phân phối trên $n$ kết quả, và các đỉnh là những phân phối chắc chắn. Đầu ra của một bộ phân loại luôn nằm trong của đơn hình này. Nguồn: Convex Optimization, §2.2.4.

Ví dụ

Tam giác $\{x\in {\mathbb{R}}^2:x⪰0,x_1+x_2\le 1\}$ vừa là đa diện vừa là đơn hình, với ba đỉnh $(0,0)$, $(1,0)$ và $(0,1)$.

Khi nào cần dùng?

của và tập các phân phối xác suất rời rạc.

Câu hỏi ôn lại

Hình tròn có phải đa diện không?

Xem đáp án

Không. Hình tròn là giao của vô số và không viết được bằng hữu hạn bất đẳng thức tuyến tính.

Thuật ngữ liên quan

• Siêu phẳng và nửa không gian
• Tập lồi
• Nghiệm cơ sở của quy hoạch tuyến tính