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,. . | 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
