Tài liệu Khoá luận tốt nghiệp toán Phương pháp gradient và phương pháp Newton

TRƯỜNG ĐẠI HỌC s ư PH Ạ M HÀ NỘI 2 KHOA TOÁN ------0O0--------------------- K HÓA L U Ậ N TỐT N G H IỆ P Phương pháp Gradient và phương pháp N ew ton Chuyên ngành: T O Á N G IẢ I T ÍC H Giảng viên hướng dẫn: Sinh viên: Lớp: Phùng Đức Thắng Vũ T h ị Y ến K 37-sp Toán H À N Ộ I, 5 /2 0 1 5 LỜI C ẢM ƠN Bài khóa luận này được hoàn thành dưới sự hướng dẫn nhiệt tình của thầy giáo T h . s P h ù n g Đ ứ c T h ắ n g . Qua đây em xin gửi lời cảm ơn sâu sắc tới các thầy cô trong tổ Toán giải tích và các thầy cô trong khoa Toán trường ĐHSP H à N ộ i 2 đã giúp đỡ em trong quá trình học tập để thuận lợi cho việc nghiên cứu. Đặc biệt, em xin gửi lời cảm ơn chân thành tới thầy giáo T h . s P h ù n g Đ ứ c T h ắ n g người đã dành cho em sự hướng dẫn nhiệt tình, chu đáo và chỉ bảo cho em trong suốt quá trình học tập nghiên cứu và thực hiện khóa luận. Dù đã hết sức cố gắng, nhưng do đây là lần đầu tiên làm quen với việc nglỉiên cứu khoa học và do năng lực còn hạn chế nên khó tránh kliỏi những sai sót. Em mong muốn nliận được sự chỉ bảo, đóng góp của quí thầy cô để cho bài klióa luận được tốt hơn. Em xin chân thành cảm ơn! Hà Nội, tháng 05 năm 2015 Sinh viên Vũ T h ị Yến LỜI C AM Đ O A N Sau một thời gian nghiên cứu với sự cố gắng, nỗ lực của bản thân cùng sự hướng dẫn nhiệt tình chỉ bảo của thầy giáo T h . s P h ù n g Đ ứ c T h ắ n g em đã hoàn thành bài khóa luận của mình. Em xin cam đoan bài khóa luận là do bản thân nghiên cứu cùng với sự hướng dẫn của thầy giáo T h . s P h ù n g Đ ứ c T h ắ n g không hề trùng với bất cứ đề tài nào. Hà Nội, tháng 05 năm 2015 Sinh viên Vũ T h ị Yến M ục lục Lòi cảm ớn 1 Lời cam đoan 2 Lời 4 1 1TLỞ đầu M ộ t số kiến th ứ c cần nhớ 1.1 Đạo hàm của hàm vô hướng 1.1.1 Định nghĩa 1.1.2 Một số loại vi phân thường găp: 1.2 Đao hàm của hàm vect.o: 1.3 Đao hàm bâc 2 1.4 Các hàm số lồi 1.5 Cấc diều kiện về cực trị 1.5.1 Diều kiện cần bậc nhất 1.5.2 Diều kiện đủ bậc nhất 1.5.3 Diều kiện cần bậc hai 1.5.4 Điều kiện đủ bậc hai 5 5 5 6 8 9 10 12 12 13 13 14 2 P h ư ơ n g p háp G rad ien t 2.1 Nôi dung của phương pháp 2.2 Tính hội tụ 15 15 16 3 P h ư ơ n g p háp N e w t o n 3.1 Nôi dung của phương pháp 3.2 Tính hôi tu 3.3 Phương pháp Newton trong việc giải các phương trình 22 22 23 25 Tài liệu th a m khảo 28 3 LỜI MỞ Đ Ầ U Bài toán tối ưu có ứng dụng rộng 1’ãi trong toán học cũng như trong đời sống. Nó được nghiên cứu một cácli toàn diện nhờ các phương pliáp định tính và địnli lượng như phương pháp miền tin cậy, phương pliáp nhân tử Lagrange,... Trong đó phương pháp Gradient và phương pháp Newton là những phương pháp số đầu tiên để giải bài toán tối ưu. Khóa luận này trình bày một số hiểu biết về hai phương pháp này. Cuốn chuyên khảo [I] của tác giả B. T. Polyak là một cẩm nang khá đầy đủ và chi tiết về lý thuyết phương pháp Gradient và phương pháp Newton. Khi nghiên cứu về hai phương pháp này em quan tâm đến tính hội tụ của hàm khả vi và ứng dụng của chúng trong việc giải toán. N ộ i d u n g chính của khóa luận g ồm 3 chương: • 1. Một vài kiến thức cần nhớ • 2. Phương pliáp Gradient • 3. Phương pliáp Newton Do thời gian thực hiện đề tài không nhiều, kiến thức còn hạn chế nên báo cáo không tránh khỏi những sai sót. Em mong nhận được sự góp ý và những ý kiến phản biện của quý thầy cô và bạn đọc. Em xin chân thành cảm ơn! Chương 1 M ột số kiến thức cần nhớ 1.1 1.1.1 Đ ạo hàm của hàm vô hướng Đ ị n h n g h ĩa Đ ịn h n gh ĩa 1.1.1. Hàm vô hướng f ( x ) của đối số X trong không gian n chiều. / : Mn —>■ M1 được gọi là khả vi tại điểm X nếu tìm được a € : Vĩ/ E ( 1 . 1) f ( x + y) = f ( x ) + (a, y) + o(y) trong đó a được gọi là đạo hàm của f ( x ) tại X. Kí hiệu: f ' ( x) hoặc Ị ( x + y) = f ( x ) + ( V f ( x ) , y ) + o(y) trong đó (x) v/(x) = f d fdx,\ ' ( 1.2 ) df(x)\ ’ dxn ì Nói cách khác hàm số khả vi tại điểm X nếu nó xác định xấp xỉ với hàm tuyến tính bậc nhất tại X. Có nghĩa là có thể tìm ra hàm số momen tuyến tính f ( y ) = f ( x ) + ( V / 0 ) , y) là f ( x + y ) - f ( y ) = o{y). V í dụ 1. Cho hàm toàn phương f { x ) = { A x ĩ x ) / 2 - (b, x) trong đó A là ma trận đối xứng n X n, b € Khi đó f ( x + y) = ( A( x + y ) ĩ x + y ) / 2 - (6, (x + Ij)) 5 Khóa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng = ( A t , . t ) / 2 - (b, x) + ( Ax - b, y) + ( A y ì y ) / 2 = f ( x ) + ( Ax - b , y ) + (A y ,y ) / 2. Mà I(i4ĩ/,ỉ/)| < ||Ẩ||||?/||2. Do đó ( A y ì y ) / 2 = o(y). Vậy / ( # ) khả vi tại bất kì điểm X nào và v / ( x ) = Ax — b. (1.3) Hàm /( . t ) được gọi là khả vi trên tập Q c R n nếu nó khả vi tại mọi điểm trên Q. Nếu f ( x ) khả vi trên toàn bộ Mn thì nó được gọi là vi pliân đơn giản. Giả sử f ( x ) khả vi trên [x, X + y] ( tức là tại các điểm X + T7/, 0 < T < 1 ).Cliúng ta xét hàm một biến Ộ( t ) = f ( x + Ty) vàtính đạo hàm trong 0 < r < 1 : ộ {t + A x ) - ộ (t ) _ f (x + ( r + A r ) y) - f ( x + Ty) AT AT = (V/(-T + Ty), A Ty) + o ( Ar y ) Ar ______ _ 1.-™ ^ t + At) - ^ ( t) ệ ( t) = l i m ăT^ 0-----------T- ----------- = ( V / ( x + T i j ) , y ) . Aĩ Do đó 0 ( r ) là vi phân trên [0,1] và Ộ'(T) = ( V f ( x + r y ) , y ) . (1.4) ỉ ( x + e y ) - f ( x) ft't(x\y) =_ lI-™ i me^ 0+------------—------------ r, c, (1.5) Giá trị £ được gọi là đạo hàm theo hướng của f ( x ) tại X theo hướng y. Đạo hàm theo hướng có thể tồn tại với các hàm số không trơn. V í d ụ 2. Hàm f ( x ) = ||x|| có 1.1.2 = ||ĩ/||. M ộ t số loại vi p h â n th ư ờ n g gặp: • V i phân G â te a u x Nếu / có đạo hàm theo mọi hướng y tại X thì ta nói f ( x ) có đạo hàm Gâuteaux tại điểm X. Vũ Thị Yến 6 K 3 7 C - S P T D H S P Hà Nội 2 Khóa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng C hú ý:Hàm sô có tập nghiệm riêng , J (x\eị) ỡf(x) = —^ — (ẽị là tọa độ (_/ X 2 các vecto cơ sở), a I df ỞX ị ’ df ’ dxr Hàm này tuân theo công thức (1.4) là nếu f ( x ) khả vi tại X thì đó cũng là đạo hàm vi pliân Gâut.eaux với f ( x ; y ) = ậ'(0) = ( V f ( x ) , y ) . (1.6) Điều ngược lại là không đúng V í d ụ 3. Cho / : R" -»• R 1, n > 2 I / ( x ) = r 1 " nếu IIX — ail = Il a II , x ^ 0 " 11 11 ’ (1.7) trong đó a € Mn, a ^ 0. Hàm số này có vi phân theo mọi hướng tại 0 và f'{0', y) = 0,Vy. Do đó nó có đạo hàm Gâuteaux tại 0. Nhưng nó không khả vi (thậm chí không liên tục) tại 0. • V i p h ân Frechet: Nếu hàm f ( x ) có vi pliân trên công thức Newton- Leibniz có [.T ,.T + y] . Khi đó sử dụng (1.4) và ệ{ l ) = 0(0) + / ệ' ( r) dT Jo Chúng ta có được biểu thức cho phần dư trong định lý tích phân: I f ( x + y) = f ( x ) + '1 = f ( x ) + ( V / ( x ) , Ij) + / 0 ( V / (x + Ty), y) CỈT (v/o + Tij) - (1.8) v/(x), y) dr. Một kết quả có ích khác (định lý giá trị trung bình) tuân theo công thức số gia hữu hạn ộ( l ) — Ộ(Q) + ộ f( 0 ) ) 0 < 0 < 1 và từ (1.4) f ( x + y) = / 0 ) + ( V / 0 + Qy ) , y ) ) , 0 < 0 < 1. Vũ Thị Yến 7 (1.9) K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng 1.2 Đ ạo hàm của hàm vecto: Đ ịn h n gh ĩa 1.2.1. Cho hàm g : R n —>■R m được gọi là đạo hàm tại X nếu tìm được ma trận A cấp m X n sao cho với Vy G Mn : g( x + y) = g(x) + A y + o{y). (1.10) Ma trận A được gọi là đạo hàm hoặc ma trận Jacobian của ánlỉ xạ g(x) và giống nhau trong trường hợp vô hướng. Kí hiệu: g' (x) hoặc Vg ( x ) Do đó g( x + y) = g( x) + g ' { x ) y + o(y) (1.11) CÓ nghĩa là đạo hàm của hàm số xác định tại X là xấp xỉ tuyến tính bậc nhất. Với hàm vecto có đạo hàm g( x) = (gi ( x ) , g m (#)) có những phần tử trong ma trận Jacobian được định nghĩa bởi công thức dỹi {x) 9'{x)a = dXi Cho g : R n —>• Mm có đạo hàm tại X và h : R m —> M6’ có đạo hàm tại g(x). Khi đó quy tắc cho đạo hàm vi phân với hàm số phức hợp (hay quy tắc chuỗi) có hiệu lực [h(g(x))ì = h' ( g( x ) ) g ' ( x ) (1.12) Định lý giá trị trung bìnlỉ không thỏa mãn các hàm số vecto. Có nghĩa là Ệ6, 0 < 6 < 1 để g( x + v) = g 0 ) + g' (x + 0y) y Cho hàm g : Mn —¥ ( m > l).G iả sử g(x) khả vi trên [x, x + y] thì g ( x + ij) = g ( x ) + g' ( x + Ti j )ydT (1.13) •'0 = 9( z) + 9'{x)y + / Nếu \\g'(x + Ty) II (g'(x + Ty) - g'(x)) IJCỈT < I/, 0 < T < 1 thì \\g(x + y) - g{:r)|| < L\\y\\ Vũ Thị Yến 8 (1.14) K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng ngược lại nếu g' (x) thỏa mãn điều kiện Lipschitz trên [x, x + y]: llö'O) - p'(w)|| < L\\u - I’ll, M, V € [ x , x + y} thì ị\g(x + y) - g( x) - g'(x)y\\ < (1-15) Trong trường liỢp vô hướng, hàm số g : Mn —>• R n có đạo hàm tại mọi điểm trên R n được gọi là đạo hàm vi phân. 1.3 Đ ạo hàm bậc 2 Đ ị n h n g h ĩ a 1.3.1. Hàm vô hướng / ( x ) t r ê n R ” được gọi là khả vi 2 lần tại X nếu nó khả vi tại X và tồn tại ma trận H đối xứng cấp n x n: My G Kn, f { x + y) = ỉ ( x ) + ( V f ( x ) , y) + ( H y , y) / 2 + o (\\y\\2) (1.16) Ma trận H được gọi là ma trận của đạo hàm bậc 2 (hay ma trận Hessian). Kí hiệu: f " ( x ) hoặc v 2/ ( x ) . Ta cũng có the định nghĩa theo cácli khác: Một hàm số có khả vi 2 lần tạ i điểm X nếu xác đ ịn h được m ộ t h à m x ấ p xỉ b ậc 2 tạ i lân cận diem X. Có nghĩa là tồn tại hàm bậc 2 ĩ ( y) = / M + (V / (x ), y) + ( v 2/(x)ỉ/, y) / 2 để If ( x + y) - f ( y ) \ = o(||ỉ/||2) . Xét hàm vô hướng ộ( r ) = f ( x + Ty) Ta thấy / có vi phân 2 lần trên [x, X + y] và = ( V 2/ ( * + r y ) y , y ) . (1.17) Từ công thức Taylor với các hàm số hữu tỷ ộ(l) = ộ ( 0) + ặ ( 0) + í I ộ"{r)(ỈTdị •'0 -^0 Vũ Thị Yến 9 K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng t a CÓ f { x + y) = f ( x ) + Ợ7 f ( x ) , y ) + / / ( v 2/ ( x + Ty)y, y) dr dt ( 1.18) Đặc biệt nếu IIV2/ ( x + T y ) II < L ,0 < r < 1 ta có \.f(x + y ) ~ f ( x ) - ( V / ( x ) , y) I < llỉ/ll2 (1.19) ngược lại nếu IIv2/(.x + Ty) - v 2/(.x)II < Lrịịyịị thì l/(z + y ) ~ / M - (V/(a:), y) - Q ) ( v 2/(x)ỉ/, ỉ/) I < ||ỉ/||3. ( 1.20 ) Sử dụng công thức Taylor với hàm các số dư trong dạng Lagrange 0(1) = ự)(0) + "(0)/2, 0 < 0 < 1 ta tìm được 0 , 0 < 0 < 1 để f ị x + y) = f ị x ) + ( V f ( x ) , y ) + ( V 2/ ( ® + Qy) y, y) / 2 . 1.4 Các hàm số lồi Đ ịn h ngh ĩa 1.4.1. f ( x ) là hàm vô hướng trên Mn được gọi là lồi nếu / (Ảx + (1 - A )y) < X f ( x ) + (1 - A ) f ( y ) , ' i x , y e K ” ,0 < A < 1. ( 1.21) BỔ đ ề 1.4.2. ( B ấ t đ ẳ n g t h ứ c J e n s e n ) (ỊH LEMMA l,p.8]) Cho f ( x ) là hàm lồi trên M” . Khi đó Vx1,...,# * G Mn,Aj > 0, %— 1,... ?k 5 tci co I / (ÀiX1 + ... + ẰkXh) < Ằ ị f ( x i ) + ... + X k f { x h). Vũ Thị Yến 10 (1-22) K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng Hàm f ( x ) mà —f ( x ) lồi được gọi là hàm lõm. Rõ ràng, hàm affine f ( x ) = ( a, x) + ß vừa là hàm số lồi vừa là hàm lõm. Các trường hỢp đặc b iệt của hàm số lồi: H à m lồi n g ặ t : Hàm f ( x ) trên R n được gọi là lồi ngặt nếu Vx Ỷ y, 0 < A < 1 : / (Xx + (1 - A )y) < A f ( x ) + (1 - A )f( y) . H à m lồi m ạ n h : Hàm f ( x ) trên t > 0 nếu với mọi 0 < À < 1 ta có (1.23) được gọi là lồi mạnh với hệ số / (Xx + (1 - X)y) < X f ( x ) + (1 - A ) f ( y) - n ( l - A)||x - y\\2/ 2 . (1.24) C h ú ý: Hàm lồi mạnli là lồi ngặt. B ổ đ ề 1.4.3. (ỊU LEMMA 2,p.9]) Cho ĩỊj(t) là hàm khả vi trên M1. Khi đó bề lồi của ĩp(r) tương đương với sự đơn điệu của đạo hàm (ĩp' (Tị) > '0/( r 2)) cho Tị > r 2, lồi n g ặ t cho đơn điệu n g ặ t (ĩp' (Ti) > ĩp1^ ) ) cho Tị > r 2 và lồi m ạ n h cho đơn điệu m ạ n h ( ĩ p ' ( r i ) — ^ /( t 2) > Í ( t \ — r 2), Tị > r 2) . B ổ đ ề 1.4.4. (ỊH LEMMA 3,p.9]) Cho f ( x ) khả vi trên E n.Vx,?/ G Mn f ( x ) lồi tương đương với bất đẳng thức: f ( x + y) > Ị ( x ) + ( Ụ f ( x ) , y ) , (1.25) f ( x ) lồi ngặt tương đương với bất đẳng thức: f { x + y ) > f ( x ) + (V /(x ), y ) , y Ỷ 0 (1.26) f ( x ) lồi mạnh tương đương với bất đẳng thức: f ( x + y ) > f ( x ) + ( V / ( x ) , y) + i\\y\\2/ 2 . (1.27) C h ú ý: 1) Đồ thị của hàm lồi ngặt nằm trên siêu pliẳng tiếp xúc, đò th ị củ a h à m lồi m ạ n h n ằ m tr ê n m ộ t số đư ờng p a ra b o l. Sự su y rộng điều kiện đơn điệu tro n g trư ờng hỢp nh iều chiều: Vũ Thị Yến 11 K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng Với hàm lồi ( V / O ) - v/(ị/), X - y) > ũ. (1.28) Với hàm lồi ngặt thì điều kiện đơn điệu ngặt ( V / ( x ) - V f ( y ) , x - y) > 0, x ^ y . (1.29) Với hàm lồi mạnh thì điều kiện đơn điệu mạnli ( V / ( x ) - V f { y ) , x - y) > e\\x - ỉ/ll2. (1.30) 2)Tiêu chuẩn cho lồi là đơn giản nhất cho các hàm số khả vi hai lần f ( x ) . Lồi tương đương với điều kiện v 2/ (z ) > 0. (1.31) lồi m ạ n h tư ơ n g đư ơng với điều kiện v 2/(x) > a y x . (1.32) lồi ngặt tương đương với điều kiện v 2f ( x ) > 0. (1.33) Cho X* là điểm cực tiểu của vi phân trên hàm lồi mạnh f ( x ) (với hệ số í). Tồn tại duy nhất một điểm và v/(x*) = 0. Do đó từ các bất đẳng thức (1.27),(1.30) ta có các kết luận: / O ) > f {x* + £\\x - .t*||2/ 2 . (1.34) (’V f ( x ) , x — X*) > í\\x — x*\\2. (1.35) ||V / ( x ) || > t\\x - x*||. (1.36) 1.5 Các điều kiện về cực trị 1.5.1 Đ i ề u k iện cầ n b ậ c n h ấ t Đ ịn h n gh ĩa 1.5.1. Điểm .T* được gọi là cực tiểu địa phương của f ( x ) tr ê n R n nếu 3 e > 0 : f ( x ) > /(.T*),V.T là lân cận củ a X*. Có nghĩa là \\x — x*|| < £. Trong trường hợp này X* còn được gọi là điểm cưc tiểu. Vũ Thị Yến 12 K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng Đ ịn h lí 1.5.2. ( F e r m a t : ) ([U THEREM 1,p. 11]) Cho X* là điểm cực tiểu của f ( x ) trên Mn,/(a ;) khả vi tại X* thì V/(:E*) = 0. (1.37) Chứng minh. Giả sử V f ( x*) ^ 0. Ta có / (z* - r V / ( i * ) ) = f {x*) - r | | V / ( i * ) | | 2 + o ( t V / ( i * ) ) = f { x ' ) — T ( || V / ( . T *)||2 + r - 1o ( r ) ) < / ( x * ) (với r > ũ đủ nhỏ). ( Trái với giả thiết .T* là điểm cực tiểu ) Vậy V f ( x * ) = 0. □ 1 .5.2 Đ iề u k iện đ ủ b ậ c n h ấ t Đ ịn h lí 1.5.3. (ỊH THEREM 2,p. 12]) Cho f ( x ) là h à m lồi khả vi tại X*, Ụ f ( x*) = 0. Thì X* gọi là điểm cực tiểu toàn cục của f ( x ) trên Chứng minh. Chứng minh này trực tiếp tuân theo từ công thức (1.25) của phần 1.3 VI / 0 ) > f {x*) + ( V / ( x * ) ,x - X*) = ỉ ( x * ) , \ / x e M' □ 1 .5.3 Đ i ề u k iện cầ n b ậ c hai Đ ịn h lí 1.5.4. (ỊU THEREM 3,p. 13]) Cho X* là điểm cực tiểu của f ( x ) trên Mn, / ( x ) khả vi hai lần tại X* thì Chứng minh. Từ định lý cò: v2/(z*) > 0. (1.38) 1.5.2 v/(x*) = 0, do đó My và T đủ nhỏ ta /(•?*) < f ( x * + Ty) = f ( x " ) + r 2 ( V 2/(.T*)ĩ/, y) / 2 + o ( r 2), Vũ Thị Yến 13 K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng { v 2f ( x*) y, ĩ j ) > o( t 2) / t 2. K h i T —> 0 t a có ( v 2f ( x * ) y , y ) > 0. Vì y tù y ý nên v 2/(x*) > 0. □ 1 .5 .4 Đ i ề u k iện đ ủ b ậ c hai Đ ị n h lí 1.5.5. (ỊH THEREM 4,p. 13]) Cho f *( x ) khả vi hai lần tại .T*,cho điều kiện cần b ậc nhất. ( V / ( ; X*) = 0) và V 2/(-T*) > 0. (1.39) t a có X* là điểm cực tiểu. Chứng minh. Cho y là vecto đơn vị. Ta có: f(x" + Ty) = f(x") + T2 ( v 2/(®*)ỉ/, y) / 2 + o ( t 2||ỉ/||2) > ỉ(x') + ~ TY + °(r2) trong đó í > 0 là giá trị riêng nhỏ nhất của V 2f ( x*) và hàm số o ( r 2) không phụ thuôc vào y. £ Do đó 3 t q : 0 < r < Tq ta có —- > o ( r 2) hay f ( x* + Ty) > f ( x*) . □ C hú ý: Nếu điều kiện cần bậc nhất và bậc hai thỏa mãn tại X* ( v / ( X*) = 0, v 2/(x*) > o) nhưng điều kiện đủ bậc hai không thỏa m ã n (m a t r ậ n v 2/( :r* ) kh ô n g xác đ ịn h dương) th ì X* kh ô n g là điềm cực tiểu. Vũ Thị Yến 14 K 3 7 C - S P T D H S P Hà Nội 2 Chương 2 Phương pháp Gradient 2.1 N ội dung của phương pháp Giả sử tại điểm X bất kì có thể tính được đạo hàm của hàm số V f ( x ) . Trong trường hợp này cách đơn giản nhất để tính cực tiểu của hàm số f ( x ) là phương pháp Gradient bằng cách bắt đầu từ xấp xỉ gần đúng Xq để tạo thành chuỗi lặp x*+ 1= i * - 7 tv / ( x *)1 trong đó (2.1) > 0 là độ dài bước nhảy. Đầu tiên, xem lại việc chứng minh các điều kiện cần với cực trị (Địnlỉ lý 1.5.2 phần 1.5), nếu điều kiện cực trị không thỏa mãn tại x ( V f ( x ) ^ 0) th ì giá tr ị củ a h à m số có th ể bị giảm tới X — r V f ( x ) với r > 0 đ ủ nhỏ. Thứ hai, tại điểm x k hàm khả vi f ( x ) được xấp xỉ với hàm tuyến tính f k( x) = f ( x k + ( v f ( x k) , x — x k) với độ sai khác o(x — x k) . Do đó có the tìm cực tiểu xấp xỉ c ủ a hàm f k ( x ) tạ i lân cận c ủ a Xỵ. C h ẳ n g h ạ n n h ư t a đi xác đ ịn h Eỵ và giải bài to á n bổ trợ: m i n \\z-xk\\ f* > -o o , và 7 thỏa mãn điều kiện: 0< 7 < (2.7) L Thì trong phương pháp (2.4) đạo hàm tiến tới 0, tức là li v ik^ x V ỉ ( xk) = 0 và h à m f ( x ) đơn điệu giảm: f ( x k+i) < f ( x k). Chứng minh. Trong công th ứ c (1.8) phần th ế X = x h, y = và sử dụng (2.5): f ( x k+1) = V / ( x *)||2- 7 f 0' ( V / ( xk - T7 V f ( x k)) < f ( x k) - 7 ||V /( X * ) ||2 + L 7 2| | V / ( x * ) | | 2 I ' 1 r d r Jo = /(* * )- 7(1 - ^ ) l | v / ( ^ ) | | 2. Tổng các bất đẳng tliức f ( x k+1) < f ( x k) - a\ \ Vf ( x k) r , a = 7 ( l Vũ Thị Yến 16 . ( 2 .8 ) K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng với k = 0,...,s ta có Khi a > 0, theo (2.7) ta có: EĩLo IIW(^)II2 < ữ 1 ư ( x°) - ỉ ( xS+ỉ)) < a 1 ( / 0 ° ) - ỉ *) >Vs. có nghĩa là ||V /(.Tfc)||2 < (X) tức là | | V / ( x fc)|| —>• 0. Ta có điều pliải chứng minh. □ ơ đây, các điều kiện của định lý là rất cần thiết. Các vi phạm điều kiện 2J3 có thể có hai phần: 1) Hàm /(;x) có thể không trơn tại một số điểm. V í dụ 4. Cho f ( x ) = ||a;||1+a,0 < a < 1 f ( x ) khả vi nhưng không có đạo hàm thỏa mãn điều kiện Lipschitz vi = ( a + l)||.T ||a 1 —> oo khi ||x|| —> 0. ||x — 0 II Trong trường hợp này ta có 7 ||V f ( x k)\\ > IIa;* — x*\\ = ||xfc|| với ||.Tfc|| đ ủ nhỏ. Có nghĩa là độ dài bước nhảy trong công tliức (2.4) nhỏ và /(;x) không đơn điệu giảm. 2) Bất đẳng thức (2.5) không phụ thuộc vào các hàm số lớn hơn hàm số bậc hai. V í dụ 5. Cho f ( x ) = ||x||2+a, a > 0 Ta có: \x Với V7 > 0, 3x° đề công thức (2.4) khi áp dụng cho hàm số ||a:||2+ữ, (q > 0) với xấp xỉ ban đầu x° sẽ phân kì vì \x•'c+1|| > ||a:*||,A: = 0 ,1 ,... B ổ đ ề 2.2.2. (ỊH LEM MA l,p.23]) Cho f ( x ) khả vi, V /( ;x) thỏa mãn điều kiện Lipscliitz với hệ số L và /(;x) > /*,V.T thì l|V /(a:)||2 < 2 L ( f ( x ) - / * ) . Vũ Thị Yến 17 (2.9) K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng Chứng minh. f* < f (x — L l v f ( x ) ) < f ( x ) — (2 L) 1IIV f ( x ) ||2. □ B ổ đ ề 2.2.3. (ỊH LEMMA 2,p.24]) Cho f ( x ) là hàm lồi, khả vi và thỏa mãn điều kiện Lipschitz với hệ số L thì v/(x) (V /(x ) - v/(y),s - y) > L - ' W V t t x ) - v/(y)II2. ( 2 . 10 ) Chứng minh. Clỉứng minh công thức (2.10) với các hàm số khả vi hai lần. Từ (1.13) phần 1.1 ta có v/(y) = v/(x)+ / V f ( x + r ( y - x)) ( y - x ) d T = V f ( x ) + A { i j - x ), trong đó ma trận A= Ị V / (x + r ( y — x)) dr 0 là đối xứng và không âm xác định bởi công thức (1.31) của phần 1.4 có nghĩa là A > 0. Mà ||i4|| < L khi IIv2/ ( x ) || < L,Wx. Do đó ( V / ( x ) - V f ( y ) , x - y) = ( A( x - y ) , x - y) > WAW-' WAix - y)\\2 > L ^ I I V / C t ) - v / ( i / ) | | 2. □ B ổ đ ề 2.2.4. (ỊH LEMMA 3,p.24]) Cho f ( x ) là hàm lồi mạnh khả vi ( với hệ số £) và X* là điểm cực tiểu thì ||v /(x )||2 > 2ĩ (f (x) — f ( x *) ) . Đ ị n h lí 2.2.5. (ỊH TH EO REM 2,p.24]) Cho f ( x ) khả vi trên ]Rn có đạo hàm thỏa mãn điều kiện Lipschitz với hệ số L và f ( x ) là hàm lồi 2 n i , mạnli với liệ số L Cho 0 < 7 < — phương pháp (2.4) hội tụ tới điếm Lj cực tiểu toàn cục X* ___ duy nhất, với sự suy biến của cấp số nhân \\xk - x , \ \ < c q k, ữ < q < l . Vũ Thị Yến 18 (2.11) K 3 7 C - S P T D H S P Hà Nội 2 Khỏa luận tốt nghiệp GVHD: Th.s Phùng Đức Thắng Chứng minh. Các điều kiện của định lý 1.5.2 đều được thỏa mãn. / ( * t+1) < / ( . * * ) - 7 ( l - ậ ) l|V/(.T*)||2. Sử dụng bổ đề 2.2.4 f ( x k+1) < f ị x k) - ^7(2 - L 7 ) { f ( x h) - f ( x " ) ) hay - £ 7 )) i f ( x k) - f ( x*) ) /( ■ ^ +1) - /(-T*) < (1 - = 91 ( / ( * * ) - / ( * • ) ) / ( z * ) - /( z * ) < 0, \/x Khi 0 < 7 < (2 .12) L x k — £*11 < ||x° — x*\\qk, q = m a x {|1 — 7 -ể|, |1 — j L \ } < 1- (2.13) thì (L -t) (2.14) L +i với 7 = 7 * = L + e' Chứng minh. Từ công thức (1.13) phần (1.2) ta có V f ( x k) = V f ( x*) + I V 2/ (x* + r ( x k — X*)) ( xk — x*)dr •'ú Vũ Thị Yến 19 K 3 7 C - S P T D H S P Hà Nội 2