Bài giảng Tối ưu hóa nâng cao - Bài 3: Bài toán tối ưu không ràng buộc - Hoàng Nam Dũng

Bài toán tối ưu không ràng buộc 
Hoà ng Nam Dũng
Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
min f (x)
x
với f : Rn ! R là một hàm trơn (smooth).
min f (x)
x
với f : Rn ! R là một hàm trơn (smooth).
Định nghĩa
x* được gọi là cực tiểu toàn cục nếu
f(x*) < f(x); 8x.
min f (x)
x
với f : Rn ! R là một hàm trơn (smooth).
Định nghĩa
x* được gọi là cực tiểu toàn cục nếu
f(x*) < f(x); 8x.
x* được gọi là cực tiểu địa phương nếu tồn tại một lẫn cận N của x* sao cho
f (x*) < f(x); 8x 2 N.
min f (x)
x
với f : Rn ! R là một hàm trơn (smooth).
Định nghĩa
x* được gọi là cực tiểu toàn cục nếu
f(x*) < f(x); 8x.
x* được gọi là cực tiểu địa phương nếu tồn tại một lẫn cận N của
x* sao cho
f (x*) < f(x); 8x 2 N.
x* được gọi là cực tiểu địa phương mạnh (hay ngặt) nếu tồn tại
một lẫn cận N của x* sao cho
f (x*) < f(x); 8x 2 N\{x*}.
	 J'
Ví dụ
Hàm số dưới đây có nhiều cực tiểu địa phương và khó để tìm cực tiểu toàn cục.
Định lý (Khai triển Taylor)
Cho f : Rn ! R khả vi liên tục và p 2 Rn. Ta có
f (x + p) = f (x) + Vf (x + tp)T p, với t 2 (0; 1) nào đó.
Định lý (Khai triển Taylor)
Cho f : Rn ! R khả vi liên tục và p 2 Rn. Ta có
f (x + p) = f (x) + Vf (x + tp)T p,
với t 2 (0; 1) nào đó. Neu f khả vi liên tục hai lần thi
f (x + p) = f (x) + Vf (x )T p + 1 pT V2f (x + tp)p, với t 2 (0; 1) nào đó.
Định lý (Điều kiện cần bậc nhất)
Nếu x* là một cực tiểu địa phương và f khả vi liên tục trong một lẫn cận mở của x* thì rf (x*) = 0.
Định lý (Điều kiện cần bậc nhất)
Nếu x* là một cực tiểu địa phương và f khả vi liên tục trong một lẫn cận mở của x* thì Vf (x*) = 0.
Chứng minh.
Giả sử Vf(x*) = 0. Chọn p = —Vf(x*) thì pTVf(x*) = — ||Vf(x*)||2 < 0.
Định lý (Điều kiện cần bậc nhất)
Nếu x* là một cực tiểu địa phương và f khả vi liên tục trong một lẫn cận mở của x* thì Vf (x*) = 0.
Chứng minh.
Giả sử Vf(x*) = 0. Chọn p = —Vf(x*) thì
pTVf(x*) = — ||Vf(x*)||2 < 0.
Từ đó và do Vf liên tục trong lân cận của x*, tồn tại T > 0 sao cho
pTVf(x* + sp) < 0; 8s 2 [0; T].
Định lý (Điều kiện cần bậc nhất)
Nếu x* là một cực tiểu địa phương và f khả vi liên tục trong một lẫn cận mở của x* thì Vf (x*) = 0.
Chứng minh.
Giả sử Vf(x*) = 0. Chọn p = —Vf(x*) thì pTVf(x*) = — ||Vf(x*)||2 < 0.
Từ đó và do Vf liên tục trong lân cận của x*, tồn tại T > 0 sao cho
pTVf(x* + sp) < 0; 8s 2 [0; T].
Với mỗi t 2 (0; T] theo định lý Taylor tồn tại s 2 (0; t) sao cho
f (x * + tp) = f (x *) + t Vf (x * + sp)T p
Định lý (Điều kiện cần bậc nhất)
Nếu x* là một cực tiểu địa phương và f khả vi liên tục trong một lẫn cận mở của x* thì Vf (x*) = 0.
Chứng minh.
Giả sử Vf(x*) = 0. Chọn p = —Vf(x*) thì
pTVf(x*) = -||Vf(x*)||2 < 0.
Từ đó và do Vf liên tục trong lân cận của x*, tồn tại T > 0 sao cho
pTVf(x* + sp) < 0; 8s 2 [0; T].
Với mỗi t 2 (0; T] theo định lý Taylor tồn tại s 2 (0; t) sao cho
f(x* + tp) = f(x*) + tVf(x* + sp)Tp < f(x*);
mâu thuẫn.	□
Định lý (Điều kiện cần bậc hai)
Nếu x* là một cực tiểu địa phương và r2f tồn tại và liên tục trong một lân cận mở của x* thi rf (x*) = 0 và r2f (x*) là nửa xác định dương (positive semidefinite).
Định lý (Điều kiện cần bậc hai)
Nếu x* là một cực tiểu địa phương và V2f tồn tại và liên tục trong một lân cận mở của x* thi Vf (x*) = 0 và V2f (x*) là nửa xác định dương (positive semidefinite).
Chứng minh.
Từ định lý trước ta có Vf(x*) = 0.
Định lý (Điều kiện cần bậc hai)
Nếu x* là một cực tiểu địa phương và v2f tồn tại và liên tục trong một lân cận mở của x* thi Vf (x*) = 0 và v2f (x*) là nửa xác định dương (positive semidefinite).
Chứng minh.
Từ định lý trước ta có Vf(x*) = 0. Giả sử v2f(x*) không phải nửa xác định dương, tức là tồn tại p sao cho pTv2f(x*)p < 0.
Định lý (Điều kiện cần bậc hai)
Nếu x* là một cực tiểu địa phương và v2f tồn tại và liên tục trong một lân cận mở của x* thi Vf (x*) = 0 và v2f (x*) là nửa xác định dương (positive semidefinite).
Chứng minh.
Từ định lý trước ta có Vf(x*) = 0. Giả sử v2f(x*) không phải nửa xác định dương, tức là tồn tại p sao cho pTv2f(x*)p 0 sao cho
pTV2f(x* + sp)p < 0; 8s 2 [0; T].
Định lý (Điều kiện cần bậc hai)
Nếu x* là một cực tiểu địa phương và v2f tồn tại và liên tục trong một lân cận mở của x* thi Vf (x*) = 0 và v2f (x*) là nửa xác định dương (positive semidefinite).
Chứng minh.
Từ định lý trước ta có Vf(x*) = 0. Giả sử v2f(x*) không phải nửa xác định dương, tức là tồn tại p sao cho pTv2f(x*)p 0 sao cho
pTV2f(x* + sp)p < 0; 8s 2 [0; T].
Áp dụng định lý Taylor ta có với mỗi t 2 (0; T] tồn tại s 2 (0; t) sao cho
f (x * + tp) = f (x *) + t Vf (x *)T p + 212pT v2f (x * + sp)p
Định lý (Điều kiện cần bậc hai)
Nếu x* là một cực tiểu địa phương và v2f tồn tại và liên tục trong một lân cận mở của x* thi Vf (x*) = 0 và v2f (x*) là nửa xác định dương (positive semidefinite).
Chứng minh.
Từ định lý trước ta có Vf(x*) = 0. Giả sử v2f(x*) không phải nửa xác định dương, tức là tồn tại p sao cho pTv2f(x*)p 0 sao cho
pTV2f(x* + sp)p < 0; 8s 2 [0; T].
Áp dụng định lý Taylor ta có với mỗi t 2 (0; T] tồn tại s 2 (0; t) sao cho
f(x* + tp) = f(x*) + tVf(x*)Tp + 212pTv2f(x* + sp)p < f(x*);
mâu thuẫn.	□	5
Diều kiện cần bậc 2 không phải là điều kiện đủ.
Ví dụ vói f (x) = x3 thì f0(0) = 0 và f/0(0) = 0, tức là x = 0 thỏa mãn điều kiện cần bậc 2, tuy nhiên nó không phải là một điếm cực tiêu địa phương của x3.
Định lý (Điều kiện đủ bậc hai)
Neu r2f tổn tại và liên tục trong một lân cận mỏ của x*, rf (x*) = 0 và r2f (x*) là xác định dương (positive definite) thi x* là một cực tiểu địa phương ngặt.
Định lý (Điều kiện đủ bậc hai)
Neu v2f tổn tại và liên tục trong một lân cận mỏ của x*, vf (x*) = 0 và v2f (x*) là xác định dương (positive definite) thi x* là một cực tiểu địa phương ngặt.
Chứng minh.
Vì ma trận Hessian v2f liên tục và xác định dương tại x* nên ta có thể chọn r > 0 sao cho v2f(x) cũng xác định dương với mọi x thuộc hình cầu B := fy 2 Rn I ky — x* II < rg.
Định lý (Điều kiện đủ bậc hai)
Neu v2f tổn tại và liên tục trong một lân cận mỏ của x*, vf (x*) = 0 và v2f (x*) là xác định dương (positive definite) thi x* là một cực tiểu địa phương ngặt.
Chứng minh.
Vì ma trận Hessian v2f liên tục và xác định dương tại x* nên ta có thể chọn r > 0 sao cho v2f(x) cũng xác định dương với mọi x thuộc hình cầu B := fy 2 Rn I ky — x* II < rg.
Với p 2 Rn thỏa mãn p = 0 và IIpII < r, ta có x* + tp 2 B với mọi t 2 (0; 1).
Định lý (Điều kiện đủ bậc hai)
Neu v2f tổn tại và liên tục trong một lân cận mỏ của x*, vf (x*) = 0 và v2f (x*) là xác định dương (positive definite) thi x* là một cực tiểu địa phương ngặt.
Chứng minh.
Vì ma trận Hessian v2f liên tục và xác định dương tại x* nên ta có thể chọn r > 0 sao cho v2f(x) cũng xác định dương với mọi x thuộc hình cầu B := fy 2 Rn I ky — x* II < rg.
Với p 2 Rn thỏa mãn p = 0 và IIpII < r, ta có x* + tp 2 B với mọi t 2 (0; 1). Do đó
pTv2f(x* + tp)p > 0; 8t 2 (0; 1).
Định lý (Điều kiện đủ bậc hai)
Neu v2f tổn tại và liên tục trong một lân cận mỏ của x*, vf (x*) = 0 và v2f (x*) là xác định dương (positive definite) thì x* là một cực tiểu địa phương ngặt.
Chứng minh.
Vì ma trận Hessian v2f liên tục và xác định dương tại x* nên ta có thể chọn r > 0 sao cho v2f(x) cũng xác định dương với mọi x thuộc hình cầu B := fy 2 Rn I ky — x* II < rg.
Với p 2 Rn thỏa mãn p = 0 và IIpII < r, ta có x* + tp 2 B với mọi t 2 (0; 1). Do đó
pTv2f(x* + tp)p > 0; 8t 2 (0; 1).
Theo định lý Taylor tồn tại t 2 (0; 1) sao cho
f (x * + p) = f (x *) + vf (x *)Tp + 1 pT v2f (x * + tp)p	7
Định lý (Điều kiện đủ bậc hai)
Neu v2f tổn tại và liên tục trong một lân cận mỏ của x*, vf (x*) = 0 và v2f (x*) là xác định dương (positive definite) thì x* là một cực tiểu địa phương ngặt.
Chứng minh.
Vì ma trận Hessian v2f liên tục và xác định dương tại x* nên ta có thể chọn r > 0 sao cho v2f(x) cũng xác định dương với mọi x thuộc hình cầu B := fy 2 Rn I ky — x* II < rg.
Với p 2 Rn thỏa mãn p = 0 và IIpII < r, ta có x* + tp 2 B với mọi t 2 (0; 1). Do đó
pTv2f(x* + tp)p > 0; 8t 2 (0; 1).
Theo định lý Taylor tồn tại t 2 (0; 1) sao cho
f(x* + p) = f(x*) + vf(x*)Tp + 2pTv2f(x* + tp)p > f(x*).	7
Lưu ý
Diều kiện đủ bậc 2 không phải là điều kiện cần cho cực tiểu địa phương ngặt.
Lưu ý
Diều kiện đủ bậc 2 không phải là điều kiện cần cho cực tiểu địa phương ngặt.
Hàm f (x) = x4 có cực tiểu ngặt tại x = 0 tuy nhiên đạo hàm bậc 2 của nó bằng 0, tức là không xác định dương.
Cực tiểu của hàm lồi
Định nghĩa
Cho một hàm f khả vi. Một điểm x thỏa mãn r f (x) = 0 gọi là một điểm dừng.
Cực tiểu của hàm lồi
Định nghĩa
Cho một hàm f khả vi. Một điểm x thỏa mãn r f (x) = 0 gọi là một điểm dừng.
Định lý
Nếu f lồi thì mọi điểm cực tiểu địa phương của f cũng là cực tiểu toàn cục. Ngoài ra nếu f khả vi thì mỗi điểm dừng là một cực tiểu toàn cục.
Chứng minh.
Xem định lý 2.5 sách của Nocedal.	□
Cực tiểu của hàm lồi
Định nghĩa
Cho một hàm f khả vi. Một điểm x thỏa mãn r f (x) = 0 gọi là một điểm dừng.
Định lý
Nếu f lồi thì mọi điểm cực tiểu địa phương của f cũng là cực tiểu toàn cục. Ngoài ra nếu f khả vi thì mỗi điểm dừng là một cực tiểu toàn cục.
Chứng minh.
Xem định lý 2.5 sách của Nocedal.	□
Câu hỏi: Với cực đại thì kết quả tương tự thế nào?
Tống quan về thuật toán
Các thuật toán đều đòi hỏi được cung cấp một điểm xuất phát x0-
Tổng quan về thuật toán
I Các thuật toán đều đòi hỏi được cung cấp một điểm xuất phát x0-
I Từ đó thuật toán tạo ra chuỗi x1; x2;... -
Tổng quan về thuật toán
I Các thuật toán đều đòi hỏi được cung cấp một điểm xuất phát x0.
I Từ đó thuật toán tạo ra chuỗi x1; x2;... -
I Thuật toán sẽ dừng lại nếu không có sự cải thiện hay có vẻ nghiệm đã xấp xỉ đủ tốt.
Tổng quan về thuật toán
I Các thuật toán đều đòi hỏi được cung cấp một điểm xuất phát x0.
I Từ đó thuật toán tạo ra chuỗi x1; x2;... -
I Thuật toán sẽ dừng lại nếu không có sự cải thiện hay có vẻ nghiệm đã xấp xỉ đủ tốt.
I Có 2 chiến thuật cơ bản để tính điểm tiếp theo Xk+1 từ điểm hiện tại Xk, đó là line search và trust region.
ỏ bước k thuật toán chọn một hướng Pk và tìm kiếm theo hướng đó từ giá trị hiện tại Xk để tìm được điểm tiếp theo với hàm mục tiêu thấp hơn.
ỏ bước k thuật toán chọn một hướng Pk và tìm kiếm theo hướng đó từ giá trị hiện tại Xk để tìm được điểm tiếp theo với hàm mục tiêu thấp hơn.
De tìm khoảng cách đi theo hướng này ta có thể giải bài toán tối ưu 1 chiều
min f (xk + apk).
a>0 
ỏ bước k thuật toán chọn một hướng Pk và tìm kiếm theo hướng đó từ giá trị hiện tại Xk để tìm được điểm tiếp theo với hàm mục tiêu thấp hơn.
De tìm khoảng cách đi theo hướng này ta có thể giải bài toán tối ưu 1 chiều
min f (xk + apk).
a>0
Thực tế ta sẽ không giải chính xác vì nó tốn kém và không can thiết. Thay vào đó ta chỉ giải xấp xỉ (tương đối lỏng) qua một số bước lặp.
ỏ bước k ta xây dựng một hàm xấp xỉ mk của f. Hàm này xấp xỉ f tốt quanh Xk và có thể tệ khi ở xa.
ỏ bước k ta xây dựng một hàm xấp xỉ mk của f. Hàm này xấp xỉ f tốt quanh Xk và có thể tệ khi ở xa. Do đó ta chỉ tìm cực tiểu của mk trong miền quanh Xk qua việc xét bài toán
min mk(xk + p); sao cho Xk + p thuộc trust region.
p
ỏ bước k ta xây dựng một hàm xấp xỉ mk của f. Hàm này xấp xỉ f tốt quanh Xk và có thể tệ khi ở xa. Do đó ta chỉ tìm cực tiểu của mk trong miền quanh Xk qua việc xét bài toán
min mk(xk + p); sao cho Xk + p thuộc trust region, p
Nếu điểm được tạo ra không có giá trị hàm mục tiêu giảm đủ nhiều thì ta kết luận rằng trust region quá lớn và phải thu hẹp lại và giải lại bài toán tối ưu trên.
ỏ bước k ta xây dựng một hàm xấp xỉ mk của f. Hàm này xấp xỉ f tốt quanh Xk và có thể tệ khi ở xa. Do đó ta chỉ tìm cực tiểu của mk trong miền quanh Xk qua việc xét bài toán
min mk(xk + p); sao cho Xk + p thuộc trust region, p
Nếu điểm được tạo ra không có giá trị hàm mục tiêu giảm đủ nhiều thì ta kết luận rằng trust region quá lớn và phải thu hẹp lại và giải lại bài toán tối ưu trên.
Thông thường trust region là một hình cau định nghĩa bởi ||p||2 0 được gọi là bán kính trust region.
ỏ bước k ta xây dựng một hàm xấp xỉ mk của f. Hàm này xấp xỉ f tốt quanh Xk và có thể tệ khi ở xa. Do đó ta chỉ tìm cực tiểu của mk trong miền quanh Xk qua việc xét bài toán
min mk(xk + p); sao cho Xk + p thuộc trust region, p
Nếu điểm được tạo ra không có giá trị hàm mục tiêu giảm đủ nhiều thì ta kết luận rằng trust region quá lớn và phải thu hẹp lại và giải lại bài toán tối ưu trên.
Thông thường trust region là một hình cau định nghĩa bởi ||p||2 0 được gọi là bán kính trust region.
mk thường được chọn là hàm bậc 2
12
mk (xk + p) = f (Xk) + pT vf (xk) + 1 pT Bk p
với ma trận Bk là ma trận Hessian v2f(xk) hay xấp xỉ của nó.
về mặt nào đó có thể coi phương pháp line search và trust region khách nhau về thứ tự chọn hướng và khoảng cách. về mặt nào đó có thể coi phương pháp line search và trust region khách nhau về thứ tự chọn hướng và khoảng cách.
Line search chọn hướng trước rồi theo hướng đó chọn khoảng cách. 
về mặt nào đó có thể coi phương pháp line search và trust region khách nhau về thứ tự chọn hướng và khoảng cách.
Line search chọn hướng trước rồi theo hướng đó chọn khoảng cách.
Trust region cố định khoảng cách tối đa trước rồi chọn hướng tốt nhất theo ràng buộc đó.
Tà i liệu tham khảo
Chương 2, J. Nocedal and S. Wright, Numerical Optimization, Springer.
Chi tiết ve Line search: Chương 3, J. Nocedal and S. Wright, Numerical Optimization, Springer.
Chi tiết ve Trust region: Chương 4, J. Nocedal and S. Wright, Numerical Optimization, Springer.