Chương 2. Lí thuyết cơ bản về bài toán tối ưu
2.5. Giải thuật cho bài toán tối ưu tự do
Trong phần này, chúng ta xét Bài toán (2.1) với Ω = Rn, tức là xét bài toán tối ưu không điều kiện ràng buộc
x∈minRn
f(x), (2.4)
với f : Rn → R là hàm liên tục và khả vi. Chúng ta đã biết ở Hệ quả 2.1, nếu x là cực tiểu địa phương của Bài toán (2.4) thì
∇f(x) = 0.
Nếu f là hàm đơn giản thì ta có thể tìm được tất cả các điểm dừng và tất cả các điểm cực tiểu địa phương bằng việc giải trực tiếp hệ phương trình trên và/hoặc sửa dụng các điều kiện cần và đủ. Tuy nhiên, đối với những hàm số f phức tạp hơn thì việc tính toán này trở nên khó khăn và khó có thể áp dụng trực tiếp Hệ quả 2.1. Chính vì vậy chúng ta cần đến những giải thuật để tìm nghiệm số (xấp xỉ) của bài toán. Trong trường hợp này, phương pháp lặp để giải Bài toán (2.4) là một trong những phương pháp số cần được nghiên cứu. Về mặt ý tưởng, một phương pháp lặp là một phương pháp xây dựng một dãy điểmxk ∈ Rn hội tụ đến nghiệm của Bài toán (2.4). Trên thực tế, phương pháp lặp được tiến hành k lần cho đến khi nhận được giá trị x∗k xấp xỉ nghiệm của bài toán.
Trong phương pháp lặp, với một điểm xk ∈ Rn ta cần tìm điểm xk+1 ∈ Rn sao cho
f(xk+1) < f(xk). (2.5) Mặc dù điều kiện này không phải là điều kiện cần hay đủ để phương pháp lặp hội tụ đến nghiệm của Bài toán (2.4) nhưng đó là ý tưởng ban đầu cho việc giải bài toán. Một trong những cách để xây dựng dãy {xk} thỏa mãn Điều kiện (2.5) là chọn hướng dk ∈ Rn và xây dựng dãy điểm
xk+1 = xk +αkdk, (2.6)
với αk là vô hướng dương và được gọi là kích thước bước.
Xét dãy truy hồi được cho bởi Công thức (2.6). Giả sử hướng chấp nhận được dk được cố định. Thực hiện khai triển Taylor đối với f(xk+1) = f(xk+
αkdk) tại điểm xk ta 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) ̸= 0. Để đảm bảo cho Điều kiện (2.5) xảy ra với kích thước bước αk > 0 nào đó đủ bé, chúng ta cần
∇f(xk)Tdk < 0.
Hướng dk thỏa mãn bất đẳng thức trên được gọi là hướng giảm.
Như vậy, để xây dựng một giải thuật lặp, ở bước lặp thứ k chúng ta cần có phương pháp chọn hướng giảmdk và sau đó cần có phương pháp tính toán kích thước bước αk sao cho tính chất (2.5) được thỏa mãn. Trong các phần còn lại của chương này, chúng ta tập trung vào các phương pháp chọn hướng dk và các phương pháp tính toán kích thước bước αk.
2.5.1. Tính toán kích thước bước không chính xác
Giải thuật về tính toán kích thước bước rất quan trọng trong phương pháp lặp cho bài toán tối ưu không điều kiện ràng buộc. Trên thực tế, với mỗi điểm x ∈ Rn và hướng giảm d ∈ Rn, các phương pháp này tìm kiếm giá trị nhỏ nhất của hàm số
φ(α) = f(x+αd), α ≥ 0.
Bài toán tìm cực tiểu của hàm một biến này được gọi là bài toán tính toán kích thước bước. Bởi vì việc tìm chính xác giá trị cực tiểu α cho hàm một biến này đôi khi rất khó khăn, nên chúng ta sẽ đưa ra các phương pháp tìm giá trị gần đúng của nó. Các phương pháp như thế được gọi là tính toán kích thước bước không chính xác. Ta xét hai trường hợp tính toán kích thước bước không chính xác sau.
Quy tắc Armijo:
Một trong những phương pháp phổ biến để xác định kích thước bước xấp xỉ là quy tắc Armijo. Ý tưởng cơ bản của phương pháp này là đảm bảo cho việc chọn α không quá lớn và cũng không quá nhỏ. Quy tắc Armijo được thực hiện bằng cách xét hàm số φ(0) +εφ′(0)α với ε cố định và 0< ε < 1. Hàm số này được mô tả bởi đường nét đứt trên Hình 2.5. Giá trịα được xem là không quá lớn nếu giá trị hàm số nằm phía dưới đường nét đứt, tức là nếu φ(α) ≤ φ(0) +εφ′(0)α. (2.7)
Hình 2.5: Khoảng chọn phù hợp cho kích thước bước trong quy tắc Armijo.
Để đảm bảo cho α không quá nhỏ, một giá trị η > 1 được chọn trước và α được xem là không quá nhỏ nếu
φ(ηα) > φ(0) +εφ′(0)ηα. (2.8) Trên thực tế, quy tắc Armijo là một quy tắc đơn giản, thường được sử dụng giải bài toán tìm đường không chính xác cho Bài toán (2.4). Đầu tiên, người ta thường bắt đầu bằng một giá trị α0. Nếu nó thỏa mãn (2.7) thì tăng η (η = 2, η = 10 và ε = 0,2 là những giá trị thường được chọn) cho đến khi không thỏa (2.7). Khi đó, α = ηα0 được chọn. Tuy nhiên, nếu giá trị α0 đầu tiên không thỏa (2.7) thì ta chia α0 cho η cho đến khi α = α0/η thỏa (2.7).
Quy tắc Goldstein:
Một trong những phương pháp tính toán kích thước bước thường được sử dụng khác là quy tắc Goldstein. Trong quy tắc Goldstein, giá trị α được chọn không quá lớn nếu nó thỏa mãn (2.7) với một số ε,1/2 < ε < 1 cho trước. Một giá trị α được xem là không quá nhỏ trong quy tắc Goldstein nếu φ(α) > φ(0) + (1−ε)φ′(0)α, (2.9) hay φ(α) nằm trên đường nét đứt thứ hai trong Hình 2.6. Do đó, giá trị α ứng với xk+1 = xk +αdk thỏa tiêu chuẩn Goldstein nếu
1−ε ≤ f(xk+1)−f(xk) α∇f(xk)Tdk ≤ε.
Điều này tương đương với
f(xk) +εα∇f(xk)dk ≤f(xk+1) ≤f(xk) + (1−ε)α∇f(xk)dk, (2.10) với ε ∈ (1/2; 1) cho trước. Tương tự như Quy tắc Armijo, chúng ta cũng có thể tìm α bằng một giải thuật đơn giản như sau: đầu tiên, ta bắt đầu bằng một giá trị α0. Nếu nó thỏa mãn (2.7) thì tăng η cho đến khi không thỏa (2.7). Khi đó, α = ηα0 được chọn. Ngược lại, nếu giá trị α0 đầu tiên không
Hình 2.6: Khoảng chọn phù hợp cho kích thước bước trong quy tắc Goldstein
thỏa (2.7) thì ta chia α0 cho η cho đến khi α = α0/η thỏa (2.9).
2.5.2. Giải thuật giảm nhanh nhất
Trong phần trước, chúng ta thấy rằng dk là một hướng giảm nếu
∇f(xk)Tdk < 0.
Từ Định lý 1.8, điều này tương đương với đạo hàm theo hướng f′(xk, dk) < 0.
Như vậy để 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 được dk sao cho đạo hàm theo hướng dk của hàm số f tại điểm xk nhỏ nhất có thể. Với mỗi hướng chấp nhận được dk không đổi ta có thể xem dk có độ dài ∥ dk ∥= 1. Khi đó, theo bất đẳng thức Cauchy-Schwarz, ta có:
∥ ∇f(xk)Tdk ∥≤∥ ∇f(xk) ∥ . ∥dk ∥=∥ ∇f(xk) ∥ . Do đó
− ∥ ∇f(xk) ∥≤ ∇f(xk)dk ≤∥ ∇f(xk) ∥.
Vậy ∇f(xk)Tdk nhỏ nhất khi dk = −∇f(xk)/ ∥ ∇f(xk) ∥. Nói cách khác, f(xk+αdk) giảm nhanh nhất theo hướng dk = −∇f(xk) (được gọi là hướng giảm nhanh nhất). Khi đó, Công thức (2.6) trở thành:
xk+1 = xk −αk∇f(xk). (2.11) Đâ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ụ 2.5. Dùng phương pháp giảm nhanh nhất vớix0 = (1,2)T để tìm cực tiểu của hàm số f : R2 →R xác định bởi:
f(x1, x2) = x31 +x22 −3x1 −2x2 + 12, với x1, x2 ∈ R.
Giải: Ta có
∇f(x)T = (3x21 −3,2x2 −2).
Với điều xuất phát x0 = (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 (vì f là hàm lồi chặt).
2.5.2.1. Giải thuật giảm nhanh nhất với kích thước bước hằng
Dạng đơn giản nhất của giải thuật giảm nhanh nhất thu được bằng cách cố định mọi kích thước bước αk tại mỗi bước không đổi và bằng α > 0. Khi đó, giải thuật có dạng
xk+1 = xk−α∇f(xk). (2.12) Định lý sau chứng mình sự hội tụ của giải thuật trong trường hợp này.
Định lí 2.8. 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
∥ ∇f(x)− ∇f(y) ∥≤ M ∥ x−y ∥,∀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ọi x0, dãy {xk} sinh ra bởi Giải thuật (2.12) đề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.9) ta có:
f(xk+1) = f(xk +αdk) =f(xk) +α∇f(x)Tdk, với x = θ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+α ∥ ∇f(x)− ∇f(xk) ∥ . ∥dk ∥ . với dk = −∇f(xk) và sử dụng tính liên tục Lipschitz của gradient, ta được
f(xk+1) ≤ f(xk)−α ∥ ∇f(xk) ∥2 +αM ∥xk −x ∥. ∥ ∇f(xk) ∥ . Mặt khác ∥ xk − x ∥= (1 −θ) ∥ xk −xk+1 ∥≤ α ∥ ∇f(xk) ∥. Do đó, bất
đẳng thức trên tương đương với:
f(xk+1) ≤ f(xk)−α ∥ f(xk) ∥2 +α2M ∥ ∇f(xk) ∥2
≤ f(xk)−α(1−αM) ∥ ∇f(xk) ∥2
⇒f(xk)−f(xk+1) ≥ α(1−αM) ∥ ∇f(xk) ∥2 (2.13) Theo giả thiết ta có
0< α < 1
M ⇔α(1−αM) > 0.
Vậy f(xk+1) ≤ f(xk) với mọi k. 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 (2.13), ta được
0≤ α(1−αM) ∥ ∇f(xk) ∥2≤f(xk)−f(xk+1) →0.
Vậy
k→∞lim ∇f(xk) = 0.
□ Hệ quả 2.3. Trong Định lý 2.8, 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ụ đến x∗. Theo Định lý 2.8 ta có
m→∞lim ∇f(xm) = 0 ⇒ ∇f(x∗) = 0.
□
2.5.2.2. Giải thuật giảm nhanh nhất với kích thước bước xác định bởi Quy tắc Goldstein
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ố Lipschitz M 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
αk sao cho
β ≤ f(xk+1)−f(xk)
αk∇f(xk)Tdk ≤ 1−β.
Để ý rằng dk = −∇f(xk) nên bài toán tương đương với việc tìm αk sao cho f(xk)−(1−β)αk ∥ ∇f(xk) ∥2≤ f(xk+1) ≤ f(xk)−βαk ∥ ∇f(xk) ∥2 .
(2.14) Sự hội tụ của giải thuật giảm nhanh nhất với kích thước bước được tính bởi Quy tắc Goldstein được phát biểu trong định lý sau:
Định lí 2.9. Cho f ∈ C1 và 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 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 (2.14), ta được f(xk+1) ≤ f(xk).
Vì X0 bị 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 (2.14) suy ra:
αk ∥ ∇f(xk) ∥2≤ f(xk)−f(xk+1)
β .
Do đó
k→∞lim αk ∥ ∇f(xk) ∥2= 0. (2.15) Theo chứng minh ở Định lý 2.8 ta có bất đẳng thức (2.13), tức là
f(xk+1) ≤f(xk)−αk(1−αkM) ∥ ∇f(xk) ∥2 . Do đó, kết hợp với vế trái của bất đẳng thức (2.14), ta có
f(xk)−αk(1−β) ∥ ∇f(xk) ∥2≤ f(xk)−αk(1−αkM) ∥ ∇f(xk) ∥2 . Rút gọn thu được
β ∥ ∇f(xk) ∥2≤ αkM ∥ ∇f(xk) ∥2 . Cho k → ∞, ta nhận được
k→∞lim ∥ ∇f(xk) ∥= 0 ⇒ ∇f(x∗) = 0.
□
2.5.2.3. Giải thuật giảm bước nhanh nhất với kích thước bước chính xác
Trong phần này, chúng ta nghiên cứu giải thuật giảm nhanh nhất với kích thước bước chính xác. Trong trường hợp này, kích thước bước αk là giá trị cực tiểu của hàm số một biến
φ(αk) =f(xk +αk∇f(xk)),
với αk > 0.
Định lý sau đưa ra các điều kiện để đảm bảo giải thuật hội tụ trong trường hợp tổng quát này.
Định lí 2.10. Cho f ∈ C1 và tập hợp X0 = {x ∈ Rn|f(x) ≤ f(x0)} bị chặn. Khi đó, giải thuật gradient giảm bước nhanh nhất với kích thước bước chính xác sinh ra một dãy điểm {xk} sao cho mỗi điểm tụ x∗ của dãy đều thỏa mãn ∇f(x∗) = 0.
Chứng minh. Dãy {xk} sinh bởi tính toán kích thước bước không chính xác nên ta có f(xk+1) ≤ f(xk) với mọi k. Vì X0 bị chặn nên nó là tập compact.
Do đó, dãy {f(xk)} bị chặn và hội tụ. Dãy {xk} có điểm tụ x∗ nên tồn tại tập chỉ số K sao cho
k→∞lim
k∈K
xk = x∗.
Vì {f(xk)} hội tụ nên f(x∗) = limk→∞f(xk). Tiếp theo ta sẽ chứng minh Định lý bằng phương pháp phản chứng. Giả sử∇f(x∗) ̸= 0. Xét hướng giảm bước nhanh nhất −∇f(x∗) và điểm
y(α) = x∗ −α∇f(x∗).
Vì ∇f(x∗) ̸= 0 nên bài toán
minα≥0 f(y(α)), (2.16)
có nghiệm α∗ > 0 và f(y(α∗)) < f(x∗) với mọi α∗. Xét điểm xk với k ∈ K.
Khi đó, ta có
f(xk+1) ≤ f(xk−αk∇f(xk)),∀αk ≥ 0. (2.17) Khi k → ∞, k ∈ K thì xk → x∗ và ∇f(xk) → ∇f(x∗). Đặt η =∥ ∇f(x∗) ∥, ta có
xk+1 = xk −αk∇f(xk) (2.18) và ∥ ∇f(xk) ∥≥ η/2 với mọi k ∈ K đủ lớn. Do đó, với mọi k ∈ K đủ lớn, ta có
0 ≤αk = ∥ xk+1−xk ∥
∥ ∇f(xk) ∥ ≤ 2
ηdiam(X0),
trong đó diam(X0) là khoảng cách lớn nhất giữa hai điểm thuộc X0. Điều này suy ra rằng với k ∈ K đủ lớn, {αk} bị chặn đều. Do đó, ta chọn được K1 ⊂ K sao cho {αk} hội tụ với k ∈ K1. Đặt α là giới hạn này. Trong (2.18) chuyển qua giới hạn khi k → ∞, ta được
k→∞lim
k∈K1
xk+1 = x∗ −α∇f(x∗)
Trong (2.17) chuyển qua giới hạn khi k → ∞, ta được
f(x∗ −α∇f(x∗)) ≤ f(x∗ −α∇f(x∗)),∀α ≥ 0.
Do đó, kích thước bước α là nghiệm của Bài toán (2.16). Điều này suy ra
k→∞lim
k∈K1
f(xk+1) =f(y(α∗)) < f(x∗), nên
k→∞lim f(xk) = lim
k→∞k∈K1
f(xk+1) < f(x∗).
Điều này trái với điều kiện
f(x∗) = lim
k→∞f(xk).
Vậy ∇f(x∗) = 0. □
Ví dụ 2.6. Dùng phương pháp giảm nhanh nhất với kích thước bước chính xác và điểm khởi tạo x0 = (4,2,1)T để tìm cực tiểu của hàm số f : R3 → R xác định bởi:
f(x1, x2, x3) = (x1 −4)4 + (x2 −3)2 + 4(x3 + 5)4, với x1, x2, x3 ∈ R.
Giải: Ta có : ∇f(x)T = 4(x1 −4)3,2(x2 −3),16(x3 + 5)3. Với điểm x0 = (4,2,1)T, ta có:
∇f(x0)T = (0,−2,3456),
và φ(α0) = f(x0 −α0∇f(x0)) = (2 + 2α0 −3)2 + 4(−1−1024α0 + 5)4. Sử dụng phương pháp tính toán kích thước bước không chính xác ta tính được α0 = 3,967×10−3. Khi đó,
x1 = x0 −α0∇f(x0)T = (4,000; 2,008;−5,062)T
∇f(x1) = (0,000;−1,984;−0,003875),
và φ(α1) = (2,008 + 1,984α1−3)2+ 4(−5,062 + 0,003875α1 + 5)4. Tương tự, ta tính được, bằng phương pháp tính toán kích thước bước không chính xác, α1 = 0,5. Khi đó
x2 = x1 −α1∇f(x1) = (4,000; 3,000;−5,060)T
∇f(x2)T = (0,000; 0,000;−0,003525).
Ta có φ(α2) = 4(−5,060 + 0,003525α2 + 5)4 và α2 = 16,29. Do đó x3 = x2 −α2∇f(x2) = (4,000; 3,000;−5,002)T.
Cứ tiếp tục quá trình này ta sẽ được x∗ = (4,3,−5)T.
2.5.2.4. 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 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) ≤M I ,∀x ∈ Rn (2.19) với 0< m ≤ M (nhắc lại rằng A ≤B nếu B −A là nửa xác định dương).
Khi đó, theo Định lý 1.11, f là hàm lồi chặt và nó có một cực tiểu duy nhất x∗. Do đó, giải thuật giảm nhanh nhất hội tụ về nghiệm duy nhất cho Bài toán (2.4). 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í 2.11. Cho f ∈ C2 và thỏa mãn Điều kiện (2.19). Khi đó, giải thuật giảm 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
∥ xk+1−x∗ ∥≤ qk ∥x0 −x∗ ∥, với q = 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). (2.20) Vì x∗ là cực tiểu của Bài toán (2.4) 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 đó, (2.20) trở thành
xk+1−x∗ = xk −x∗ −αQk(xk −x∗) = (I −αQk)(xk−x∗).
Vì thế,
∥ xk+1 −x∗ ∥≤∥ I −αQk ∥ . ∥xk −x∗ ∥ . Theo (2.19), ta có
mI ≤ Qk ≤M I,
nên mọi giá trị riêng củaQk đều thuộc đoạn [m;M]. Chú ý rằng∥ I−αQk ∥ là giá trị tuyệt đối lớn nhất của giá trị riêng của ma trận I − α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ận I −αQk đều thuộc đoạn [1−αM,1− αm]. Vì thế, ta có
∥ xk+1−x∗ ∥≤ q ∥xk −x∗ ∥,
với q = 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 quanh 0. Khi đó, kích thước bước phù hợp nhất là
α = 2
M +m. Lúc này, tỉ số q bằ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ấy r ≥ 1. Khi đó, ta có q = r −1
r + 1
và nếu r tiến tới 1 thì q tiến tới 0 và vì thế giải thuật giảm nhanh nhất với kích thước bước bằng hội tụ càng nhanh. Ngược lại, nếu r càng lớn thì q càng gần 1. 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 tính toán kích thước bước 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ổ đề 2.1. Cho f ∈ C2 và có ma trận Hessian thỏa mãn Điều kiện (2.19). Khi đó, với mọi x ta có đánh giá
∥ ∇f(x) ∥2≥ m1 + m M
[f(x)−f(x∗)], với x∗ là cực tiểu duy nhất của f.
Chứng minh. Bất đẳng thức (2.19) 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ểu x∗ 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∗) = 0 và kết hợp với (2.19), ta có m
2 ∥x−x∗ ∥2≤f(x)−f(x∗) ≤ M
2 ∥ x−x∗ ∥2 . (2.21) Khai triển Taylor của f tại điểm 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).
Kết hợp với vế trái của Bất đẳng thức (2.19) ta được f(x)−f(x∗) =∇f(x)T(x−x∗)− 1
2(x∗ −x)TF(λx+ (1−λ)x∗)(x∗ −x)
≤∥ ∇f(x) ∥ . ∥ x−x∗ ∥ −m
2 ∥ x−x∗ ∥2 . (2.22) Kết hợp với vế trái của (2.21) ta có:
m
2 ∥x−x∗ ∥2 ≤∥ ∇f(x) ∥ . ∥ x−x∗ ∥ −m
2 ∥x−x∗ ∥2 m ∥ x−x∗ ∥ ≤∥ ∇f(x) ∥ .
Suy ra
∥ x−x∗ ∥ ≤ 1
m ∥ ∇f(x) ∥. (2.23)
Từ (2.21) ta có
∥ x−x∗ ∥≥ 2
M[f(x)−f(x∗)]. (2.24) Thay (2.23) và (2.24) vào (2.22), ta thu được
f(x)−f(x∗) ≤ 1
m ∥ ∇f(x) ∥2 −m
M[f(x)−f(x∗)].
Vậy
∥ ∇f(x) ∥2≥ m1 + m M
[f(x)−f(x∗)].
□ Dựa trên kết quả nhận được trong Định lý 2.11, chúng ta có thể chứng minh được kết quả sau:
Định lí 2.12. Cho f ∈ C2 thỏa mãn Điều kiện (2.19). 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/M thỏa mãn các bất đẳng thức sau
f(xk)−f(x∗) ≤ γk[f(x0)−f(x∗)] (2.25)
∥ xk −x∗ ∥ ≤ γk/2 M
m 1/2
∥x0 −x∗ ∥, (2.26)
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)−α ∥ ∇f(xk) ∥2 + α2
2 ∇f(xk)TF(θxk+1 + (1−θ)xk)∇f(xk). (2.27) Từ vế phải của (2.19), ta có: F(x) ≤ M I,∀x ∈ Rn. Vì thế, từ đẳng thức trên ta có:
f(xk+1) ≤ f(xk)−α ∥ ∇f(xk) ∥2 +M α2
2 ∥ ∇f(xk) ∥2 .
Vì α được chọn sao cho f(xk+1) = f(xk − α∇f(xk)) ≤ f(xk), nên với α = 1/M ta vẫn có dấu bất đẳng thức
f(xk+1) ≤f(xk)− 1
2M ∥ ∇f(xk) ∥2 . Áp dụng Bổ đề 2.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 (2.26). Theo (2.21) trong phần chứng minh Bổ đề 2.1, ta có
m
2 ∥ xk −x∗ ∥2≤ f(xk)−f(x∗) ≤ M
2 ∥ xk −x∗ ∥2 . Kết hợp với (2.25), ta được:
m
2 ∥ xk −x∗ ∥2≤ f(xk)−f(x∗) ≤γk[f(x0)−f(x∗)] ≤ γkM
2 ∥ xk −x∗ ∥2 . Từ đây suy ra Bất đẳng thức (2.26):
∥ xk−x∗ ∥≤ γk/2 M
m 1/2
∥ x0 −x∗ ∥ .
□ Trong Bất đẳng thức (2.25), dãy {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ằng 1 và 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→∞lim supf(xk+1)−f(x∗) f(xk)−f(x∗) .
Hiển nhiên Định lý 2.12 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 (2.4).
2.5.2.5. Bài toán tối ưu bậc hai
Trong phần này chúng ta nghiên cứu giải thuật giảm nhanh nhất cho bài toán tối ưu bậc hai. Cụ thể, chúng ta xét bài toán tìm cực tiểu của hàm f cho bởi
f(x) = 1
2xTQx−xTb (2.28)
với Q là n×n-ma trận đối xứng xác định dương.
Với giả thiết trên, ta có các giá trị riêng của Q đều dương, 0 < m= λ1 ≤ λ2. . . ≤ λn = M và f là hàm lồi chặt. Áp dụng định lý về đạo hàm hàm hợp và giả thiết Q là ma trận đối xứng xác định dương, ta có
∇f(x) = 1
22xTQ−b
= QTx−b
∇f(x) =Qx−b.
Vì x∗ là nghiệm của bài toán (2.28) nên ∇f(x∗) = 0 hay Q(x∗) =b.
Với g(x) = ∇f(x), giải thuật giảm nhanh nhất sinh ra một dãy điểm {xk} xác định bởi
xk+1 = xk−αkgk,
với αk ≥ 0 thỏa mãn φ(αk) =f(xk −αkgk) là giá trị nhỏ nhất. Ta có:
φ′(αk) = (xk−αkgk)TQ(−gk)−(−gk)Tb.
Vì αk là cực tiểu của φ(αk) =f(xk −αkgk) nên φ′(αk) = 0, hay αkgTkQgk = (xTkQ−bT)gk.
Hơn nữa gk = ∇f(xk) = Qxk−b nên αk = gkTgk
gkTQgk
.
Tóm lại, với bài toán tối ưu bậc hai, ta có giải thuật giảm nhanh nhất có