Tìm kiếm đường và backtracking

Tìm kiếm đường chọn độ dài t sau khi đã có hướng d. Backtracking bắt đầu từ một bước thử rồi giảm dần cho đến khi điểm mới thuộc miền và cho mức giảm đủ theo điều kiện đã chọn.

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
• Các phương pháp tối ưu trong học sâuToán cho AI

Giải thích kỹ thuật

Điều kiện Armijo trong backtracking. Với hướng giảm $d$, chọn $0<\alpha <\frac{1}{2}$, $0<\beta <1$ và giảm $t\leftarrow \beta t$ cho tới khi

$$f(x+td)\le f(x)+\alpha t\mathrm{\nabla }f(x{)}^{T}d.$$

Nếu hàm có miền hạn chế, phải kiểm $x+td\in \mathrm{dom}f$ trước khi tính giá trị. Backtracking tìm một bước giảm đủ, không tìm minimum chính xác trên đường. Hướng và độ dài bước là hai quyết định riêng. Nguồn: Convex Optimization, §9.2–9.3.

Ví dụ

Với t ban đầu 1 và $\beta =\frac{1}{2}$, các bước thử lần lượt là 1, $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$,… cho tới khi đạt điều kiện.

Khi nào cần dùng?

Chọn bước cho descent, Newton và các hướng giảm khác.

Câu hỏi ôn lại

Một hướng giảm có bảo đảm mọi bước dương đều làm hàm giảm không?

Xem đáp án

Không. Chỉ các bước dương đủ nhỏ mới được bảo đảm cục bộ.

Thuật ngữ liên quan

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