Bài giảng Tối ưu hóa nâng cao - Bài 4: Line search method - Hoàng Nam Dũng

Hoa ng Nam Dung
Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà NộiTại mỗi bước, từ điểm Xk hiện tại, phương pháp line search tính một hướng tìm kiếm (search direction) Pk rồi quyết định sẽ tiến bao xa theo hướng đó.
Tại mỗi bước, từ điểm Xk hiện tại, phương pháp line search tính một hướng tìm kiếm (search direction) Pk rồi quyết định sẽ tiến bao xa theo hướng đó. Công thức lặp để tính điểm tiếp theo được cho bởi
Xk+1 = Xk + ak Pk
trong đó ữk > 0 được gọi là độ dài bước (step length).
Tại mỗi bước, từ điểm Xk hiện tại, phương pháp line search tính một hướng tìm kiếm (search direction) Pk rồi quyết định sẽ tiến bao xa theo hướng đó. Công thức lặp để tính điểm tiếp theo được cho bởi
Xk+1 = Xk + ak Pk
trong đó ữk > 0 được gọi là độ dài bước (step length).
Hiệu qua của phương pháp phụ thuộc vào việc chọn hướng Pk và độ dài bước ữk thích hợp.
Tại mỗi bước, từ điểm Xk hiện tại, phương pháp line search tính một hướng tìm kiếm (search direction) Pk rồi quyết định sẽ tiến bao xa theo hướng đó. Công thức lặp để tính điểm tiếp theo được cho bởi
Xk+1 = Xk + ak Pk
trong đó ữk > 0 được gọi là độ dài bước (step length).
Hiệu qua của phương pháp phụ thuộc vào việc chọn hướng Pk và độ dài bước ữk thích hợp.
Hau hết các phương pháp line search đòi hỏi Pk là một hướng giẳm (descent direction)
Pk rf (xk) < 0
bởi nó sẽ đam bao là giá trị hàm f có thể giam xuống theo hướng này.	1
Giả sử p là một hướng giảm, tức là
pTrf(xk) < 0.
Giả sử p là một hướng giảm, tức là
pTrf(xk) < 0.
Theo công thức khai triển Taylor ta có
f (xk + ap) = f (xk) + apT rf (xk) + O (oi22).
Giả sử p là một hướng giảm, tức là
pTrf(xk) < 0.
Theo công thức khai triển Taylor ta có
f (xk + ap) = f (xk) + apT rf (xk) + O (oi22).
Suy ra f(xk + ap) 0 đủ nhỏ. Tức là ta có thể giảm giá trị hàm số f theo hướng p.
Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min pTrf(xk); s.t. ||p|| = 1.
p
Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min pTVf(xk); s.t. ||p|| = 1.
p
Gọi ỡ là góc giữa p và Vf(xk).
Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min pTVf(xk); s.t. ||p|| = 1.
p
Gọi ỡ là góc giữa p và Vf(xk). Ta có
pT Vf (xk) = ||p||||Vf (xk )|| cos ỡ = ||Vf (xk )|| cos ỡ,
Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min pTVf(xk); s.t. ||p|| = 1.
p
Gọi ỡ là góc giữa p và Vf(xk). Ta có
pT Vf (xk) = ||p||||Vf (xk )|| cos ỡ = ||Vf (xk )|| cos ỡ,
tức là nó đạt giá trị bé nhất khi cosỡ = —1 hay
Vf (xk)
p	||Vf (xk )||.
Hướng giảm nhanh nhất là nghiệm của bài toán tối ưu min pTVf(xk); s.t. ||p|| = 1.
p
Gọi ỡ là góc giữa p và Vf(xk). Ta có
pT Vf (xk) = ||p||||Vf (xk )|| cos ỡ = ||Vf (xk )|| cos ỡ,
tức là nó đạt giá trị bé nhất khi cosỡ = —1 hay
Vf (xk)
p	||Vf (xk )||.
Phương pháp line search với pk = —Vf(xk) được gọi là steepest descent method hay gradient descent method.
Ta thường chọn hướng giảm có dạng
Pk = —Bk rf (xk)
trong đó Bk là một ma trận đối xứng không suy biến.
Ta thường chọn hướng giảm có dạng
Pk = —Bk vf (xk)
trong đó Bk là một ma trận đối xứng không suy biến.
Phương pháp gradient descent: Bk = I
I Phương pháp Newton: Bk = v2f(xk)
Phương pháp tựa Newton: Bk xấp xỉ ma trận Hessian v2f (xk)'
Ta thường chọn hướng giảm có dạng
Pk = —Bk vf (xk)
trong đó Bk là một ma trận đối xứng không suy biến.
Phương pháp gradient descent: Bk = I
I Phương pháp Newton: Bk = v2f(xk)
Phương pháp tựa Newton: Bk xấp xỉ ma trận Hessian v2f (xk)'
Phần tiếp theo chúng ta sẽ tìm hiểu xem chọn hướng và độ dài bước như thế nào để thuật toán hội tụ.
Ta phải cân nhắc lựa chọn giữa hai yếu tố
I Tìm (\k để cải thiện đáng kể giá trị hàm mục tiêu
I Dồng thời không được mất quá nhiều thời gian.
Ta phải cân nhắc lựa chọn giữa hai yếu tố
I Tìm ak để cải thiện đáng kể giá trị hàm mục tiêu
I Dồng thời không được mất quá nhiều thời gian.
Ly tưởng thì ak là nghiệm của bài toán tối ưu
min 0(a) = f (xk + apk); a > 0.
Ta phải cân nhắc lựa chọn giữa hai yếu tố
I Tìm ak để cải thiện đáng kể giá trị hàm mục tiêu
I Dồng thời không được mất quá nhiều thời gian.
Ly tưởng thì ak là nghiệm của bài toán tối ưu min 0(a) = f (xk + apk); a > 0.
Tuy nhiên nó quá tốn kém (ví dụ xem hình vẽ).
I ỳ(a)
De tìm cực tiểu địa phương vói độ chính xác vừa phải có thể ta phải tính rat nhiều lan hàm mục tiêu f và gradient rf.
De tìm cực tiểu địa phương vói độ chính xác vừa phải có thể ta phải tính rat nhiều lan hàm mục tiêu f và gradient rf.
Chiến lược thực tế hơn đó là chúng ta tìm các độ dài bưóc đủ tốt theo nghĩa hàm mục tiêu phải giảm đủ nhiều.
De tìm cực tiểu địa phương vói độ chính xác vừa phải có thể ta phải tính rat nhiều lan hàm mục tiêu f và gradient rf.
Chiến lược thực tế hơn đó là chúng ta tìm các độ dài bưóc đủ tốt theo nghĩa hàm mục tiêu phải giảm đủ nhiều.
Yêu cau giảm f(xk + &kPk) < f(xk) là chưa đủ.
De tìm cực tiểu địa phương vói độ chính xác vừa phải có thể ta phải tính rat nhiều lan hàm mục tiêu f và gradient rf.
Chiến lược thực tế hơn đó là chúng ta tìm các độ dài bưóc đủ tốt theo nghĩa hàm mục tiêu phải giảm đủ nhiều.
Yêu cau giảm f(xk + &kPk) < f(xk) là chưa đủ.
Ví dụ:
f(x)
Giá trị tối ưu f* = —1 nhưng một chuỗi Xk vói f(xk) = 5 chỉ hội tụ đến 0.
Các điều kiện Wolfe
Diều kiện 1: hàm mục tiêu phải giảm đủ nhiều
í(xk + akPk) < f (xk) + CiữkVf/Pk; với C1 2 (0; 1).
Các điều kiện Wolfe
Diều kiện 1: hàm mục tiêu phải giảm đủ nhiều
í(xk + akPk) < f (xk) + CiữkVf/Pk; với C1 2 (0; 1).
Lưu ý rằng Pk là hướng giảm, VfTPk < 0.
Các điều kiện Wolfe
Diều kiện 1: hàm mục tiêu phải giảm đủ nhiều
í(xk + akPk) < f (xk) + CiữkVf/Pk; với C1 2 (0; 1).
Lưu ý rằng Pk là hướng giảm, VfTPk < 0.
Dộ giảm của f tỉ lệ với độ dài bước ữk và VfkPk.
Các điều kiện Wolfe
Diều kiện 1: hàm mục tiêu phải giảm đủ nhiều
í(xk + akPk) < f (xk) + CiữkVf/Pk;
với C1 2 (0; 1).
Lưu ý rằng Pk là hướng giảm, VfTPk < 0.
Dộ giảm của f tỉ lệ với độ dài bước ữk và VfkPk.
Trong thực tế C1 được chọn khá nhỏ, ví dụ C1 = 10_4.
Điều kiện Wolfe - minh họa điều kiện 1
l(ả) := f(xk) + ciaVfTPk (là một đường thẳng có hệ số góc âm).
Hình 1 cho thấy Diều kiện 1 thỏa mãn với a đủ nhỏ.
Hình 1 cho thấy Diều kiện 1 thỏa mãn với a đủ nhỏ.
De loại trừ những bước quá ngắn ta đòi hòi thêm Diều kiện 2 (curvature condition)
rf (xk + ữkPk)TPk > c2rfkTPk
với c2 2 (c1; 1).
Hình 1 cho thấy Diều kiện 1 thỏa mãn với a đủ nhỏ.
De loại trừ những bước quá ngắn ta đòi hòi thêm Diều kiện 2 (curvature condition)
rf (xk + ữkPk)TPk > c2rfkTPk
với c2 2 (c1; 1).
Lưu ý rằng vế trái chính là ộ'(ữk).
Hình 1 cho thấy Diều kiện 1 thỏa mãn với a đủ nhỏ.
De loại trừ những bước quá ngắn ta đòi hòi thêm Diều kiện 2 (curvature condition)
rf (xk + ữkPk)TPk > c2rfkTPk
với c2 2 (ci, 1).
Lưu ý rằng vế trái chính là ộ'(ữk). Diều kiện này đòi hỏi độ dốc của ộ tại ữk lớn hơn hoặc bằng c2 lan độ dốc ban đau ộ0(0).
Hình 1 cho thấy Diều kiện 1 thỏa mãn với a đủ nhỏ.
De loại trừ những bước quá ngắn ta đòi hòi thêm Diều kiện 2 (curvature condition)
rf (xk + ữkPk)TPk > c2rfkTPk
với c2 2 (ci, 1).
Lưu ý rằng vế trái chính là ộ'(ữk). Diều kiện này đòi hỏi độ dốc của ộ tại ữk lớn hơn hoặc bằng c2 lan độ dốc ban đau ộ0(0).
Trong thực tế ta chọn
I c2 = 0.9 với thuật toán Newton, tựa Newton
I c2 = 0.1 với thuật toán conjugate gradient.
ộ'(ak) = Vf(xk + akPk)TPk > C2 VfTPk = £2/(0)
Lưu ý rằng ộ'(0) < 0 và 0 < c2 < 1.
ộ'(ak) = Vf(xk + akPk)TPk > C2 VfTPk = £2/(0)
Lưu ý rằng ộ°(0) < 0 và 0 < c2 < 1.
Như vậy để thỏa mãn điều kiện thì ak sẽ không quá gần 0.
Dồng thời điều kiện đó cũng loại a có độ dốc đủ lớn ộ'(a). Diều này hợp lí vì đó là dấu hiệu ta có thể tiếp tục đi xa hơn theo hướng Pk.
Hình 2: Độ dài bước thỏa mãn điều kiện 2
Diều kiện Wolfe
f(xk + akPk) C2Vf7Pk vói 0 < c1 < c2 < 1.
Hình 3: Dộ dài bước thỏa mãn hai điều kiện Wolfe
Hình 3 cho thấy có những độ dài bước thỏa mãn điều kiện Wolfe nhưng nó không đủ gần một cực tiểu.
Hình 3 cho thấy có những độ dài bước thỏa mãn điều kiện Wolfe nhưng nó không đủ gần một cực tiểu.
Ta có thể điều chỉnh điều kiện 2 để ép ak nằm trong lân cận của một cực tiểu địa phương.
Hình 3 cho thấy có những độ dài bước thỏa mãn điều kiện Wolfe nhưng nó không đủ gần một cực tiểu.
Ta có thể điều chỉnh điều kiện 2 để ép ak nằm trong lân cận của một cực tiểu địa phương.
Diều kiện Wolfe mạnh:
f(xk + akPk) < f (xk) + CiữkVf/Pk;
\vf(xk + ữkPk)T'pkI < C2V|f/PkI
với 0 < C1 < c2 < 1.
Sự tồn tại độ dài bước thỏa mãn điều kiện Wolfe
Bổ đề
Cho f : Rn ! R khả vi liên tục, Pk là một hướng giảm tại Xk và giả sử rằng f bị chặn dưới dọc theo tia {xk + ak I a > 0g. Neu 0 < Cl < c2 < 1 thi ton tại độ dài bước thỏa mãn điều kiện Wolfe và điều kiện Wolfe mạnh.
Chứng minh.
Xem chứng minh Bổ đề 3.1, sách Nocedal.	□
Với 0 < c < 2, điều kiện Goldstein đòi hỏi ữk thỏa mãn
f(xk) + (1 - c)akVfkPk < f(xk + ữkPk) < f(xk) + cữkVí/Pk■
Ve ý nghĩa và nhận xét xem trang 36 sách của Nocedal.
Phương pháp backtracking tìm độ dài bước thỏa mãn điều kiện Wolfe thứ nhất theo một cách thích hợp (mà không can đòi hỏi điều kiện 2).
Phương pháp backtracking tìm độ dài bước thỏa mãn điều kiện Wolfe thứ nhất theo một cách thích hợp (mà không can đòi hỏi điều kiện 2).
Algorithm 2 Backtracking line search
1: Chọn (ã > 0, p 2 (0; 1), c 2 (0; 1)
2: Lấy a := (ã
3: while f (xk + akPk) > f (xk) + cakrfTPk do
4:	a := pa
5: end while
6: ak := a
Nhận xét: Sau một số bước thì a sẽ đủ nhỏ để thỏa mãn điều kiện.
I ty(a.)=f(xk+apk)
acceptable
acceptable
>2a pa
Chọn «:
I (ã = 1 với phương pháp Newton hay tựa Newton
I Có các giá trị khác nhau với thuật toán gradient.
Chọn ã:
I (ã = 1 với phương pháp Newton hay tựa Newton
I Có các giá trị khác nhau với thuật toán gradient.
p có thể chọn khác nhau trong mỗi bước lặp của phương pháp line search.
Dọc thêm mục 3.5 sách của Nocedal (quan trọng nhưng không đủ thời gian để trình bày trên lớp).
Sự hội tụ của phương pháp line search và tốc độ hội tụ
Mục 3.2 sách của Nocedal chứng minh sự hội tụ của phương pháp line search khi độ dài bước thỏa mãn điều kiện Wolfe.
Sự hội tụ của phương pháp line search và tốc độ hội tụ
Mục 3.2 sách của Nocedal chứng minh sự hội tụ của phương pháp line search khi độ dài bước thỏa mãn điều kiện Wolfe.
Ta sẽ chứng minh công thức tốc độ hội tụ khi xét từng thuật toán
I Gradient descent
I Newton
I Tựa Newton.
Tà i liệu tham khảo
Chương 3, J. Nocedal and S. Wright, Numerical Optimization, Springer.