Bài giảng "Tối ưu hóa nâng cao - Chương 4: Line search method" cung cấp cho người học các kiến thức: Line search method, hướng giảm, hướng giảm nhanh/dốc nhất, hướng giảm phổ biến, lựa chọn độ dài bước, . | Bài giảng Tối ưu hóa nâng cao: Chương 4 - Hoàng Nam Dũng Line search method Hoàng Nam Dũng Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội Line search method Tại mỗi bước, từ điểm xk hiện tại, phương pháp line search tính một hướng tìm kiếm (search direction) pk rồi quyết định sẽ tiến bao xa theo hướng đó. 1 Line search method Tại mỗi bước, từ điểm xk hiện tại, phương pháp line search tính một hướng tìm kiếm (search direction) pk rồi quyết định sẽ tiến bao xa theo hướng đó. Công thức lặp để tính điểm tiếp theo được cho bởi xk+1 = xk + αk pk trong đó αk > 0 được gọi là độ dài bước (step length). 1 Line search method Tại mỗi bước, từ điểm xk hiện tại, phương pháp line search tính một hướng tìm kiếm (search direction) pk rồi quyết định sẽ tiến bao xa theo hướng đó. Công thức lặp để tính điểm tiếp theo được cho bởi xk+1 = xk + αk pk trong đó αk > 0 được gọi là độ dài bước (step length). Hiệu quả của phương pháp phụ thuộc vào việc chọn hướng pk và độ dài bước αk thích hợp. 1 Line search method Tại mỗi bước, từ điểm xk hiện tại, phương pháp line search tính một hướng tìm kiếm (search direction) pk rồi quyết định sẽ tiến bao xa theo hướng đó. Công thức lặp để tính điểm tiếp theo được cho bởi xk+1 = xk + αk pk trong đó αk > 0 được gọi là độ dài bước (step length). Hiệu quả của phương pháp phụ thuộc vào việc chọn hướng pk và độ dài bước αk thích hợp. Hầu hết các phương pháp line search đòi hỏi pk là một hướng giảm (descent direction) pkT ∇f (xk ) < 0 bởi nó sẽ đảm bảo là giá trị hàm f có thể giảm xuống theo hướng này. 1 Hướng giảm (descent direction) Giả sử p là một hướng giảm, tức là p T ∇f (xk ) < 0. 2 Hướng giảm (descent direction) Giả sử p là một hướng giảm, tức là p T ∇f (xk ) < 0. Theo công thức khai triển Taylor ta có f (xk + αp) = f (xk ) + αp T ∇f (xk ) + O(α2 ). 2 Hướng giảm (descent direction) .
