Đăng ký Đăng nhập
Trang chủ Phương pháp hiệu chỉnh tikhonov cho bài toán quy hoạch với ràng buộc là bài toán...

Tài liệu Phương pháp hiệu chỉnh tikhonov cho bài toán quy hoạch với ràng buộc là bài toán bù tổng quát

.PDF
34
280
61

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRỊNH THỊ HÀ PHƯƠNG PHÁP HIỆU CHỈNH TIKHONOV CHO BÀI TOÁN QUY HOẠCH VỚI RÀNG BUỘC LÀ BÀI TOÁN BÙ TỔNG QUÁT LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRỊNH THỊ HÀ PHƯƠNG PHÁP HIỆU CHỈNH TIKHONOV CHO BÀI TOÁN QUY HOẠCH VỚI RÀNG BUỘC LÀ BÀI TOÁN BÙ TỔNG QUÁT Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TS. NGUYỄN BƯỜNG Thái Nguyên - 2015 i Mục lục Lời cảm ơn iii Mở đầu 1 1 Các khái niệm và vấn đề cơ bản 3 1.1 Không gian Euclid n chiều . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Không gian vectơ . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Không gian Euclid . . . . . . . . . . . . . . . . . . . . . . . 4 Bài toán đặt không chỉnh . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.1 Khái niệm bài toán đặt không chỉnh . . . . . . . . . . . . . . 6 1.2.2 Ví dụ về bài toán đặt không chỉnh . . . . . . . . . . . . . . . 7 1.2.3 Định nghĩa toán tử hiệu chỉnh . . . . . . . . . . . . . . . . . 8 1.2 1.3 1.4 2 Phương pháp đường dốc nhất . . . . . . . . . . . . . . . . . . . . . . 10 1.3.1 Nội dung phương pháp . . . . . . . . . . . . . . . . . . . . . 10 1.3.2 Sự hội tụ của phương pháp . . . . . . . . . . . . . . . . . . . 11 Kết luận Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Phương pháp hiệu chỉnh Tikhonov cho bài toán quy hoạch với ràng buộc là bài toán bù tổng quát 16 2.1 Bài toán thực tế dẫn đến bài toán bù tổng quát . . . . . . . . . . . . . 16 2.2 Bài toán quy hoạch với ràng buộc là bài toán bù tổng quát . . . . . . . 19 2.3 Sự hội tụ của phương pháp . . . . . . . . . . . . . . . . . . . . . . . 22 2.4 Kết quả số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.5 Kết luận Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 ii Kết luận 28 Tài liệu tham khảo 29 iii Lời cảm ơn Luận văn này được hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn tận tình của GS.TS. Nguyễn Bường. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy. Em xin chân thành cảm ơn Ban giám hiệu, Khoa Toán - Tin, Trường Đại học Khoa học - Đại học Thái Nguyên đã quan tâm và giúp đỡ em trong suốt thời gian học tập tại Trường. Nhân dịp này em cũng xin được gửi lời cảm ơn chân thành tới gia đình, bạn bè đã luôn bên em, cổ vũ, động viên, giúp đỡ em trong suốt quá trình học tập và thực hiện khóa luận tốt nghiệp. 1 Mở đầu Nhiều vấn đề trong thực tế chúng ta gặp phải như khoa học, công nghệ, kinh tế,..., tồn tại một lớp các bài toán mà nghiệm không ổn định theo nghĩa một thay đổi nhỏ của dữ liệu đầu vào sẽ dẫn đến những thay đổi lớn của dữ liệu đầu ra (nghiệm của bài toán), thậm chí còn làm cho bài toán trở nên vô nghiệm. Người ta nói những bài toán đó không chính quy hay đặt không chỉnh. Vì vậy cần phải có những phương pháp giải ổn định các bài toán đặt không chỉnh sao cho khi sai số của dữ liệu càng nhỏ thì nghiệm xấp xỉ tìm được càng gần với nghiệm đúng của bài toán xuất phát. Do tầm quan trọng đặc biệt của lý thuyết này mà nhiều nhà toán học nước ngoài và Việt Nam đã dành phần lớn thời gian và công sức của mình cho việc nghiên cứu các phương pháp hiệu chỉnh để giải các bài toán đặt không chỉnh. Trong khuôn khổ luận văn này chúng tôi xin được trình bày đề tài: “Phương pháp hiệu chỉnh Tikhonov cho bài toán quy hoạch với ràng buộc là bài toán bù tổng quát”. Luận văn được tổng hợp từ bài báo của GS. TS. Nguyễn Bường cùng với cộng sự Nguyễn Thị Thúy Hoa. Mục đích của luận văn này là trình bày lại một kết quả mới đây của GS.TS. Nguyễn Bường và cộng sự về phương pháp hiệu chỉnh Browder-Tikhonov tìm nghiệm của bài toán quy hoạch với ràng buộc là bài toán bù trên không gian Euclid n chiều. Ngoài phần mở đầu, kết luận, danh mục các tài liệu tham khảo, bố cục của luận văn được trình bày trong hai chương. • Chương 1. Các khái niệm và vấn đề cơ bản. Trình bày các khái niệm cơ bản về không gian Euclid n chiều. Tiếp theo giới thiệu bài toán đặt không chỉnh. Đồng thời cũng trình bày định nghĩa toán tử hiệu chỉnh và phương pháp đường dốc nhất. 2 • Chương 2. Phương pháp tìm nghiệm của bài toán quy hoạch với ràng buộc là bài toán bù tổng quát. Luận văn được hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên dưới sự hướng dẫn của GS.TS. Nguyễn Bường. Mặc dù tác giả đã hết sức cố gắng nhưng do vấn đề nghiên cứu là khá phức tạp và kinh nghiệm nghiên cứu còn hạn chế nên không trành khỏi thiếu sót. Trong quá trình viết luận văn cũng như xử lý văn bản chắc chắn không tránh khỏi những sai sót nhất định. Tác giả rất mong nhận được những ý kiến đóng góp của quý thầy cô và các bạn để luận văn được hoàn thiện hơn. Thái Nguyên, ngày 10 tháng 6 năm 2015 Trịnh Thị Hà Học viên Cao học Toán Lớp 7A, khóa 06/2013-06/2015 Chuyên ngành Toán ứng dụng Trường Đại học Khoa học - Đại học Thái Nguyên Email: [email protected] 3 Chương 1 Các khái niệm và vấn đề cơ bản Chương này gồm ba mục, trình bày một số khái niệm cơ bản được sử dụng liên quan tới nội dung nghiên cứu của đề tại. Mục 1.1 nêu vấn đề, tính chất và ví dụ về không gian Euclid n chiều. Mục 1.2 nêu khái niệm, ví dụ về bài toán đặt không chỉnh và định nghĩa toán tử hiệu chỉnh. Mục 1.3 trình bày nội dung và sự hội tụ của phương pháp đường dốc nhất. 1.1 1.1.1 Không gian Euclid n chiều Không gian vectơ Định nghĩa 1.1. Xét tập V khác rỗng mà mỗi phần tử ta quy ước là một vectơ trên trường số thực R, giả sử trong V ta định nghĩa được hai phép toán: phép cộng vectơ và phép nhân một vectơ với một số thực. Phép cộng vectơ là một luật hợp thành trên V cho phép tạo ra từ một cặp vectơ x, y ∈ V một vectơ duy nhất gọi là tổng của chúng, kí hiệu là x + y. Phép nhân một vectơ với một số, còn gọi là phép nhân với vô hướng, là một luật hợp thành ngoài trên V cho phép tạo ra từ một vectơ x ∈ V và một số thực k ∈ R một vectơ duy nhất gọi là tích của chúng, kí hiệu là kx. Nếu mười yêu cầu sau thỏa mãn với mọi x, y, z ∈ V và mọi k, l ∈ R thì tập V gọi là một không gian vectơ trên trường R. (1) Nếu x, y ∈ V thì x + y ∈ V . (2) x + y = y + x, ∀x, y ∈ V . 4 (3) x + (y + z) = (x + y) + z, ∀x, y, z ∈ V (4) Tồn tại vectơ θ ∈ V sao cho θ + x = x + θ = x, ∀x ∈ V. Phần tử θ gọi là phần tử trung hòa của phép + (hay của V ). (5) Với mỗi x ∈ V tồn tại vectơ −x ∈ V sao cho x + (−x) = (−x) + x = θ. Phần tử (−x) gọi là phần tử đối xứng (hay phần tử đối) của x. (6) Nếu k ∈ R và x ∈ V thì kx ∈ V . (7) k(x + y) = kx + ky. (8) (k + l)x = kx + lx. (9) k(lx) = (kl)x. (10) 1.x = x. Chú ý: yêu cầu (1) là tính đóng kín của phép cộng vectơ. Yêu cầu (6) là tính đóng kín của phép nhân với vô hướng. Yêu cầu (2) nói lên tính giao hoán của phép cộng vectơ. Yêu cầu (3) nói lên tính kết hợp của phép cộng vectơ. Mười yêu cầu (1) - (10) gọi là mười tiên đề của không gian vectơ. 1.1.2 Không gian Euclid Định nghĩa 1.2. Cho V là một không gian vectơ, u và v là hai vectơ của V . Tích vô hướng của u và v là một số thực, kí hiệu là hu, vi, thỏa mãn các tính chất sau gọi là các tiên đề của tích vô hướng: (1) hu, vi xác định đối với mọi cặp u, v ∈ V ; (2) hu, vi = hv, ui; (3) hu + v, wi = hu, wi + hv, wi; (4) hku, ui = khu, vi; (5) hu, ui ≥ 0 và hu, ui = 0 ⇔ u = θ. 5 Không gian vectơ V có trang bị một tích vô hướng gọi là không gian có tích vô hướng. Không gian vô hạn chiều có tích vô hướng gọi là không gian Euclid. Định nghĩa 1.3. Không gian vectơ V được gọi là không gian n chiều (1 ≤ n nguyên) nếu trong V tồn tại n vectơ độc lập tuyến tính và không tồn tại quá n vectơ độc lập tuyến tính. Khi đó ta nói số chiều của không gian V là n và kí hiệu là dim(V ). Định nghĩa 1.4. V là một không gian vectơ, S = {x1 , . . . , xn } ⊂ V . Xét điều kiện: c1 x1 + . . . + cn xn = θ. (∗) Nếu điều kiện (∗) chỉ xảy ra khi c1 = 0, . . . , cn = 0 thì ta nói họ S độc lập tuyến tính. Định nghĩa 1.5. V là một không gian vectơ với hai phép tính: cộng vectơ và nhân vectơ với một số, W là một tập con của V . Nếu với hai phép tính trên W cũng là một không gian vectơ thì W được gọi là không gian vectơ con của V. • Ví dụ về không gian Euclid n chiều. Trong Rn với u = (u1 , u2 , . . . , un ), v = (v1 , v2 , . . . , vn ) thì biểu thức tọa độ của tích vô hướng trong Rn : hu, vi := u1 v1 + u2 v2 + . . . + un vn . Rn là một không gian Euclid n chiều. • Tính chất của không gian Euclid n chiều: (a) Phần tử trung hòa θ là duy nhất. (b) Phần tử đối xứng của bất kỳ phần tử x nào thuộc V cũng là duy nhất. (c) ∀x ∈ V ta đều có 0x = θ. (d) ∀x ∈ V ta đều có −x = (−1)x. (e) ∀k ∈ R ta đều có kθ = θ. (f) Với x ∈ V , và k ∈ R ta có: nếu kx = θ thì hoặc k = 0 hoặc x = θ. 6 1.2 1.2.1 Bài toán đặt không chỉnh Khái niệm bài toán đặt không chỉnh Khái niệm bài toán đặt chỉnh được J. Hadamard đưa ra khi nghiên cứu về ảnh hưởng của các điều kiện biên lên nghiệm của các phương trình eliptic cũng như parabolic. Xét bài toán Cauchy đối với phương trình Laplace ∂ 2 un ∂ 2 un + = 0, −∞ < x < ∞, 0 < y, ∂x2 ∂y 2 un (x, 0) = n−2 sin nx, −∞ < x < ∞, ∂un (x, 0) = n−1 sin nx, −∞ < x < ∞. ∂y Bài toán này có nghiệm duy nhất là un (x, y) = n−2 exy sin nx, ở bài toán này ta dễ ∂un thấy un (x, 0), (x, 0) → 0 khi n → ∞, trong khi đó un (x, y) → ∞ khi n → ∞ ∂y với mọi y > 0. Việc tìm nghiệm của phương trình toán tử Ax = f, f ∈ Y, (1.1) cũng phải dựa vào dữ kiện ban đầu f, có nghĩa là x = R(f ). Ta sẽ coi nghiệm cũng như các dữ kiện đó là những phần tử thuộc không gian X và Y với các độ đo tương ứng là ρX (x1 , x2 ) và ρY (f1 , f2 ), x1 , x2 ∈ X, f1 , f2 ∈ Y. Giả sử có một khái niệm thế nào là nghiệm của một bài toán. Khi đó bài toán tìm nghiệm x = R(f ) được gọi là ổn định trên cặp không gian (X, Y ), nếu với mỗi số ε > 0 có thể tìm được một số δ(ε) > 0, sao cho từ ρY (f1 , f2 ) ≤ δ(ε) cho ta ρX (x1 , x2 ) ≤ ε, ở đây x1 = R(f1 ), x2 = R(f2 ); x1 , x2 ∈ X; f1 , f2 ∈ Y. Định nghĩa 1.6. Bài toán tìm nghiệm x ∈ X theo dữ kiện f ∈ Y được gọi là bài toán đặt chỉnh trên cặp không gian metric (X, Y ), nếu: 1. Phương trình (1.1) có nghiệm x0 với mọi f ∈ Y, 2. Nghiệm x0 được xác định một cách duy nhất, 7 3. Nghiệm x0 phụ thuộc liên tục vào f. Nếu ít nhất một trong ba điều kiện trên không được thỏa mãn thì bài toán (1.1) được gọi là đặt không chỉnh. Đối với các bài toán phi tuyến thì điều kiện thứ hai gần như không thỏa mãn. Do vậy hầu hết các bài toán phi tuyến đều là bài toán đặt không chỉnh. Trong nhiều ứng dụng thì vế phải của (1.1) thường được cho bởi đo đạc, nghĩa là thay cho giá trị chính xác f, ta chỉ biết xấp xỉ fδ của nó thỏa mãn kfδ − f k ≤ δ. Giả sử xδ là nghiệm của (1.1) với f thay bởi fδ (giả thiết rằng nghiệm tồn tại). Khi δ → 0 thì fδ → f nhưng với bài toán đặt không chỉnh thì xδ không hội tụ tới x. 1.2.2 Ví dụ về bài toán đặt không chỉnh Sau đây ta sẽ chỉ ra một số ví dụ về toán tử A mà (1.1) là bài toán đặt không chỉnh. Ví dụ 1.1. Ta xét bài toán cổ điển. Đó là bài toán khôi phục hàm số khi biết hệ số Fourier của nó. Giả sử ϕk (t) là một hệ trực chuẩn đầy đủ có sup |ϕk (t)| ≤ C0 , và hệ t∈[a,b] số Fourier a = (a1 , a2 , . . .) của hàm f (t) = ∞ X ak ϕk (t). k=1 Thay cho ak được cho xấp xỉ bởi ck , ck thỏa mãn điều kiện: ∞ X (ak − ck )2 ≤ δ 2 . k=1 Hàm f˜(t) = ∞ X ak ϕk (t), f˜(t) 6= f (t), tại t. Giả thiết maxt∈[a,b] |ϕk (t)| ≤ C0 . Tìm k=1 xấp xỉ của f (t0 ) 6= f˜(t0 ). Lấy hàm: f˜n(δ) (t0 ) = n(δ) X ck ϕk (t0 ), k=1 n(δ) chọn sao cho n(δ) → ∞, δ → ∞, n(δ) = n(δ) X ˜ |f (t0 ) − fn(δ) (t0 )| = ak ϕk (t0 ) + k=1  η(δ)  , η(δ) → 0, δ → 0. Thật vậy: δ2 n(δ) ∞ X X ak ϕk (t0 ) − ck ϕk (t0 ) k=1+n(δ) k=1 8 ≤ n(δ) X k=1 Vì chuỗi ∞ X ak ϕk (t0 ) . k=1+n(δ) ak ϕk (t0 ) hội tụ, cho nên phần dư k=1 ∞. ∞ X |ak − ck ||ϕk (t0 )| + ∞ X ak ϕk (t0 ) → 0 khi n(δ) → k=1+n(δ) Ngoài ra, n(δ) X |ak − ck ||ϕk (t0 )| ≤ k=1 n(δ) X 2 |ak − ck | . k=1 n(δ) X ≤ C0 δ 1/2 k=1 r p |ϕk (t0 )|2 n(δ) = C0 δ p  η(δ)  = C 0 η(δ) → 0 khi δ → 0. δ2 Ví dụ 1.2. Cho A là một toán tử đơn điệu, cho X = Y = R3 , A là một ma trận được xác định bởi ma trận vuông cấp 3. Toán tử A : R3 → R3 được xác định bởi ma trận   1 0 0     A = 0 1 0  .   0 0 0 Dễ thấy rằng hAx, xi = x21 + x22 ≥ 0, ∀x = (x1 , x2 , x3 ) ∈ R3 . Suy ra A là một toán tử đơn điệu. Khi đó hệ phương trình trên có dạng x1 = f1 , x2 = f2 , 0x1 + 0x2 + 0x3 = f3 với f = (f1 , f2 , f3 ) ∈ R3 . Hiển nhiên, hệ phương trình này có nghiệm khi f = (f1 , f2 , 0) với f1 , f2 tùy ý. Khi vế phải được cho xấp xỉ bởi fδ = (f1 , f2 , f3δ ) với f3δ 6= 0 thì hệ phương trình trên trong trường hợp này vô nghiệm. 1.2.3 Định nghĩa toán tử hiệu chỉnh Để tìm nghiệm xấp xỉ của bài toán (1.1) khi không biết thông tin về nghiệm chính xác x0 , A. N. Tikhonov đã đưa ra một số khái niệm mới. Đó là phương pháp hiệu chỉnh dựa trên việc xây dựng toán tử hiệu chỉnh và cách chọn giá trị của một tham số mới đưa vào. 9 Giả sử A−1 không liên tục và thay cho f ta biết fδ : ρY (fδ , f ) ≤ δ → 0. Bài toán đặt ra là dựa vào thông tin về (A, fδ ) và mức sai số δ, tìm một phần tử xδ xấp xỉ nghiệm chính xác x0 của bài toán (1.1). Rõ ràng là không thể xây dựng phần tử xδ theo quy tắc xδ = A−1 fδ . Vì thứ nhất A−1 có thể không xác định với f ∈ Y, thứ hai A−1 không liên tục nên A−1 fδ nếu tồn tại cũng chưa chắc đã xấp xỉ A−1 f. Tham số δ chỉ cho ta độ sai số vế phải của (1.1). Vì vậy một điều tự nhiên nảy sinh là liệu có thể xây dựng phần tử xấp xỉ phụ thuộc vào một tham số nào đó và tham số này được chọn tương thích với δ sao cho khi δ → 0 thì phần tử này xấp xỉ hội tụ đến nghiệm x0 . Ta cũng thấy nếu được thì từ fδ ∈ Y ta có phần tử xấp xỉ thuộc E, tức là tồn tại một toán tử nào đó tác động từ không gian Y vào không gian X. Định nghĩa 1.7. Toán tử R(f, α) phụ thuộc tham số α, tác động từ Y vào X được gọi là một toán tử hiệu chỉnh cho bài toán (1.1) nếu: 1. Tồn tại hai số dương δ1 và α1 sao cho toán tử R(f, α) xác định với mọi α ∈ (0, α1 ) và với mọi fδ ∈ Y : ρY (fδ , f ) ≤ δ, δ ∈ (0, δ1 ); 2. Tồn tại một sự phụ thuộc α = α(fδ , δ) sao cho với mọi ε > 0, ∃δ(ε) ≤ δ1 để với mọi fδ ∈ Y thỏa mãn ρY (fδ , f ) ≤ δ ≤ δ1 thì ρX (xα , x0 ) ≤ ε, ở đây x0 là nghiệm chính xác của (1.1) và xα ∈ R(fδ , α(fδ , δ)). Phần tử xα ∈ R(fδ , α) được gọi là nghiệm hiệu chỉnh của bài toán (1.1) và α = α(fδ , δ) = α(δ) được gọi là tham số hiệu chỉnh. Cũng dễ dàng nhận thấy từ định nghĩa trên, nghiệm hiệu chỉnh ổn định với dữ kiện ban đầu. Chú ý 1.1. Trong trường hợp α = δ, định nghĩa về toán tử hiệu chỉnh có dạng đơn giản sau: Toán tử R(f, δ) tác động từ Y vào X được gọi là một toán tử hiệu chỉnh nếu 1. Tồn tại một số dương δ1 sao cho toán tử R(f, δ) xác định với mọi 0 ≤ δ ≤ δ1 và với mọi f ∈ Y sao cho ρY (f, f0 ) ≤ δ; 2. Với ε > 0 bất kì, tồn tại δ0 = δ0 (ε, fδ ) ≤ δ1 sao cho từ ρY (fδ , f0 ) ≤ δ ≤ δ0 ta có ρX (xδ , x0 ) ≤ ε, ở đây xδ ∈ R(fδ , δ). 10 1.3 Phương pháp đường dốc nhất 1.3.1 Nội dung phương pháp Xét bài toán tối ưu không ràng buộc min{f (x) : x ∈ Rn }. Ta sẽ xây dựng một dãy điểm x0 , x1 , x2 , . . . sao cho f (xk+1 ) < f (xk ), ∀k = 1, 2, 3, . . . dãy {xk } hội tụ tới x∗ khi k → ∞ và ∇f (x∗ ) = 0. Giả 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 vectơ gradient ∇f (xk ) một góc tù, tức là xác định xk+1 = xk + αk dk trong đó αk > 0, h∇f (xk ), di < 0. Thậy vậy, khai triển hàm f (x) thành chuỗi Taylor quanh điểm xk ta nhận được f (x) = f (f k ) + αh∇f (xk ), di + α2 2 h∇ f (x̄k )d, di, 2 ∂f (x) ∂f (x) ∂f (x) T ∂ 2 f (x)  , ,..., và x̄k = , ∇2 f (x) = ∂x1 ∂x2 ∂xn ∂xi ∂xj xk + θ(x − xk ) với θ ∈ [0, 1]. Nếu h∇f (xk ), di < 0 thì với α > 0 đủ nhỏ ta có trong đó ∇f (x) = f (x) < f (xk ). Việc lựa chọn hướng dịch chuyển dk và độ dài bước αk khác nhau sẽ cho ta các phương pháp gradient khác nhau. Nếu chọn dk ≡ −∇f (xk ), ∀k thì phương pháp gradient như thế có tên gọi là phương pháp đường dốc nhất (steepest descent method). Đây là một phương pháp thông dụng để tìm cực tiểu, nó rất đơn gian 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+1 = xk − αk ∇f (xk ), αk > 0, k = 0, 1, . . . (1.2) Thuật toán xác định αk tại mỗi bước lặp (Qui tắc Armijo) 1. Chọn giá trị α tùy ý (như nhau với mọi bước lặp, chẳng hạn α = 1) và xác định điểm x = xk − α∇f (xk ). 11 2. Tính f (x) = f [xk − α∇f (xk )]. 3. Kiểm tra bất đẳng thức f (x) − f (xk ) ≤ εαh∇f (xk ), dk i = −εαk∇f (xk )k2 (1.3) với 0 < ε < 1 là một hằng số được chọn tùy ý và như nhau ∀k = 0, 1, . . . 4. Nếu (1.3) thỏa mãn thì α là giá trị cần tìm: αk = α. Nếu (1.3) không thỏa mãn thì ta giảm α (bằng cách nhân α với một số λ ∈ (0, 1), chẳng hạn λ = 1/2) cho đến khi bất đẳng thức (1.3) được thỏa mãn. 1.3.2 Sự hội tụ của phương pháp Ta nói dãy {xk } hội tụ tới điểm x∗ với tốc độ hội tụ tuyến tính hay tốc độ hội tụ cấp số nhân (công bội q) nếu bắt đầu từ một chỉ số k nào đó ta có bất đẳng thức kxk+1 − x∗ k ≤ qkxk − x∗ k, 0 < q < 1. Cơ sở của việc lựa chọn α như trên và sự hội tụ của phương pháp đường dốc nhất cho trong định lý sau. Định lý 1.1. Giả sử hàm f (x) bị chặn dưới, gradient ∇f (x) thỏa mãn điều kiện Lipschitz k∇f (x) − ∇f (y)k ≤ Lkx − yk, ∀x, y ∈ Rn và αk được chọn theo thuật toán nêu trên. Khi đó, với bất kỳ điểm ban đầu x0 , quá trình lặp (1.2) có tính chất k∇f (xk )k → 0 khi k → ∞. Chứng minh. Theo định lý giá trị trung bình f (y) − f (xk ) = h∇f (x̄k ), x − xk i, trong đó x̄k = xk + θ(x − xk ) với θ ∈ [0, 1]. Do x − xk = −α∇f (xk ) nên ta có f (y) − f (xk ) = h∇f (xk ), x − xk i − h∇f (x̄k ) − ∇f (xk ), x − xk i 12 ≤ −αh∇f (xk ), ∇f (xk )i + αLkx̄k − xk k.k∇f (xk )k ≤ −αk∇f (xk )k2 + αLkx − xk k.k∇f (xk )k = αk∇f (xk )k2 (−1 + αL). Từ đánh giá đó suy ra rằng, nếu chọn α sao cho −1 + αL ≤ −ε hay α ≤ (1 − ε)/L thì bất đẳng thức (1.3) sẽ được thỏa mãn. Vậy việc chọn α theo thuật toán trên là có thể thực hiện được. Khi đã chọn αk như trên ta có f (xk+1 ) − f (xk ) ≤ −εαk k∇f (xk )k2 , (1.4) tức là với bất kỳ k thì f (xk+1 ) − f (xk ) < 0 (với điều kiện ∇f (xk ) 6= 0). Vì hàm f (x) bị chạn dưới, nên bất đẳng thức nhận được cho thấy f (xk+1 ) − f (xk ) → 0 khi k → ∞. (1.5) k∇f (xk )k2 ≤ [f (xk ) − f (xk+1 )]/(εαk ). (1.6) Từ (1.4) suy ra Chú ý là thuật toán chọn αk đảm bảo rằng với bất kỳ k sẽ có αk ≥ ᾱ > 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 (1.3) hay (1.4) được thỏa mãn với α = (1 − ε)/L). Từ (1.5), (1.6) và chú ý này suy ra k∇f (xk )k → 0 khi k → ∞. Định lý được chứng minh. Định lý 1.1 bảo đảm giá trị hàm mục tiêu hội tụ hoặc đến cận dưới inf f (x), hoặc tới giá trị của hàm tại điểm dừng nào đó (có thể là điểm cực tiểu địa phương hay điểm yên ngựa). Với những giả 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, ta có thể đánh giá được tốc độ của phương pháp gradient. Định lý 1.2. Giả sử f (x) hai lần khả vi liên tục và ma trận các đạo hàm bậc hai thỏa mãn điều kiện mkyk2 ≤ −h∇2 f (x)y, yi ≤ M kyk2 , M ≥ m > 0, (1.7) 13 với bất kỳ x, y ∈ Rn , còn dãy {xk } được xây dựng theo phương pháp (1.2), trong đó αk được chọn theo thuật toán đã mô tả. Khi đó với bất kỳ điểm ban đầu x0 , ta sẽ có xk → x∗ , f (xk ) → f (x∗ ), trong đó x∗ là điểm cực tiểu (duy nhất) của f (x). Đồng thời, ta có các đánh giá sau về tốc độ hội tụ của thuật toán: f (xk ) − f (x∗ ) ≤ q k [f (x0 ) − f (x∗ )], kxk − x∗ k ≤ Cq k/2 , C < ∞, 0 < q < 1. Chứng minh. Bất đẳng thức bên trái của điều kiện (1.7) đảm bảo hàm f (x) có cực tiểu và cực tiểu đó là duy nhất. Dùng công thức Taylor, ta nhận được 1 f (x∗ ) = f (x) + h∇f (x), x∗ − xi + h∇2 f (x̄)(x∗ − x), x∗ − xi. 2 Từ đó nhờ tính đến (1.7) ta có 1 f (x) − f (x∗ ) = h∇f (x), x − x∗ i − h∇2 f (x̄)(x∗ − x), x∗ − xi 2 m ≤ h∇f (x), x − x∗ i − kx − x∗ k2 2 m ≤ k∇f (x)k.kx − x∗ k − kx − x∗ k2 2 (1.8) Đồng thời (do ∇f (x∗ ) = 0) 1 f (x) − f (x∗ ) = h∇2 f (x̄)(x∗ − x), x∗ − xi. 2 Vì vậy theo giả thiết (1.7) m M kx − x∗ k2 ≤ f (x) − f (x∗ ) ≤ kx − x∗ k2 . 2 2 Sử dụng bất đẳng thức trái của (1.9) và ước lượng (1.8) ta có kx − x∗ k ≤ 1 k∇f (x)k m và từ bất đẳng thức phải của (1.9) suy ra kx − x∗ k ≥ 2 [f (x) − f (x∗ )]. M Dùng hai bất đẳng thức, ta đánh giá tiếp (1.8) f (x) − f (x∗ ) ≤ 1 m k∇f (x)k2 − [f (x) − f (x∗ )]. m M (1.9) 14 Từ đó m [f (x) − f (x∗ )]. M Sử dụng đánh giá này vào bất đẳng thức (1.4) ta nhận được k∇f (x)k2 ≥ m 1 + f (xk+1 ) − f (xk ) ≤ −εαk m 1 + m [f (x) − f (x∗ )]. M (1.10) (1.11) Với các điều kiện của định lý thì 1 f (x) − f (xk ) = h∇f (xk ), x − xk i + h∇2 f (x̄k )(x − xk ), x − xk i 2 2 α = −αk∇f (xk )k2 + h∇2 f (x̄k )∇f (xk ), ∇f (xk )i 2 αM  ≤ −α 1 − k∇f (xk )k2 . 2 Từ đó suy ra rằng bất đẳng thức (1.3) sẽ được thỏa mãn nếu chọn 1− αM  2(1 − ε) ≥ ε, tức là α ≤ ᾱ = . 2 M Khi đó, từ (1.11) suy ra f (xk+1 ) − f (x∗ ) ≤ [1 − εαk m 1 + trong đó q = 1 − εαk m 1 + m ][f (xk − f (x∗ ))] ≤ q[f (xk − f (x∗ ))], M m < 1, tức là M f (xk ) − f (x∗ ) ≤ q k [f (x0 ) − f (x∗ )]. (1.12) Do ᾱ = 2(1 − ε)/M , ta có 2ε(1 − ε)m m (1 + ). M M 1 Từ đó suy ra rằng giá trị cực tiểu của q đạt được khi ε = , đồng thời 2  m m qmin = 1 − 1+ 2M M 1 vì thế trong điều kiện (1.3) nên đặt ε = . 2 Đánh giá (1.12) cùng với vế trái của (1.9) cho phép khẳng định sự hội tụ và đánh q =1− giá tốc độ hội tụ của dãy {xk } tới điểm cực tiểu kxk − x∗ k ≤ 2 1/2 2 1/2 [f (xk ) − f (x∗ )]1/2 ≤ [f (x0 ) − f (x∗ )]1/2 q 1/2 ≤ Cq 1/2 . m m Định lý được chứng minh đầy đủ. 15 Qua chứng minh trên ta thấy rằng để thu được đánh giá (1.12) ta đã sử dụng các điều kiện (1.3), (1.10). Ta kết luận rằng lớp hàm có đánh giá (1.12) thực sự rộng hơn nhiều so với lớp hàm thỏa mãn điều kiện (1.7), vì đánh giá (1.12) đúng với mọi hàm thỏa mãn các điều kiện của Định lý 1.1 và điều kiện k∇f (x)k2 ≥ δ[f (x) − f (x∗ )], δ > 0. Thuật toán xác định α theo (1.3) thường được gọi là thuật toán quay lui (backtracking). 1.4 Kết luận Chương 1 Trong chương này chúng tôi đã trình bày các khái niệm cơ bản: 1. Không gian Euclid n chiều. 2. Bài toán đặt không chỉnh. 3. Phương pháp đường dốc nhất. Trong chương tiếp theo chúng tôi sử dụng các phương pháp trên cụ thể cho bài toán cực trị với ràng buộc là bài toán bù tổng quát.
- Xem thêm -

Tài liệu liên quan