3.3 Giải thuật giảm bước nhanh nhất
3.3.1 Hướng giảm nhanh nhất
Xét dãy truy hồi được cho bởi Công thức (3.3). Giả sử hướng chấp nhận đượcdk được cố định. Thực hiện khai triển Taylor đối với f(xk+1) =
f(xk+αkdk)tại điểmxkta thu được:
f(xk+αkdk) =f(xk) +αk∇f(xk)Tdk+o(αk),
trong đóo(αk)là vô cùng bé bậc cao hơnαk. Giả sử thêm rằng∇f(xk)6=0.
Để đảm bảo cho Điều kiện (3.2) xảy ra với kích thước bướcαk>0nào đó đủ bé, chúng ta cần
∇f(xk)Tdk<0.
Theo Định lý 1.5.2 điều này tương đương với đạo hàm theo hướngf0(xk,dk)<
0. Như vậy đển hàm f giảm nhanh sau mỗi bước lặp, chúng ta cần chọn hướng chấp nhận đượcdksao cho đạo hàm theo hướngdkcủa hàm số f tại điểmxknhỏ nhất có thể. Với mỗi hướng chấp nhận đượcdkkhông đổi ta có thể xemdkcó độ dàikdkk=1. Khi đó, theo bất đẳng thức Cauchy-Schwarz, ta có:
k∇f(xk)Tdkk≤k∇f(xk)k.kdkk=k∇f(xk)k. Do đó
− k∇f(xk)k≤∇f(xk)dk≤k∇f(xk)k.
Vậy∇f(xk)Tdk nhỏ nhất khidk =−∇f(xk). Nói cách khác, f(xk+αdk) giảm nhanh nhất theo hướngdk=−∇f(xk)(được gọi là hướng giảm nhanh nhất). Khi đó, Công thức (3.3) trở thành:
xk+1=xk−αk∇f(xk). (3.8)
Đây là một giải thuật quan trọng trong các giải thuật tối ưu và là cơ sở để hình thành nên các phương pháp khác tiên tiến hơn.
Ví dụ 3.3.1. Tìm cực tiểu của hàm số f :R2→Rxác định bởi:
f(x1,x2) =x31+x22−3x1−2x2+12,
vớix1,x2∈R. Giải:Ta có
∇f(x)T = (3x21−3,2x2−2).
Với điều xuất phátx0= (1,2)T, ta có:
∇f(x0)T = (0,2).
Khi đó, ta được:
x1 = x0−α0∇f(x0) =
1 2
−α
0 2
=
1 2−2α
.
α0được chọn sao choϕ(α0) = f(x1) =4α20−4α0+10đạt giá trị nhỏ nhất.
Dễ dàng tìm đượcα0=1/2. Khi đó, x1= (1,1)T và ∇f(x1) =0. Vậy, x= (1,1)T là cực tiểu địa phương chặt của f.
3.3.2 Kích thước bước hằng
Dạng đơn giản nhất của giải thuật giảm bước nhanh nhất thu được bằng cách cố định mọi kích thước bướcαk tại một giá trị không đổiα>0. Khi đó, giải thuật có dạng
xk+1=xk−α∇f(xk). (3.9) Định lý 3.3.1. Cho hàm số f ∈C1 có gradient liên tục Lipschitz với hằng sốM, nghĩa là f thỏa mãn
k∇f(x)−∇f(y)k≤Mkx−yk,∀x,y∈Rn.
Hơn nữa, giả sử thêm rằng f bị chặn dưới. Khi đó, nếu kích thước bướcα thỏa mãn bất đẳng thức
0<α< 1 M,
thì với mọix0, dãy{xk}sinh ra bởi Giải thuật(3.9)đều mãn điều kiện
k→∞lim∇f(xk) =0.
Chứng minh. Áp dụng Định lý về giá trị trung gian (Định lý 1.6.1) ta có:
f(xk+1) = f(xk+αdk) = f(xk) +α∇f(x)Tdk, vớix=θxk+ (1−θ)xk+1,θ∈[0; 1]. Do đó,
f(xk+1) = f(xk) +α∇f(xk)Tdk+α(∇f(x)−∇f(xk))Tdk
≤ f(xk) +α∇f(xk)Tdk+αk∇f(x)−∇f(xk)k.kdkk.
vớidk=−∇f(xk)và sử dụng tính liên tục Lipschitz của gradient, ta được f(xk+1)≤f(xk)−αk∇f(xk)k2+αMkxk−xk.k∇f(xk)k. Mặt kháckxk−xk= (1−θ)kxk−xk+1k≤αk∇f(xk)k. Do đó, bất đẳng thức trên tương đương với:
f(xk+1) ≤ f(xk)−αk f(xk)k2+α2Mk∇f(xk)k2
≤ f(xk)−α(1−αM)k∇f(xk)k2
⇒ f(xk)−f(xk+1) ≥ α(1−αM)k∇f(xk)k2 (3.10) Theo giả thiết ta có
0<α< 1
M⇔α(1−αM)>0.
Vậy f(xk+1)≤ f(xk)với mọik. Dãy{f(xk)}đơn điệu giảm và bị chặn dưới nên tồn tại giới hạn hữu hạn. Do đó
k→∞lim[f(xk)−f(xk+1)] =0.
Kết hợp với (3.10), ta được
0≤α(1−αM)k∇f(xk)k2≤f(xk)−f(xk+1)→0.
Vậy
k→∞lim∇f(xk) =0.
Hệ quả 3.3.1. Trong Định lý 3.3.1, giả sử thêm rằng tập hợp X0={x∈Rn|f(x)≤ f(x0)},
bị chặn. Khi đó, dãy{xk}bị chặn và mọi điểm tụx∗của dãy đều thỏa mãn điều kiện∇f(x∗) =0.
Chứng minh. Dễ thấy mọi phần tử thuộc dãy{xk} đều thuộc X0 nên dãy {xk} bị chặn. Giả sử x∗ là một điểm tụ của dãy {xk} thì tồn tại dãy con {xm}của{xk}hội tụ đếnx∗. Theo Định lý 3.3.1 ta có
m→∞lim∇f(xm) =0⇒∇f(x∗) =0.
3.3.3 Quy tắc Goldstein trong giải thuật giảm bước nhanh nhất
Một trong những hạn chế của giải thuật với kích thước bước hằng là cần phải biết hằng số LipschitzM của gradient. Vì thế, để khắc phục hạn chế này, chung ta sẽ sử dụng phương pháp tìm kích thước bước không chính xác. Như đã được trình bày ở phần trước, phương pháp đơn giản có thể sử dụng để xác định kích thước bước là quy tắc Goldstein. Phương pháp này tìm giá trị xấp xỉ cho cực tiểu của hàm số một biến
ϕ(αk) = f(xk−αk∇f(xk)).
Nhắc lại rằng, trong quy tắc Golstein, vớiβ∈(0; 1/2)chúng ta cần tìm αksao cho
1−β≤ f(xk+1)−f(xk) αk∇f(xk)Tdk
≤β.
Để ý rằngdk=−∇f(xk)nên bài toán tương đương với việc tìmαksao cho f(xk)−(1−β)αkk∇f(xk)k2≤ f(xk+1)≤ f(xk)−βαkk∇f(xk)k2(3.11). Sự hội tụ của giải thuật giảm bước nhanh với đường tìm kiếm được xấp xỉ bởi Quy tắc Golstein được phát biểu trong định lý sau:
Định lý 3.3.2. Cho f∈C1và có gradient liên tục Lipschitz với hằng sốM.
Giả sửX0={x∈Rn|f(x)≤ f(x0)}bị chặn. Khi đó, dãy{xk}sinh bởi giải thuật giảm bước nhanh nhất vớiαk được chọn theo Quy tắc Goldstein là dãy bị chặn và mọi điểm tụx∗của dãy đều thỏa điều kiện∇f(x∗) =0.
Chứng minh. Từ vế phải của (3.11), ta được f(xk+1)≤ f(xk).
VìX0bị chặn nên dãy{f(xk)}bị chặn và do đó nó hội tụ. Hơn nữa, từ vế phải của bất đẳng thức (3.11) suy ra:
αkk∇f(xk)k2≤ f(xk)−f(xk+1)
β .
Do đó
k→∞limαkk∇f(xk)k2=0. (3.12)
Theo chứng minh ở Định lý 3.3.1 ta có bất đẳng thức (3.10), tức là f(xk+1)≤ f(xk)−αk(1−αkM)k∇f(xk)k2.
Do đó, kết hợp với vế trái của bất đẳng thức (3.11), ta có
f(xk)−αk(1−β)k∇f(xk)k2≤ f(xk)−αk(1−αkM)k∇f(xk)k2.
Rút gọn thu được
βk∇f(xk)k2≤αkMk∇f(xk)k2.
Chok→∞, ta nhận được
k→∞limk∇f(xk)k=0⇒∇f(x∗) =0.