Bài giảng Tối ưu hóa nâng cao: Chương 4 - Hoàng Nam Dũng

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,.... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Tối ưu hóa nâng cao: Chương 4 - Hoàng Nam DũngLine search methodHoàng Nam DũngKhoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà NộiLine 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 đó. 1Line 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). 1Line 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. 1Line 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. 1Hướng giảm (descent direction) Giả sử p là một hướng giảm, tức là p T ∇f (xk ) < 0. 2Hướ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 ). 2Hướ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 ). Suy ra f (xk + αp) < f (xk ) với α > 0 đủ nhỏ. Tức là ta có thể giảm giá trị hàm số f theo hướng p. 2Hướng giảm nhanh/dốc nhất (steepest descent direction) Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min p T ∇f (xk ), s.t. kpk = 1. p 3Hướng giảm nhanh/dốc nhất (steepest descent direction) Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min p T ∇f (xk ), s.t. kpk = 1. p Gọi θ là góc giữa p và ∇f (xk ). 3Hướng giảm nhanh/dốc nhất (steepest descent direction) Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min p T ∇f (xk ), s.t. kpk = 1. p Gọi θ là góc giữa p và ∇f (xk ). Ta có p T ∇f (xk ) = kpkk∇f (xk )k cos θ = k∇f (xk )k cos θ, 3Hướng giảm nhanh/dốc nhất (steepest descent direction) Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min p T ∇f (xk ), s.t. kpk = 1. p Gọi θ là góc giữa p và ∇f (xk ). Ta có p T ∇f (xk ) = kpkk∇f (xk )k cos θ = k∇f (xk )k cos θ, tức là nó đạt giá trị bé nhất khi cos θ = −1 hay ∇f (xk ) p=− . k∇f (xk )k 3Hướng giảm nhanh/dốc nhất (steepest descent direction) Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min p T ∇f (xk ), s.t. kpk = 1. p Gọi θ là góc giữa p và ∇f (xk ). Ta có p T ∇f (xk ) = kpkk∇f (xk )k cos θ = k∇f (xk )k cos θ, tức là nó đạt giá trị bé nhất khi cos θ = −1 hay ∇f (xk ) p=− . k∇f (xk )k Phương pháp line search với pk = −∇f (xk ) được gọi là steepest d ...