Chương 4. Bài toán tối ưu không trơn
4.2. Sự tồn tại nghiệm và điều kiện cần cho nghiệm của bài toán 86 4.3. Giải thuật giảm kiểu gradient
Đầu tiên, chúng ta tập trung nghiên cứu các điều kiện để Bài toán (4.1) có nghiệm và điều kiện cần cho nghiệm của bài toán. Để nhận được kết quả như thế ta cần các giả thiết sau:
Giả thiết 4.1. (1) Φ là một hàm không âm, lồi chính thường, nửa liên
tục dưới và coercive với Dom(Φ) ̸= ϕ.
(2) F bị chặn dưới và nửa liên tục dưới. Không mất tính tổng quát, ta giả thiết F (u) ≥ 0, ∀u ∈ Rd.
(3) F khả vi Fréchet và F′ liên tục Lipschitz, tức là, tồn tại một hằng số L sao cho
∥F′(u)ưF′(u′)∥ ≤ L∥uưu′∥,∀u, u′ ∈ Rd.
(4) Nếu {un} hội tụ đến u sao cho {Θ (un)} là đơn điệu giảm, thì tồn tại một dãy con {unj} sao cho
{F′(unj)} → F′(u).
Điều kiện (1) và (2) được sử dụng để chứng minh sự tồn tại nghiệm của Bài toán (4.1). Điều kiện (3) và (4) của Giả thiết 4.1 ta áp dụng để chứng minh sự hội tụ của giải thuật giảm kiểu gradient.
Chú ý 4.1. 1. Điều kiện (3) của Giả thiết 4.1 ta có:
|F (v)ưF (u)ư ⟨F′(u), vưu⟩| ≤ L2∥v ưu∥2,∀v, u ∈ Rd. Thật vậy, ta có:
|F (v)ưF (u)ư ⟨F′(u), vưu⟩|
=
1
R
0
⟨F′(u+t(v ưu)), vưu⟩dtư ⟨F′(u), vưu⟩
=
1
R
0
⟨F′(u+t(v ưu)) ưF′(u), vưu⟩dt
≤
1
R
0
L∥vưu∥2tdt = L2∥v ưu∥2.
2. Điều kiện (4) của Giả thiết 4.1 suy ra rằng tậpEt = u ∈ Rd : Φ (u) ≤ t là compact với mỗi t ∈ R vì F′ liên tục. Thật vậy, un hội tụ đến u và Θ (un) là đơn điệu giảm. Khi đó, {Φ (un)}n∈
N bị chặn và {un} ⊂ Et với một số t > 0. Vì Et compact nên có một dãy con {unj} sao cho unj → u. Vì F′ liên tục ta có F′(unj) → F′(u).
Bổ đề 4.1 (Điều kiện có nghiệm). Giả sử Bài toán (4.1) thỏa mãn các giả thiết (1) và (2) của Giả thiết 4.1. Khi đó, Bài toán (4.1) có ít nhất một nghiệm.
Chứng minh. Vì F và Φ bị chặn dưới nên infΘ > −∞. Gọi {un} là dãy cực tiểu, tức Θ{un} → inf Θ. Vì Θ coercive nên {un} bị chặn. Do đó, tồn tại dãy con {unk} hội tụ đến u∗ ∈ Rd. Hơn nữa, vì Θ nửa liên tục dưới nên
Θ (u∗) ≤ lim inf Θ (unk)
k→∞
= inf Θ.
Do đó, u∗ là một điểm cực tiểu của Θ. □
Để đưa ra điều kiện cần của nghiệm, trước hết chúng ta cần định nghĩa toán tử gần kề (proximal operator) như sau:
Định nghĩa 4.1 (Toán tử gần kề). Cho Φ : Rd → R là hàm lồi, chính thường, nửa liên tục dưới, v ∈ Rd và λ ∈ R+. Khi đó, toán tử gần kề của Φ được xác định như sau:
PλΦ(v) = arg min
u∈Rd
∥u−v∥2
2 +λΦ (u)
!
. (4.2)
Chú ý rằng, định nghĩa trên là hoàn toàn xác định vì từ Giả thiết 4.1 và tính chất của hàm Φ, ta suy ra rằng với mỗi y ∈ Rd và s > 0, hàm
v →Θ (v) = 1
2∥v−y∥2 + 1
sΦ (v),
là lồi chặt và nửa liên tục dưới. Hơn nữa, Φ là chính thường, Dom(Φ) ̸= ϕ và như vậy cho v0 ∈ Dom (Φ) và v0∗ ∈ ∂Φ (v0) ta có
Φ (v) ≥ Φ (v0) +⟨v∗0, v−v0⟩, ∀v ∈ Rd.
Bất đẳng thức cuối cùng suy ra Θ (v) → ∞ khi ∥v∥ → ∞, tức là Θ là hàm coercive. Do đó, Θ có duy nhất một điểm cực tiểu.
4.3. Giải thuật giảm kiểu gradient
Ý tưởng của giải thuật giảm kiểu gradient là thay vì giải trược tiếp Bài toán (4.1), chúng ta giải một dãy các bài toán cực tiểu trung gian {minv∈RdΘsn (v, un)}, trong đó Θsn(., un) hàm xấp xỉ bậc hai của Θ tại un. Vì hàm Θsn (., un) lồi chặt và cực tiểu của nó có thể tìm được dễ dàng với một vài trường hợp đặc biệt của hàm Φ. Khi đó, với một số điều kiện đặt lên cho tham số sn, dãy
un+1 = arg minv∈RdΘsn (v, un) sẽ hội tụ đến một nghiệm của Bài toán (4.1). Cụ thể, với mỗi s > 0 chúng ta định nghĩa xấp xỉ bậc hai của Θ (v) tại một điểm u ∈ Rd như sau:
Θs(v, u) := F (u) +⟨F′(u), vưu⟩+ s
2∥v −u∥2 + Φ (v). (4.3) Bổ đề 4.2. Cho mỗi u ∈ Rd cố định và s > 0, hàm Θs(v, u) có một cực tiểu duy nhất xác định bởi
v∗ = P1
sΦ
u− 1
sF′(u)
. Chứng minh. Ta cần chứng minh rằng bài toán cực tiểu
min
v∈Rd
Θs(v, u) (4.4)
có một nghiệm duy nhất. Ta thấy rằng Bài toán (4.4) tương đương bài toán
min
v∈Rd
(1 2
v −
u− 1
sF′(u)
2
+ 1 sΦ (v)
)
. (4.5)
Áp dụng định nghĩa toán tử gần kề ta suy ra được điều phải chứng minh. □ Từ Bổ đề trên, ta định nghĩa được ánh xạ sau:
Js :Rd → Rd
u 7→Js(u) = argminΘs(v, u). Khi đó, dãy cực tiểu của xấp xỉ bậc hai được cho bởi:
un+1 = Jsn(un) = P1
snΦ
un − 1
snF′(un)
. (4.6)
4.3.1. Tốc độ hội tụ
Trong phần này, chúng ta nghiên cứu sự hội tụ của vòng lặp (4.6). Chúng ta sẽ chỉ ra rằng với các điều kiện thích hợp về sn và F, vòng lặp (4.6) sẽ hội tụ và có tốc độ hội tụ tuyến tính. Để chứng minh sự hội tụ của giải thuật giảm kiểu gradient ta cần các kết quả sau:
Bổ đề 4.3. Giả sử rằng F và Φ thỏa mãn các tính chất (1), (3) của Giả thiết 4.1. Nếu u ∈ Rd và s > 0 thỏa mãn:
Θ (Js(u)) ≤ Θs(Js(u), u). (4.7) thì với mọi v ∈ Rd, ta có:
Θ (v)ưΘ (Js(u)) ≥ s2∥Js(u)ưu∥2 +s⟨uưv, Js(u)ưu⟩ ư L2∥vưu∥2, trong đó L là hằng số Lipschitz của F′. Hơn nữa, nếu F lồi, thì ta có bất đẳng thức mạnh hơn
Θ (v)−Θ (Js(u)) ≥ s2∥Js(u)−u∥2 + s⟨Js(u)−u, u−v⟩. Chứng minh. Từ (4.7) ta có:
Θ (v)−Θ (Js(u)) ≥ Θ (v)−Θs(Js(u), u). (4.8) Mặt khác, vìz = Js(u)là một cực tiểu củaΘs(., u)nên tồn tạiγ ∈ ∂Φ (z) sao cho:
F′(u) + s(z −u) + γ = 0. Vì F′ Lipschitz và Φ lồi nên ta có:
F (v) ≥ F (u) +⟨F′(u), vưu⟩ ư L
2∥vưu∥2, (4.9) Φ (v) ≥Φ (z) +⟨γ, v−z⟩. (4.10)
Cộng (4.9) với (4.10) vế theo vế ta có:
Θ (v) ≥ F (u) +⟨F′(u), v −u⟩+ Φ (z) +⟨γ, v−z⟩ − L
2∥vưu∥2. (4.11) Hơn nữa, vì z = Js(u), ta có:
Θs(z, u) =F (u) +⟨F′(u), z −u⟩+ s
2∥zưu∥2 + Φ (z). (4.12) Từ (4.8) kết hợp với (4.11) và (2.12) ta có:
Θ (v)ưΘ (z) ≥ ưs2∥z ưu∥2 +⟨F′(u) +γ, vưu⟩ ư L2∥v ưu∥2.
= ưs2∥zưu∥2+s⟨uưz, vưz⟩ưL2∥vưu∥2+s∥z ưu∥2ưs∥zưu∥2
= −2s∥z −u∥2 +s⟨z −u, u−v⟩ − L2∥v −u∥2.
Nếu F lồi, thì ta có F (v) ≥ F (u) + ⟨F′(u), vưu⟩. Vì vậy, từ chứng minh trên, ta thay bất đẳng thức (4.9) bằng bất đẳng thức cuối cùng này ta được:
Θ (v)−Θ (Js(u)) ≥ 2s∥Js(u)−u∥2 +s⟨Js(u)−u, u −v⟩.
□ Chú ý 4.2. Từ Nhận xét 4.1, ta dễ dàng thấy rằng (4.7) thỏa mãn nếu s≥ L.
Bây giờ, chúng ta đi chứng minh tính chất hội tụ của giải thuật giảm kiểu gradient cho Bài toán (4.1), tức là chứng minh sự hội tụ của dãy được xác định bởi (4.6). Trước hết ta chứng minh tính đơn điệu giảm của hàm mục tiêu Θ (un).
Bổ đề 4.4. Cho F và Φ thỏa mãn các tính chất (1), (3) của Giả thiết 4.1. Giả sử dãy {un} được xác định bởi (4.6) và thỏa mãn:
sn ∈ [s, s] (0 < s ≤ L ≤ s) và Θ un+1 ≤ Θsn un+1, un. Khi đó, dãy {Θ (un)} là đơn điệu giảm, dãy {un} bị chặn và
n→∞lim
un+1 −un = 0.
Chứng minh. Từ giả thiết, ta có:
Θ un+1≤ Θsn un+1, un ≤ Θsn(un, un) = Θ (un).Do đó, dãy {Θ(un)}
là đơn điệu giảm.
Cho k = 0,1, ..., n, áp dụng Bổ đề 4.3 với v = u = uk và s = sk, ta được:
2
sk Θ uk−Θ uk+1 ≥ uk−uk+1
2. Do đó,
2
s Θ uk−Θ uk+1 ≥ uk −uk+1
2.
Lấy tổng các bất đẳng thức trên với k = 0, ..., n, ta được
2
s Θ u0−Θ un+1 ≥
n
P
k=0
uk −uk+1
2, ∀n. Điều này suy ra chuỗi P∞
k=0
uk −uk+1
2 hội tụ. Như một hệ quả, ta có:
n→∞lim
un+1 −un = 0.
Mặt khác, dãy {un} bị chặn vì dãy {Θ (un)} đơn điệu dãy giảm và hàm Θ
là coercive, tức là, Θ (u) → ∞ khi ∥u∥ → ∞. □
Từ bổ đề trên, ta suy ra dãy {un} bị chặn. Do đó, nó có một điểm tụ.
Bây giờ, ta chứng minh rằng mỗi điểm tụ là một điểm dừng củaΘ, tức là nó thỏa mãn điều kiện cần cho cực tiểu của Θ. Điều này được đưa ra ở định lý sau:
Định lí 4.1 (hội tụ). Cho F và Φ thỏa mãn Giả thiết 4.1. Giả sử dãy {un} được xác định bởi (4.6) và thỏa mãn các giả thiết của Bổ đề 4.4. Khi đó, mỗi điểm tụ u∗ của {un} là một điểm dừng của Θ.
Chứng minh. Trước hết theo Bổ đề 4.4 ta có:
Θ un+1≤ Θsn un+1, un.
Để chứng minh định lý, tiếp theo ta chứng minh rằng giả thiết sau: Nếu {xn} hội tụ đến x, {gn} hội tụ đến g và xn ∈ ∂Φ (gn) thì x ∈ ∂Φ (g).
Thật vậy, ta thấy rằng ∀v ∈ Rd cố định, ta có:
n→∞lim ⟨xn, v−gn⟩ = lim
n→∞⟨xn−x, v−gn⟩+ lim
n→∞⟨x, v−gn⟩. Vì dãy hội tụ là bị chặn, nên tồn tại một hằng số c sao cho
|⟨xn−x, v−gn⟩| ≤ c∥xn−x∥ → 0. Sự hội tụ của {gn} kéo theo rằng
n→∞lim ⟨xn, v−gn⟩ = ⟨x, v −g⟩. Vì xn ∈ ∂Φ (gn), ta có
Φ (v) ≥Φ (gn) +⟨xn, v−gn⟩,∀v ∈ Rd. Mặt khác, vì Φ nửa liên tục dưới cho nên ta kết luận:
Φ (v) ≥ lim
n→∞infΦ (gn) + lim
n→∞inf⟨xn, v−gn⟩ ≥ Φ (g) + ⟨x, v−g⟩,∀v ∈ Rd Điều này tương đương x ∈ ∂Φ (g).
Bây giờ, chúng ta tiếp tục chứng minh định lý. Giả sử {unj}j∈
N là một dãy con hội tụ đến u∗. sn ∈ [s, s] và điều kiện (4) của Giả thiết 4.1, tồn tại một dãy con của {unj} (cũng kí hiệu là {unj}) sao cho: limj→∞unj =
u∗, F′ unj → F′(u∗) và lim
j→∞snj = s∗ ∈ [s, s]. Theo Bổ đề 4.4, unj+1 cũng hội tụ đến u∗. Từ (4.6), ta có
0 ∈ unj+1 −
unj − 1
snjF′(unj)
+ 1
snj∂Φ unj+1 hay
vnj+1 := snj unj −unj+1−F′(unj) ∈ ∂Φ unj+1.
Chú ý rằng vnj+1 → −F′(u∗) và unj+1 −→ω u∗. Từ kết quả vừa được chứng minh ở trên, ta có:
−F′(u∗) ∈ ∂Φ (u∗).
hay u∗ là một điểm dừng của Θ. □
Định lí 4.2. Giả sử F là hàm lồi và thỏa mãn các tính chất (1), (3) của Giả thiết 4.1 và {un} sinh bởi (4.6) thỏa mãn các giả thiết trong Bổ đề 4.4.
Khi đó, ∀n≥ 1
Θ (un)−Θ (u∗) ≤ s∥u0−u∗∥2
2n ,
trong đó u∗ là một cực tiểu của Θ.
Chứng minh. Vì F là lồi, sử dụng Nhận xét 4.4 với v = u∗, u = uk và s = sk, ta được
2
sk Θ (u∗)−Θ uk+1 ≥ uk+1−uk
2 + 2uk −u∗, uk+1 −uk
= u∗ −uk+1
2 −u∗ −uk
2. Vì sk ∈ [s, s] và Θ (u∗)−Θ uk+1 ≤ 0, nên ta có
2
s Θ (u∗)−Θ uk+1 ≥ u∗ −uk+1
2 −u∗ −uk
2. (4.13) Tổng bất đẳng thức này với k = 0,1, . . . , n−1 ta được
2
s nΘ (u∗)−
n−1
X
k=0
Θ uk+1
!
≥ ∥u∗ −un∥2 −u∗ −u02. (4.14) Sử dụng Bổ đề 4.4 một lần nữa với u = v = uk và s = sk ta được
2
sk Θ uk−Θ uk+1 ≥ uk+1−uk2. Vì sk ∈ [s, s] và Θ uk−Θ uk+1 ≥ 0 suy ra
2
s Θ uk−Θ uk+1 ≥ uk −uk+1
2.
Nhân hai vế với k và lấy tổng hai vế của bất đẳng thức trên với k = 0,1, ..., n−1, ta được
2 s
n−1
P
k=0
kΘ uk−(k+ 1) Θ uk+1+ Θ uk+1 ≥
n−1
P
k=0
kuk −uk+1
2.
Suy ra:
2
s −nΘ (un) +
n−1
X
k=0
Θ uk+1
!
≥
n−1
X
k=0
kuk −uk+12. (4.15) Cộng (4.14) với (4.15) và nhân s/s ta được
2n
s (Θ (u∗)−Θ (un)) ≥ ∥u∗ −un∥2 + ss
n−1
P
k=0
kuk −uk+1
2 −u∗ −u0
2. Do đó,
Θ (un)−Θ (u∗) ≤ 2ns u∗ −u0
2.
□ 4.3.2. Phương pháp chọn stepsize
Trong phần trước, chúng ta đã chứng minh rằng giải thuật giảm kiểu gradient dẫn đến vòng lặp:
un+1 = Jsn(un) = P1
snΦ
un − 1
snF′(un)
. (4.16)
và vòng lặp hội tụ tới một điểm dừng của Bài toán (4.1) nếu và chỉ nếu các tham số sn thỏa mãn các điều kiện sau:
{sn} bị chặn, sn ∈ [s, s] (0 < s ≤L ≤s),∀n và
Θ un+1≤ Θsn un+1, un.
Tích hợp các điều kiện này, giải thuật giảm kiểu gradient được trình bày chi tiết ở Giải thuật 4.3.1.
Algorithm 4.3.1 Giải thuật giảm kiểu Gradient
Require: Dự đoỏn ban đầu u0 : Φ (u0)<∞, à∈(1,∞) vàs0 ∈[s, s] (0< s≤L/à≤s)
1: for n= 0,1,2, . . . do
2: repeat
3: un+1 ←P1
snΦ un− s1nF′(un)
4: if θ(un+1)> θsn(un+1, un) then
5: sn←sn.à
6: end if
7: untillθ(un+1)≤θsn(un+1, un) or sn ∈/ [s, s]
8: Tính dự đoán ban đầu cho sn+1
9: end for
Ensure: u= limun.
Chú ý rằng, từ Giả thiết 4.1, F khả vi Lipschitz với hằng số Lipschitz L. Vì vậy, cho s ≥ L, ta có:
|F (v)ưF (u)ư ⟨F′(u), vưu⟩| ≤ 2s∥v ưu∥2.
Do đó, với s ≥ L ta được
Θ (v) =F (v)ưΦ (u) ≤ F (u) +⟨F′(u), vưu⟩
+s2∥v −u∥2 + Φ (v) = Θs(v, u).
Do đó, trong lần lặp thứn của Giải thuật 4.3.1, vòng lặp trong chỉ thực hiện một lần nếu các điều kiện về stepsize được thỏa mãn. Điều này xảy ra nếu dự đoán ban đầu sn ≥L . Tuy nhiên, nếu L có giá trị lớn thì dự đoán ban đầu chosn như vậy thường dẫn đến một stepsize s1n nhỏ và sự hội tụ của {un} trở nên chậm. Mặt khác, nếu dự đoán ban đầu cho sn khá bé (sn ≪ L) thì điều kiện Θ un+1 ≤ Θsn un+1, un có thể không thỏa mãn. Khi đó, vòng lặp trong cần thực hiện nhiều lần. Điều này cũng làm cho giải thuật chậm hơn.
Trong cả hai trường hợp, giải thuật hội tụ chậm. Như vậy, dự đoán ban đầu cho sn nên không quá nhỏ và thỏa mãn điều kiện Θ un+1≤ Θsn un+1, un. Để thỏa mãn điều đó, người ta thường dùng các phương pháp dự đoán cho sn như sau:
* Quy tắc stepsize hằng số : sn = L,∀n.
* Quy tắc quay lùi: sn+1 = sn.
* Quy tắc quay lùi hiệu chỉnh: sn+1 = sn/γ với γ ∈ (1,∞).
* Quy tắc Barzilai - Borwein:
1
sn = P[s−1,s−1]
un −un−1, F′(un)−F′ un−1
⟨F′(un)−F′(un−1), F′(un)−F′(un−1)⟩
!
. (4.17)