Tổ hợp lồi

lồi là tổng có trọng số không âm và tổng trọng số bằng 1. Với hai điểm, $\lambda x+(1-\lambda )y$, $0\le \lambda \le 1$, chạy trên đoạn thẳng nối chúng. Cho $\lambda$ ngoài khoảng đó thường đưa điểm ra khỏi đoạn thẳng.

Lĩnh vực: Đại số & giải tích

Đị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.

Bài giảng dùng khái niệm này

• Giới thiệu tối ưu, tập lồi và hàm lồiToán cho AI

Giải thích kỹ thuật

Nhiều điểm và điều kiện trọng số. Với $k$ điểm $x_1,\dots ,x_k$, một lồi được biểu diễn dưới dạng tường minh:

$$z={\lambda }_1{x}_1+{\lambda }_2{x}_2+\cdots +{\lambda }_k{x}_k=\sum _{i=1}^k{\lambda }_i{x}_i.$$

Mỗi trọng số không âm và tổng toàn bộ các trọng số bằng 1:

$$\sum _{i=1}^k{\lambda }_i={\lambda }_1+{\lambda }_2+\cdots +{\lambda }_k=1({\lambda }_i\ge 0,\mathrm{\forall }i=1,\dots ,k).$$

Về mặt bản chất, đây là một phép bình quân gia quyền hay trộn tỉ lệ phần trăm (tổng bằng 100% và không có thành phần âm):

$$z=\sum _{i=1}^k{\lambda }_i{x}_i,\sum _{i=1}^k{\lambda }_i=1,{\lambda }_i\ge 0(\mathrm{\forall }i=1,\dots ,k)$$

Chỉ số $i$ chạy từ 1 đến $k$, qua các điểm đã chọn. Khi phạm vi ngữ cảnh đã hoàn toàn rõ ràng, tài liệu có thể viết vắn tắt là $\sum _i{\lambda }_i=1$ (hoặc dùng ký hiệu ${\theta }_i$ thay cho ${\lambda }_i$).

Với hai điểm ($k=2$), điều kiện trở thành $\lambda x+(1-\lambda )y$ với $\lambda \in [0,1]$, quét nên trọn vẹn đoạn thẳng nối hai điểm. Nếu bỏ điều kiện không âm mà chỉ giữ tổng bằng 1, ta được kéo dài ra vô hạn trên toàn bộ đường thẳng. Bao lồi là chứa tất cả các lồi có thể tạo ra từ các điểm đã cho.

Ví dụ

$x=0$, $y=10$, $\lambda =0.3$: Điểm tạo ra là $0.3\times 0+0.7\times 10=7$.

Khi nào cần dùng?

Đọc định nghĩa , và nội suy.

Câu hỏi ôn lại

$2x-y$ có phải lồi của x và y không?

Xem đáp án

Không. Trọng số của y là −1, vi phạm điều kiện không âm.

Thuật ngữ liên quan

• Vector
• Tập hợp
• Hàm số