Tài liệu Phương pháp gradient liên hợp và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM THỊ MINH THUẬN PHƯƠNG PHÁP GRADIENT LIÊN HỢP VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ TOÁN HỌC THÁI NGUYÊN - NĂM 2010 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC PHẠM THỊ MINH THUẬN PHƯƠNG PHÁP GRADIENT LIÊN HỢP VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ TOÁN HỌC Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60.46.36 Người hướng dẫn khoa học: GS. TS. TRẦN VŨ THIỆU THÁI NGUYÊN - NĂM 2010 i Mục lục Mở đầu 1 Cơ sở toán học của phương pháp và các khái niệm liên quan 1.1 Một số khái niệm và kết quả cơ bản của giải tích lồi . . . 1.2 Phương pháp hướng giảm . . . . . . . . . . . . . . . . . 1.2.1 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . 1.2.2 Hướng giảm . . . . . . . . . . . . . . . . . . . . . 1.2.3 Độ dài bước . . . . . . . . . . . . . . . . . . . . . 1.3 Phương pháp gradient . . . . . . . . . . . . . . . . . . . 1.3.1 Thuật toán gradient với thủ tục tìm chính xác theo tia . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Thuật toán gradient với thủ tục quay lui . . . . . 1.4 Phương pháp Newton . . . . . . . . . . . . . . . . . . . . 2 Phương pháp gradient liên hợp 2.1 Hướng liên hợp . . . . . . . . . . . . . . . . . . . . . . . 2.2 Phương pháp gradient liên hợp . . . . . . . . . . . . . . 2.2.1 Phương pháp Fletcher - Reeves tìm cực tiểu hàm toàn phương (F-R) . . . . . . . . . . . . . . . . . 2.2.2 Phương pháp Fletcher - Reeves tìm cực tiểu hàm khả vi liên tục bất kỳ . . . . . . . . . . . . . . . . 2.2.3 Một số ví dụ áp dụng . . . . . . . . . . . . . . . . 2.3 Tốc độ hội tụ của phương pháp gradient liên hợp . . . . 1 3 3 7 7 9 11 13 13 14 14 17 17 22 22 35 37 40 ii 3 Mở rộng phương pháp gradient liên hợp 3.1 Phương pháp gradient liên hợp 3-số hạng . . . . . . . . . 3.1.1 Thuật toán tái khởi Beale-Powell . . . . . . . . . 3.1.2 Tính hội tụ toàn cục của phương pháp gradient liên hợp 3-số hạng với thủ tục tìm theo tia kiểu Wolfe . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Phương pháp gradient liên hợp 3-số hạng Beale . 3.2 Phương pháp gradient liên hợp hiệu chỉnh trước chỉ số điều kiện . . . . . . . . . . . . . . . . . . . . . . . . . . . Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . Phụ lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 42 42 43 49 51 55 56 63 1 Mở đầu Trong thực tế rất nhiều hoạt động kinh tế, xã hội,... đòi hỏi con người phải quan tâm tới việc tìm phương án tốt nhất để đạt được mục tiêu mong muốn. Đó chính là các bài toán tối ưu. Các bài toán tối ưu là một chủ đề hấp dẫn với nhiều kết quả phong phú luôn thu hút sự quan tâm của các nhà nghiên cứu. Luận văn này đề cập tới phương pháp gradient liên hợp và ứng dụng của nó. Phương pháp gradient liên hợp được Hestenes và Stiefel nêu ra đầu tiên vào những năm 1950 để giải hệ tuyến tính. Vì việc giải một hệ tuyến tính tương đương với tìm cực tiểu của một hàm toàn phương xác định dương, nên vào năm 1960 Fletcher - Reeves đã cải biên và phát triển nó thành phương pháp gradient liên hợp cho cực tiểu không ràng buộc. Nhờ đó phương pháp này hoàn thiện phương pháp giảm nhanh nhất nhằm làm tăng hiệu quả và độ tin cậy của thuật toán. Phương pháp gradient liên hợp là trung gian giữa phương pháp gradient và phương pháp Newton, nó thay đổi hướng tìm trong phương pháp gradient bằng cách thêm vào một tỷ lệ dương của hướng dùng ở bước ngay trước đó. Phương pháp này chỉ cần tới đạo hàm riêng bậc nhất nhưng lại khắc phục được tính hội tụ chậm của phương pháp gradient. Mục tiêu của luận văn là tìm hiểu và trình bày những kết quả cơ bản đã biết liên quan đến phương pháp gradient liên hợp, các tính chất như tính liên hợp, tính trực giao, tính hội tụ và một số phương pháp mở rộng của phương pháp này. Nội dung đề cập trong luận văn được trình bày một cách chặt chẽ về mặt toán học kèm theo một số ví dụ minh họa. Luận văn được chia làm 3 chương: 2 Chương 1: nhắc lại một số khái niệm cơ bản của giải tích lồi, như tập lồi, hàm lồi và hàm toàn phương, hướng giảm và phương pháp gradient, phương pháp Newton... để phục vụ cho các chương tiếp theo. Chương 2: trình bày các khái niệm, tính chất của hướng liên hợp, phương pháp gradient liên hợp giải bài toán cực tiểu hàm toàn phương, nêu các định lý về tính hội tụ của phương pháp gradient liên hợp và mở rộng phương pháp này để tìm cực tiểu của một hàm khả vi liên tục bất kỳ. Cuối chương tác giả nêu ra một số ví dụ áp dụng. Chương 3: trình bày phương pháp gradient liên hợp 3-số hạng. Đó là sự cải tiến phương pháp F-R tìm cực tiểu hàm khả vi liên tục bất kỳ bởi vì nếu dùng hướng giảm nhanh nhất thì mức giảm hàm mục tiêu thường kém so với mức giảm có thể thu được khi không dùng tái khởi; còn nếu dùng hướng tái khởi tùy ý thì quan hệ liên hợp đòi hỏi có thể không còn đúng. Ngoài ra, trong chương này còn chỉ ra nguyên nhân làm cho phương pháp gradient liên hợp kết thúc sau nhiều hơn n lần lặp là do sai số trong quá trình tính toán và từ đó đưa ra biện pháp khắc phục tình trạng này. Các kết quả tính toán thử nghiệm được thực hiện bằng các chương trình lập trong môi trường Matlap. Mặc dù đã rất cố gắng, song bản luận văn không thể tránh khỏi những sai sót. Tác giả rất mong nhận được sự chỉ bảo, đóng góp của các Thầy Cô và các bạn đồng nghiệp để luận văn thêm hoàn thiện. Tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc đến Thầy hướng dẫn GS.TS Trần Vũ Thiệu đã tận tình hướng dẫn trong suốt quá trình làm luận văn. Tác giả cũng xin chân thành cảm ơn các Thầy Cô, các bạn bè, đồng nghiệp và gia đình luôn giúp đỡ, động viên, khích lệ trong suốt quá trình học tập và nghiên cứu. Thái Nguyên, ngày 18 tháng 09 năm 2010. Học viên Phạm Thị Minh Thuận 3 Chương 1 Cơ sở toán học của phương pháp và các khái niệm liên quan Trong chương này ta sẽ giới thiệu một số khái niệm và các kiến thức cơ bản sẽ dùng ở các chương sau. 1.1 Một số khái niệm và kết quả cơ bản của giải tích lồi Giải tích lồi đóng vai trò quan trọng trong việc nghiên cứu và xây dựng các thuật toán giải các bài toán tối ưu, trước hết ta sẽ nhắc lại các khái niệm tập lồi và hàm lồi. Định nghĩa 1.1 (Tập lồi). Cho hai điểm a, b ∈ Rn , tập tất cả các điểm x = (1 − λ)a + λb với 0 ≤ λ ≤ 1 gọi là đoạn thẳng đóng nối a và b và được kí hiệu là [a, b]. Tập C ∈ Rn được gọi là lồi nếu nó chứa mọi đoạn thẳng nối hai điểm bất kỳ thuộc nó. Nói cách khác, nếu (1 − λ)a + λb ∈ C, ∀a, b ∈ C và mọi 0 ≤ λ ≤ 1. Định nghĩa 1.2 (Hàm lồi). Hàm f : X → [−∞, +∞] xác định trên tập lồi X ⊆ Rn được gọi là lồi nếu f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) với bất kì x1 , x2 ∈ X và mọi số thực λ ∈ [0, 1]. 4 Ta gọi f là hàm lồi chặt trên tập lồi X nếu f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ)f (x2 ) với bất kì x1 , x2 ∈ X, x1 6= x2 và mọi số thực λ ∈ (0, 1). Hàm f (x) gọi là lõm (hay lõm chặt) trên X nếu −f (x) là lồi (lồi chặt) trên X. Định nghĩa 1.3. Cho hàm số f xác định trên tập mở X ⊆ Rn . Hàm f được gọi là liên tục tại điểm x0 ∈ X nếu với mọi ε > 0, tồn tại δ > 0 sao cho |f (x) − f (x0 )| < ε với mọi x ∈ X thỏa mãn k x − x0 k< δ. Nói cách khác, hàm f liên tục tại x0 ∈ X nếu với mọi dãy {xn } ⊂ X hội tụ đến x0 , ta có {f (xn )} → f (x0 ). Hàm f được gọi là nửa liên tục dưới (t.ư., nửa liên tục trên) tại điểm x0 ∈ X nếu tồn tại ε > 0, tồn tại δ > 0 sao cho f (x) ≥ f (x0 ) − ε (t.ư., f (x) ≤ f (x0 ) + ε) với mọi x ∈ X thỏa mãn k x − x0 k< δ. Nói cách khác, hàm f là nửa liên tục dưới (t.ư., nửa liên tục trên) tại điểm x0 ∈ X nếu với mọi dãy {xn } ⊂ X hội tụ đến x0 và dãy {f (xn )} ⊂ R hội tụ, ta có lim inf f (xn ) ≥ f (x0 ) (t.ư., lim sup f (xn ) ≤ f (x0 )). n→∞ n→∞ Rõ ràng, nếu f là nửa liên tục dưới tại x0 thì −f là nửa liên tục trên tại x0 . Hàm f vừa là nửa liên tục dưới vừa là nửa liên tục trên tại x0 thì liên tục tại điểm đó. Hàm f được gọi là liên tục (t.ư., nửa liên tục dưới, nửa liên tục trên) trên Xnếu nó liên tục (t.ư., nửa liên tục dưới, nửa liên tục trên) tại mọi điểm của X. Định nghĩa 1.4. Giả sử f : Rn → [−∞, +∞] là hàm số tùy ý và C ⊂ Rn là tập tùy ý. Điểm x0 ∈ C ∩ domf được gọi là điểm cực tiểu toàn cục của f (x) trên C nếu −∞ < f (x0 ) ≤ f (x) với mọi x ∈ C. 5 Điểm x0 ∈ C được gọi là điểm cực tiểu địa phương của f (x) trên C, nếu tồn tại lân cận U (x0 ) của x0 sao cho −∞ < f (x0 ) ≤ f (x) với mọi x ∈ C ∩ U (x0 ). Các khái niệm cực đại địa phương và cực đại toàn cục được định nghĩa tương tự. Đối với hàm f tùy ý trên tập C, ta ký hiệu tập tất cả các điểm cực tiểu (cực đại) toàn cục của f trên C là Argmin f (x) (Argmax f (x)). x∈C x∈C Định nghĩa 1.5. Cho A là ma trận vuông cấp n không suy biến. Giá trị của tích k A k . k A−1 kđược gọi là chỉ số điều kiện của A và ký hiệu là cond(A). Nhận xét 1.1. Chỉ số điều kiện của A luôn lớn hơn hay bằng 1. Thật vậy, 1 =k AA−1 k≤k A k . k A−1 k= cond(A). Định nghĩa 1.6. Cho dãy {xk } ⊂ Rn hội tụ đến x∗ ∈ Rn . Dãy {xk } gọi là: hội tụ đến x∗ với tốc độ tuyến tính nếu ∃γ ∈ [0, 1), ∃k0 sao cho ∀k > k0 :k xk+1 − x∗ k≤ γ k xk − x∗ k, hội tụ đến x∗ với tốc độ trên tuyến tính nếu ∀k :k xk+1 − x∗ k≤ ck k xk − x∗ k và ck → 0, hội tụ đến x∗ với tốc độ hội tụ bậc hai nếu ∃γ > 0, ∃k0 sao cho k xk+1 − x∗ k≤ γ k xk − x∗ k2 , ∀k > k0 . Mệnh đề 1.1. Cho hàm f xác định trên Rn và điểm x0 ∈ Rn . Nếu f khả vi tại x0 thì f 0 (x0 , d) = h∇f (x0 ), di, ∀d ∈ Rn \ {0}. Chứng minh. Vì f khả vi tại x0 nên với mọi d ∈ Rn \ {0} ta có f (x0 + td) − f (x0 ) − h∇f (x0 ), tdi lim = 0. t→0+ tkdk 6 Do đó f 0 (x0 , d) − h∇f (x0 ), di = 0, kdk và ta nhận được điều phải chứng minh. Nhận xét. Đặt ϕ(t) := f (x0 + td). Khi đó, theo định nghĩa ta có ϕ(t) − ϕ(0) dϕ(t) ¯¯ f (x0 + td) − f (x0 ) 0 ϕ (0) = = lim+ = f 0 (x0 , d). ¯ = lim t→0 dt t=0 t→0 t t Như vậy, đạo hàm theo hướng của f tại x0 phản ánh tốc độ biến thiên của f tại x0 theo hướng đó. Hơn nữa, theo bất đẳng thức CauchyBunjakowski-Schwarz trong tất cả các hướng d ∈ Rn có k d k= 1, ta có |h∇f (x0 ), di| ≤k ∇f (x0 ) kk d k=k ∇f (x0 ) k ⇒ − k ∇f (x0 ) k≤ h∇f (x0 ), di ≤k ∇f (x0 ) k . Do đó, đạo hàm theo hướng của f tại x0 đã cho là lớn nhất khi hướng ∇f (x0 ) ∇f (x0 ) d= và nhỏ nhất khi d = − . k ∇f (x0 ) k k ∇f (x0 ) k Định lí 1.1 (xem [1]). Cho f là hàm khả vi hai lần trên tập lồi mở X ⊆ Rn . Khi đó, i) Hàm f là lồi trên X khi và chỉ khi ma trận Hessian ∇2 f (x) là nửa xác định dương trên X, tức là với mỗi x ∈ X, y T ∇2 f (x)y ≥ 0, ∀y ∈ Rn . Hàm f là lồi chặt trên X nếu ∇2 f (x) xác định dương trên X, tức là với mỗi x ∈ X, y T ∇2 f (x)y > 0, ∀y ∈ Rn \{0}. ii) Hàm f là lõm trên X khi và chỉ khi ma trận Hessian ∇2 f (x) là nửa xác định âm trên X, tức là với mỗi x ∈ X, y T ∇2 f (x)y ≤ 0, ∀y ∈ Rn . 7 Hàm f là lõm chặt trên X nếu ∇2 f (x) xác định âm trên X, tức là với mỗi x ∈ X, y T ∇2 f (x)y < 0, ∀y ∈ Rn \{0}. Hệ quả 1.1. Cho hàm toàn phương 1 f (x) = hx, Qxi + hx, ai + b, 2 trong đó Q là ma trận đối xứng cấp n × n. Khi đó: i) f là hàm lồi (t.ư., lồi chặt) trên Rn khi và chỉ khi Q là ma trận nửa xác định dương (t.ư., xác định dương). ii) f là hàm lõm (t.ư., lõm chặt) trên Rn khi và chỉ khi Q là ma trận nửa xác định âm (t.ư., xác định âm). 1.2 Phương pháp hướng giảm Xét bài toán tối ưu không ràng buộc minf (x) v.đ.k x ∈ Rn , (1.1) trong đó f : Rn → R là một hàm phi tuyến, khả vi trên Rn . 1.2.1 Điều kiện tối ưu Định lí 1.2 (Điều kiện cần cấp 1). Cho hàm f xác định, khả vi trên Rn . Nếu x∗ ∈ Rn là nghiệm cực tiểu địa phương của bài toán (1.1) thì ∇f (x∗ ) = 0. Chứng minh. Theo mệnh đề 1.1 và do x∗ là nghiệm cực tiểu địa phương nên f (x∗ + td) − f (x∗ ) f (x , d) = lim+ = h∇f (x∗ ), di ≥ 0, ∀d ∈ Rn . t→0 t 0 ∗ Suy ra ∇f (x∗ ) = 0. Điểm x∗ ∈ Rn thỏa mãn điều kiện ∇f (x∗ ) = 0 được gọi là điểm dừng của hàm f . 8 Định lí 1.3. Giả sử f là hàm lồi khả vi trên Rn . Khi đó, x∗ ∈ Rn là nghiệm cực tiểu toàn cục của bài toán (1.1) khi và chỉ khi ∇f (x∗ ) = 0. Chứng minh. Theo định lý trên, ta chỉ cần chứng minh rằng nếu ∇f (x∗ ) = 0 thì x∗ là nghiệm cực tiểu toàn cục của bài toán (1.1). Thật vậy, do f là hàm lồi khả vi trên Rn nên nó có đạo hàm theo mọi hướng d ∈ Rn tại x∗ . Khi đó, h∇f (x∗ ), di = f 0 (x∗ , d) ≤ f (x∗ + d) − f (x∗ ), ∀d ∈ Rn . Do đó, với điểm bất kỳ x ∈ Rn , ta có 0 = h∇f (x∗ ), x − x∗ i ≤ f (x∗ + (x − x∗ )) − f (x∗ ) = f (x) − f (x∗ ). Suy ra f (x∗ ) ≤ f (x) ∀x ∈ Rn , tức x∗ là điểm cực tiểu của f trên Rn . Định lí 1.4 (Điều kiện cấp 2). Giả sử hàm f khả vi liên tục hai lần trên Rn . Khi đó: i) Nếu x∗ ∈ Rn là điểm cực tiểu địa phương của f trên Rn thì ∇f (x∗ ) = 0 và ∇2 f (x∗ ) nửa xác định dương. ii) Nếu ∇f (x∗ ) = 0 và ∇2 f (x∗ ) xác định dương thì x∗ là điểm cực tiểu địa phương chặt của f trên Rn . Chứng minh. i) Với mọi d ∈ Rn mà 0 0 với mọi d ∈ Rn . Vì các thành phần của ∇2 f (x) là các hàm liên tục tại x∗ nên dT ∇2 f (x)d cũng là hàm liên tục tại x∗ . Do đó ta có dT ∇2 f (ξ)d > 0 với mọi ξ sao cho k ξ − x∗ k< ε với ε đủ nhỏ. Theo khai triển Taylo (1.2) của f tại x∗ , ta có thể chọn ε đủ nhỏ sao cho f (x∗ + d) > f (x∗ ) với mọi 0 0, k := 0. Tính ∇f (x0 ). Bước 2. Nếu k ∇f (x0 ) k< ε. Dừng. Trái lại đi đến bước 3. Bước 3. Xác định xk+1 := xk + tk dk sao cho f (xk+1 ) < f (xk ). Bước 4. Đặt k := k + 1 quay trở lại bước 1. 10 Trong thuật toán trên, dk ∈ Rn là hướng giảm của f tại xk và số thực tk > 0 là độ dài bước. Sau đây ta sẽ giới thiệu về hướng giảm và các cách xác định độ dài bước. Định nghĩa 1.7 (Hướng giảm). Cho x0 ∈ Rn . Ta gọi d ∈ Rn là hướng giảm của hàm f tại x0 nếu tồn tại ε > 0 sao cho với mọi t thoả mãn 0 < t < ε ta có f (x0 + td) < f (x0 ). Mệnh đề 1.2. Cho hàm f khả vi trên Rn , điểm x0 ∈ Rn và hướng d ∈ Rn . Nếu h∇f (x0 ), di < 0 thì d là hướng giảm của f tại x0 . Chứng minh. Vì hàm f khả vi tại x0 theo mệnh đề 1.1 và giả thiết của mệnh đề 1.2, ta có f (x0 + td) − f (x0 ) f (x , d) = lim+ = h∇f (x0 ), di < 0. t→0 t 0 0 Do đó, f (x0 + td) − f (x0 ) < 0 với t đủ nhỏ. Mệnh đề 1.3. Cho hàm lồi f khả vi trên Rn , điểm x0 ∈ Rn và hướng d ∈ Rn . Khi đó, h∇f (x0 ), di < 0 khi và chỉ khi d là hướng giảm của f tại x0 . Chứng minh. Theo mệnh đề 1.2 ta chỉ cần chứng minh điều kiện cần. Giả sử d ∈ Rn là hướng giảm của f tại x0 , tức là ∃ε > 0 sao cho f (x0 + td) < f (x0 ), ∀t : 0 < t < ε. (1.4) Vì hàm f lồi khả vi trên Rn và hàm f có đạo hàm theo mọi hướng d tại điểm x0 ∈ Rn và f (x0 + td) − f (x0 ) ≥ f 0 (x0 , td) = h∇f (x0 ), tdi = th∇f (x0 ), di. Kết hợp điều này và (1.4) với 0 < t < ε ta có h∇f (x0 ), di ≤ f (x0 + td) − f (x0 ) < 0. t Hệ quả 1.2. Cho hàm f khả vi trên Rn và điểm x0 ∈ Rn . Nếu ∇f (x0 ) 6= 0 thì d = −∇f (x0 ) là một hướng giảm của f tại x0 . 11 1.2.3 Độ dài bước Giả sử đã biết hướng giảm dk của hàm f tại xk theo lược đồ chung của phương pháp hướng giảm, điểm lặp tiếp theo được xác định bởi xk+1 := xk + tk dk , với tk là một số thực dương. Như vậy, xk+1 là một điểm nằm trên tia {xk + tdk , t > 0}, tk > 0 thông thường có hai cách lựa chọn tk ứng với hai thủ tục tìm chính xác theo tia và thủ tục quay lui. a. Thủ tục tìm chính xác theo tia Cho điểm xk ∈ Rn và hướng giảm dk của hàm f tại xk . Thủ tục này chọn độ dài bước chính xác tk > 0 là nghiệm cực tiểu của hàm f theo tia {xk + tdk , t ≥ 0}. Đặt ϕk (t) := f (xk + tdk ). Khi đó, tk là nghiệm cực tiểu của hàm một biến ϕk (t) với t ≥ 0, tức tk = argmin{ϕk (t)|t ≥ 0}. Mệnh đề 1.4. Cho hàm toàn phương lồi chặt 1 f (x) = xT Ax − bT x + c, 2 trong đó A là ma trận cấp n × n, đối xứng, xác định dương, vectơ b ∈ Rn và c ∈ R. Cho xk ∈ Rn và hướng giảm dk của hàm f tại xk . Khi đó, độ dài bước chính xác tk được xác định bởi (Axk − b)T dk > 0. tk = − (dk )T Adk Chứng minh. Vì f (x) là hàm lồi nên ϕk (t) = f (xk + tdk ) là hàm lồi một biến. Nếu tk là điểm cực tiểu của hàm ϕk (t) thì ϕ(tk + t) − ϕ(tk ) dϕ(t) ¯¯ 0 = lim ϕk (t)|t=tk = ¯ dt t=tk t→0 t k f ((x + tk dk ) + tdk ) − f (xk + tk dk ) = lim+ t→0 t 0 k = f ((x + tk dk ), dk ) = h∇f (xk+1 ), dk i = 0. 12 Vì ∇f (x) = Ax − b nên h∇f (xk+1 ), dk i = hA(xk + tk dk ) − b, dk i = hAxk − b, dk i + tk hAdk , dk i = 0. Do dk là hướng giảm của hàm f tại xk và f (x) là hàm lồi nên theo mệnh đề 1.3 h∇f (xk ), dk i = hAxk −b, dk i < 0. Hơn nữa, vì A là xác định dương nên (Axk − b)T dk T hAdk , dk i = (dk ) Adk > 0 ⇒ tk = − > 0. (dk )T Adk b. Thủ tục quay lui. Mệnh đề sau là cơ sở của thủ tục quay lui xác định điểm xk+1 khi đã biết hướng giảm dk của hàm f tại xk . Mệnh đề 1.5. Cho hàm f khả vi trên Rn , điểm xk ∈ Rn và vectơ dk ∈ Rn thoả mãn h∇f (xk ), dk i < 0. Cho số thực m1 ∈ (0, 1). Khi đó ∃t0 sao cho f (xk + tdk ) ≤ f (xk ) + m1 th∇f (xk ), dk i, ∀t ∈ (0, t0 ]. Chứng minh. Vì h∇f (xk ), dk i < 0 nên dk là hướng giảm của f tại xk . Theo mệnh đề 1.1 ta có f (xk + tdk ) − f (xk ) f (x , dk ) = lim+ = h∇f (xk ), dk i, t→0 t 0 k nên lim+ t→0 f (xk + tdk ) − f (xk ) = 1 > m1 . th∇f (xk ), dk i Do đó, tồn tại số thực t0 > 0 đủ nhỏ sao cho với mọi t ∈ (0, t0 ] ta có f (xk + tdk ) − f (xk ) ≥ m1 . th∇f (xk ), dk i Kết hợp với giả thiết h∇f (xk ), dk i < 0 ta có điều phải chứng minh. Điều kiện f (xk + tk dk ) ≤ f (xk ) + m1 tk h∇f (xk ), dk i với m1 ∈ (0, 1) và tk > 0 được gọi là điều kiện Armijo. 13 1.3 Phương pháp gradient Đây là phương pháp thông dụng để giải bài toán cực tiểu không ràng buộc vì nó đơn giản và có thể áp dụng cho những lớp hàm rất rộng. Ý tưởng của phương pháp này như sau: tại mỗi bước lặp k ta chọn hướng giảm dk của hàm f tại xk là dk = −∇f (xk ). Đây chính là hướng mà theo đó hàm mục tiêu f giảm nhanh nhất tại xk . Vì vậy người ta còn gọi phương pháp gradient là phương pháp giảm nhanh nhất. 1.3.1 Thuật toán gradient với thủ tục tìm chính xác theo tia Trong thuật toán này, tại mỗi bước lặp k điểm lặp tiếp theo được xác định bởi xk+1 := xk − tk ∇f (xk ) trong đó tk là nghiệm cực tiểu của hàm một biến ϕ(t) := f (xk −t∇f (xk )) với t > 0. Thuật toán 1.2 (Thuật toán gradient với thủ tục tìm chính xác theo tia). Bước 1. Cho một điểm x0 ∈ Rn , ε > 0, k := 0. Tính ∇f (x0 ). Bước 2. Nếu k ∇f (x0 ) k< ε, dừng. Trái lại, đi đến bước 3. Bước 3. Xác định xk+1 := xk − tk ∇f (xk ), trong đó tk = argmin{ϕk (t)}. Bước 4. Tính ∇f (xk+1 ). Bước 5. Đặt k := k + 1 quay trở lại bước 2. Định lí 1.5 (xem [1]). Cho x0 ∈ Rn và hàm f khả vi liên tục trên Rn và có tập mức dưới {x ∈ Rn |f (x) ≤ f (x0 )} bị chặn. Khi đó, mỗi điểm tụ x∗ của dãy {xk } được chọn như trong thuật toán trên thoả mãn ∇f (x∗ ) = 0. 14 1.3.2 Thuật toán gradient với thủ tục quay lui Trong thuật toán này, tại mỗi bước lặp k điểm lặp tiếp theo được xác định bởi xk+1 := xk − tk ∇f (xk ), trong đó tk là giá trị đầu tiên trong dãy t, λt, λ2 t, λ3 t, ... thoả mãn f (xk+1 )−f (xk ) ≤ −εtk k ∇f (xk ) k2 , trong đó t > 0, ε ∈ (0, 1), λ ∈ (0, 1). Thuật toán 1.3 (Thuật toán gradient với thủ tục quay lui). Bước 1. Cho một điểm x0 ∈ Rn , ε > 0, k := 0, chọn m1 ∈ (0, 1), α ∈ (0, 1). Tính ∇f (x0 ), nếu k ∇f (x0 ) k< ε. Dừng. Trái lại, đến bước 2. Bước 2. Đặt tk := 1. Bước 3. Tính xk+1 := xk − tk ∇f (xk ) và f (xk+1 ). Bước 4. Nếu f (xk+1 ) − f (xk ) ≤ m1 tk h∇f (xk ), −∇f (xk )i = −m1 tk k ∇f (xk ) k2 thì chuyển sang bước 5. Trái lại, tk := αtk quay trở về bước 3. Bước 5. Tính ∇f (xk+1 ). Bước 6. Nếu k ∇f (xk+1 ) k< ε, dừng. Trái lại, đặt k := k + 1 quay trở về bước 1. Định lí 1.6 (xem [1]). Giả sử rằng f bị chặn dưới và gradient ∇f (x) là Lipschitz, tức là: ∃L > 0 :k ∇f (x) − ∇f (y) k≤ L k x − y k ∀x, y. Khi đó, với bất kỳ điểm xuất phát x0 , dãy {xk } được chọn theo thuật toán gradient với thủ tục quay lui hội tụ theo nghĩa ∇f (xk ) → 0 khi k → +∞. 1.4 Phương pháp Newton Phương pháp Newton giải bài toán tối ưu không ràng buộc (1.1) với hàm phi tuyến khả vi hai lần trên Rn chính là việc ứng dụng phương pháp 15 Newton cổ điển giải hệ phương trình phi tuyến n ẩn, n phương trình để tìm điểm dừng của hàm f , tức là giải hệ phương trình ∇f (x) = 0. Trước hết ta nhắc lại định nghĩa hàm vectơ. Hàm vectơ F là một ánh T xạ F : Rn → Rm trong đó F (x) = (f1 (x) f2 (x) · · · fm (x)) , trong đó fi : Rn → R, i = 1, ..., m là các hàm n biến. Giả thiết rằng các hàm tọa ∂fi độ fi có các đạo hàm riêng . Khi đó, ma trận ∂xj  ∂f  ∂f1 1 · · · ∂xn  ∂x1  DF (x) =  ... · · · ...  ∂fm ∂fm ∂x1 · · · ∂xn được gọi là ma trận Jacobian của f tại x. Xét hệ phương trình n ẩn, n phương trình F (x) = 0 (1.5) trong đó F (x) là hàm vectơ. Giả sử x∗ ∈ Rn là nghiệm của hệ phương trình (1.5). Thuật toán Newton giải hệ (1.5) cũng xuất phát từ một điểm x0 ∈ Rn đủ gần nghiệm x∗ và xây dựng một dãy điểm x1 , x2 , ... hội tụ đến nghiệm x∗ . Tại điểm xk ∈ Rn thuộc dãy này, khai triển Taylor của F tại xk là F (xk + p) = F (xk ) + DF (xk )p + o(k p k), trong đó vectơ p ∈ Rn có k p k đủ nhỏ, DF (xk ) là ma trận Jacobian của F tại điểm xk ∈ Rn và o(k p k) là vô cùng bé so với chuẩn k p k khi p → 0. Khi đó xấp xỉ Taylor bậc nhất hàm F tại xk là F (xk + p) ≈ F (xk ) + DF (xk )p. Giả sử ma trận Jacobian DF (xk ) không suy biến. Giải hệ phương trình F (xk ) + DF (xk )p = 0 ta được vectơ p = −[DF (xk )]−1 F (xk ) 16 và điểm lặp tiếp theo là xk+1 := xk + p = xk − [DF (xk )]−1 F (xk ). Đặt xk := xk+1 và lặp lại quá trình tính toán đối với điểm xk mới.