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 3 - Hoàng Nam Dũng

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

Báo xấu

35
lượt xem 4
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 3: Bài toán tối ưu không ràng buộc" cung cấp cho người học các kiến thức: Bài toán tối ưu không ràng buộc, điều kiện cực tiểu địa phương, cực tiểu của hàm lồi, tổng quan về thuật toán,... 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 3 - Hoàng Nam Dũng

Bài toán tối ưu không ràng buộc 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
Bài toán tối ưu không ràng buộc (unconstrained) min f (x) x với f : Rn → R là một hàm trơn (smooth). 1
Bài toán tối ưu không ràng buộc (unconstrained) min f (x) x với f : Rn → R là một hàm trơn (smooth). Định nghĩa x ∗ được gọi là cực tiểu toàn cục nếu f (x ∗ ) ≤ f (x), ∀x. 1
Bài toán tối ưu không ràng buộc (unconstrained) min f (x) x với f : Rn → R là một hàm trơn (smooth). Định nghĩa x ∗ được gọi là cực tiểu toàn cục nếu f (x ∗ ) ≤ f (x), ∀x. x ∗ được gọi là cực tiểu địa phương nếu tồn tại một lân cận N của x ∗ sao cho f (x ∗ ) ≤ f (x), ∀x ∈ N . 1
Bài toán tối ưu không ràng buộc (unconstrained) min f (x) x với f : Rn → R là một hàm trơn (smooth). Định nghĩa x ∗ được gọi là cực tiểu toàn cục nếu f (x ∗ ) ≤ f (x), ∀x. x ∗ được gọi là cực tiểu địa phương nếu tồn tại một lân cận N của x ∗ sao cho f (x ∗ ) ≤ f (x), ∀x ∈ N . x ∗ được gọi là cực tiểu địa phương mạnh (hay ngặt) nếu tồn tại một lân cận N của x ∗ sao cho f (x ∗ ) < f (x), ∀x ∈ N \{x ∗ }. 1
Ví dụ Hàm số dưới đây có nhiều cực tiểu địa phương và khó để tìm cực tiểu toàn cục. 2
Điều kiện cực tiểu địa phương Định lý (Khai triển Taylor) Cho f : Rn → R khả vi liên tục và p ∈ Rn . Ta có f (x + p) = f (x) + ∇f (x + tp)T p, với t ∈ (0, 1) nào đó. 3
Điều kiện cực tiểu địa phương Định lý (Khai triển Taylor) Cho f : Rn → R khả vi liên tục và p ∈ Rn . Ta có f (x + p) = f (x) + ∇f (x + tp)T p, với t ∈ (0, 1) nào đó. Nếu f khả vi liên tục hai lần thì 1 f (x + p) = f (x) + ∇f (x)T p + p T ∇2 f (x + tp)p, 2 với t ∈ (0, 1) nào đó. 3
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc nhất) Nếu x ∗ là một cực tiểu địa phương và f khả vi liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0. 4
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc nhất) Nếu x ∗ là một cực tiểu địa phương và f khả vi liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0. Chứng minh. Giả sử ∇f (x ∗ ) 6= 0. Chọn p = −∇f (x ∗ ) thì p T ∇f (x ∗ ) = −k∇f (x ∗ )k2 < 0. 4
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc nhất) Nếu x ∗ là một cực tiểu địa phương và f khả vi liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0. Chứng minh. Giả sử ∇f (x ∗ ) 6= 0. Chọn p = −∇f (x ∗ ) thì p T ∇f (x ∗ ) = −k∇f (x ∗ )k2 < 0. Từ đó và do ∇f liên tục trong lân cận của x ∗ , tồn tại T > 0 sao cho p T ∇f (x ∗ + sp) < 0, ∀s ∈ [0, T ]. 4
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc nhất) Nếu x ∗ là một cực tiểu địa phương và f khả vi liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0. Chứng minh. Giả sử ∇f (x ∗ ) 6= 0. Chọn p = −∇f (x ∗ ) thì p T ∇f (x ∗ ) = −k∇f (x ∗ )k2 < 0. Từ đó và do ∇f liên tục trong lân cận của x ∗ , tồn tại T > 0 sao cho p T ∇f (x ∗ + sp) < 0, ∀s ∈ [0, T ]. Với mỗi t ∈ (0, T ] theo định lý Taylor tồn tại s ∈ (0, t) sao cho f (x ∗ + tp) = f (x ∗ ) + t∇f (x ∗ + sp)T p 4
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc nhất) Nếu x ∗ là một cực tiểu địa phương và f khả vi liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0. Chứng minh. Giả sử ∇f (x ∗ ) 6= 0. Chọn p = −∇f (x ∗ ) thì p T ∇f (x ∗ ) = −k∇f (x ∗ )k2 < 0. Từ đó và do ∇f liên tục trong lân cận của x ∗ , tồn tại T > 0 sao cho p T ∇f (x ∗ + sp) < 0, ∀s ∈ [0, T ]. Với mỗi t ∈ (0, T ] theo định lý Taylor tồn tại s ∈ (0, t) sao cho f (x ∗ + tp) = f (x ∗ ) + t∇f (x ∗ + sp)T p < f (x ∗ ), mâu thuẫn. 4
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc hai) Nếu x ∗ là một cực tiểu địa phương và ∇2 f tồn tại và liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0 và ∇2 f (x ∗ ) là nửa xác định dương (positive semidefinite). 5
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc hai) Nếu x ∗ là một cực tiểu địa phương và ∇2 f tồn tại và liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0 và ∇2 f (x ∗ ) là nửa xác định dương (positive semidefinite). Chứng minh. Từ định lý trước ta có ∇f (x ∗ ) = 0. 5
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc hai) Nếu x ∗ là một cực tiểu địa phương và ∇2 f tồn tại và liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0 và ∇2 f (x ∗ ) là nửa xác định dương (positive semidefinite). Chứng minh. Từ định lý trước ta có ∇f (x ∗ ) = 0. Giả sử ∇2 f (x ∗ ) không phải nửa xác định dương, tức là tồn tại p sao cho p T ∇2 f (x ∗ )p < 0. 5
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc hai) Nếu x ∗ là một cực tiểu địa phương và ∇2 f tồn tại và liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0 và ∇2 f (x ∗ ) là nửa xác định dương (positive semidefinite). Chứng minh. Từ định lý trước ta có ∇f (x ∗ ) = 0. Giả sử ∇2 f (x ∗ ) không phải nửa xác định dương, tức là tồn tại p sao cho p T ∇2 f (x ∗ )p < 0. Vì ∇2 f liên tục quanh x ∗ nên tồn tại T > 0 sao cho p T ∇2 f (x ∗ + sp)p < 0, ∀s ∈ [0, T ]. 5
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc hai) Nếu x ∗ là một cực tiểu địa phương và ∇2 f tồn tại và liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0 và ∇2 f (x ∗ ) là nửa xác định dương (positive semidefinite). Chứng minh. Từ định lý trước ta có ∇f (x ∗ ) = 0. Giả sử ∇2 f (x ∗ ) không phải nửa xác định dương, tức là tồn tại p sao cho p T ∇2 f (x ∗ )p < 0. Vì ∇2 f liên tục quanh x ∗ nên tồn tại T > 0 sao cho p T ∇2 f (x ∗ + sp)p < 0, ∀s ∈ [0, T ]. Áp dụng định lý Taylor ta có với mỗi t ∈ (0, T ] tồn tại s ∈ (0, t) sao cho 1 f (x ∗ + tp) = f (x ∗ ) + t∇f (x ∗ )T p + t 2 p T ∇2 f (x ∗ + sp)p 2 5
Điều kiện cực tiểu địa phương Định lý (Điều kiện cần bậc hai) Nếu x ∗ là một cực tiểu địa phương và ∇2 f tồn tại và liên tục trong một lân cận mở của x ∗ thì ∇f (x ∗ ) = 0 và ∇2 f (x ∗ ) là nửa xác định dương (positive semidefinite). Chứng minh. Từ định lý trước ta có ∇f (x ∗ ) = 0. Giả sử ∇2 f (x ∗ ) không phải nửa xác định dương, tức là tồn tại p sao cho p T ∇2 f (x ∗ )p < 0. Vì ∇2 f liên tục quanh x ∗ nên tồn tại T > 0 sao cho p T ∇2 f (x ∗ + sp)p < 0, ∀s ∈ [0, T ]. Áp dụng định lý Taylor ta có với mỗi t ∈ (0, T ] tồn tại s ∈ (0, t) sao cho 1 f (x ∗ + tp) = f (x ∗ ) + t∇f (x ∗ )T p + t 2 p T ∇2 f (x ∗ + sp)p < f (x ∗ ), 2 mâu thuẫn. 5
Điều kiện cực tiểu địa phương Điều kiện cần bậc 2 không phải là điều kiện đủ. Ví dụ với f (x) = x 3 thì f 0 (0) = 0 và f 00 (0) = 0, tức là x = 0 thỏa mãn điều kiện cần bậc 2, tuy nhiên nó không phải là một điểm cực tiểu địa phương của x 3 . 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.