Khoá luận tốt nghiệp toán Phương pháp miền tin cậy cho các bài toán tối ưu không có ràng buộc

  • Số trang: 36 |
  • Loại file: PDF |
  • Lượt xem: 67 |
  • Lượt tải: 0
tailieuonline

Đã đăng 27372 tài liệu

Mô tả:

T R Ư Ờ N G Đ Ạ I H Ọ C s ư P H Ạ M H À N Ộ I II KHOA TOÁN ĐÀO T H Ị HẬ U PHƯƠNG PH Á P MIỀN TIN CẬY CHO CÁC BÀI TOÁN TỐI ƯU KHÔNG CÓ RÀNG BUỘC K H Ó A L U Ậ N T Ố T N G H IỆ P Đ Ạ I H Ọ C C h u y ê n n g à n h : G iải tíc h Người hướng dân khoa học T h .s . P h ù n g Đ ức T h ắ n g H à N ội - 2015 LỜI C Ả M Ơ N Em xin chân thành cảm ƠĨ1 T h.s Phùng Đức Thắng đã tận tình hướng dẫn, giúp dỡ em trong suốt thời gian thực hiện khóa luận. Em cũng xin được cảm ƠĨ1 thầy Bùi Ngọc Mười đã góp ý chi tiết về cách trình bày một số kết quả trong khóa luận. Em xin chân thành cảm ƠĨ1 các thầy, các cô trong tổ giải tích- khoa Toán, trường Đại học sư phạm Hà Nội 2 đã tạo mọi điều kiộn giúp đỡ em hoàn thành khóa luận này. Erri xin chân thành cảm ơn gia đình và bạn bò đã tạo mọi điều kiộn thuân lợi cho crri trong quá trình thực hiộn khóa luận. E m xin chân thành cảm ơn. Hà Nội, tháng 05 năm 2015 Sinh viên Đào Thị Hậu 1 LỜI C A M Đ O A N Em xin cam đoan, dưới sự hướng dẫn của T h.s Phùng Đức Thắng khóa luận "P h ư ơ n g p h á p m iề n tin cậy cho b à i to á n tố i ư u k h ô n g có rà n g buộc" được hoàn thành không trùng với bất kỳ đề tài nào khác. Trong quá trình hoàn thành khóa luận, em đã thừa kế những thành tựu của các nhà khoa học với sự trân trọng và biết ƠĨ1. Hà Nội, tháng 0-5 năm 2015 Sinh viên Đào Thị Hậu 2 M ục lục Lời mở đầu 1 1 T h u ậ t to á n m iền tin cậy cơ b ả n 3 1.1. Một số khái niộm cơ b ả n ....................................................... 3 1.2. Một số giả thiết với hàm rriục tiêu và hàm xấp xỉ . 6 1.2.1. Giả thiết cho hàm mục t i c u ..................................... 6 1.2.2. Giả thiết cho hàrri xấp x ỉ ............................................ 7 1.3. Điểm và một hàm xấp xỉ g iả m .............................................. 9 1.3.1. ... Phương Cauchy ......................................................... 1.3.2. Điểm Cauchy cho hàm xấp xỉ dạng toàn phương 2 Sự hội tụ 9 10 15 2.1. Sự hội tụ đến điềm tới hạn bậc nhất ............................... 15 2.2. Sự hội tụ đến điểm tới hạn bậc h a i .................................. 23 Tài liệu tham khảo 31 3 Khóa luận tốt nghiệp Đào Thị Hậu Lời mở đầu Bài toán tối ưu có ứng dụng rộng rãi trong toán học cũng như trong dời sống. Nó được nghiên cứu một cách toàn diện Iihờ các phương pháp định tính và định lượng như phương pháp gradient, phương pháp gradicnt chiếu, phương pháp Newton, phương pháp nhân tử Lagrangc... Cùng với sự phát triển của khoa học công nghệ, chúng ta đã tạo ra những thuật toán hữu hiệu giúp ta giải các bài toán tối ưu một cách hiộu quả nhất. Và phương pháp rniồn tin cậy được xcm là một trong số đó. Xét bài toán tìm cực tiểu hàm / : Rn — >R, được giả thiết là khả vi liên tục đến cấp hai và bị chặn dưới ở trên Rn. Với mỗi điổrri khởi đầu Xo £ Mn được chọn tùy ý, phương pháp m iề n tin cậy (thuật ngữ tiếng Anh là Trust-Region Mcthod) cho phóp tạo ra dãy lặp {#*;} mà, tại mỗi bước Ả:, việc chuyển từ điểm Xk sang điểm Xk+I làm giảm hàm mục tiêu xấp xỉ, được ký hiộu bởi 77ifc(;x), của f ( x) . Một trong những cách xấp xỉ thông dụng nhất là thay hàm số f ( x ) bởi phần tuyến tính-toàn phương trong khai triều Taylor bậc hai của nó tại điểm Xỵ. ơ mỗi bước thay cho Mn người ta xét một hình cầu tâm x k với bán kính A k thích hợp. Quy tắc chọn Ajt, nhằm đảm bảo tốc độ tính toán cao nhất có thể được, là một phần nội dung quan trọng của phương pháp này. Cụ thể, tỷ số giữa độ giảm hàm mục tiêu /(;x) và độ giảm của hàm xấp xỉ của nó tại bước k — 1, tức là hàm 77ifc_i(x), là cơ sở để xác định bán kính Afc. Dưới một số điều kiện, dãy lặp {.7;^} hội tụ đến một, điểrn tới hạn bậc nhất của bài toán. Thuật toán miền tin cậy là thuật toán làm giảm hàrri rriục tiêu, tức là ta có f (xk+ 1) < f{xk) với mọi k. 1 Khóa luận tốt nghiệp Đào Thị Hậu Cuốn chuyên khảo [1] của các tác giả A. R. Corm, N. I. M. Gould, và p. L. Toint là một cẩrri nang khá đầy đủ và chi tiết về lý thuyết phương pháp rriiền tin cậy. Lịch sử phát triển của phương pháp miền tin cậy và rriột số ứng dụng của các thuật toán miền tin cậy đã được giới thiệu ở [1, tr. 8-12]. Khi nghiên cứu phương pháp miền tin cậy, em quan tâm đến tính ổn định và sự hội tụ địa phương của dãy lặp, ở đây em cũng đã chứng rnirih một, kết quả về tính ổn định và sự hội tụ địa phương của các dãy lặp { x k} được sinh ra bởi thuật toán rriiền tin cậy trong trường hợp bài toán không có ràng buộc. Khóa luận gồm hai chương. Chương 1: "Thuật toán miền tin CẬĨJ cơ bản" trình bày thuật toán miền tin cậy BTR và một số giả thiết cho hàm mục tiêu và hàm xấp xỉ trong [1, Chương 6]. Chương 2: "Sụ hội t ụ 11 chính là lời giải cho vấn đề tính 011 định và tốc độ hội tụ địa phương của dãy lặp {.Xa-} được sinh ra bởi thuật toán miền tin cậy trong trường hợp bài toán không có ràng buộc [1, Chương 6]. 2 Chương 1 T huật toán m iền tin cậy cơ bản 1.1. Một số khái niệm cơ bản Trước hết ta xét bài toán tối ưu không có ràng buộc (P) Bài toán. (p ) : rriin f ( x ) . (1-1) xeR" trong đỏ f : Mn — y R là hàm, khả vi liên tục cấp hai và bị chặn dưới trong R n. Đ ịn h n g h ĩa 1.1. Tập điểm tới hạn bậc nhất của (p), được kí hiệu S(P), ì,à: S( P) = { x * e R n I V * /( * .) = <>}, (1.2) ở đây Va:/(£ * ) là gradient của hàm f ( x ) tại điểm X* Chúng ta xem xét kĩ thuật để sinh vọng nó hội tụ tới điểrn tới hạn bậc nhất ra một dãy lặp {Xyt}, rriàta hi của bài toán (1.1). Thuật toán miền tin cậy cơ bản cho bài toán (P) được tiến hành như sau. Với mỗi bước lặp Xỵ , chúng ta xác định một hàm m ục tiêu xấp xỉ niỵ{x) trong một lân cận thích hợp của 3 mà ta gọi là miền tin cẠy. Khóa luận tốt nghiệp Đào Thị Hậu Đ ịn h n g h ĩa 1.2. Miền tin cậy ỉ,à tập hợp các điểm Bk = {x e Mn I \\x - x k\\ < A k}. (1.3) được gọi là bán kính miền tin cậy và tại mỗi bước lặp ||.||fc là một chuẩn phụ thuộc vào k. Cho hàm xấp xỉ này và miền tin cậy của Ĩ1Ó, chúng ta tìm một bước thử sk tới một điểrn thử x k + Sỵ với mục đích giảm hàm xấp xỉ trong đó thỏa rriãn tính bị chặn ||.Sfc||jfc < A k. 0 đây, ta sẽ tính tỉ số giữa độ giảm, hàm, mục tiêu và độ giảm, hàm xấp xỉ. Nếu tỉ số đủ 1ỚĨ1, tức hàm mục tiêu Ị (x) giảrn nhanh chóng, khi đó điểm thử được chấp nhận và được chuyển sang bước lặp tiếp k+1. Ớ bước k+1, điểm thử được xác định Xk +1 = + Sfc và rniền tin cậy sẽ đu’Ợc tăng lên hoặc giữ nguyên. Ngược lại nếu tỉ số nhỏ, thậrn chí là một số ârri, khi đó điểrn thử bị bác bỏ và ở bước lặp tiếp theo vẫn giữ nguyên điểrn thử này nhưng rriiền tin cậy sẽ bị thu hẹp. Khi dó, thuật toán miền tin cậy cơ bản (được viết tắt là thuật toán BTR), được mô tả như sau. T huật toán 1.1. Thuật toán m iền tin cậy cơ bản ( B T R ) B ư ớ c 0: K h ở i chạy. Cho trước một điếm, Xq ban đầu và một bán kính miền tin cậy ban đầu A0. Các hằng số ĩji, r/2, 7 i và 72 cho trước thỏa mẫn 0 < ĩì\ < ĩ]2 < 1 và 0 < 7 i < 72 < 1 (1-4) Tính /(.Xo) và đặt k = 0. Bước 1: X á c định hàm xấp xỉ mẫu. Chọn ||.||fc và xác định m ộ t hàm ĩĩík xấp xỉ với hàm f tại Xỵ trong B ỵ . Bước 2: Bước tính toán. Tỉnh một bước ,Sfc/ "đủ ỉ,àm giảm hàm, x ấp TÂ" ĩĩlỵ, sao cho Xỵ + Sỵ G Bỵ. 4 Khóa luận tốt nghiệp Đào Thị Hậu Bước 3: Chấp nhận điểm thử. Tỉnh f ( x k + Pk = nếu •Ek+l Pk Sk) và xác định f(Xk) - f(Xk + sk) (1.5) rnk ( x k) - m k ( x k + s k) > rji, sau đó xác định Xỵ+ 1 = Xk + Skỉ ngược lại nếu pk < ĩ/i thì '^k • Bước ị : Cập nhật bán kính m iền tin cậy. Tập nế upk >ĩ]2, [Afc,oo) Ak+I £ < [7 2A fc,Afc) ( 1.6 ) n ế u Ọk € [771, 772), [7 iA yt, 7 2A fc) nếupk < ĩ]1. Tăng k thêm 1 và quay trở lại buớc 1. Ta có thể lấy ví dụ, các hằng số thỏa mãn điều kiện (1.4) là ĩ/1 0 .01,772 0.9,71 72 (1.7) ị, nhưng những giá trị khác vẫn có thể phù hợp. Tại bước lặp rnà f)ỵ > 771, và do đó những lặp rnà Xk+1 = x k + sk, được gọi là bước lặp chấp nhận được, và chúng ta kí hiệu tập các chỉ số bởi kí hiệu 0IỌỵ > //1}. Tương tự, chúng ta cũng định nghĩa V = { k > 0 I p k > 772}, là tập các bước lặp chấp nhận đuợc tốt. Chú ý rằng V c s . Sự lặp mà các chỉ số của nó không thuộc s được gọi là không chấp nhận được. Trong thực hành, thường chọn hàm xấp xỉ toàn phương dạng m k(xk + .s) = m k(xk) + (gkĩ s) + ị ( s , H ks), 5 ( 1.8 ) Khóa luận tốt nghiệp Đào Thị Hậu ở đây m k(xk) = f ( x k) và gk - sỵxf ( x k) và Hỵ là rriột ma trận đối xứng xấp xỉ \ 7xxf(x k)- Nếu H k Ỷ 0, chúng ta nói rằng (1.8) là một hàrn xấp xỉ bậc hai. Một cách cụ thể để tìm bước thử Sk hoặc điều kiện " đủ giảm" không được mô tả cụ thể ở dây. Đặc biệt, khi thuật toán BTR không chứa bước dừng, ta giả thiết rằng có một chuỗi vô hạn được tạo ra. Nếu thuật toán BTR được thực hiện như một chương trình máy tính, Ĩ1Ó sẽ dừng lại ngay khi bước lặp Xỵ được đánh giá là "đủ gần điểm tới hạn". Trong trường hợp không có ràng buộc, ticu chuẩn đơn giản nhất là chuẩn của gradicnt của hàm mục II Va- f{Xk)\\- ticu tại 1.2. Một số giả thiết với hàm mục tiêu và hàm xấp xỉ Đe thuận tiện cho việc nêu các giả thiết trong các định lý hội tụ, chúng ta nhóm tấ t cả chúng lại trong rnột phần; phân biệt giữa giả thiết cho hàrri mục tiêu và giả thiết cho hàrri xấp xỉ. 1.2.1. G iả th iết cho hàm m ục tiêu Ta có các giả thiết cho hàm mục tiêu A F .l f ( x ) nhận giá trị thực và khả vi liên tục cấp 2 trong Rn. A F .2 /( * ) bị chặn dưới trong R?i, nghĩa là, tồn tại một hằng số KibỊ sao cho với mọ i X £ Mn, / 0 ) > « 16/ . 6 Khóa luận tốt nghiệp Đào Thị Hậu A F .3 Ma trận Hessian của hàm mục tiêu bị chặn đều; tức là, tồn tại một hằng số dương Kufh sao cho, với mọi X G Mn, ^11 \7XX /(*^)|| — K'ufh- Ta thấy giả thiết cuối cùng thì quá mạnh. Thực tế, ta thường cần tính bị chặn của II Vx-X- f ( x ) II với giá trị X nằm giữa hai lần lặp licn tiếp của thuật toán cơ bản. Yôu cầu yếu hơn này tự động được thỏa mãn nếu những lần lặp vẫn trong một tập con bị chặn của Mn, như là, tập {x E Mn|/(a;) < f ( x o)} với x 0 tùy ý. Không mất tính tổng quát, chúng ta cũng có thổ giả sử rằng Kufh ^ 1- Cụm từ "lbf" và "ufh" xuất phát từ "lower bound oil the objective function" và "upper bound oil the objective function’s Hessian". 1.2.2. G iả th iết cho hàm xấp xỉ Ta sẽ giả thiết rằng hàm 77lỵ tại bước lặp thứ k xấp xỉ với hàm mục tiêu trong miền till cậy Bk là một xấp xỉ bậc một trơn tốt của hàm mục tiêu. Do dó, chúng ta bù lại những giả thiết sau. A M .l Với mọi k, hàm xấp xỉ mỵ là khả vi hai lần trong Bỵ. A M .2 Giá trị của hàm mục tiêu và hàm xấp xỉ phù hợp tại một dòng lặp; tức là, với mọi k, mk( xk) = f ( x k) (1.9) A M .3 Gradient của mô hình tại Xỵ bằng gradient của hàm mục tiêu; tức ỉ,à, với mọi k, 9k d- = Va: f ( x k) 7 (1.10) Khóa luận tốt nghiệp Đào Thị Hậu A M .4 Ma trận Hessian của hàm xấp xỉ củng bị chặn trong miền tin CẨiy; tứ c là, II s/XX m k (x)\\ ^ l^umh 1 với mọi k, khỉ numh > 1 là hằng số phụ thuộc vào k. Ta chú ý rằng những giả thiết này được đáp ứng nếu ta xcm xót một miền tin cậy đơn giản nhưng rất quan trọng của phương pháp Newt,on trên miền bị chặn đóng, tức là, nếu chúng ta chọn niỵ sao cho (1.9) và (1.10) được thỏa mãn, như tốt hơn VxxMk(%k “tvới mọi s sao cho \7xxỉ(%k) + s e Bk. Nếu ta giả thiết rằng hàm rriục tiêu khả vi hai lần (ví dụ, A F .l), phương trình (1.11) sau đó kết quả từ (1.12) và AF.3. Điều này chưa được rõ ràng nếu (1.12) được giả sử khắp. Chúng ta cũng chú ý rằng AM. 1-AM.4 cho phép trường hợp mà hàm mục tiêu không thể gần tới một hàm xấp xỉ. Ví dụ, chúng ta có thể xem xét trường hợp mà trong dó hàm mục tiêu có dạng ỉ ( x ) = fo(x,y{x)) (1.13) ỏ đó f 0(x, y) là một hàm số từ Mn X w p vào R Ĩ1Ó tương đối đơn giản để tính toán, nhưng y(x) thì phức tạp từ Mn vào R7\ Ví dụ, /o có thể là rriột. tiêu chí đơn giản cho một hệ thống được kí hiệu y(x) chỉ có thể được tính toán nhờ sử dụng một công cụ tính toán như là giải phương trình vi phân từng phần hoặc chạy một, mô phỏng chuyên dụng. Trong trường hợp này, có thể xây dựng một hàm xấp xỉ ĩrìị{x) thích hợp của y(x) trong lân cận của x k và khi đó xác định m k(x) = /oO , mị ( x) ) (1.14) Những điều kiộn AM .l- AM.4 của hàm xấp xỉ rriỵ có thổ được trình bày như là điều kiộn của m ị và / 0. 8 Khóa luận tốt nghiệp Đào Thị Hậu Chúng ta hoàn thiện những giả thiết trong thuật toán nhờ việc chỉ rõ rriối liên hệ giữa các chuẩn \\.\\k khác nhau xác định hình dạng của miền till cậy trong (1.3). A N .l Tồn tại một hằng số Kune > 1 sao cho, với mọi k, 1 I . ,, ,, ,, ,, ----- \\x\\k < IMI < Kune\\x\\k . K'une với mọ i X E R 11 Cụm từ "urnh" và "line" xuất phát từ "upper bound 011 the model’s Hessian" và "uniform norm equivalence". 1.3. Điểm và một hàm xấp xỉ giảm Điểrn cốt yếu trong thuật toán của ta là sự xác định bước k, để hàrri xấp xỉ giảm trong miền tin cậy. Trong phần này, chúng ta đưa ra cách xác định bước lặp như thế từ một kĩ thuật tính toán đơn giản. 1.3.1. Phương Cauchy Đ ịnh nghĩa 1.3. Phương Cauchy được xác định bởi x k № Chú ý rằng “f {x \ X = Xk — tgkì t > 0 và X £ Bk} (t ) = Xỵ với mọi t > 0 khi đó Qk = 0. Trong phần này, f t =f 1 + max II V o rrik(x)\ị xeBk (1.15) được xerri như là cận trên của độ cong. Sự xác định này và AM.4 cũng có nghĩa là Pk < Kumh với rriọi k. 9 (1-16) Khóa luận tốt nghiệp 1.3.2. Đào Thị Hậu Đ iểm C auchy cho hàm xấp xỉ dạng toàn phương Nếu chúng ta giả thiết rằng hàm xấp xỉ của chúng ta là hàm toàn phương, tức là, nó có dạng (1.8), khi đó Ĩ1Ó có thẻ có cực tiểu nằrri trên phương Cauchy. Đ ịnh nghĩa 1.4. Điểm, Cauchy, kí hiệu là là điểm cực tiểu (duy nhất) của hàm xấp xỉ dọc theo phương Cauchy, tức x ị ( t ) = x k - t ck yk = {arg mill rnk ( x k - t y k) I t > 0 v à x k - t y k G 5*}, (1.17) Nếu gk Ỷ 0. Xk - tgk € B k tức \\x - x k\\ < A k. Khi đó, \\%k - tfyk - Xk\\ < Ajfc, suy ra t\\9k\\ < A*. Do đó. t < A* \\9k\\ Từ đó, điều kiện (1.17) có thể viết lại thành t ĩ = { arg min m k(xk - tgk) I 0 < t < Ịj—^ĩị} Đ ịnh lý 1.1. ([1, Theorem 6.3.1, p. 125]) Nếu hàm xấp xỉ được CÌIO bởi (1.8) và điểm Cauchy được xác định bởi (1.17), khi đó chúng ta có m k(xk) - m k{xỵ) > ^ll^jfell mill 2 10 , Pk (1.18) Khóa luận tốt nghiệp Dào Thị Hậu trong đó Pk được xác định bởi (1.15) và Vk = (1.19) \\yk\\k Chứng minh. Với mọií > 0 ta có: mk{xk - tgk) = m k(xk)- t\\gk\\2 + ị ( g k, ỉ ĩ kgk) (1.20) Trường hợp 1: (gk, H kgk) > 0 (1.21) Khi đó ta tính toán giá trị của tharn số t tại điểm cực tiểu của (1.20), kí hiệu tham số tối Ưu là tỵ. Lấy vi phân theo tham số t của (1.20), ta được 0 = I\9k\\2 — tịịgk, H kgk) từ đó suy ra Ạ* _ Ị -Ị r)ON llí^ll 1 - ) { ’ Nếu tl\\(jk\\ < A k (tức điểm cực tiểu nằm trong miền tin cậy). Khi đó = tị và thay vào (1.20) ta được m k(xk) - m k{ x ck ) = t*k\ịgk\\2 - ị(t*k)2 {gk, H kgk) 2v I I I \\gk\ỵ_ _ 1 \\gk\y_ (9k, Hkyk) 2 (ykì Hkyk) 1 Ikll4 2 (gki Hk9k) ’ Theo bất đẳng thức Cauchy- Schwarz ta có \( 9 k ỉ H kg k )\ < || 0 fc||||i/fc0 fc|| < \\9k\\2Pk Vì vậy m.ìẨ:Xu) m k(xk) — - rn m k{(T,ọ x ck ) > - 11 C1-23) Khóa luận tốt nghiệp Dào Thị Hậu Nếu (1.24) t-kìM > A * (đường cực tiểu nằm ngoài miền tin cậy). Khi đó, ta có: (1.25) í* 11*11 = A k. Kết hợp (1.22), (1.24) và (1.2-5) ta thấy t ĩ \ \ 9 k \ \ k < t l \ \ g k \\k hay Điều này dẫn tới ( g k , H kg k ) < Ta có m k(xk) - m k{xck ) = tck \\yk\Ỹ- - ị ( t t ) 2(gk,Hkyk} > t kc = Ik ll2 - ^i /' ^) l k l l 2 2[k) 1 ưk \ \ 9 k \ \ & k - t? 'k 7;i'ĩ\ịykị\&k: do đó m k(xk) - m k(xck ) > ị u Ị IIêíìIIA*. ( 1.26) với Vỵ được cho bởi (1.19). Nếu Ì9k,Hk9k) < 0. Khi đó, ta có mk(xk - tgk) = m k(xk) - t\\gk\\2 + ^ t2(gk,Hkgk) < m k(xh) - í||íft||2 12 (1.27) Khóa luận tốt nghiệp Dào Thị Hậu với t > 0. Trong trường hợp này, điểrn Cauchy phải nằrri trên biên của miền tin cậy, do đó (1.25) vẫn đúng. Có mk(xk) - m kix h) ằ Ils*||277^7j\\9k\\k = I'kWukW^kVì vậy m k(xk) - m k{xck ) > ^ ||fttl|A*- Từ (1.23), (1.26) và (1.28) ta có điều phải chứng rriinh. (1-28) □ Định lí 1.1 là một trường hợp đặc biệt của kếtquả tổng quát cho bài toán tìrri cực tiểu hóa của hàm toàn phương q(s) = f + (g, s) + i ( s , H s ) với tấ t cả các (1.29) điểm nằm dọc theo arcố’ = —ty trong miền ||ò‘||Q < A, (1.30) chuẩn IMU cho trước tùy ý. Từ đây ta có hệ quả H ệ quả 1.1. ([1, Corollary 6.3.2, p. 127]) Giỏ, sử rằng sc hàm toàn phương (1.29) trong m iề n tin cẬy (1.30) cho mọ i ì,àcực tiểu của điểm, nằm, dọc theo arcs = —tg. Khi đó chúng ta có 9(0) - 9 ( s c ) ằ ^1 MI min Ll + \\H\Ự ỈSCA khi /yc Chứng minh. Điều này được suy ra từ Định lí 1.1 nếu chúng ta chọn q(s) = m k(xk + s), / = m k(xk), g = g(xk), H = H k, A = A k và ll-IU = ll-IU thay (3k bởi cận trên. 13 □ Khóa luận tốt nghiệp Dào Thị Hậu Chúng ta thấy hàm xấp xỉ giảm tại điềm Cauchy phụ thuộc vào giá trị của /y^, ít nhất là bán kính miền tin cậy A k. ơ mỗi bước lặp ta thường sử dụng chuẩn Eclidean ||.|| 2, khi đó ưk = 1. Đối với các chuẩn khác thì AN.l đầrn bảo rằng 1 vck > > 0 Khi đó, điểrn Cauchy thỏa rnãn AA.l m k(xk) - m k(xk + sk) > Kmdc\\9kị\min Ikll Aj Pk (1.31) với mọi k và hằng số nmdc € (0,1). Điều này có nghĩa là hàm xấp xỉ sẽ giảm một phần tại điổm Cauchy. Chữ A thứ hai trong cụm từ AA có nguồn gốc từ "acccpt", cụm từ ”mdc” là viết tắt của "model decrease". 14 Chương 2 Sự• hội tụ• • 2.1. Sự hội tụ đến điểm tới hạn bậc nhất Bây giờ chúng ta sẽ đi chứng minh rằng, với hệ thống những giả thiết đã nêu trong phần trước, tất cả các điểm giới hạn £•* của chuỗi lặp {£*;} được tạo ra bởi th ật toán BTR là điổm tới hạn bậc nhất của bài toán (1.1), tức là, chúng thỏa mãn V x f 0*) = 0 không phụ thuộc vào vị trí vủa vecto Xo ban đầu và sự lựa chọn bán kính miền tin cậy A0 ban đầu. Định lí sau sẽ cho phép chúng ta tính sai số giữa hàm mục tiêu và hàm xấp xỉ tại điổm Xỵ + Sỵ € B. Đ ịn h lý 2.1. ([1, Theorem 6.4.1, p.133]) Giả sử các điều kiện AF. l , AF.3, và AM. l - A M .4 được thỏa mãn. Khi đó chúng ta có 1/0*. + sk) - m k(xk + sk)\ < [vị]2 rnax[/€ufhi umh ]At 2, khi Xỵ + Sỵ G Bỵ và 15 (2.1)
- Xem thêm -