Giáo trình Tối ưu phi tuyến: Phần 2 - Trần Vũ Thiệu, Nguyễn Thị Thu Thủy

Nối tiếp nội dung phần 1 cuốn giáo trình 'Tối ưu phi tuyến', phần 2 giới thiệu tới người đọc các nội dung: Phương pháp Gradient, phương pháp tìm cục tiểu có ràng buộc (Phương pháp trực tiếp, phương pháp tuyến tính hóa, phương pháp hướng chấp nhận được, phương pháp phạt). Mời các bạn cùng tham khảo nội dung chi tiết.

Nội dung trích xuất từ tài liệu:
Giáo trình Tối ưu phi tuyến: Phần 2 - Trần Vũ Thiệu, Nguyễn Thị Thu Thủy Chương 7 PHƯƠNG PHÁP GRADIENT 7.1ẵPHƯƠNG PHÁP HƯỚNG D ố c NHÂT 7.1.1ệ Nội d u n g phư ư ng ph áp Xét bài toán tối ưu không ràng buộc min ( f ( x ) : X £ K|. Ta sẽ xây dựng một dãy điểm x°, X1, X2, ... sao cho f(xk+l) < f(x k) với mọi k = 0, 1 , 2 , . . . , dãy (x k Ị hội tụ tới X* khi k -> 00 và Vf(x*) = 0. G iả sử ta có điểm xk thuộc lân cận của X*, khi đó để giảm hàm m ục tiêu ta sẽ dịch chuyển từ xk theo hướng dk tạo với véctơ gradient Vf(xk) một góc tù, tức là xác định xk+l = xk + a kdk trong đó a k > 0, < 0. Thật vậy, khai triển hàm f(x) thành chuỗi Taylor tại điểm xk ta được a2 f(x) = f(xk) + a + — , „ong dó vf(x) . ỠX| Ể g í ì ....... ỡx2 m f. ỡxn v>f(j) . ƠXịỡXj cấp nxn và x k = xk + 0(x - xk) với 0 e [0,1]. Nếu < 0 thì với a > 0 đủ nhỏ ta có f(x) < f(xk). Việc lựa chọn hướng dịch chuyển dk và độ dài bước a k khác nhau sẽ cho ta các phương pháp gradient khác nhau. N ếu chọn d k — - Vf(xk) với mọi k thì phương pháp gradient như thế gọi là phương 183 pháp luỉớng dốc nhất (Steepest Descent M ethod). Đây là một phương pháp thông dụng để tìm cực tiểu, nó rất đơn giản và có thể áp dụng cho nhiều lớp hàm rất rộng. Phương pháp này xây dựng dãy lặp: xk+' = xk - otkVf(xk), ctk > 0, k = 0, 1 ,... (7.1) Ì3. T h u ậ t toán xác địn h a k tại mỗi bước lặp {Qui tắc Armijo): 1) Chọn giá trị a tùy ý (như nhau với mọi bước lặp, chẩng hạn a = 1) và xác định đ iểm X = x k - ccV f(xk). 2) Tính f(x) = f[xk - a V f(x k)]. 3) Kiểm tra bất đảng thức: f(x) - f(xk) < e a = - eallV f(xk)ll2 (7.2) với 0 < £ < 1 là một hằng số được chọn tùy ý, như nhau với mọi k = 0,1, ... 4) Nếu (7.2) thỏa mãn thì a là giá trị cần tìm: a k = a. Nếu (7.2) không thỏa mãn thì ta giảm a (bằng cách nhân a với một số Ấ 6 (0, 1), chẳng hạn Ằ = Vì) cho đến khi bất đẳng thức (7.2) được thỏa mãn. 7.1.2. Sự hội tụ củ a phương p h á p g ra d ie n t Ta n ói dãy ( x k) hội tụ tới đ iểm X* v ớ i tô Ệ c đ ộ l i ộ i t ụ t u y ế n lí n h hay tốc độ hội tụ cấp số nhân (công bội q) nếu bắt đầu từ một chi số k nào đó ta có bất đảng thức llxk+l - x*ll < q llxk - x * ll, 0 < q < 1. Cơ sở của việc lựa chọn a như trên và sự hội tụ của phương pháp gradient cho trong định lý sau. Đ ịnh lý 7.1ẻ Giả sử hàm f(x) bị chặn dưới, gradient Vf(x) thỏa mãn điều kiện L ipschitz: IIVf(x) - Vf(y)ll < Lllx - yll, Vx, y e l ” và a k được chọn theo thuật toán nêu trên. Khi đó, với bát kỳ’ điềm ban đầu x°, quá trình lặp (7.1) có tính chất: IIVf(xk)ll -> 0 khi k -► X. 184 C h ứ n g m inh. Theo định lý giá trị trung bình: f(x ) - f(x k) = < V f( x k ), x - x k>, trong đó x k = xk + 0(x - xk) với 0 e [0, 1], Do X - xk = - aV f(x k) nên ta có f(x) - f( x k) = < V f ( x k), X - x k> + < V f( x k ) - V f(x k), X - x k>, < - a< V f(x k), Vf(xk)> + ã > 0, trong đó ã có thể chọn là hằng sô' tùy ý không vượt quá (1 - £)/ L (vì bất đảng thức (7.2) hay (7.3) được thỏa mãn với a = (1 - e)/L). Từ (7.4), (7.5) và chú ý này suy ra IIVf(xk)ll -» 0 khi k -> 00. Đ ịnh lý được chứng minh. Đ ịnh lý 7.1 bảo đàm giá trị hàm mục tiêu hội tụ hoặc đến cận iưới inf f(x), hoặc tới giá trị của hàm tại điểm dừng nào đó (có thể à điểm cực tiểu địa phương hay điểm yên ngựa). Với những giả 185 thiết nhất định về độ trơn và tính lồi của hàm cần tìm cực tiểu, la có thế đánh giá được tốc độ hội tụ cùa phương pháp gradient. Đ ịnh lý 7.2. Giá sử f(x) là hàm lồi hai làn khá vi liên tục và ma trận các dạo liàm bậc hai llìòa m ãn điêu kiện : m llyll2 < < v 2f(x)y, y> < M llyll2, M > m > 0. (7.6) với m ọi X, y 6 Kn, CÒI1 d ã y 1xk I dược x â y dựng th eo phương pháp (7.1 ), trong dó a k được chọn tlieo tliuật toán d ã mó tà. Khi dó với b ấ t kỳ điểm ban (láu Xo, ta s ẽ có x k —> X*, f ( x k) —> f(x *), trong dó X* lủ điểm cực tiểu (duy nhất) của f(x). Đồng tliời, ta có các đánh giá sau về tấc dộ liội tụ cùa tliuật toán: f(xk) - f(x*) < q'ff ...