Bài tập phương pháp tối ưu- Khai triển Taylor hàm nhiều biến
Vì f(1, 2) = 1 nên (1, 2) ∈ C(f; 1). Vec-tơ ∇f(1, 2) = (−2, 1) vuông. góc với C(f; 1) và hướng lên trên (tức là hướng vào miền H
+(f; 1)).Đường thẳng tiếp xúc với C(f; 1) tại (1, 2) có phương trình:h(−2, 1),(x − 1, y − 2)i = 0 ⇔ −2x + y = 0.
Cực tiểu địa phương:
Một điểm X. ∗ được gọi là cực tiểu địa phương của f, nếu tồn tại số dương ϵ sao cho f(x∗) ≤ f(x); ∀ x ∈ B(x∗; ϵ).
Tư tưởng thuật toán
Xuất phát từ một điểm x0 ta sẽ sinh ra các điểm x1, x2, … sao. cho dãy điểm (xk) sinh ra hội tụ về nghiệm. Tại mỗi bước thứ
k trước tiên ta cần xác định một hướng giảm tại đó, tức là tìm. vec-tơ dk sao cho h∇f(xk), dki < 0. Sau đó ta tìm một bước giảm
thích hợp αk > 0 sao cho f(xk + αkdk) < f(xk). Lúc đó ta đặt xk+1 := xk + αkdk.
Thuật toán tổng quát tìm điểm cực tiểu
Bước 0. Lấy x0 ∈ R
n , chọn sai số ϵ > 0, đặt k := 0.
Bước 1. Nếu k∇f(xk)k < ϵ, thì dừng. Ngược lại sang Bước 2.
Bước 2. Tìm hướng giảm dk: h∇f(xk), dki < 0.
Bước 3. Tìm bước giảm αk > 0 sao cho f(xk + αkdk) < f(xk).
Bước 4. Đặt xk+1 := xk + αkdk, k := k + 1.
Bước 5. Nếu kxk+1 − xkk < ϵ hoặc |f(xk+1) − f(xk)| < ϵ, thì dừng.
Ngược lại sang Bước 1.
Tìm kiếm theo tia
Trong thuật toán tổng quát, tại bước lặp thứ k, khi đã có xk và hướng giảm dk. ta cần tìm bước giảm αk > 0 sao cho: f(xk + αkdk) < f(xk).Lí tưởng nhất là ta tìm được αk > 0 sao cho:f(xk + αkdk) = minα>0f(xk + αdk).
Phương pháp nhát cắt vàng và Phương pháp Fibonacci
Khoảng đơn cách:Khoảng [a, b] được gọi là một khoảng đơn cách của hàm ϕ nếu tồn tại x∗ ∈ (a, b) sao cho ϕ giảm trên [a, x
∗. ] và tăng trên [x∗, b]
Ý tưởng các phương pháp:
Xuất phát từ một khoảng đơn cách [a0, b0] cho trước, ta chọn λ0, µ0 sao cho a0 < λ0 < µ0 < b0. Lúc đó một trong hai khoảng
[a0, µ0] và [λ0, b0] sẽ là khoảng đơn cách. Ta đặt tên khoảng đó. là [a1, b1]. Lại tiếp tục chọn λ1, µ1 sao cho a1 < λ1 < µ1 < b1
và lại chọn ra khoảng đơn cách [a2, b2]. Cứ tiếp tục như thế, đến. một bước nào đó, ta nhận được khoảng đơn cách [ak, bk] có độ dài
Bài tập phương pháp tối ưu- Thuật toán nhát cắt vàng:
Bước 0. Xác định [a0, b0], chọn ϵ > 0, k := 0. Tính
λ0 = a0 + 0, 382(b0 − a0); µ0 = a0 + 0, 618(b0 − a0);
ϕ1 := ϕ(λ0); ϕ2 := ϕ(µ0).
Bước 1. So sánh, Nếu ϕ1 > ϕ2: sang B2, nếu ϕ1 ≤ ϕ2: sang B3.
Bước 2. Nếu bk − λk ≤ ϵ Dừng với µk là nghiệm. Ngược lại thì
đặt ak+1 := λk; bk+1 := bk; λk+1 := µk; ϕ1 := ϕ2; Tính
µk+1 := ak+1 + 0.618(bk+1 − ak+1); ϕ2 := ϕ(µk+1).
Sang Bước 4.
Bước 3. Nếu µk − ak ≤ ϵ Dừng với λk là nghiệm. Ngược lại thì
đặt ak+1 := ak; bk+1 := µk; µk+1 := λk; ϕ2 := ϕ1; Tính
λk+1 := ak+1 + 0.382(bk+1 − ak+1); ϕ1 := ϕ(λk+1).
Sang Bước 4.
Bước 4. Đặt k := k + 1. Sang Bước 1.
