zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Khoa Học Tự Nhiên

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

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:54

Báo xấu

56
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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) 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. 2
Hướ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 3
Hướ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 ). 3
Hướ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 θ, 3
Hướ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 3
Hướ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 descent method hay gradient descent method. 3
Hướng giảm phổ biến Ta thường chọn hướng giảm có dạng pk = −Bk1 ∇f (xk ) trong đó Bk là một ma trận đối xứng không suy biến. 4
Hướng giảm phổ biến Ta thường chọn hướng giảm có dạng pk = −Bk1 ∇f (xk ) trong đó Bk là một ma trận đối xứng không suy biến. I Phương pháp gradient descent: Bk = I I Phương pháp Newton: Bk = ∇2 f (xk ) I Phương pháp tựa Newton: Bk xấp xỉ ma trận Hessian ∇2 f (xk ). 4
Hướng giảm phổ biến Ta thường chọn hướng giảm có dạng pk = −Bk1 ∇f (xk ) trong đó Bk là một ma trận đối xứng không suy biến. I Phương pháp gradient descent: Bk = I I Phương pháp Newton: Bk = ∇2 f (xk ) I Phương pháp tựa Newton: Bk xấp xỉ ma trận Hessian ∇2 f (xk ). Phần tiếp theo chúng ta sẽ tìm hiểu xem chọn hướng và độ dài bước như thế nào để thuật toán hội tụ. 4
Lựa chọn độ dài bước Ta phải cân nhắc lựa chọn giữa hai yếu tố I Tìm αk để cải thiện đáng kể giá trị hàm mục tiêu I Đồng thời không được mất quá nhiều thời gian. 5
Lựa chọn độ dài bước Ta phải cân nhắc lựa chọn giữa hai yếu tố I Tìm αk để cải thiện đáng kể giá trị hàm mục tiêu I Đồng thời không được mất quá nhiều thời gian. Lý tưởng thì αk là nghiệm của bài toán tối ưu min φ(α) = f (xk + αpk ), α > 0. 5
Lựa chọn độ dài bước Ta phải cân nhắc lựa chọn giữa hai yếu tố I Tìm αk để cải thiện đáng kể giá trị hàm mục tiêu I Đồng thời không được mất quá nhiều thời gian. Lý tưởng thì αk là nghiệm của bài toán tối ưu min φ(α) = f (xk + αpk ), α > 0. Tuy nhiên nó quá tốn kém (ví dụ xem hình vẽ). 5
Lựa chọn độ dài bước Để tìm cực tiểu địa phương với độ chính xác vừa phải có thể ta phải tính rất nhiều lần hàm mục tiêu f và gradient ∇f . 6

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.