Hàm tự tương hợp (self-concordant)

Tự tương hợp là điều kiện khống chế tốc độ thay đổi của bậc hai bằng chính thang độ cong hiện tại. Điều kiện này giúp phân tích bước Newton, nhưng không phải tên khác của tính lồi.

Lĩnh vực: Thuật toán tối ưu

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

• Tối ưu không ràng buộc và ràng buộc đẳng thứcToán cho AI

Giải thích kỹ thuật

Định nghĩa theo mọi đường. Trong một chiều, chuẩn tự tương hợp dùng $|f\prime \prime \prime (x)|\le 2[f\prime \prime (x){]}^{3/2}$. Trong nhiều chiều, áp dụng điều kiện ấy cho $t\mapsto f(x+tv)$ với mọi $x,v$ sao cho đường nằm trong miền.

Điều kiện bất biến affine thích hợp này kiểm soát mức đổi trong chuẩn cục bộ, nhờ đó Newton decrement có thể quyết định khi nào bước Newton đầy đủ an toàn. Các hằng số và bảo đảm cần đúng phiên bản định nghĩa đang dùng. Nguồn: Convex Optimization, §9.6.

Ví dụ

$f(x)=-\log x$ trên $x>0$ thỏa $|f^{‴}(x)|=2[f^{″}(x){]}^{3/2}=\frac{2}{x^3}$.

Khi nào cần dùng?

Phân tích Newton cho hàm barrier và các bài tối ưu lồi.

Câu hỏi ôn lại

Mọi có tự tương hợp không?

Xem đáp án

Không. Tự tương hợp là một giả thiết bổ sung.

Thuật ngữ liên quan

• Hessian
• Tìm kiếm đường và backtracking
• Điều kiện KKT