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

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.
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 3 - Hoàng Nam DũngBài toán tối ưu không ràng buộcHoà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ộiBà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). 1Bà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. 1Bà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 . 1Bà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 ∗ }. 1Ví 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ê ...