›
›

Bài giảng Tối ưu - Chương 3: Bài toán quy hoạch phi tuyến tính không ràng buộc

pdf 66 trang ngocly 2580
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tối ưu - Chương 3: Bài toán quy hoạch phi tuyến tính không ràng buộc", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toi_uu_chuong_3_bai_toan_quy_hoach_phi_tuyen_tinh.pdf

Nội dung text: Bài giảng Tối ưu - Chương 3: Bài toán quy hoạch phi tuyến tính không ràng buộc

  1. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 1
  2. NỘI DUNG 1. Bài toán QHPT không ràng bu ộc. 2. Điều ki ện tối ưu. 3. Một số ph ương pháp gi ải bài toán QHPT không ràng bu ộc. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 2
  3. Bài toán Quy ho ạch phi tuy ến không ràng bu ộc có dạng: (Pkrb ) min{(): f x x ∈ ℝ n }, trong đó f :ℝℝn → là hàm phi tuy ến. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 3
  4. I. Đi ều ki ện tối ưu Đị nh lý 1(Điều ki ện bậc nh ất) Cho hàm f xác đị nh, khả vi trênℝn . Nếu x* ∈ℝn là nghi ệm cực ti ểu đị a ph ương của bài toán thì ∇f( x * ) = 0. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 4
  5. Đị nh lý 2 Gi ả sử f là hàm lồi khả vi trênℝn . Khi đó, x* ∈ℝn là nghi ệm cực ti ểu toàn cục của bài toán (Pkrb ) khi và ch ỉ khi ∇f( x * ) = 0. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 5
  6. Đị nh lý 3 (Điều ki ện bậc hai) Gi ả sử hàm f khả vi liên tục hai lần trênℝn . Khi đó: i) Nếux* ∈ℝn là điểm cực ti ểu đị a ph ương của f trênℝn thì ∇f( x * ) = 0 và∇2f( x * ) nửa xác đị nh dương ; ii) Ng ược lại , nếu ∇f( x * ) = 0 và∇2f( 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ℝn . 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 6
  7. Ví dụ1: Cho hàm số =3 x2 − x 2 + 3 fxx(12 , ) e 3 xe 1 x 1 Ta có : −3ex2 + 3 x 2  ∇f( x ) = 1  3x2− x 2  3e 3 x1 e  6x− 3 e x2  ∇2 f( x ) =1  −x23 x 2 − x 2 3e 9 e 3 xe1  10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 7
  8. II. Phương pháp hướng gi ảm 1. Ý tưởng 2. Lược đồ chung 3. Đị nh nghĩa hướng gi ảm 4. Xác đị nh độ dài bước + Thủ tục tìm chính xác theo tia + Thủ tục quay lui 5. Tốc độ hội tụ Tuyến tính; Trên tuyến tính; Bậc 2 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 8
  9. 1. Ý tưởng 2. Lược đồ chung 3. Đị nh ngh ĩa hướng gi ảm 4. Xác đị nh độ dài bước + Th ủ tục tìm chính xác theo tia + Th ủ tục quay lui 5. Tốc độ hội tụ Tuy ến tính; Trên tuy ến tính; Bậc 2 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 9
  10. Ý tưởng: Xu ất phát từ một điểm bất kỳ x0 ∈ℝn , ta xây dựng một dãy điểmx1, x 2 , , x k , saocho fx(0 )≥ fx () 1 ≥ fx ( 2 ) ≥ ≥ fx (k ) và dãy{x k } hội tụ đế n điểm dừngx* ∈ℝn của hàm f . (∇f( x * ) = 0) 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 10
  11. 1. Ý tưởng 2. Lược đồ chung 3. Đị nh ngh ĩa hướng gi ảm 4. Xác đị nh độ dài bước + Th ủ tục tìm chính xác theo tia + Th ủ tục quay lui 5. Tốc độ hội tụ Tuy ến tính; Trên tuy ến tính; Bậc 2 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 11
  12. Lược đồ chung của phương pháp hướng gi ảm Bước kh ởi đầ u. Xu ất phát từ một điểm tùy ý x 0 ∈ ℝ n Gán k:= 0; Bước lặp k, (k=0,1,2, ) k (k 1 ) If x th ỏa mãn điều ki ện dừng Then dừng thu ật toán k+1 = k + k Else xác đị nhx x tk d saocho fx(k+1 )< fx () k = + (k 2 ) Gánk: k 1; Quay lại bước lặp k. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 12
  13. 1. Ý tưởng 2. Lược đồ chung 3. Đị nh nghĩa hướng gi ảm 4. Xác đị nh độ dài bước + Th ủ tục tìm chính xác theo tia + Th ủ tục quay lui 5. Tốc độ hội tụ Tuy ến tính; Trên tuy ến tính; Bậc 2 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 13
  14. Hướng gi ảm Đị nh nghĩa: Cho x 0 ∈ ℝ n . Ta nóid ∈ℝn là hướng gi ảm của hàm f tạix0 nếu tồn tạiε > 0 saocho với mọi t th ỏa mãn 0 <t < ε ta có f( x0+ td ) < f () x 0 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 14
  15. Mệnh đề 1. Cho f khả vi trênℝn , điểmx0 ∈ℝn , và hướng d ∈ℝn Nếu∇f( x0 ), d < 0 thì d là hướng gi ảm của f tạix 0 . Mệnh đề 2. Cho hàm lồi f khả vi trênℝn , điểmx0 ∈ℝn và hướngd ∈ℝn . Khi đó, ∇ f ( x 0 ), d < 0 khi và chi khi d là hướng gi ảm củaf tạix 0 . 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 15
  16. Hệ quả 1.Cho hàm f kh ả vi trênℝn và điểm x0 ∈ℝn Nếu∇f( x 0 ) ≠ 0 thìd=−∇ f( x 0 ) là một hướng gi ảm của f tạix 0 . Mệnh đề 3. Gi ả sử hàm f kh ả vi trên ℝn và ∇f( x 0 ) ≠ 0 .Trong các hướng gi ảm d của hàm f tạix 0 có d =1 thì hàm f gi ảm nhanh nh ất theo hướng ∇f( x 0 ) d = − ∇f( x 0 ) 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 16
  17. 1. Ý tưởng 2. Lược đồ chung 3. Đị nh ngh ĩa hướng gi ảm 4. Xác đị nh độ dài bước + Th ủ tục tìm chính xác theo tia + Th ủ tục quay lui 5. Tốc độ hội tụ Tuy ến tính; Trên tuy ến tính; Bậc 2 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 17
  18. Xác đị nh độ dài bước (tk ) i) Thủ tục tìm chính xác theo tia : =ϕ =k + k > tkargmin{ k ( tfxtdt ): ( ): 0} 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 18
  19. Mệnh đề 4. Cho hàm toàn ph ương lồi chặt 1 fx( )= xAxbxT − T + c , 2 n trong đó, A n × n đố i xứng, xác đị nh dương, b∈ℝ và c∈ℝ. Cho x k ∈ ℝ n và hướng gi ảm d k của hàm k f tạix . Khi đó, độ dài bước chính xác tk được xác đị nh bởi (Axk− b ) T d k t = − > 0 k (dk ) T Ad k 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 19
  20. ii) Th ủ tục quay lui + (xác đị nhxk 1 khi đã bi ếtd k ) Mệnh đề 5. Cho hàm f kh ả vi trênℝn , điểm xk∈ℝ n và véct ơ dk∈ℝ n th ỏa mãn ∇f( xk ), d k kk + ≤ k + ∇ kk ∀ ∈ t0 0:( fxtd ) fx () mtfxd1 (), , t (0,]. t 0 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 20
  21. Th ủ tục quay lui (Quy tắc Armijo) Đầ u vào: điểmxk∈ℝ n và hướng gi ảmd k của hàm f tạixk ; k+1 k+ k > Đầ u ra: điểmx trên tia x tdk, t k 0 th ỏa mãn fx(k+1 )< fx () k ∈ α∈ - Bước 1: Tùy ch ọnm1 (0,1) và(0,1) (ch ẳng α = = hạn1/2 ). Đặ t tk : 1; k+1 = k + k k +1 - Bước 2: Tínhx: x tdk và f( x ); k+1 ≤ k + ∇ kk - Bước 3: If fx() fx () mt1 k fxd (), Then dừng th ủ tục(tacóxk+1 ). 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 21
  22. = α Else t k : t k và quay về Bước 2. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 22
  23. 1. Ý tưởng 2. Lược đồ chung 3. Đị nh ngh ĩa hướng gi ảm 4. Xác đị nh độ dài bước + Th ủ tục tìm chính xác theo tia + Th ủ tục quay lui 5. Tốc độ hội tụ Tuy ến tính; Trên tuy ến tính; Bậc 2 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 23
  24. Tốc độ hội tụ Đị nh nghĩa. Cho dãy{xk } ⊂ ℝ n hội tụ đế n x* ∈ℝn Dãy {xk } được gọi là: ° Hội tụ đế nx* với tốc độ tuy ến tính nếu ∃ k+1 − * ≤ γ k − * 01k0 sao cho k k 0 : x x x x ; ° Hội tụ đế nx* với tốc độ trên tuy ến tính nếu ∀k+1 −≤ * k − * → kx: x cxxk ; và ck 0 ; ° Hội tụ đế nx* với tốc độ hội tụ bậc hai nếu ∃γ > ∃k+1 − * ≤ γ k − * 2 ∀ > 0,kx0 : x xx kk 0 . 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 24
  25. Phương pháp Gradient (tại mỗi bước lặp k, ch ọn hướng gi ảmdk= −∇ f( x k ) ) Thuật toán 1(TT Gradient với th ủ tục tìm chính xác theo tia) Bước kh ởi đầ u. Ch ọn tr ước sốε >0 đủ nh ỏ. Xu ất phát từ một điểm tùy ý x 0 ∈ ℝ n có∇f( x 0 ) ≠ 0 ; Đặ t k := 0; Bước lặp k (k=0,1,2, ) k+1 = k − ∇ k (k1 ) Tínhx: x tfxk (), trong đó =ϕ =k − ∇ k > tkargmin{ k (): tfxtfxt ( ( )), 0} 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 25
  26. ∇ k+1 (k2 ) Tính f( x ); ∇k+1 ≤ ε (k3 ) Iff( x ) Then dừng thu ật toán + (lấy điểm dừngx*≈ x k 1 ) Else, k : = k + 1 và quay lại Bước lặp k. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 26
  27. Đị nh lý 4 (Đị nh lý hội tụ) Cho x 0 ∈ ℝ n và hàm f kh ả vi liên tụctrênℝn vàcó tập mức dưới{x∈ℝn :() fx ≤ fx ()}0 bị ch ặn. Khi đó, mỗi điểm tụ x* của dãy {xk } được ch ọn nh ư trong Thuật toán 1 th ỏa mãn ∇f( x * ) = 0. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 27
  28. Thuật toán 2 (TT Gradient với th ủ tục quay lui) Bước kh ởi đầ u. ∈ α ∈ ε > Tùy ch ọnm1 (0,1) và(0,1) . Ch ọn số th ực 0 đủ nh ỏ. Xu ất phát từ một điểm tùy ý x 0 ∈ ℝ n có ∇f( x 0 ) ≠ 0. Đặ t k := 0; Bước lặp k ( k=0,1,2, ) = (k1 ) Đặ t tk : 1; k+1 = k − ∇ k k+1 (k2 ) Tínhx: x tfxk ( ) và f( x ); (k3 ) If kk+1 − ≤ ∇ kk −∇ = − ∇ k 2 fx()() fx mt1k fx (,() fx mt 1 k fx () 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 28
  29. Then chuy ển sang Bước (k4 ); = α Else t k : t k và quay về Bước (k2 ); ∇ k +1 (k4 ) Tính f( x ); ∇k +1 < ε (k5 ) If f ( x ) Then dừng thu ật toán (lấy x*≈ x k+ 1 ) Else k : = k + 1, quay về Bước lặp k. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 29
  30. Đị nh lý 5 (Đị nh lý hội tụ) Gi ả sử hàm f bị ch ặn dưới , Gradient ∇ f ( x ) th ỏa mãn điều ki ện Lipschitz, tức tồn tại L > 0 sao cho ∇fx() −∇ fy () ≤ Lxy − ,, ∀ xy ∈ℝn Khi đó, với bất kỳ điểm xu ấtphátx0 , dãy {xk } được ch ọn nh ư trong Thuật toán 2 có tính ch ất k ∇f( x ) → 0 khi k → ∞ . 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 30
  31. Ví dụ: Xétbàitoán(Pkrb ) với hàm mục tiêu =3 + 2 − − + f( x12 , x ) x 12 x 3 x 1 2 x 2 12 i) Điều ki ện tối ưu; ii) Thu ật toán Gradient với th ủ tục tìm chính xác theo tia(x0 =(1,2) ) ; iii) Thu ật toán Gradient với th ủ tục quay lui ( x0 =(1,2)) . 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 31
  32. Phương pháp Newton 1. Ph ương pháp Newton cổ điển 2. Ph ương pháp Newton thu ần túy 3. Ph ương pháp Newton với bước điều ch ỉnh 4. Ph ương pháp tựa Newton 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 32
  33. Ph ương pháp Newton gi ải bài toán (Pkrb ) min{f ( x ) : x ∈ℝn }, với hàm mục tiêu phi tuy ến f khả vi hai lần trên ℝn, chính là gi ải hệ ph ương trình ∇f( x ) = 0 ( 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 ). 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 33
  34. 1. Phương pháp Newton cổ điển 2. Ph ương pháp Newton thu ần túy 3. Ph ương pháp Newton với bước điều ch ỉnh 4. Ph ương pháp tựa Newton 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 34
  35. Phương pháp Newton cổ điển Tr ường hợp n=1. Xét ph ương trình một bi ến số f( x )= 0. Gi ả sử nghi ệm của ph ương trình này là x* ∈ℝ. Thu ật toán Newton tìm nghi ệmx * sẽ xu ất phát từ một điểm x 0 đủ gần x * và sinh ra một dãy nghi ệm xấp xỉ xxx0, 1 , 2 , , x k , hội tụ đế nx * . Xấp xỉ Taylor bậc nh ất của hàm f (x) tạix k là: fx(k+ p ) ≈ fx () k + pfx′ () k , vớip ∈ℝ , p đủ bé 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 35
  36. Ta có():d y= fx ()k + pfx′ () k chính là ph ương trình ti ếp tuy ến của hàm số y= f( x ) tại điểm(xk , f ( x k )) Gi ả sử f′( x )≠ 0 . Khi đó, ph ương trình fx()k+ pf′ ()0 x k = có nghi ệm p= − fx(k )/ fx′ ( k ) Đặ t xk+1 := x k − fx ()/() k fx′ k Ta cóxk+1 =() d ∩ ( Ox ) . Gán k:=k+1 và lặp lại quá trình tính toán với điểmx k mới. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 36
  37. Đị nh lý 6 (Đị nh lý hội tụ) Gi ả sử rằng: i) Hàm f (x) kh ả vi liên tục cấp hai; ii) x * là nghi ệm ph ương trình f( x )= 0 , tức f( x * )= 0; iii) f′( x * )≠ 0. Khi đó, nếu x0− x * đủ nh ỏ thìdãy{xk } xác đị nh bởi xk+1 = x k − fx( k )/ fx′ ( k ) f′′ ( x * ) hội tụ đế n x* với tốc độ bậc hai và hệ số γ = . f′( x * ) 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 37
  38. Tr ường hợp tổng quát (n>1 ) Xét hàm véct ơ : F :ℝℝn→ m = ()T x֏ Fx( ) fxfx1 ( ), 2 ( ), , fxm ( ) n → = trong đófi :ℝℝ , i 1, , m , cócác đạ o hàm riêng Kí hi ệu: DF ( x ) là ma tr ận Jacobi của hàm F tại x. ( ma tr ận cấpm× n ) 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 38
  39. Xét hệ ph ương trình n ẩn, n ph ương trình F( x )= 0 = trong đóFx( ) ( fxfx1 ( ), 2 ( ), , fxn ( )) ( m=n ) . Xu ất phát : x 0 đủ gần nghi ệmx* , xây dựng dãy điểm {xk }, k = 1,2, hội tụ đế n x* . Khai tri ển Taylor của F tạixk là Fx(k+ p ) = Fx () k + DFxpop () k + ( ), trong đóp∈ℝn có p đủ nh ỏ, o ( p ) là vô cùng bé cấp cao hơn so vớip khi p →0. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 39
  40. Khi đó, xấp xỉ Taylor bậc nh ất của hàm F tạixk là F( xk+ p) ≈ F ( x k ) + DF () x k p. Gi ả sử DF( x k ) không suy bi ến . Hệ ph ương trình F( xk )+ DF ( x k ) p = 0 có nghi ệm pk= −[ DFx ( k )]−1 Fx ( k ) và điểm lặp ti ếp theo là xkkkk+1 := x + p = x − [()](). DFx k− 1 Fx k Đặ txk:= x k +1 và lặp lại quá trình tính toán với điểmx k mới. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 40
  41. 1. Ph ương pháp Newton cổ điển 2. Phương pháp Newton thuần túy 3. Ph ương pháp Newton với bước điều ch ỉnh 4. Ph ương pháp tựa Newton 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 41
  42. Phương pháp Newton thuần túy Xétbàitoán(Pkrb ) , cóthêm gi ả thi ết ∇2 f( x ) xác đị nh dương với mỗi x∈ℝn . Gi ải hệ n ẩn n ph ương trình: T ∂f ∂ f ∂ f  ∇fx( ) = ( x ), ( x ), , ( x ) = 0 ∂ ∂ ∂  x1 x 2 x n  Để tìm điểm dừng của hàm f trênℝn . Ta có: Dfx∇() = ∇2 fx () Tại điểmx k nếu ma tr ận∇2 f( x k ) khôngsuybi ến 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 42
  43. thì ta có điểm ti ếp theo xkk+1:= x − [ ∇ 2 fx ()]. k − 1 ∇ fx (). k + hay xk1 := x k + p k trong đóp k lànghi ệm của hệ ph ương trình [∇2 fx ()].k p = −∇ fx () k ( hệ ph ương trình Newton ), véct ơ pk= −[ ∇2 fx ( k )].− 1 ∇ fx ( k ). được gọi là hướng Newton của hàm f tại xk. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 43
  44. Mệnh đề 6. Nếu ma tr ận Hessian ∇ 2 f ( x k ) xác đị nh dương thì hướng Newton p k của hàm f tại xk cũng là hướng gi ảm của f tạixk . 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 44
  45. Thuật toán 3(TT Newton thu ần túy gi ải bt(Pkrb ) ) Bước kh ởi đầ u. Xu ất phát từ một điểm tùy ý x 0 ∈ ℝ n đủ gần điểm dừngx* và∇f( x 0 ) ≠ 0; Ch ọn tr ước sốε >0 đủ nh ỏ. Đặ t k := 0; Bước lặp k ( k =1,2, ) k k (k1 ) Tính hướng Newton p của hàm f tại x bằng vi ệc gi ải hệ ph ương trình tuy ến tính [∇2 fx (k )]. p = −∇ fx ( k ) 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 45
  46. k+1 = k + k ∇ k+1 (k2 ) Xác đị nhx: x p và f( x ); ∇k +1 ≤ ε (k3 ) If f ( x ) Then dừng thu ật toán (lấy điểm dừngx*≈ x k + 1 ) Else k : = k + 1 và quay lại Bước lặp k . 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 46
  47. Đị nh lý 7 (Đị nh lý hội tụ) Gi ả sử : i) Hàm f kh ả vi hai lần trênℝ n ; ii) Hàm ∇f( x ) là liên tục và Lipschitz trong lân cận của điểm dừngx * của hàm f , tức tồn tại lân cậnB( x * ,ε ) và số L > 0 sao cho ∇fx() −∇ fy () ≤ Lxy − ,, ∀ xyBx ∈ (,);* ε iii) Ma tr ận∇2 f( x ) xác đị nh dương tại mọi x∈ℝn . Khi đó, nếu xu ất phát từ một điểm đủ gầnx * thì dãy{xk } sinh ra bởi Thu ật toán 3 sẽ hội tụ tới x * theo tốc độ cấp hai. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 47
  48. 1. Ph ương pháp Newton cổ điển 2. Ph ương pháp Newton thu ần túy 3. Phương pháp Newton với bước điều chỉnh 4. Ph ương pháp tựa Newton 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 48
  49. Phương pháp Newton với bước điều chỉnh Xu ất phát từ một điểm tùy ý x0 ∈ℝn. Tại bướ c lặp k, + điểm xk 1 đượ c xác đị nh bởi k+1 = k + k x: x tk d , trong đód k vẫn là hướ ng Newton của hàm f tại x k k= − ∇2 k− 1 ∇ k tứcd[ fx ( )]. fx ( ) và độ dài bướ c tk đượ c tính theo th ủ tục quay lui. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 49
  50. Thuật toán 4 ( TT Newton với bước điều ch ỉnh) Bước kh ởi đầ u Xu ất phát từ một điểm tùy ý x 0 ∈ ℝ n có ∇f( x 0 ) ≠ 0; Ch ọn tr ước sốε >0 đủ nh ỏ. Đặ t k := 0; Bước lặp k (k=1,2, ) k (k1 ) Tính hướng Newton d bằng vi ệc gi ải hệ [∇2 fxd (k )] k = −∇ fx ( k ) (k ) k+1 = k + k 2 Tínhx: x tk d , theo th ủ tục quay lui Tính ∇f( x k+1 ). 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 50
  51. ∇k +1 ≤ ε (k3 ) If f ( x ) Then dừng thu ật toán (lấyx*≈ x k + 1 ) Else k : = k + 1 và quay lại Bước lặp k. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 51
  52. 1. Ph ương pháp Newton cổ điển 2. Ph ương pháp Newton thu ần túy 3. Ph ương pháp Newton với bước điều ch ỉnh 4. Phương pháp tựa Newton 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 52
  53. Phương pháp tựa Newton Tại mỗi bước lặp, thay vì tính hướng Newton p k , ta tính hướng k= − ∇ k d Hk f( x ), trong đóHk là ma tr ận không suy bi ến, đố i xứng, xác đị nh dương. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 53
  54. Thuật toán 5 (Thu ật toán D.F.P.) Bước kh ởi đầ u Xu ất phát từ một điểm tùy ý x 1 ∈ ℝ n có ∇f( x 1 ) ≠ 0; Ch ọn tùy ý ma tr ận xác đị nh dươngH1 (Th ường ch ọnH1 là ma tr ận đơn vị I ). Đặ t k := 1; Bước lặp k (k=1,2, ) (k ) k= − ∇ k 1 Đặ t d: Hfxk (); =ϕ =k + k > (k2 ) Tính tk : argmin{ ( tfxtdt ): ( ), 0}; 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 54
  55. k+1= k + kkkk = + 1 − ∇ k + 1 (k3 ) Tính x: xtdvk ;: x x ;(). fx k +1 (k4 ) If ∇ f ( x ) ≈ 0 Then dừng thu ật toán Else Chuy ển bước(k5 ) ; k= ∇ k+1 −∇ k (k5 ) Tínhu: fx () fx () và vk( v k ) T (H uk )( H u k ) T HH:= + − k k ; k+1 k kk k k u, v u , Hk u = + (k6 ) Đặ tk: k 1 và quay lại Bước lặp k. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 55
  56. III. Phương pháp tìm ki ếm trực ti ếp Để gi ảibàitoán(Pkrb ) khihàm mục tiêu f(x) không kh ả vi ho ặc có kh ả vi nh ưng vi ệc lấy các đạ o hàm đạ o hàm riêng khó kh ăn. Xét hai thu ật toán: 1. Thu ật toán của Hooke và Jeeves 2. Thu ật toán tìm ki ếm theo đơn hình 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 56
  57. 1. Thuật toán của Hooke và Jeeves . 2. Thu ật toán tìm ki ếm theo đơn hình. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 57
  58. Thuật toán của Hooke và Jeeves Thuật toán 6 (Thu ật toán gi ảm theo tọa độ ) Bước 0. 1 = ∈ n Xu ất phát từ một điểm tùy ý x( xx1 , 2 , , x n )ℝ . Ch ọn các véct ơ i =δ = v(0, ,0, ,0, ,0), i 1, , n , i trong đóδ > 0 là số cho tr ước. Ch ọn tr ước số ε > 0 đủ nh ỏ. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 58
  59. Bước 1. Đặ tx10 = x 1. Trongba điểmx10 và x10 ± v 1 ch ọn một điểm mà tại đó giá tr ị hàm mục tiêu bé nh ất, ký hi ệu điểm đó làx11 . Để đơn gi ản ta vi ết: Tìm x11 =arg min{ fxfxvfxv (10 ), ( 1 0 +1 ), ( 1 0 − 1 )} (theo tọa độ th ứ nh ất); x12=arg min{ fxfxvfxv ( 11 11 ), ( +2 ), ( 1 1 − 2 )} (theo tọa độ th ứ hai ); ⋮ x1n=arg min{ fx ( 11 nn−1 ), fx ( − 1 + vfxvn ), ( 1 n − 1 − n )} (theo tọa độ th ứ n); 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 59
  60. Gán y1 := x 1n ; Bước 2. If x 1 = y 1 Then Chuy ển Bước 3 Else Chuy ển Bước 4; Bước 3. If δ ≤ ε Then Dừng th ủ tục (x*≈ x 1 ) Else Đặ t v i vi =, i = 1, , n và quay lại Bước 1; 2 Bước 4. Đặ txx21= +2( yxx 111 − ); : = x 2 và quay lại Bước 1. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 60
  61. 1. Thu ật toán của Hooke và Jeeves. 2. Thuật toán tìm ki ếm theo đơn hình. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 61
  62. Thu ật toán tìm ki ếm theo đơn hình Thuật toán 7 Bước 1. • Tạo một đơn hình có (n+1) đỉ nh x1, , x n+ 1 ∈ℝ n . • Tính fxi(i ),= 1, , n + 1. Bước 2. Tính max =iM =i = + ∈ + f: fx ( ) max{ fxi ( ) : 1, , ni 1},M {1, , n 1} min =im =i = + ∈ + f: fx ( ) max{ fxi ( ) : 1, , ni 1},m {1, , n 1} Đặ t xmax:= xxiM ; min : = x im . 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 62
  63. Bước 3 ( Tiêu chu ẩn tối ưu) If f max − f min ≤ ε Then Dừng th ủ tục ( x min là nghi ệm tối ưu đị a ph ương vàf min là giá tr ị tối ưu tương ứng) Else Chuy ển Bước 4. Bước 4.(Tính điểm tr ọng tâm) n+1 f( x i ) S= i x∑ n+1 x i=1 ∑ f( x i ) i=1 (tổ hợp lồi của xi , i= 1, , n + 1 ) 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 63
  64. Bước 5. Chi ếu đố i xứngx max qua x S được 1 1 xxR= max +2( xx S − max ) (tứcxS= x max + x R ) 2 2 Đặ t fR:= f ( x R ). Bước 6. If f R ≤ f min Then Chuy ển Bước 7 Else Chuy ển Bước 8. Bước 7. Chi ếu đố i xứngx S qua x R được xE= x S +2( xx RS − ); Đặ t fE:= f ( x E ). If f E < f min Then Đặ txiM := x E ( x max : = x E ), 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 64
  65. được đơn hình mới và Quay về Bước 2 Else Đặ txiM := xxR (max : = x R ), Quay về Bước 2. Bước 8. (Đã có fR > f min ) If f R < f max Then xiM := xxR (max : = x R ), được đơn hình mới và Quay về Bước 2 Else Chuy ển Bước 9. Bước 9. (Đã có fR ≥ f max ) Tính 1 1 xK= x max + x S và fK:= f ( x K ). 2 2 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 65
  66. If f K < f max Then x iM : = xx K ( max : = x K ), được đơn hình mới và Quay về Bước 2 Else Thu hẹp đơn hình theo công th ức 1 1 xxxii= i +min , ∀ ∈ {1, , n + 1}\{ i }. 2 2 m Quay lại Bước 2. 10/6/2010 MaMH C02012 Ch ươ ng 3: QHPT không ràng bu ộc 66