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

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:168

Thêm vào BST

Báo xấu

352
lượt xem 104
download

Download Vui lòng tải xuống để xem tài liệu đầ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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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íx") - f(x*)], llxk - x*ll < C q ^ , c < 00,0 < q , trong đó X = 0X + ( 1 - 0)x* với 9 e [0, 1]. Từ đó nhà tính đến (7.6) ta có f(x) - f(x*) = < V f(x ), X - x*> - ‘/ 2 < v 2f ( x ) ( x - X*), X - x*>. < < V f(x ), X - x * > - — llx - x * ll2 2 < IIVf(x)llắllx - x*ll - — llx - x*ll2. (7.7) 2 Đồng thời (do Vf(x*) = 0) f(x) - f(x*) = Vỉ < v 2f( X )(x - X*), X - x*>, trong đó X = 0X + ( 1 - 0)x* với e e [0, 1]. Vì vậy theo giả thiết (7.6) V llx - x*ll2 < f(x ) - f(x * ) < — llx - x*ll2. (7.8) 2 2 186
Sử dụng bất đẳng thức trái của (7.8) và ước lượng (7.7) ta có llx -x * ll< — IIVf(x)ll m và từ bất đẳng thức phải của (7ề8) suy ra llx -x * ll2 > — [f(x) - f(x*)]. M Dùng hai bất đẳng thức trên, ta đánh giá tiếp (7.7) f(x) - f(x*) < — IIVf(x)ll2 - — [f(x) - f(x*)]. m M Từ đó IIVf(x)ll2 > m( 1 + — )[f(x) - f(x*)]. (7.9) M Sử dụng đánh giá này vào bất đẳng thức (7.3) ta nhận được f(xk+1) - f ( x k) < - e a km (l + — )[f(xk) - f(x*)]. (7.10) M Với các điều kiện cùa định lý thì f(x) - f(xk) = + Vỉ 2 = - allV f(xk)ll2 + — 2 < - a( 1 - — )IIVf(xk)ll2. 2 Từ đó suy ra rằng bất đẳng thức (7.2) sẽ được thỏa mãn nếu chọn aM . 2(1 - e ) ( 1 ------ —- ) > £, tức là a < a = — --------. 2 M Khi đó, từ (7.10) suy ra f(xk+l) - f(x*) < [1 - e a km( 1 + — )].[f(xk) - f(x*)] < q[f(xk) - f(x*)], M 187
trong đ ó q = l - e a ư i ( l + m /M ) < 1, tức là f(xk) - f ( x * ) < q k[ f ( x ") - f ( x * ) ] . (7.11) Do ã = 2(1 - e)/M . ta có M M Từ đó suy ra ràng giá trị cực tiểu cùa q đạt được khi E = ị-, đổng thời m ,ấ m X qm,n" 2M M vì thế trong điểu kiện (7.2) nên đật e = —. Đánh giá (7.11) cùng với vế trái cùa (7.8) cho phép khảng định sự hội tụ và đánh giá tốc độ hội tụ của dãy I xk I tới điểm cực tiểu llxk - x * l l < í — ì " [ f ( x k) - f ( x * ) ] l/2 Vm ) < 2 [f(x " )-f(x * )]lữ qk/2< C q k--. Định lý được chứng minh đầy đù. Q ua chứng minh trên ta thấy rằng để thu được đánh giá (7.11) ta đã sứ dụng các điều kiện (7.2). (7.9). Ta kết luận rằng lớp hàm có đánh giá (7.11) thực sự rộng hơn nhiều so với lớp hàm thòa mân điều kiện (7.6). vì đánh giá (7.11) đúng với mọi hàm thỏa mãn điều kiện cùa Định lv 7.1 và điều kiện: IIVf(x)ll: > ỗ[f(x) - f(x*)]. ỗ > 0. Thuật toán xác định a theo (7.2) thường được gọi là thuật toán quay lui (backtracking). Sau đây sẽ nêu một số cách xác định a khác m à vẫn bảo đảm sự hội tụ cùa phương pháp gradient. 188
7.1.3. C ác d ạ n g k h ác của phương p h á p g rad ie n t • P hư ơ ng p h áp g rad ie n t với độ dài bước cỏ định Nếu hằng số L (trong Định lý 7.1) và M (trong Định lý 7.2) biết trước thì trong phương pháp (7.1) có thể chọn cố định trước a k = ã , trong đó 0 < ã < — hoặc 0 < ã < — . L M Khi đó, các định lý hội tụ 7.1 và 7.2 vẫn đúng. • Phương pháp gradient với cực tiều hàm theo hướng dịch chuyển Độ dài bước a k ở mỗi bước lặp được chọn từ điều kiện f[xk - a kV f(xk)] = min I f[xk - ctVf(xk)] : a > 0 ). Cách xác định a như trên được gọi là phiíơiiỊi pliáp tìm clúiih xác theo lia (Exact Line Search). Khi đó các định lý hội tụ 7.1 và 7.2 vẫn đúng. Ngoài ra, ta còn nhận được đánh giá chính xác hơn về ló c đ ộ h ộ i tụ : „ k Í m Y /2 ( M - mÝ llx - x*ll < — xllx - x * l l x — ------ . V, m y VM + m ) • P hương p h áp g ra d ie n t khác Cho F(x) là một ma trận đối xứng thỏa mãn điều kiện: pllyll2 < < TỊllyll2 (p > 0), Vx. y e K". (7.12) Nếu chọn d = - F(x).V f(x) và nếu Vf(x) * 0 thì = - < - pllVf(x)ll2 < 0, nghĩa là d = - F (x).V f(x) là hướng giảm của f(x). Như vậy, để tìm ực tiếu của f(x) ta có thê dùng phép lặp: XUI = xk - a kFk.Vf(x), a k > 0, k = 0. 1,... rong đó {Fk) là dãy ma trận bát kỳ thỏa mãn (7.12). 189
Đế thống nhất ký hiệu, đôi khi ta dùng phép lặp xk+' = xk - c x kF k 1.Vf(xk) , a k > 0 , k = 0, 1,... (7.13) trong đó F ¡“1 là ma trận nghịch đảo cùa Fk. Có thế chứng minh được rằng nếu Fk thỏa mãn (7.12) thì F [ ' sẽ thỏa mãn: mIllyll2 < < F [ ‘ y, y> < M|llyll: với m, = p /iỷ và M | = 1/p. = -
Sau đây là m ột số cách chọn ma trận Fk • Fk xác định dương và dk = - F k' .Vf(xk). • F k = In với In là m a trận đơn vị cấp n (Phương pháp hướng dốc nhất). • Fk = v 2f(xk) nếu v 2f(xk) xác định dương (Phương pháp Newton). 0 • Fk = m a x j?' l(ì - , 1} nếu v 2f(xk) không xác định ỔXj 0 dương và n lớn. • Fk = v 2f(xk) + yln nếu v 2f(xk) không xác định dương và n không quá lớn, trong đó Y = max {0, 1 - Ằmin (giá trị riêng nhỏ nhất) của v 2f(xk) |. Ví d ụ 7.1ế Dùng phương pháp gradient tìm cực tiểu của hàm số f(x„ x 2) = (X, - 6 ) 2 + 2(x 2 - 3)2. Giải: Tính Vf(x) = (2x, - 12; 4x2 - 12)T. Chọn điếm ban đầu x' = (0; 0)T, f(x ') = 54. Bước lặp 1. Ta có V f(x') = (- 12; - 12)T. Chọn hướng giảm nhanh nhất d' = (1; 1)T, tỉ lệ với -Vf(x'). Xét điểm X = (X|, X2)T trên tia X1 + Id' (t > 0): X| = 0 + l x t = t v à x 2 = 0 + l x t = t. Thay vào hàm m ục tiêu cần tìm cực tiểu ta được:
Bước lặp 2. Ta có Vf(x2) = (- 4; 4)T. Hướng giảm nhanh nhất d 2 = (1; - 1)T (tỉ lệ với - V f(x 2)). Xét các điếm X = (X|, X2)T irên tia X2 + td2 (t > 0): X, = 4 + t và x 2 = 4 - 1. Thay vào hàm mục tiêu ta được: 0): X| = 16/3 + t và x 2 = 8/3 + t. T hế vào hàm mục tiêu ta được: 0): X, = 5 2 / 9 + t v à x 2 = 2 8 /9 - 1. T hế vào hùm mục tiêu ta được: (t) = f(x4 + td4) = (52/9 + t - 6)2 + 2(28/9 - 1 - 3): = (t - Ĩ /9 Ý + 2( 1/9 - 1)2 = 3t2 - (8/9)1 + 2/27. 192
Cho đạo hàm (p’(t) = 6t - 8/9 = 0, ta được t4 = 4/27. Đ iểm lặp mới X5 = X4 + t4d 4 = (52/9; 2 8 /9 )T + (4 /2 7 )x (l; - 1)T = (160/27; 80/27)t , f(x5) = 2/243. Bước lặp 5. Ta có Vf(x5) = (- 4/27; - 4/27)T. Hướng giảm nhanh nhất d 5 = (1; 1)T (tỉ lệ với - V f(x 5)). Xét các điểm X = (Xị, X2)T trên tia X5 + td 5 (t > 0): X! = 160/27 + t và x2 = 80/27 + t. T hế vào hàm mục tiêu ta được:
Hình 7.2. Minh họa Ví dụ 7.1 7ễ2ẵ PHƯƠNG PHÁP NEWTON 7.2.1. Nội d u n g phương ph áp Trong phương pháp gradient chỉ có số hạng tuyến tính ờ khai triển f(x) thành chuỗi Taylor được dùng để chọn hướng dịch chuyển, nghĩa là chỉ sử dụng xấp xi thô của hàm cần tìm cực tiểu. Phương pháp Newton sử dụng cả đạo hàm cấp hai và vì thê' nó đòi hỏi hàm f(x) hai lần khả vi liên tục. Ta biết rằng nếu X* là điểm cực tiểu tự do của hàm f(x) thì Vf(x*) = 0 . Do đó, nếu điểm x" ở gần X* t h ì trong lân cận x° có thể xấp xỉ f(x) bởi hàm bậc hai:
x m = x ° - [ V 2f(x 0) r ' - V f ( x n). N hư vậy, nếu hàm f(x) hai lần khả vi liên tục và [V2f(xk)]~' tồn tại với m ỗi x k thì để tìm X* ta có thể dùng công thức lặp: x k+l = x k - [V 2f(x k)]"'.V f(xk). (7.14) • Phuơng pháp Newton thuần túy (P u re N ew ton M ethod) Chọn điểm x° tùy ý. Tính dãy điểm (xk) theo công thức (7.14). Quá trình lặp sẽ dừng khi Vf(xk+I) * 0. Như vậy hướng tìm trong phương pháp Newton không phải là véctơ - Vf(xk) như trong các phương pháp gradient thông thường mà là hướng - [V2f(xk)] '.V f(xk), gọi là hướng Newton, trong đó đã dùng đến các đạo hàm riêng cấp hai của hàm f(x). Phương pháp này có một số tính chất đáng chú ý sau: ìs. Nếu f là hàm toàn phương thì phương pháp Newton sẽ cho điểm cực tiểu chỉ sau một bước lăp. Thật vậy, giả sử f(x) = a + + 'Á , trong đó c là ma trận đối xứng nửa xác định dương, b e K" và a € K. Khi đó, V f(x ) = Cx + b (Vx) và v 2f(x) = c . Điểm cực tiểu của f(x) là nghiệm của phương trình Vf(x) = Cx + b = 0. Từ đó X* = - c ' b . Bày giờ xuất phát từ điểm bất kỳ xcl và áp dụng phép lặp (7.14) ta có x' = x" - C ' ( C x (l + b) = - c ~ 'b = X*. íằ. CÓ thể chứng minh được rằng nếu f hai lần khả vi liên tục, v 2f liên tục L ip sch itz trong lân cận đ iểm cự c tiểu địa phương X* của f, v 2f(x*) xác định dương và nếu xuất phát từ điểm x°đủ gần X*, thì dãy |x kỊ xây dựng theo phương pháp N ewton thuần túy sẽ hội tụ tới X* với tốc độ hội tụ bậc hai. Cụ thể ta có: ll.\k+l- x * l l < — llxk - x * ll2, m 195
trong đó L là hằng số Lipschitz và m là giá trị riêng nhỏ nhất của V f(x*). Nói chung, nếu f không phải là hàm toàn phương thì dãy điểm {xkỊ xây dựng theo (7.14) có thể phân kỳ hoặc hội tụ đến điểm yên ngựa hay điểm cực tiểu địa phương. • Phương p h áp N ew ton suy rộng Có thể cải tiến phép lặp (7.14) nhờ sử dụng công thức lặp: xk+l = xk - a k[V2f(xk)]"'.V f(xk), (7.15) trong đó độ dài bước a k được xác định nhờ các phương pháp tìm kiếm một chiều theo hướng d k = - [V2f(xk)]” ‘.V f(xk). Quá trình lặp theo công thức (7.15) thuờng được gọi là phương pliáp N ew ton với bước điều chình hay phươiìg pháp New ton suy rộng. Khi sử dụng phương pháp này tốc độ hội tụ của xk —> X* và f(xk) -> f(x*) sẽ nhanh hơn so với khi dùng phương pháp gradient. Khi a k = 1 (với mọi k) thì ta có phương pháp N ew ton thuẩn túy như đã xét ờ trên. Sau đây sẽ trình bày hai dạng phương pháp Newton SUV rộng, khác nhau ờ cách chọn độ dài bước a : Cách thứ nhất, gọi là phương pháp quay lui, bao gồm các bước sau: 1. Đ ặt a =1, tính điểm X = xk + a d k. 2. Tính giá trị hàm f(x) = f(xk + a d k). 3. Kiểm tra bất đẳng thức f(x) - f(xk) < s a < V f (x k). dk>, 0 < e < Vỉ. (7.16) 4. Nếu (7.16) được thòa mãn thì ctk =1 là giá trị cán tìm. Trái lại, giảm a (bằng cách nhân a với số X < 1) cho tới khi bất đẳng thức (7.16) được thỏa mãn. Cách này giống cách chọn a theo (7.2) trong phương pháp gradient. 196
Cách thứ hai, gọi là phương pháp dò tìm chính xác, theo hướng: d k = - [ V 2f ( x k) ] - '.V f ( x k), nghĩa là tìm a k sao cho f(x k - a k[ V 2f(x k) r ' V f ( x k)) = = m in (f(x k - a [ V 2f(xk) r 'V f ( x k) ) : a > 0 | . (7.17) 7.2.2. S ự hội tụ của phươ ng p h á p N ew ton suy rộ n g Theo công thức (7.15) phương pháp Newton chỉ áp dụng được để tìm cực tiểu của hàm số với ma trận đạo hàm cấp hai của nó có nghịch đảo và m a trận [V2f(x)]_l phải bị chặn. Các hàm lồi mạnh, hai lần khả vi liên tục sẽ có các tính chất này. Vì thế, trong mục này ta luôn giả thiết rằng hàm f(x) thỏa mãn các điều kiện sau với m ọi X, y e R": m.llyll2 < < v 2f(x)y, y> < M.llyll2, m > 0. (7.18) Nhớ rằng các hàm như thế luôn có điểm cực tiểu duy nhất, ký hiệu X*. Đ ịnh lý 7.3. N ếu hàm f(x) thỏa mãn điều kiện (7.18) và a k dược chọn theo điều kiện (7.16) thì với bất kỳ điểm ban đầu Xo, dãy |x k) sin h 'ra theo (7 .1 5 ) s ẽ hội tụ tới điểm cực tiểu X* theo tốc độ hội tụ trên tuyến tính: llxN+k - x*ll < CA.nX.n+1 ... XN+k, (7.19) trong đ ó N , C < 00, A.N+k < 1 (Vk > 0) và Â.N+k -> 0 khi k -> 00. C h ứ n g m in h . Phép lặp (7.15) chính là phép lặp (7.13) với F|7' = [V2f(xk) r ‘. Vì m a trận v 2f(xk) có các tính chất đòi hỏi (so sánh (7.12) và (7.18)) nên sự hội tụ của phép lặp (7.15) được suy ra từ các định lý hội tụ của phương pháp gradient. Bây giờ ta chứng m inh tính đúng đắn của đánh giá (7.19). Muốn thế, trước hết chú ý rằng do dk = - [V2f ( \ k)]_1Vf(xk) hay Vf(xk) = - v 2f(xk)dk nên 197
< V f(x k), dk> = - < v 2f(xk)dk, dk> < - mlldkll2. (7.20) Do < 0 và -> 0 nên từ (7.20) suy ra lldkll - » 0 khi k -> + 00. Bây giờ la sẽ chỉ ra rằng từ một bưốe lặp nào đó trờ đi trong công thức lặp (7.15) ta luôn có a k = 1. Thật vậy, sử dụng công thức Taylor và (7.20) ta thu được f(xk+l) - f ( x k) = = a t
với x k = X* + 0 ( x k - X*), 0 6 [0, 1] (Chú ý V f(x * ) = o do X* là cực tiểu). Do đó Ilxk+' - x*ll2 = = < [ V 2f(x k) r ' . [ V 2f(x k) - v 2f( x k )].(x k - X *), x k+l - x * > < — IIv 2f(x k) - v 2f( x k )ll.llxk - x*ll.llxk+1 - X*II. m Từ đó llxk+l - x*ll < A.k.llxk - x*ll, (7.21) trong đó = — IIV2f(xk) - v 2f ( x k )ll. Do IIV2f(xk) - v 2f( x k )ll -> 0 m nên tồn tại số N sao cho với N + k, k = 0, 1 ,... ta có X.N+k < 1 và Ằ.N+k -» 0 khi k - » 00. Đặt c = llxN - x*ll, từ các nhận xét trên ta suy ra đánh giá (7.19). Bây giờ giả sử ngoài điều kiện (7.18), ma trận v 2f(x) còn thỏa mãn thêm điều kiện Lipschitz: IIv2f(x) - v 2f(y)ll < L.llx - yll, Vx, y e 0Tử (7.22) Với trường hợp này, trong hệ thức (7.21) ta có X. = — ||V2f(xk) - v 2f ( x k )ll < — llxk - x*ll m m và vì thế ta có đánh giá tốc độ hội tụ: llxk + l - x * l l < — llxk - x * l l 2. ( 7 .2 3 ) m Kết quả, ta có định lý: Đ ịnh lý 7.4. N ếu lĩàm f(x) thỏa mãn các điều kiện (7.18), (7.22) và a k được chọn theo điều kiện (7.16) thì với bất kỳ điểm ban đầu Xo, dãy | x k) sinh ra theo (7 .1 5 ) s ẽ hội tụ tới nghiệm X* với tốc độ liội tụ bậc hai, tức là có đánh giá (7.23). 199
• Nếu chọn độ dài bước nhờ phương pháp tìm chính xác theo tia, tức là theo (7.17), thì sự hội tụ của dãy {xk} được suy ra từ sụ hội tụ của phương pháp gradient. Trong trường hợp này, cũng như trước đây, tốc độ hội tụ là trên tuyến tính nếu f(x) thỏa mãn điều kiện (7.18) và là bậc hai nếu có thêm điều kiện (7.22). 7.2.3. C ải biên phương p h áp N ew ton suy rộn g • Xét thuật toán xây dựng dãy điểm xấp xỉ xk theo công thức: xk+1 = xk - a k[V2f(x°)]_l.Vf(xk) với a k > 0, k = 0, 1 , ( 7 . 2 4 ) Trong phương pháp này dk = - [V2f(x°)] '.V f(xk), nghĩa là để làm hướng giảm ờ mỗi bước ta sử dụng cùng một ma trận [V2f(x°)]_l. Công thức lặp (7.24) là một trường hợp riêng của phép lặp (7.13) với F^' = [V2f ( x ° X f B ở i vậy có thể khẳng định rằng dãy (7.24) với bất kỳ điểm ban đầu x° nào, sẽ hội tụ tới nghiệm cực tiểu theo tốc độ hội tụ cấp số nhân nếu chọn độ dài bước theo điều kiện (7.16) hoặc (7.17). Tuy nhiên, tỉ số q (tốc độ hội tụ) sẽ phụ thuộc vào điểm xấp xỉ ban đẩu x°: q càng nhỏ khi x" càng gần điểm cực tiểu X*. • M ột dạng cải biên khác của phương pháp N ewton suy rộng: Chỉ số bước lặp k = T|t + i với r| = 0, 1, , i = 0, 1, .... t -1 và t > 1 là một số nguyên tùy ý. Ta xây dựng quá trình lặp: + = xnề+ i _ a n, + 1[ v 2f((x ni)]“‘.V fix '" + '), 0, hay với các chỉ số bước lặp theo k: xk+l = xk - a k[V2f(xni)]"1.Vf(xk), a k > 0. (7.25) Theo phương pháp này cứ sau t phép lặp ta lại thay đổi ma trận nghịch đảo. Nó là trung gian giữa thuật toán xây dựng hướng dịch chuyển dk theo ma trận mới [V2f(xk)]_l và thuật toán cải biên luôn sử dụng cùng một m a trận [V2f (x ° ) ] '\ Thuật toán này cũng có thể xem như một dạng của phương pháp gradient thực hiện theo công 200
thức lặp (7.13), do đó sự hội tụ của nó với các cách chọn độ dài bước khác nhau được suy ra từ sự hội tụ của các phương pháp gradient tương ứng. Người ta chứng minh được rằng với các giả thiết tương tự như trong Định lý 7.4 thì dãy (xn' | xây dựng theo công thức lặp (7.25) hội tụ tới nghiệm cực tiểu vói tốc độ bậc t + 1. Cụ thể, ta có đánh giá: llxcn + ã)l - x*ll < c .llx n' - x *lll + 7.3. PHƯƠNG PHÁP TỰA NEWTON 7.3.1. Nội d u n g phưưng p h áp Trong phương pháp Newton, ở mỗi bước ta cần tính m a trận nghịch đảo [V2f(xk)]_l. Đó là một công việc khó khăn, vì thế phương pháp N ew ton ít được sử dụng trong thực tiễn khi n > 1, mặc dầu phương pháp có tốc độ hội tụ bậc hai. Phương pháp tựa N ew ton (Quasi-Newton M ethod) sử dụng hiệu các gradient để xấp xỉ [V2f(xk)]_l. Theo phương pháp này quá trình lặp có dạng: x k+l = xk - ẦkH kV f(x k), trong đó Hk là xấp xỉ của [V 2f(x k) r ' và ta nhận được phương pháp với số bước lặp nhiều hơn, nhưng mỗi bước lặp ít phức tạp hơn và tốc độ hội tụ cũng chậm hơn: nói chung không còn là bậc hai nữa. Một phương pháp tiêu biểu thuộc loại này và bảo đảm được tốc độ hội tụ trên tuyến tính là pliươiìg pliáp m etric biến thiên do Davidon - Fletcher - Powell để xuất năm 1963. 7.3.2. P hư ư n g p h á p D avidon - F letc h er - Powell Phương pháp này sử dụng phép lặp (7.15), nhưng ở mỗi bước ma trận nghịch đảo [ V 2f(x k) r ' được thay bằng m a trận đối xứng xác định dương Hk. Hk+| tính truy hồi theo H k, Vf(xk), V f(xk+I). Khi 201
f(x) là hàm lồi toàn phương thì ở bước lạp n + 1 m a trận Hnt| sẽ Irờ thành ma trận Hessian nghịch đảo. Hinh 7.3. Sơ dố khôi phương pháp Davidon - Fletcher - Powell Xuất phát từ điểm X1 được chọn tùy ý, ma trận ban đẩu Hị là ma trận đơn vị In hoặc có thể là ma trận đối xứng xác định dương bất kỳ. Đặt k = 1. Thủ tục lặp gồm các bước sau đây (đê cho gọn, la viết gk thay cho V f(xk)): 1. ơ bước k = 1. 2 ... ta có xk và m a trận đối xứng xác định dương Hk. 2. Để làm hướng tìm ta chọn d k = - Hkgk. 3. Tim À.k đạt cực tiểu của hàm 0. 202