3.3 Giải thuật giảm bước nhanh nhất
3.3.5 Tốc độ hội tụ
Một trong những vấn đề quan trọng được xem xét khi sử dụng giải thuật lặp là tốc độ hội tụ. Trong giải thuật giảm bước nhanh nhất, ta giả sử f∈C2 và có ma trận Hessian thỏa mãn điều kiện
mI≤F(x)≤MI ,∀x∈Rn (3.16)
Hình 3.6: Đồ thị hàm sốϕ(α2)
với0<m≤M(nhắc lại rằngA≤BnếuB−Alà nửa xác định dương).
Khi đó, theo Định lý 1.7.2, f là hàm lồi chặt và nó có một cực tiểu duy nhấtx∗. Do đó, giải thuật giảm bước nhanh nhất hội tụ về nghiệm duy nhất cho Bài toán (3.1). Bây giờ, chúng ta sẽ xem xét tốc độ hội tụ của giải thuật này.
Định lý 3.3.4. Cho f ∈C2và thỏa mãn Điều kiện(3.16). Khi đó, giải thuật giảm bước nhanh nhất với kích thước bước hằngα∈(0,2/M)sinh ra một dãy{xk}thỏa mãn điều kiện
kxk+1−x∗k≤qkkx0−x∗k, vớiq=max(|1−αm|,|1−αM|)<1.
Chứng minh. Ta cóxk+1=xk−α∇f(xk)nên
xk+1−x∗=xk−x∗−α∇f(xk). (3.17) Vìx∗là cực tiểu của Bài toán (3.1) nên∇f(x∗) =0. Do đó, ta có biểu diễn
∇f(xk) = Z 1
0
[F(x∗+θ(xk−x∗))](xk−x∗)dθ.
Đặt
Qk= Z 1
0
[F(x∗+θ(xk−x∗))]dθ.
Khi đó, (3.17) trở thành
xk+1−x∗=xk−x∗−αQk(xk−x∗) = (I−αQk)(xk−x∗).
Vì thế,
kxk+1−x∗k≤kI−αQkk.kxk−x∗k. Theo (3.16), ta có
mI≤Qk≤MI,
nên mọi giá trị riêng củaQkđều thuộc đoạn[m;M]. Chú ý rằngkI−αQkk là giá trị tuyệt đối lớn nhất của giá trị riêng của ma trậnI−αQk nên từ bất đẳng thức trên, ta có
(1−α.M)I≤I−αQk≤(1−α.m)I.
Khi đó, mọi giá trị riêng của ma trậnI−αQk đều thuộc đoạn[1−αM,1− αm]. Vì thế, ta có
kxk+1−x∗k≤qkxk−x∗k,
vớiq=max(|1−αm|,|1−αM|)<1. Vậy ta có điều phải chứng minh.
Qua định lý trên, ta thấy dãy{xk}hội tụ tuyến tính với tỉ sốq. Chúng ta có thể chọnαđể tỉ sốq nhỏ nếu muốn. Điều này xảy ra nếu đoạn[1− α.M; 1−α.m]đối xứng quanh0. Khi đó, kích thước bước phù hợp nhất là
α= 2 M+m. Lúc này, tỉ sốqbằng
q=M−m M+m. Bằng cách đặt
r=M m,
được gọi là hệ số điều kiện của bài toán, ta thấyr≥1. Khi đó, ta có q=r−1
r+1
và nếurtiến tới1thìqtiến tới0và vì thế giải thuật giảm bước nhanh nhất với kích thước bước bằng hội tụ càng nhanh. Ngược lại, nếurcàng lớn thì qcàng gần1.Khi đó, giải thuật hội tụ càng chậm.
Một trong những hạn chế của giải thuật trên là chúng ta phải biết m vàM, đồng thời cũng phải sử dụng kích thước bước hằng. Giải thuật giảm bước nhanh nhất trên thực tế không thực hiện theo cách đó. Chúng ta cần quan tâm đến trường hợp khi kích thước bước được chọn dựa theo những đường tìm kiếm không chính xác vì đó là một công cụ hiệu quả hơn khi giải những bài toán tối ưu phức tạp trong thực tế.
Nhìn chung, sử dụng tỉ lệ trên chũng ta có thể thiết lập các quan hệ quan trọng, được thể hiện qua Bổ đề sau.
Bổ đề 3.3.1. Cho f∈C2và có ma trận Hessian thỏa mãn Điều kiện(3.16).
Khi đó, với mọixta có đánh giá k∇f(x)k2≥m
1+m
M
[f(x)−f(x∗)], vớix∗là cực tiểu duy nhất của f.
Chứng minh. Bất đẳng thức (3.16) suy ra f là hàm lồi chặt và có tập mức bị chặn. Khi đó, f có cực tiểux∗ duy nhất. Khai triển Taylor của f tại x∗ vớiθ∈[0; 1], ta được
f(x) = f(x∗) +∇f(x∗)T(x−x∗) +1
2(x−x∗)TF(θx+ (1−θ)x∗)(x−x∗).
Vìx∗là cực tiểu của f nên∇f(x∗) =0và kết hợp với (3.16), ta có m
2 kx−x∗k2≤ f(x)−f(x∗)≤M
2 kx−x∗k2. (3.18)
Khai triển Taylor của f tại điểmx, vớiλ∈[0; 1], ta có f(x∗) =f(x) +∇f(x)T(x∗−x) +1
2(x∗−x)TF(λx+ (1−λ)x∗)(x∗−x).
Kết hợp với vế trái của Bất đẳng thức (3.16) ta được f(x)−f(x∗) = ∇f(x)T(x−x∗)−1
2(x∗−x)TF(λx+ (1−λ)x∗)(x∗−x)
≤ k∇f(x)k.kx−x∗k −m
2 kx−x∗k2. (3.19) Kết hợp với vế trái của (3.18) ta có:
m
2 kx−x∗k2 ≤ k∇f(x)k.kx−x∗k −m
2 kx−x∗k2 mkx−x∗k ≤ k∇f(x)k
Suy ra
kx−x∗k ≤ 1
mk∇f(x)k. (3.20)
Từ (3.18) ta có
kx−x∗k≥ 2
M[f(x)−f(x∗)]. (3.21) Thay (3.20) và (3.21) vào (3.19), ta thu được
f(x)−f(x∗)≤ 1
m k∇f(x)k2−m
M[f(x)−f(x∗)].
Vậy
k∇f(x)k2≥m
1+m M
[f(x)−f(x∗)].
Dựa trên kết quả nhận được trong Định lý 3.3.4, chúng ta có thể chứng minh được kết quả sau:
Định lý 3.3.5. Cho f ∈C2 thỏa mãn Điều kiện (3.16). Khi đó, với mọi x0∈Rn, dãy{xk}sinh ra bởi phương pháp giảm bước nhanh nhất với kích thước bước hằngαk=1/Mthỏa mãn các bất đẳng thức sau
f(xk)−f(x∗) ≤ γk[f(x0)−f(x∗)] (3.22) kxk−x∗k ≤ γk/2
M m
1/2
kx0−x∗k, (3.23) với
γ=1− m 2M− m2
2M2.
Chứng minh. Xét bước lặp thứk. Khai triển Taylor của f tại xk, ta có với θ∈[0; 1]
f(xk+1) = f(xk−α∇f(xk)) = f(xk)−αk∇f(xk)k2 +α2
2 ∇f(xk)TF(θxk+1+ (1−θ)xk)∇f(xk). (3.24) Từ vế phải của (3.16), ta có:F(x)≤MI,∀x∈Rn.Vì thế, từ đẳng thức trên ta có:
f(xk+1)≤f(xk)−αk∇f(xk)k2+Mα2
2 k∇f(xk)k2.
Vìαđược chọn sao cho f(xk+1) = f(xk−α∇f(xk))≤ f(xk),nên vớiα= 1/Mta vẫn có dấu bất đẳng thức
f(xk+1)≤f(xk)− 1
2Mk∇f(xk)k2. Áp dụng Bổ đề 3.3.1, từ bất đẳng thức trên suy ra:
f(xk+1)−f(x∗) ≤ [f(xk)−f(x∗)]− m 2M
1+m
M
[f(xk)−f(x∗)]
≤ γ[f(xk)−f(x∗)].
Do đó, ta được:
f(xk)−f(x∗)≤γk[f(x0)−f(x∗)].
Tiếp theo ta sẽ chứng minh Bất đẳng thức (3.23). Theo (3.18) trong phần chứng minh Bổ đề 3.3.1, ta có
m
2 kxk−x∗k2≤ f(xk)−f(x∗)≤M
2 kxk−x∗k2. Kết hợp với (3.22), ta được:
m
2 kxk−x∗k2≤ f(xk)−f(x∗)≤γk[f(x0)−f(x∗)]≤γkM
2 kxk−x∗k2. Từ đây suy ra Bất đẳng thức (3.23):
kxk−x∗k≤γk/2 M
m 1/2
kx0−x∗k.
Trong Bất đẳng thức (3.22), dãy hàm{f(xk)}hội tụ đến giá trị nhỏ nhất f(x∗)ít nhất với tốc độ tuyến tính theo tỉ sốγ∈(0; 1). Nếuγcàng nhỏ thì tốc độ hội tụ càng nhanh. Ngoài ra, hệ số tỉ lệ
r=M m
càng lớn thìγcàng gần bằng1và sự hội tụ càng chậm.
Các bất đẳng thức trong định lý trên có ý nghĩa về mặt tổng quát. Để làm sáng tỏ hơn về tốc độ hội tụ, chúng ta có thể xét giới hạn
k→∞limsupf(xk+1)−f(x∗) f(xk)−f(x∗) .
Hiển nhiên Định lý 3.3.5 cho ta một cận trên của giới hạn này, tuy nhiên có một cận trên khác đơn giản hơn có thể dễ dàng tìm được khi xét dạng bậc hai của Bài toán (3.1).