Epigraph

Epigraph của f là tập các cặp (x,t) thỏa $t\ge f(x)$. Hàm f lồi khi và chỉ khi epigraph của nó là một . Nói cách khác, ta xét cả miền phía trên thay vì chỉ xét đường đồ thị.

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.

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
• Các bài toán tối ưu lồiToán cho AI

Giải thích kỹ thuật

Đưa giá trị hàm thành một tọa độ. Epigraph của $f$ là $\mathrm{epi}f=\{(x,t):x\in \mathrm{dom}f,f(x)\le t\}$. Điều kiện $t\ge f(x)$ đặt điểm ở trên trong trường hợp một biến.

Phép cải dạng epigraph thay $\underset{x}{min}f(x)$ bằng $\underset{x,t}{min}t$ với $f(x)\le t$. Hai bài có cùng giá trị tối ưu và thu hồi cùng $x$ tối ưu khi giá trị nhỏ nhất đạt được. Với $f=\underset{i}{max}{f}_i$, ràng buộc epigraph tách thành $f_i(x)\le t$ cho mọi $i$. Nguồn: Convex Optimization, §3.1.7 và §4.1.3.

Ví dụ

Epigraph của $f(x)=x^2$ là miền $t\ge x^2$. Điểm (0,1) thuộc epigraph còn $(0,-1)$ thì không.

Khi nào cần dùng?

Đổi một mục tiêu hoặc maximum thành ràng buộc với biến phụ.

Câu hỏi ôn lại

của một có nhất thiết là không?

Xem đáp án

Không. Epigraph mới là .

Thuật ngữ liên quan

• Hàm lồi
• Tập lồi
• Nới lỏng bài toán